2011-03-01

CentOS5.5でraid6を--growしようとしたら怒られるのでLiveCDでどうにかする

linux

# mdadm --manage /dev/md0 --add /dev/sdg1
# mdadm --grow /dev/md0 --raid-devices=6
mdadm: Cannot set device size/shape for /dev/md0: Invalid argument

とか言われる。
調べてみるとカーネルが古いのが原因で、解決策としては新しいカーネルのLiveCDを使えばなんとかなるようだ。

http://www.mail-archive.com/linux-raid@vger.kernel.org/msg09062.html
http://centos.info/modules/newbb/viewtopic.php?viewmode=thread&order=ASC&topic_id=24121&forum=37

とりあえず仮想PC上で実験をした

CentOS 5.5 x64 ja

これをOS用ディスクにインストールして、Raidのディスク6個追加し、

Ubuntu 10.10 i386 ja

これでgrowする。

アレイの作成

# mdadm --create /dev/md0 --raid-devices=5 --level=6 --chunk=128 /dev/sdb1 /dev/sdc1 /dev/sdd1 /dev/sde1 /dev/sdf1
# vgcreate -s 32M Array00 /dev/md0
# lvcreate -L 5.45T -n LogVol00 Array00
# mkfs -t ext4 -E stride=32,stripe-width=96 -i 65536 -m 0 -O extents,uninit_bg,dir_index,filetype,has_journal,sparse_super /dev/Array00/LogVol00

アレイのgrow

ここからUbuntu

//入ってないのでインストール
# apt-get install mdadm
//ディスクからアレイの情報を得る
# sudo mdadm --examine /dev/sdb1
//assemble
# sudo mdadm --assemble --uuid=上で得たUUID /dev/md0
//add
# sudo mdadm --manage /dev/md0 --add /dev/sdg1
//grow
# sudo mdadm --grow /dev/md0 --raid-devices=6

md、pv、lv、fsの拡張

CentOSに戻る

//mdの拡張
# mdadm -G -z max /dev/md0 
//pvの拡張
# pvresize /dev/md0
//vgの確認
# vgdisplay -v Array00
  Total PE（物理エクステントの総数）
  Alloc PE / Size（割り当てられている物理エクステント / サイズ）
  Free  PE / Size（フリーな物理エクステント / サイズ）
  あたりが必要な情報
//lvの拡張
# lvextend -l 新しい物理エクステント数 /dev/Array00/LogVol00 
	または
# lvextend -L 新しいサイズ /dev/Array00/LogVol00 
//fsの拡張
# resize4fs /dev/Array00/LogVol00

うまくいくようなので実機で試してみる

のこり2000分…。

まとめ

CentOS5だとRaid6の--growができなくて泣けるのでLiveCDでやりましょう
仮想PCを使えば一応テストはできる
「あれい」で変換してアレイより阿礼が先に出るGoogle日本語入力はいい感じに狂ってる

2011-02-18

あるハミング距離までに含まれるバイナリハッシュの数を計算する

バイナリ長 $n = 4$ で考えると、
ハミング距離0 → ${\small 4}C{\small 0} = 1$
[0 0 0 0]
ハミング距離1 → ${\small 4}C{\small 1} = 4$
[0 0 0 1]
[0 0 1 0]
[0 1 0 0]
[1 0 0 0]
ハミング距離2 → ${\small 4}C{\small 2} = 6$
[0 0 1 1]
[0 1 0 1]
[0 1 1 0]
[1 0 0 1]
[1 0 1 0]
[1 1 0 0]
ハミング距離3 → ${\small 4}C{\small 3} = 4$
[0 1 1 1]
[1 0 1 1]
[1 1 0 1]
[1 1 1 0]
ハミング距離4 → ${\small 4}C{\small 4} = 1$
[1 1 1 1]

というわけで、長さが $n$ のとき、バイナリハミング距離 $s$ 以内に含まれるバイナリハッシュの数は $\sum^s_{i = 0} {\small n}C{\small i}$ 。

1byte = 8bitの全通りを考えると、 $1 + 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 256$ 、合ってるようです。

2011-02-17

ハッシングの性能を調べる（てきとう）

http://d.hatena.ne.jp/ruby-U/20110215/1297757430 で、画像に変形を加えて局所特徴量の性能を調べたので、次はハッシングの性能を調べる。

