解释Merkle树用于最终一致性

Question

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

• 发电机
• 了Riak
• 卡桑德拉

毫无疑问,反熵机制是一件好事 - 在生产过程中,瞬间失败就会发生.我只是不确定我理解为什么Merkle Trees是最流行的方法.

• 将完整的Merkle树发送给对等体涉及将本地密钥空间与每个键值的散列一起发送到该对等体,存储在树的最低级别中.

• 区分从同伴发送的Merkle树需要拥有自己的Merkle树.

由于两个对等体必须已经有一个已排序的键/值 - 哈希空间,为什么不进行线性合并以检测差异？

我只是不相信树结构在考虑维护成本时会提供任何节约,而且已经完成线性遍历树叶的事实只是为了在线上序列化表示.

为了解决这个问题,一个稻草人替代方案可能是让节点交换散列摘要数组,这些散列摘要通过模数环位置逐步更新和删除.

我错过了什么？

Answer 1

Merkle树限制同步时传输的数据量.一般假设是:

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

Merkle Tree交换看起来像这样:

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

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

我无法谈论Dynamo或Cassandra如何使用Merkle树,但Riak停止使用它们进行群内同步(在大多数情况下,暗示切换和读取修复就足够了).我们计划在一些内部架构位发生变化后稍后再添加它们.

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