8

「Cassandra」と「Dynamo」の両方で、マークル ツリー (別名ハッシュ ツリー) がデータ同期に使用されます。

他のハッシュ関数と同様に、異なるデータが同じハッシュ値を持つ可能性があります。

[y!=x] であるが [hash(x) = hash(y)] である x と y が存在する

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

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

このような場合、クラスター内の 2 つの異なるマシンがマークル ツリーをトラバースすると、データが一貫しているという誤検出が発生します。ツリーのその枝にそれ以上データが書き込まれなければ、マシンは永遠に同期されないままになります。

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

4

1 に答える 1

6

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

160 ビットのハッシュ (これらのシステムのほとんどが使用する SHA-1 ハッシュ) を使用すると、世界の砂粒と同じ数のオブジェクトがデータベースにある場合に十分です。そのような衝突が発生する可能性が 1/2 未満であること。したがって、衝突が発生した場合については心配しません。それが起こる可能性は、本当に低すぎます。

于 2013-01-07T14:01:16.130 に答える