類似画像検索の枠組みは

まず、前準備として

画像から特徴点を抽出し、それぞれを $n$ bitのバイナリハッシュに変換し、DBに格納しておく。

そして検索は、

指定の画像から特徴点を抽出し、 $n$ bitのバイナリハッシュに変換し、DBに問い合わせる。

この問い合わせの対象になるバイナリハッシュの数は、例えば $n = 16$ なら、ハミング距離0で ${\small n}C{\small 0}=1$ 個、ハミング距離1以内で ${\small n}C{\small 0} + {\small n}C{\small 1}=17$ 個、ハミング距離2以内で ${\small n}C{\small 0} + {\small n}C{\small 1} + {\small n}C{\small 2}=137$ 個、ハミング距離3以内で ${\small n}C{\small 0} + {\small n}C{\small 1}+ {\small n}C{\small 2} + {\small n}C{\small 3}=697$ 個…と増えていく。これが一つの特徴点ごとであることを考えれば、広いハミング半径を問い合わせの対象にすることは、できるなら避けたい。

このような制約から、画像検索の良いパフォーマンスのためには、ハッシングをよくチューニングする必要がある。このための指標として、

無関係の画像ペアから抽出した最近傍特徴点
近似した画像ペアから抽出した最近傍特徴点

を使うことを考えた。
両者をハッシュ化し、クエリの対象とするハミング距離0、1など、比較的近い位置に、後者のみがうまく入るようにすればいい。
異なる画像同士の特徴点の距離はもっと遠くまで広がっているが、問題設定から最近傍のみに注目している。

実験

無関係の画像ペア
ある画像と、それに変形（5%の拡大）を加えた画像のペア

それぞれから抽出した、特徴点ごとの最近傍点を、前者はDB全体での最近傍のサンプルとして、後者は近似した場合での最近傍のサンプルとして用いた。

以前と同様に、

def min_dist(feature, features):
	#特徴点featureとfeaturesの中の全てを比較して、最小距離を返す。
	#最小値0。

を使って、画像ペアについて、最近傍の特徴点を選び、いくつかのハッシングビット数ごとに、そのユークリッド距離とハミング距離をプロットした。

結果

14 bit

14 bitでは非近似の点がハミング距離0、1に被っていて不適。

20 bit

20 bitもやや被っている。

28 bit

28 bitでは被っていないが、ハミング距離0の近似の点の数が20 bitよりも少ない。

以上

実際のクエリの結果からのフィードバックは必要だが、ハッシングビット数決定の大雑把な見積もり方法としては使えそうだ。

2011-02-15

局所特徴量の性能を調べる（てきとう）

ある画像と、それを変形した画像を同一だと判定したい。
それはSIFTやらSURFの仕事なのだけど、どのぐらいの変形でどのぐらいの性能があるのかは把握しておかないと、土台の部分なのであとでいろいろ困りそう。
良い評価方法が見つからなかったので、適当に考える…。

画像Aと画像Bの類似度を

def features(image):
	#画像の特徴点のリストを返す。
def min_dist(feature, features):
	#特徴点featureとfeaturesの中の全てを比較して、最小距離を返す。
	#最小値0。
def similarity(A, B):
	#画像AとBの類似度を返す。
	#最大値0。最小値はAの特徴点が多いと小さくなるので注意。
	score = 0
	for feature in features(A):
		score -= min_dist(feature, features(B))
	return score

とすれば、同一画像で0。変形を強めると、変形画像とのスコアは小さくなっていって、その他の画像とのスコアの期待値に近づく。はず。

とりあえず以下をプロットしてみた。

#違う画像同士の特徴点の最小距離
for A in dataset:
	for B in dataset:
		if A == B: continue
		for feature in features(A):
			print min_dist(feature, features(B))

#ある画像と変形画像の特徴点の最小距離
for A in dataset:
	for feature in features(A):
		print min_dist(feature, features(transform(A)))

結果

台形変形

回転

縮小

拡大

2011-02-07

最近のバイナリハッシングをいくつかJavaで実装してみた

ml java hashing

去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。

バイナリハッシングとは。

$n$ 個の $D$ 次元の点からなるデータセット $X = [x_{1} \, , \, ... \, , \, x_{n}] \in R^{D\times n}$ で、元空間での近傍点を、類似したバイナリコードに関連づける技術。

