解释用于最终一致性的默克尔树

Question

Merkle Trees是在几个分布式、复制的键值存储系统中用作反熵机制的：

• Dynamo
• Riak
• Cassandra

毫无疑问，反熵机制是一件好事——在生产环境中，瞬时故障是经常发生的。 我只是不确定为什么Merkle Trees是一个流行的方法。

• 将完整的Merkle树发送到对等方需要将本地键空间与存储在树的最低层中的每个键值的哈希一起发送给该对等方。

• 从同行发送的Merkle树的差异需要拥有自己的Merkle树。

由于两个对等方都必须已经具有排序的键/值哈希空间，那么为什么不进行线性合并以检测差异呢？

我只是不相信树结构在考虑维护成本和事实（即线性遍历树叶子节点已经被用于通过网络传输串行化表示）时提供任何节省。

为了使这更具体化，一个替代方法可能是让节点交换哈希摘要数组，这些摘要数组是通过模环位置逐步更新和分组的。

我错过了什么？

- Johnny Graettinger

---

Merkle树现在已经有了自己的维基百科主题页面：https://en.wikipedia.org/wiki/Merkle_tree - Trenton

Answer 1

默克尔树在同步时限制数据传输量。一般的假设是：

1. 网络I/O比本地I/O+计算哈希更昂贵。
2. 传输整个排序键空间比逐步限制比较更昂贵。
3. 键空间中的差异少于相似之处。

默克尔树交换的步骤如下：

1. 从树的根节点开始(一个哈希值列表)。
2. 源节点发送当前级别的哈希列表。
3. 目标节点将哈希列表与自己的列表进行差异比较，然后请求不同的子树。如果没有差异，则请求可以终止。
4. 重复步骤2和3直到达到叶子节点。
5. 源节点发送结果集中键的值。

在典型情况下，同步键空间的复杂度将为log(N)。是的，在极端情况下，当没有共同的键时，该操作将等效于发送排序哈希列表的全部内容，O(N)。可以通过动态构建默克尔树并将其序列化存储在磁盘上来分摊构建默克尔树的开销。

我无法说明Dynamo或Cassandra如何使用默克尔树，但Riak停止在集群内部同步时使用它们了(暗示式移交和读取修复在大多数情况下足够)。我们计划在一些内部架构变化后再次添加它们。

有关Riak的更多信息，请加入邮件列表：http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com。

- seancribbs

---

啊，来回交流是我所缺少的。谢谢。 - Johnny Graettinger

它们已经在Riak 1.3的AAE实现中重新引入。 - Coderoshi