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个零}29387359)。

使用160位的散列(这些系统中的大多数都使用SHA-1散列)已经足够好了，当您的数据库中有与世界上沙粒一样多的对象时。你仍然有不到1/2的概率发生这样的碰撞。因此，我不会担心发生冲突的情况。这种情况发生的概率实在太低了。