要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。
そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。

その $K$ ビットのバイナリコード $Y = [y_{1} \, , \, ... \, , \, y_{n}] \in B^{K\times n}$ を作るために、 $K$ 個のハッシュ関数が使われる。
ハッシュ関数は $h_{k}({\small X}) = sgn( f( {\small W} ^T_k {\small X} + b_{k}) )$ と定義される。ここで、 ${\small X}$ はデータセット。 ${\small W}_k$ は射影ベクトル。 $b_k$ は閾値。

線形写像ベースのハッシングはシンプルで効果的です。上の式は要するに、データに、

行列 ${\small W}$ を掛けて
ごにょごにょして
二値化

しているだけです。ごにょごにょで複雑なことをしなければ十分に高速なはずで、実際に、テストの速度は手法ごとにそれほど差はありません。
一方で、 ${\small W}$ を求めるための訓練では、手法ごとに速度差があります。用途によっては、選ぶポイントになるかもしれません。

異なる ${\small W}$ と $f(\cdot )$ を選べば、異なるハッシングのアプローチが得られる。

LSH

$f(\cdot )$	恒等関数
${\small W}$	p-stable分布からランダムに選ぶ

SpectralHashing

$f(\cdot )$	コサイン関数
${\small W}$	データの主軸方向

USPLH

$f(\cdot )$	恒等関数
${\small W}$	以下のように抽出する

入力：データ $X$ , ハッシュコード長 $K$
$X^0_{\ MC} = \phi$ , $S^0_{\ MC} = \phi$ として初期化する
for $k = 1$ to $K$ do
　　補正された共分散行列を求める
　　　　 $M_k = \sum_{i=0}^{k-1}{ \ { \lambda^{k-1} \ X^i_{MC} \ S^i_{MC} \ X^i_{MC} }^T + \eta XX^T }$
　　Mkの最初の固有ベクトル $e$ を抽出する
　　　　 $W_k = e$
　　 ${\small W}_k$ での射影から仮のラベルを生成する
　　　　 $X^k_{ \ MC}$ をサンプルし、 $S^k_{ \ MC}$ を構築する
　　残差を求める
　　　　 $X = X - w_k { w_k } ^T X$
end for

もちろん他にもいろいろ手法がありますが、最初の二つは有名ですね。
LSHが2004年、SpectralHashingが2008年、USPLHが2010年と、全体に新しい分野みたいです。

実装

LSH

まずこれを実装しました。
ランダムなベクトルをテストデータに掛けて二値化するだけ。簡単高速です。
が、やはり言われているように精度が悪い。いっぱいハッシュを作って精度を上げていくことも可能なのですが、そうするとデータベースが肥大化して、なんだかなーという事になります。もちろん、そのデメリットが呑めるようなシーンではアリです。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/LSH.java

SpectralHashing

次にこれを実装しました。
LSHではランダムに生成していた射影ベクトルを、主成分分析で得るのがポイント。
LSHとは違って、データに依存した手法なので精度がよいです。ただし、LSHのように、並列化して精度を上げていくようなことはできません。
LSHより訓練、テスト共に複雑なことをやっているので遅いです。このうち、テストの遅さがやや気になったので、即決で採用はしませんでした。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/SpectralHashing.java
ペーパーの著者がmatlabコードを公開してくれていたのでそれを参考にしています。（ライセンスは不明）

USPLH

SpectralHashingのアレンジです。
平均が0になるようにデータを前処理しておいて、固有ベクトルを求め、データを射影して、0で閾値化します。
このとき、0に近いマイナスの点と、プラスの点は、距離が近いのに、違うハッシュ値に割り当てられます。
また、同じ符号で、0に近い点と、０から遠い点は、距離が遠いのに、同じハッシュ値に割り当てられます。
この両方のエラーを、ビットを求めるごとに補正していくというのがUSPLHの手法です。
性能はだいたいSpectralHashingと同じぐらいでした。
訓練は非常に遅いですが、テストはLSH並に高速です。
訓練時間がデメリットにならない用途であることと、パフォーマンスとテスト時間のバランスから、今回はこれを採用することにしました。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/USPLH.java
ペーパーてきとう訳 https://bitbucket.org/rubyu/hashing/src/4488f99834a0/paper/UPSLH.txt

