algorithm - 说明用于最终一致性的默克尔树

Merkle Trees在多个分布式，复制的键/值存储中用作反熵机制:

毫无疑问，反熵机制是一件好事-生产中会发生短暂故障。
我只是不确定我是否理解为什么默克尔树是流行的方法。

将完整的Merkle树发送给对等方包括将本地密钥空间与该对等方一起发送
每个键值的哈希值，存储在树的最低层中。

区分从同级发送的Merkle树需要拥有自己的Merkle树。

由于两个同级都必须已经有一个排序的键/值哈希空间，为什么不进行线性合并来检测差异呢？

我只是不相信，当您将维护成本考虑在内时，树形结构可以节省任何费用，
在树叶上进行线性传递只是为了序列化导线上的表示。

为了解决这个问题，一种替代方案可能是让节点交换哈希摘要数组，
通过模环位置对它们进行增量更新和存储。

我想念什么？

最佳答案

Merkle树限制了同步时传输的数据量。一般假设为:

网络I / O比本地I / O +计算哈希值昂贵。

转移整个排序的键空间比逐步限制比较需要花费更多的成本。

键空间的差异少于相似性。

Merkle Tree交换看起来像这样:

从树的根(一个哈希值的列表)开始。

来源发送当前级别的哈希列表。

目标将哈希列表与其自身的列表进行比较，然后
请求不同的子树。如果没有
差异，请求可以终止。

重复步骤2和3，直到到达叶节点。

来源发送结果集中的键值。

在典型情况下，同步键空间的复杂度将为log(N)。是的，在极端情况下，没有共同的密钥，该操作将等同于发送哈希的整个排序列表O(N)。可以通过在写入时动态地构建Merkle树并将序列化形式保留在磁盘上来分摊构建Merkle树的费用。

我无法说出Dynamo或Cassandra如何使用Merkle树，但是Riak停止使用它们进行集群内同步(在大多数情况下，提示切换和读取修复就足够了)。我们计划在一些内部体系结构更改后，稍后再添加它们。

有关Riak的更多信息，我们建议您加入邮件列表:http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com