默克尔树 http://en.wikipedia.org/wiki/Hash_tree在几个分布式、复制的键/值存储中用作反熵机制：
- Dynamo http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
- Riak http://doc.erlagner.org/riak_core/merkerl.html
- 卡桑德拉 http://wiki.apache.org/cassandra/AntiEntropy
毫无疑问，反熵机制是一件好事——在生产中，瞬态故障就会发生。
我只是不确定我理解为什么默克尔Trees是流行的方法。
由于两个对等点都必须已经拥有排序的键/值哈希空间，为什么不进行线性合并来检测差异呢？
当您考虑维护成本时，我只是不相信树结构可以提供任何形式的节省，而事实
那已经完成了对树叶的线性传递，只是为了通过网络序列化表示.
为了解决这个问题，一个稻草人的替代方案可能是让节点交换哈希摘要数组，
它们是按模环位置增量更新和存储的。
我缺少什么？
Merkle 树限制同步时传输的数据量。一般假设是：
- 网络 I/O 比本地 I/O + 计算哈希值更昂贵。
- 传输整个排序键空间比逐步限制多个步骤的比较成本更高。
- 关键空间的差异少于相似之处。
默克尔树交换看起来像这样：
- 从树的根开始（一个哈希值的列表）。
- 源端发送当前级别的哈希列表。
- 目的地将哈希列表与其自身的哈希列表进行比较，然后
请求不同的子树。如果没有
差异，请求可以终止。
- 重复步骤2和3，直到到达叶节点。
- 源端发送结果集中的键值。
在典型情况下，同步密钥空间的复杂度将为log(N)。是的，在极端情况下，如果没有共同的键，该操作将相当于发送整个排序的哈希列表，O(N)。人们可以通过在写入时动态构建 Merkle 树并将序列化形式保留在磁盘上来摊销构建 Merkle 树的费用。
我无法谈论 Dynamo 或 Cassandra 如何使用 Merkle 树，但 Riak 停止使用它们进行集群内同步（在大多数情况下，暗示切换和读取修复就足够了）。我们计划在一些内部架构部分发生变化后将它们添加回来。
有关 Riak 的更多信息，我们鼓励您加入邮件列表：http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
