Merkle树数据同步误报

Question

Merkle树(又名哈希树)用于"Cassandra"和"Dynamo"中的数据同步.

与任何散列函数一样,不同数据可能具有相同的散列值:

存在一个x和y,其中[y!= x]但[hash(x)= hash(y)]

随着NOSQL中的"大数据"增长,遇到此类数据的概率变得更高.

这意味着随着数据集变大,几乎可以肯定Merkle树中的不同节点将产生相同的父哈希.

在这种情况下,当群集中的两台不同的机器遍历他们的merkle树时,他们会得到误报,他们的数据是一致的.如果没有更多数据写入树的该分支,则计算机将永远保持不同步.

这是怎么处理的？

Answer 1

大多数系统都不处理这个问题.为什么？因为具有相同散列值的两个不同输入的概率非常非常低.有了一个很好的哈希函数(我认为你正在使用),这应该接近1/2 ^ {hash-bits}.并且由于用于这些目的的大多数哈希长度至少为128位,因此这种冲突的概率为1/2 ^ 128.这是关于2.9387359e-39(0. {38 zeroes} 29387359).

使用160位的散列(大多数这些系统使用SHA-1哈希值)足够好,当你在数据库中拥有尽可能多的对象时,就像世界上有沙粒一样.你仍然有不到1/2的概率会发生这样的碰撞.因此,我不担心发生碰撞的情况.发生这种情况的可能性实在太低了.