テスト

訓練セット：１万件の画像から抽出した566839の64bit SURF特徴点。
テストセット： 150件の画像から抽出した9126の64bit SURF特徴点。
実際の用途で使われるような、ハッシュに対するクエリで、ハッシュ法の性能について調べる。
クエリ点からのユークリッド距離が、2パーセンタイル以内のものを正解とする。

Precision

だいたいペーパーと同じグラフ。ペーパーでは長いビットは切れてるけど、たぶんこんな感じに伸びてるはず。
PHよりUSPLHのほうがやや優れている。
LSHのグラフがギザギザなのは、一発の値（複数回取って平均していない）なので。

Recall curves

これもペーパーとだいたい同じ。

Training time

LSHと比べればSH、USPLH共に、ものすごく時間を食う。
LSHの4bitが跳ねてるのは、Javaのヒープ拡張のせい。（多分）

Test time

USPLHのテストはLSHと同じぐらい高速。

以上、グラフを見比べると、実装に大きな間違いはないかなーということが確認できました。

ペーパーとにらめっこで、昨年の終わりから、旅行やら骨折やらを挟んで約一月半ぐらいかかりましたが、そのかいはあったかなと。これを使ってぜひ何か新しいことをしたいと思います。

References

　　M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni,
　　　"Locality-sensitive hashing scheme based on p-stable distributions",
　　　in Proc. Symposium on Computational Geometry, 2004, pp.253-262.

　　Y. Weiss, A. Torralba, and R. Fergus, "Spectral hashing," in NIPS, 2008.
　　pdf: http://people.csail.mit.edu/torralba/publications/spectralhashing.pdf
　　matlab code: http://www.cs.huji.ac.il/~yweiss/SpectralHashing/sh.zip

　　Jun Wang, Sanjiv Kumar, Shih-Fu Chang,
　　　Sequential Projection Learning for Hashing with Compact Codes,
　　　InProc. of the 27th International Conference on Machine Learning (ICML), 2010.
　　pdf: http://www.sanjivk.com/SPLH_ICML10.pdf

2010-12-26

Windowsのバックアップと復元が0x81000001で失敗する件

windows

この頃、Win7のバックアップが以下のログとともに失敗するようになっていた。

バックアップは成功しませんでした。エラー: Windows バックアップで内部エラーが発生しました。設定を確認し、操作をやり直してください。 (0x81000001)。

Smartを見てもHDDに障害があるようでもなし、ファイルシステムも壊れていないし、システムの保護領域を一度消去しても効果がなかった。
僕はバックアップがないと心配で夜も寝られなくなるタイプの人間なので、昨日時間がちょっと余ったこともあり、徹底的にしらべることにした。
とはいうものの、わりと簡単に解決策が得られた。
以下の記事
Windows Backup nearly completes but fails with 0x81000001 error
http://social.answers.microsoft.com/Forums/en-US/w7performance/thread/b736a472-d27e-4032-a8fb-9cf99d893a7f?prof=required
タイトルそのまんま。

There is a file size limit (and I have now documented and verified) for any user data files located in their document folder or library. 
The value is approrimatly 162GB (Decimal) when using Backup and Restore, any file over this value by design can not be handled properly by a 64-Bit version of Windows Backup and Restore. 
32-Bit versions have a lower (about 152GB) file size limit.

ドキュメントフォルダやライブラリのファイルについて、ファイルサイズの制限があります。
64bit版のWindowsでは約162GBで、バックアップと復元がこれらのファイルのプロパティを扱えないよう設計されているためです。
32bit版では約152GBが制限です。

プロパティがなにを指してるのかよくわからなかった（ファイルのメタデータ？）ものの、当てはまるファイルを分割してみたところ、無事バックアップが成功した。

2010-12-13

かんたんsambaパフォーマンスちゅーにんぐ 2010年版

linux samba

古いsambaの記事へまだそれなりのアクセスがあるので、ここ最近の僕的トレンドを反映したものを書いてみました。

なるべく新しいsambaにアップグレードしましょう

3.5.*を推奨。

今までのチューニングtipsは忘れましょう

socket options

