Merkleツリーのデータ同期偽陽性

Question

"Cassandra" & "Dynamo"と両方のデータ同期にMerkleツリー（別名ハッシュツリー）が使用されています。任意のハッシュ関数と同様

は、異なるデータが同じハッシュ値を持つことができる可能性がある：

xおよびy [！Y = X]が、[ハッシュ（X）=ハッシュ（存在しますy）]

NOSQLの「ビッグデータ」が大きくなると、そのようなデータに遭遇する確率が高くなります。

これは、データセットが大きくなるにつれて、Merkleツリー内の異なるノードが同じ親ハッシュを生成することがほぼ確実になります。

このような場合、クラスタ内の2つの異なるマシンがMerkleツリーを横断すると、データが一貫していると誤った肯定的な結果になります。ツリーのそのブランチにそれ以上データが書き込まれないと、マシンは永久に非同期になります。

これはどのように処理されますか？

Answer 1

ほとんどのシステムはこれを処理しません。どうして？同一のハッシュ値を持つ2つの異なる入力を持つ可能性は非常に低いためです。良いハッシュ関数（これはあなたが使っていると思います）では、これは1/2^{hash-bits}に近づくはずです。そして、これらの目的のためのほとんどのハッシュが少なくとも128ビット長であるので、あなたはそのような衝突の1/2^128の確率を得ます。これは約2.9387359e-39（0. {38ゼロ）29387359）である。

160ビット（これらのシステムのほとんどはSHA-1ハッシュを使用します）のハッシュを使用すると、世界に砂粒があるほど多くのオブジェクトがデータベースにある場合に十分です。あなたはまだそのような衝突が存在する1/2の確率よりも小さいことを持っていること。したがって、私は衝突がある場合については心配しません。それが起こる確率は、実際にはあまりにも低いです。