hylomによる
2009年11月05日 17時28分の掲載
HDDのお掃除が苦手な方にぜひ部門より。
HDDのお掃除が苦手な方にぜひ部門より。
あるAnonymous Coward 曰く、
サン・マイクロシステムズのZFSに重複排除機能（dedupe：deduplication）が搭載されたとのこと（本家/.記事より）。
ZFSでは処理能力は要さないが効率の悪いファイル単位のdedupeではなく、高い処理能力を要するがバーチャルマシンイメージなどに適しているとされているブロック単位のdedupeが実装された。DedupeはSHA256ハッシュを使うとのことで、ZFSの256bitチェックサムとマップできるとのこと。マルチコアサーバなど処理能力の高いマルチスレッドOS上で走っていることを前提に、Dedupeはインラインで実行される仕様だそうだ。
仕様詳細やインプリ方法はJeff Bonwick氏のブログに掲載されているのでご確認を。
「重複排除機能」については、ITmediaのTechTargetの記事が詳しい（要登録だが、登録なしでもだいたいのところは読める）。
関連ストーリー
Firehose:ZFSに重複排除機能実装される by Anonymous Coward
概略 (スコア:3, 参考になる)
日本語で概略をみるなら↓
http://blogs.sun.com/ako/entry/zfs_dedup [sun.com]
http://blogs.sun.com/ako/entry/zfs_dedup_2 [sun.com]
簡単には・・・
・現段階でリリースされているOpenSolarisでは実装されていない
・OpenSolaisのBuild 128から実装される。
・Build 128は11/9にコードフリーズ予定らしい
・ファイル単位ではなくて、ブロック単位でdedupe
・常時dedupe処理を実施
コメントを書く
衝突の確率はもっと高いような気がするです (スコア:3, 興味深い)
リンク先のブログで書かれているコリジョンの確率の数字って、誕生日コリジョンは考慮されてないんですね。ブログに対するコメントのほうで書かれてますけど。
まあ、それでも普通のデータ量なら心配しなくていいほどに2^256は広い空間だし、どうしても心配な人は zfs set dedup=verify tank すればいいのか。
# SHA256ってまだコリジョン見つかってないんでしたっけ。
コメントを書く
Re:衝突の確率はもっと高いような気がするです (スコア:3, 参考になる)
すいません、「誕生日のパラドックス [wikipedia.org]」「誕生日問題」のほうが一般的な呼び方でした。（攻撃に使う場合は「誕生日攻撃」）
リンク先のブログのコメント欄では、birthday problem なんて書かれています。しかし、これ計算が間違っていそう。
コメントを書く
親コメント
Re:衝突の確率はもっと高いような気がするです (スコア:4, 興味深い)
# 書き忘れました。
リンク先のブログだと、「SHA256のようなセキュアなハッシュを使うときは、コリジョンの可能性は 1/2^256 または 1/10^77 」と書かれています。恐ろしく小さな確率で安全、安心。
が、任意のデータとなにか他のデータのハッシュ値が一致（衝突、コリジョン）してしまう確率としてはそれは正しいですが、ここではZFSで大量に扱う全てのデータどうしでコリジョンしないことが求められるので、正しくは誕生日問題のほうの確率でみないといけないんじゃない？ …と、いう話です。で、そのあたりもブログに対するコメントで既出なのですが、そこにある計算は間違っていそうです。
Wikipediaの表 [wikipedia.org]の値は正しそうです。この表をみると、データ個数が 4.8*10^32 でもどれか1つのデータでコリジョンが起こる確率が 10^-12 ですから、まあいずれにしても問題にならないような数字ですけど。
設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。
実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？
コメントを書く
親コメント
Re:衝突の確率はもっと高いような気がするです (スコア:2)
だとすると、衝突フラグみたいなものをキーに含めておく、というところですかねえ。
いや、なんでこんなに気にしているかというと、私もSHA256で同じようなことやっているからです。（ブロック単位はやりたいけど重過ぎるので、ファイル単位）
もちろんコリジョンにはノーガード戦法ですよー。（・∀・）
コメントを書く
親コメント
Re:衝突の確率はもっと高いような気がするです (スコア:3, 興味深い)
うふふ。皆さん同じところで悩んで、同じような解決方法に…。
はい、減ると思います。まあ、セキュアなハッシュはハッシュ空間の中に均等にばら撒かれるのに対して、ファイルサイズの値は（4GBまでだとして）32ビット内で均等にばら撒かれているわけではないので、ハッシュ32ビット分の効果はなさそうですが、サイズはすぐに判別できるので速くて便利だし、32ビットは扱いやすくておいしい。
# SHA1だと32ビットファイルサイズを加えるとちょうどいい塩梅のサイズ（192ビット）になるんですが。
あと、「MD5なら、DB上は64ビット数値2列で管理できるのにー」と思いつつSHA256を使うとか、「SHA256でコリジョンチェックするにしてもテストデータがなっしんぐ(笑)」とか、いろいろと悩みがつきません。ああ楽しい！
コメントを書く
親コメント
Re:衝突の確率はもっと高いような気がするです (スコア:2)
これが一般的に成り立つとは、にわかには信じがたいです。これが成り立たないケースが容易にありえそうなので。
ある特定のハッシュの方式では、というような前提条件はないのでしょうか。たとえば、SHA256 + MD5 (384bit) は、SHA384 よりも意図して衝突を引き起こすことは難しい、といったような。
よろしければ、その論文を教えていただけませんか。
コメントを書く
親コメント
ディスク領域の予約確保がめんどうになる？ (スコア:3, 興味深い)
作っても、重複排除でまとめられてしまうってことになるのかな？
ファイル単位で重複排除の対象外に指定できたりするのだろうか？
コメントを書く
ん？ (スコア:2)
よくわからないけど、Windows Complete PC Backupなんかを使って、
ZFSのファイルサーバにディスクイメージでフルバックアップをとっても、
差分バックアップほどの容量しか食わないってこと？
コメントを書く
ファイル単位vsブロック単位 (スコア:2)
ファイル単位よりブロック単位の方が処理能力を要するっていうのはほんとなんでしょうか。ブログにもそんな話は見当たらないし。
ファイル全体が同じな場合は、ブロックごとにハッシュ記録しないといけない分、ブロック単位の方がディスク容量的なオーバーヘッドが高いのはわかるけど。
コメントを書く
Re:ファイル単位vsブロック単位 (スコア:2)
と、ありますね。重複データがどこからどこまでかを調べるのにコストがかかるということでしょう。
コメントを書く
親コメント
発想として (スコア:2, 参考になる)
ZFSはストレージ(プール)がメモリのDIMMみたいなもんで、そっから切り出すイメージなわけですが、
KSM [atmarkit.co.jp]みたいなカンジでしょうか。
面白いですね。
BOINC説明ページ(書きかけ) [wikispaces.com]
コメントを書く
画像フォルダ専用ファイルシステム？ (スコア:1, おもしろおかしい)
T/O
コメントを書く
ここではあまり利用方法が無いのかな (スコア:1)
> DedupeはSHA256ハッシュを使うとのことで、ZFSの256bitチェックサムとマップできるとのこと。
(スコア:-1,既出) の自動化には貢献してくれなさそうですよね？
コメントを書く