など、デフォルトのconfに含まれていない、パフォーマンスのためのオプションは、一旦削除してみることをオススメします。
わざわざ指定せずとも、最新のsambaでは十分にパフォーマンスが出ます。
指定していることで、むしろパフォーマンスが悪化しているケースもあります。

ファイルシステムのマウントオプションを最適化しましょう

http://www.kernel.org/doc/Documentation/filesystems/ext3.txt
http://sourceforge.jp/projects/linuxjf/wiki/ext4.txt
ext3/4なら

noatime

最終アクセス時刻の記録がパフォーマンス低下につながるので、極力OFFにします。

data=writeback

データの整合性を捨てるモードです。クラッシュ時に古いデータに化けることがあるかも、です。

nobh

バッファヘッドのデータページへの関連づけを避けます。

commit=time

データとメタデータの同期間隔を指定します。
ぐらいを設定するとよいでしょう。

たとえば以下のように

/dev/sda    /samba    ext4    defaults,noatime,data=writeback,nobh,commit=60    1 2

デバイスのIOスケジューラを最適化しましょう

パフォーマンスが安定しないなら、topなりなんなりでio waitを観察してみましょう。
パフォーマンスが低下する際にio waitが急激に高くなっている場合、

echo /sys/block/sda/queue/scheduler
cfq

ならば

echo "deadline" > /sys/block/sda/queue/scheduler

としてみましょう。
writeは詰まりませんが、readは詰まることがあります。
これはキャッシュを用いた遅延がwriteでは容易で、readでは難しいことが原因です。
deadlineスケジューラはreadを優先します。
また、あるいはサーバに搭載されているメモリが足りていないのかもしれません。freeを観察してみましょう。

ページキャッシュの設定を最適化しましょう

dirty_expire_centisecs

この期限をすぎたページキャッシュはpdflushによりライトバックされます。

dirty_writeback_centisecs

pdflushの起動間隔。

たとえば、

echo 12000 > /proc/sys/vm/dirty_expire_centisecs 
echo  2000 > /proc/sys/vm/dirty_writeback_centisecs

だと、20秒ごとにpdflushが起動。120秒を過ぎたキャッシュはライトバックされます。単位は1/100秒。

WDのHDDでレイテンシが気になるならIntelliParkを疑いましょう

「wdidle3」でググる

言うまでもないですが、環境によって最適値は変わります。上記の数値は一つの例です。
また以下についても留意してください。

ディスク書き込み間隔について

書き込み間隔が長くなる→HDDへのアクセスが減る→パフォーマンスが向上する
書き込み間隔が長くなる→キャッシュとして保持する時間が長くなる→障害時のデータ損失の可能性が高くなる

両者はトレードオフです。

write頻度が高いサーバで書き込み間隔を長く取ると、一度に大量のディスクアクセスが発生します

この場合は書き込み間隔を短くすると、一定したパフォーマンスを得られます。

とりあえず仮想PC上で実験をした

アレイの作成

アレイのgrow

md、pv、lv、fsの拡張

うまくいくようなので実機で試してみる

まとめ

類似画像検索の枠組みは

実験

結果

14 bit

20 bit

28 bit

以上

画像Aと画像Bの類似度を

とりあえず以下をプロットしてみた。

結果

台形変形

回転

縮小

拡大

バイナリハッシングとは。

異なる と を選べば、異なるハッシングのアプローチが得られる。

LSH

SpectralHashing

USPLH

実装

LSH

SpectralHashing

USPLH

テスト

Precision

Recall curves

Training time

Test time

以上、グラフを見比べると、実装に大きな間違いはないかなーということが確認できました。

References

なるべく新しいsambaにアップグレードしましょう

今までのチューニングtipsは忘れましょう

ファイルシステムのマウントオプションを最適化しましょう

デバイスのIOスケジューラを最適化しましょう

ページキャッシュの設定を最適化しましょう

WDのHDDでレイテンシが気になるならIntelliParkを疑いましょう

ディスク書き込み間隔について

write頻度が高いサーバで書き込み間隔を長く取ると、一度に大量のディスクアクセスが発生します

修正ログ

dirty_expire_centisecs、dirty_writeback_centisecsの単位を間違えていたのを修正しました。hzさん、ご指摘ありがとうございます！

異なる ${\small W}$ と $f(\cdot )$ を選べば、異なるハッシングのアプローチが得られる。