KengoSawa2の技術的ななにか

IT屋さんのようなKengoSawa2がなんかそれっぽい事を書いていくblogです

xxhashの紹介

プロダクションEXPO2015でRapidCopyの展示員をしているのですが、当然暇なので
xxHashの紹介をしたいと思います。

xxhashってなに？

xxhashはyann Collet氏が開発したファイルチェックサム専用の軽量ハッシュライブラリ（正確に言うとアルゴリズム）です。
実装はc++用が作者自身によって公開されていて、BSDライセンスなおかげもあって様々な言語で実装されてます。

github.com

今どきの主要言語はほぼ全てサポートされているので、是非コピペ実装してみてください。
で、このxxhash何が優れているか？って話になるのですが。まとめると以下のようになります。

例えばみなさんおなじみのMD5なんかと比べると、ハッシュ生成速度はおよそ15倍。
CPU使用率は僕の開発マシンのSandyBridgeベースのCore i7 2Ghz環境下だとMD5比でほぼ半分です。
これは非常に優秀な結果だと思います。
その他のアルゴリズムとの比較結果なんかもyann氏のページに乗っていますので、是非見てください。

僕が開発しているRapidCopy
[RapidCopy] MacOSX用高速ベリファイ差分ファイルコピーソフト

なんかでは、MacBookAir等の非力なモバイルCPU環境下でチェックサム生成する時に効果が確認できます。
最近のSSDやRAIDデバイスは非常に高速なので、案外CPUリソースを食ってたりするんですよね。。
僕の場合はしょせんたかが１コピーワークロードですが、データセンター屋さんなどでは、巨大なコピーを延々やっていると想像されるわけで。
xxHashでチェックサムを行えば、センター全体の消費電力低減などにも効果があるんだろうなーなどと妄想しています。


話変わって、xxhashには当然欠点もあります。

  • 暗号化、復号化のための機構を省くことで速度を稼いでるのでセキュリティ目的での使用はできない
  • ハッシュキー長が64bitなので、ファイルの数が膨大だった場合に２つの異なるデータにおいて同一のハッシュ値を表示してしまう確率がちょっときになる。

一番目の話題は特に大事で、勘違いしてはいけない大事な部分です。

二番目のハッシュ衝突耐性ですが、基本的には気にしないで大丈夫です。
滅多に衝突しません。
コピー元とコピー先の異なるデータで同一のハッシュ値をたまたま算出する確率は天文学的に低いはずです。はず。

ただ、RapidCopy(正確に言うとRapidCopyの移植元であるFastCopy)では数百万ファイルなどのヘビーなファイルコピーを想定しています。こうなってくると、それなりに気になる確率にもなってきます。まず大丈夫なはずですが。。
上記の点を原作者でもある白水氏からのアドバイスを受け、確かにそうかもと感じたので
僕は128bit化の要望をyann氏に出してみました。

yann氏自身も128bit化の意味はあるとは思っているようで
「時間ないけどその内やりたいんだよね。今年のうちにやれたらいいなー」的な前向きなお返事を貰いました。
気長に待つが吉か、128bit版のコントリビュートがあれば素敵と思います。
(僕は数学ダメダメな人なので貢献できません、ごめんなさい。。)
xxhash，様々な局面で活用する価値があると思います。
みなさんも是非使ってみてください。


この記事はyann Collet氏twitter.com
やRapidCopyの移植元でもあるFastCopyの原作者　白水啓章氏twitter.com

からのアドバイスを受けて記述しました。
両氏の深い技術力と的確なご意見に感謝します(._.)

2015/7/2
白水氏より


とのご指摘を受けました。
ご指摘ありがとうございます＆見解の誤りでご迷惑おかけして申し訳ありません(._.)
衝突の説明について、２つの異なるデータで同一のハッシュを生成する確率の問題であることを明記すると同時に、当該確率表の説明を削除しました。

2015/7/9
yann氏への連絡に関する下りに関して、yann氏に連絡しようと思ったくだりを追加。
白水氏からに確率の教示を受けなければ128bit要望はたぶん出さなかったと思います。。