Merkle Trees在几个分布式、复制的键/值存储中用作反熵机制:
毫无疑问，反熵机制是一件好事—— transient 故障在生产中经常发生。 我只是不确定我是否理解为什么 Merkle 树 是流行的方法。
将完整的 Merkle 树发送给对等点涉及向该对等点发送本地 key 空间，以及 每个键值的哈希值，存储在树的最低层。
区分来自对等方的 Merkle 树需要拥有您自己的 Merkle 树。
既然双方手头上必须已经有一个排序的键/值哈希空间，为什么不进行线性合并来检测差异呢？
我只是不相信树结构在您考虑维护成本时提供任何形式的节省，而且事实 树叶上的线性传递已经完成，只是为了通过网络对表示进行序列化。
为了解决这个问题，一个稻草人的替代方案可能是让节点交换哈希摘要数组， 它们通过模数环位置进行增量更新和分桶。
我错过了什么？
最佳答案
Merkle 树限制同步时传输的数据量。一般假设是:
- 网络 I/O 比本地 I/O + 计算哈希更昂贵。
- 转移整个排序的键空间比逐步限制几个步骤的比较更昂贵。
- 关键空间的差异少于相似之处。
Merkle Tree 交换看起来像这样:
- 从树的根开始(一个哈希值的列表)。
- 源端发送当前级别的哈希列表。
- 目的地将散列列表与它自己的散列列表进行比较，然后 请求不同的子树。如果没有 差异，请求可以终止。
- 重复步骤 2 和 3，直到到达叶节点。
- 源端发送结果集中键的值。
在典型情况下，同步 key 空间的复杂度将为 log(N)。是的，在没有共同键的极端情况下，该操作相当于发送整个排序的哈希列表，O(N)。可以通过在写入进入时动态构建 Merkle 树并将序列化形式保存在磁盘上来分摊构建 Merkle 树的费用。
我不能说 Dynamo 或 Cassandra 如何使用 Merkle 树，但 Riak 停止使用它们进行集群内同步(在大多数情况下提示切换和读取修复就足够了)。我们计划稍后在一些内部架构位更改后将它们添加回来。
有关 Riak 的更多信息，我们鼓励您加入邮件列表:http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com
关于algorithm - 解释 Merkle 树用于最终一致性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5486304/