ZFSに「重複排除機能」が実装される 32
ストーリー by hylom
HDDのお掃除が苦手な方にぜひ 部門より
HDDのお掃除が苦手な方にぜひ 部門より
あるAnonymous Coward 曰く、
サン・マイクロシステムズのZFSに重複排除機能（dedupe：deduplication）が搭載されたとのこと（本家/.記事より）。
ZFSでは処理能力は要さないが効率の悪いファイル単位のdedupeではなく、高い処理能力を要するがバーチャルマシンイメージなどに適しているとされているブロック単位のdedupeが実装された。DedupeはSHA256ハッシュを使うとのことで、ZFSの256bitチェックサムとマップできるとのこと。マルチコアサーバなど処理能力の高いマルチスレッドOS上で走っていることを前提に、Dedupeはインラインで実行される仕様だそうだ。
仕様詳細やインプリ方法はJeff Bonwick氏のブログに掲載されているのでご確認を。
「重複排除機能」については、ITmediaのTechTargetの記事が詳しい（要登録だが、登録なしでもだいたいのところは読める）。
概略 (スコア: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:衝突の確率はもっと高いような気がするです (スコア:1)
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: (スコア:0)
>設定で zfs set dedup=verify tank とすれば、「ハッシュ値が同じ」だけでなくちゃんとビットイメージまで等しいかをチェックしてくれるので、心配性な人はそれを利用すればいいですよ、とブログにはあります。
>実際にコリジョンがあった場合にどうなるのかは分かりません。記録できないのかな？
ハッシュ値が同じならdiff取ると言うことであれば、同じ／違うの区別は明確にできると思うので大丈夫じゃない？
#それ否定されたらオイラが昔MD5で作った仕組み否定されかねない、業務の主目的じゃなかったから無くても支障無いはずだけど（笑）
Re:衝突の確率はもっと高いような気がするです (スコア:2)
だとすると、衝突フラグみたいなものをキーに含めておく、というところですかねえ。
いや、なんでこんなに気にしているかというと、私もSHA256で同じようなことやっているからです。（ブロック単位はやりたいけど重過ぎるので、ファイル単位）
もちろんコリジョンにはノーガード戦法ですよー。（・∀・）
Re:衝突の確率はもっと高いような気がするです (スコア:1)
ファイル単位で処理してると、「ファイルサイズ」もキーにすれば、もうちょっと衝突確率は減るんじゃないでしょうか。
まあ、ファイルサイズなんてせいぜい32bitで、256bit→288bitになる程度ですが…
私の自作バックアップソフトでは、リネームしたファイル検出のために、
ファイルサイズをキーにしたstd::map内に、MD5をキーにしたstd::mapを入れてました。
32bitの数値比較で先に絞り込んだ方が検索が速いって理由だったかな。←そういや、4GB超のファイルのことは考えてなかったなぁ…
あと、ファイル冒頭の何バイトかについても比較対象のキーにするとか。
ファイルサイズが小さいときには、ダイジェストを計算するよりも最初から全文比較の方が速いし。
#ちょっとプアな環境だったので、rsync を使ったら、最初のファイル一覧作成段階でタイムアウトしてしまうという…
#で、やむを得ず自作する羽目になったという。今はunison使ってます。
#帯域的にできるだけムダを減らしたかったんですが、最近はぶろーどばんどな感じなので、ムダな転送が出ても気にしなくなりました。
Re: (スコア:0)
Re: (スコア:0)
・ファイルの冒頭24kバイト(だっけ？)のCRC32
・ファイル全体のMD5
の二段構えにしてましたね。
# 32kバイトとかの「キリのいい」値ではないのは、CRC32を計算するコードも含めてCPUのキャッシュに載せるのを意図してたんだと思う。
Re:衝突の確率はもっと高いような気がするです (スコア:3, 興味深い)
うふふ。皆さん同じところで悩んで、同じような解決方法に…。
はい、減ると思います。まあ、セキュアなハッシュはハッシュ空間の中に均等にばら撒かれるのに対して、ファイルサイズの値は（4GBまでだとして）32ビット内で均等にばら撒かれているわけではないので、ハッシュ32ビット分の効果はなさそうですが、サイズはすぐに判別できるので速くて便利だし、32ビットは扱いやすくておいしい。
# SHA1だと32ビットファイルサイズを加えるとちょうどいい塩梅のサイズ（192ビット）になるんですが。
あと、「MD5なら、DB上は64ビット数値2列で管理できるのにー」と思いつつSHA256を使うとか、「SHA256でコリジョンチェックするにしてもテストデータがなっしんぐ(笑)」とか、いろいろと悩みがつきません。ああ楽しい！
Re:衝突の確率はもっと高いような気がするです (スコア:1)
ZFS 的には 32bit なんてファイルサイズを前提にするのは極めて「おいしくない」と思うんですが……。
下位 32bit だけってことでしょうか。今時 OS の DVD ISO イメージでも 4GB 超とか普通にあったりすると思うんですけど。
Re: (スコア:0)
恐らくブロック単位で重複排除のアプローチを採ってますから、プログラム的にファイルのレングスをその下位レイヤーのブロックコントロールで制御するコーディングが煩雑でいやだったんでしょうね。
皆さん知らないようですが
ハッシュのコリジョンは、同じハッシュ値の桁数でも、異なる演算方法のハッシュ関数を組み合わせて生成した方が確率は低くなるという論文が出ています。
ＳＨＡ１とＭＤ５の両方で同じ値となる元データ、
もうデータのライト機構のエラー発生確立よりも小さいので、無視すべきと考えます
それで十分ではないでしょうか？
Re:衝突の確率はもっと高いような気がするです (スコア:2)
これが一般的に成り立つとは、にわかには信じがたいです。これが成り立たないケースが容易にありえそうなので。
ある特定のハッシュの方式では、というような前提条件はないのでしょうか。たとえば、SHA256 + MD5 (384bit) は、SHA384 よりも意図して衝突を引き起こすことは難しい、といったような。
よろしければ、その論文を教えていただけませんか。
Re: (スコア:0)
同じハッシュ値を持つ2つのブロックあるとき、それらの内容が本当に同一である確率は 32/ブロックのバイト数 の筈。
32/512=0.0625, 32/4096≒0.0078, 32/16384≒0.0019, 32/65536≒0.0004, 32/131072≒0.0002
うーん。
ディスク領域の予約確保がめんどうになる？ (スコア:3, 興味深い)
作っても、重複排除でまとめられてしまうってことになるのかな？
ファイル単位で重複排除の対象外に指定できたりするのだろうか？
Re: (スコア:0)
いや、そういうことを考えなくても済むファイルシステムって事ですよ。
ZFSになれば、そんなバットノウハウは必要ないんです。
Re: (スコア:0)
重複排除でまとめられて、
Copy On Writeで、変更した部分だけが容量を食うとか？
もしかして、いろんなディレクトリにコピーしても容量を食わずに増やせる？
カテゴリごとに分類してディレクトリわけて、どっちにいれるか悩む場合も
どちらにも入れておけばOK？
って、あーん、それのやりたいことはハードリンクじゃない・・・・って気付いた。
# 重複ファイルをダウンロードしてきたら勝手にハードリンク管理になる！？
ん？ (スコア:2)
よくわからないけど、Windows Complete PC Backupなんかを使って、
ZFSのファイルサーバにディスクイメージでフルバックアップをとっても、
差分バックアップほどの容量しか食わないってこと？
ファイル単位vsブロック単位 (スコア:2)
ファイル単位よりブロック単位の方が処理能力を要するっていうのはほんとなんでしょうか。ブログにもそんな話は見当たらないし。
ファイル全体が同じな場合は、ブロックごとにハッシュ記録しないといけない分、ブロック単位の方がディスク容量的なオーバーヘッドが高いのはわかるけど。
Re:ファイル単位vsブロック単位 (スコア:2)
と、ありますね。重複データがどこからどこまでかを調べるのにコストがかかるということでしょう。
発想として (スコア:2, 参考になる)
ZFSはストレージ(プール)がメモリのDIMMみたいなもんで、そっから切り出すイメージなわけですが、
KSM [atmarkit.co.jp]みたいなカンジでしょうか。
面白いですね。
M-FalconSky (暑いか寒い)
画像フォルダ専用ファイルシステム？ (スコア:1, おもしろおかしい)
T/O
Re: (スコア:0)
Re: (スコア:0, 既出)
スラドでも導入して、既出の自動排除とかできるとよいと思うのだが、どうですかね？
ここではあまり利用方法が無いのかな (スコア:1)
> DedupeはSHA256ハッシュを使うとのことで、ZFSの256bitチェックサムとマップできるとのこと。
(スコア:-1,既出) の自動化には貢献してくれなさそうですよね？
俺がネットから落としたエロ画像をまとめてくれますか (スコア:0)
ブロック単位の管理なら、A画像のアンモザイクをB画像に適用してくれますか
Re: (スコア:0)
実用性をアピールしようと「n枚保存した」と書いてもファイルはひとつ…
これが、合理性か……
Re: (スコア:0)
＞ブロック単位の管理なら、A画像のアンモザイクをB画像に適用してくれますか
ふたなり画像が完成しました。
そもそもとして… (スコア:0)
SHA256で衝突する可能性が思い浮かばない。Fletcherでも
そこそこ行ける気がする。
ファイル単位で重複チェックするのではなく、ブロック単
位でするのも、このチェックサムを利用してだろうし。
チェックサムが同じモノを探すなら、メタデータをなめる
だけで済むから、そこそこのスピードで実行するくらいは
期待してもいいのではないかな。
Re: (スコア:0)
釣れますか？