読者です 読者をやめる 読者になる 読者になる

重複排除 技術解説(3)重複の判定方法

引き続き、ASCII.technologies 2011年1月号に寄稿した「重複排除技術が革新するストレージの世界」の第二章の技術解説です。今回は「重複の判定方法」です。


[2.2節 重複の判定方法 序文]
今までの説明では重複排除の容量削減効果に主に焦点を合わせてきたが、重複排除技術をシステムに適用するにあたり、それと同じぐらい重要なポイントがある。それは、重複排除処理を加えることによるシステム性能への影響を軽微に抑えるということである。重複排除で容量を大きく削減できたとしても、システム性能が大きく落ちてしまうと使用用途がかなり限定されてしまう。たとえば、バックアップではバックアップウィンドウ以内にバックアップを終了させることは必須なので、性能要件が非常に重要だ。ある程度の性能が出せなければ採用に至らない。
ハードウェアを増強すれば性能低下は抑えられるので、それは重要な要件ではないと考える読者がいるかもしれない。しかし、その場合にはハードウェアコストの上昇という別の問題を抱え込む。将来は状況が変わるかもしれないが、現時点の重複排除製品ビジネスにおいては、高価なハードウェアを使わずに性能への影響を軽微に抑える―つまりは少ないハードウェアリソースで重複排除処理を効率的に行う―ことが、非常に重要な要件になっている。
そして、この要件を大きく左右するのが、本節で取り上げる重複の判定方法である。どのやり方を採用するかによって、ハードウェアリソースの消費量は大きく変化する。多くのディスクリソースを必要とする製品もあれば、CPU・メモリをメインに使うという製品もある。本節では、どのようなアプローチが市場に存在し、それらがハードウェアリソース消費量の観点でどのように異なるのか、そして、どういった設計思想からそのような設計になっているか、解説していく。

比較対象をいかに減らすか

二つのデータが重複かどうかを判定する最も単純なやり方は、byte-to-byteでデータ同士をつき合わせて比較することである。しかし、この方法をストレージシステムにそのまま適用することはできない。ストレージに保存されているデータ量が非常に多いからである。新しいブロックが作られた際に、保管してある全てのブロックと比較などしていたら途方もない処理量になってしまう。比較対象をまず減らさなければならない。
そこでよく使われるのがフィンガプリントである。ブロックを保管する際に、ハッシュ関数を使ってデータのフィンガプリントを作っておく。そして、そのフィンガプリントをデータの代わりに比較する。フィンガプリントはデータよりもずっと小さいサイズなので、ストレージに保管されてある全てのブロックに関して比較することがずっと容易になる。
しかし、フィンガプリントを使った重複判定には負の側面もある。それは、ハッシュ値の「衝突」である。ハッシュ値の衝突とは、hash(m1) = hash(m2) となるような2つの異なるデータ m1 と m2の組を指す。これが起きると、実際には異なるデータなのに、フィンガプリントが一致して重複と判定されて、どちらかが消されてしまうことになる。本来は同じデータでは無いのに消されてしまうので、後々読み出したときにデータが化ける、もしくは破壊されたように見えてしまう。

ハッシュ衝突の克服

ハッシュ値の衝突はデータロスに繋がる非常に怖い現象である。この問題に対してどのような解決アプローチがあるのか、説明していこう。
まず、フィンガプリントが一致した場合に、データをつき合わせて比較して最終的な確認をとるという方式がある。つまり、フィンガプリントは比較対象を減らすためだけに用いて、最終確認はデータつき合わせでとるというハイブリッド方式である。全てのブロックと比較することはハードウェアリソースの観点から現実的ではないが、フィンガプリントが一致したブロックのみを比較するのであれば、比較対象の数はかなり減るので現実的なやり方になる。
もう一つのやり方は、衝突可能性が非常に低い、SHA1などの暗号学的ハッシュ関数をフィンガプリント計算に使う方式である。暗号学的ハッシュ関数は「強衝突困難性 (strong collision resistance)」 という、ハッシュ値の衝突を探すことが非常に困難であるという特徴を持つ。この関数を使うことで、ハッシュ値の衝突可能性を現実運用シナリオでは無視してよい確率にまで低下させるというアプローチである。

このどちらが優れているのかというのはなかなか難しい問題であるが、現在の市場の流れを見る限り、SHA1などを使った暗号学的ハッシュ関数を使う方式が優位に立っているように筆者は感じる。
その理由としては、暗号学的ハッシュ関数を使ったほうがハードウェアリソースの消費量が格段に少ないということが挙げられる。具体例を使って説明すると、Data Domain社の製品の場合、可変長ブロックの平均長は8KBで、フィンガプリントはSHA1で20 byteであるから、ブロックとフィンガプリントは400倍大きさが違う。ブロックをつき合わせて比較する場合は、ディスクアクセスやメモリ消費量がそれだけ増えて、ハードウェアリソースを圧迫することになる。結果、データ突合せ方式と比べて、暗号学的ハッシュ関数方式の方が、性能的に、もしくはハードウェアコスト的に優れていることが多い。
データつき合わせ方式の優位な点はその安全性にある。ハッシュ衝突の可能性を完全に取り除けるためである。しかし、前述のように、暗号学的ハッシュ関数を使えば現実運用シナリオでの衝突可能性は無視できるほどに小さくできるため、この安全性におけるメリットは市場で重要視されなくなりつつある。