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

Merkle树在几个分布式，复制的密钥/值存储中被用作反熵机制：

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

毫无疑问，一个反熵机制是一件好事 – 在生产过程中发生的短暂失败。 我只是不明白为什么默克尔树是stream行的方法。

• 发送一个完整的Merkle树到对等体包括发送本地密钥空间到该对等体，以及每个密钥值的散列，存储在树的最底层。

• 对从同伴发送的Merkle树进行分解需要拥有自己的Merkle树。

由于两个对等体必须已经有一个已sorting的键/值 – 散列空间，为什么不进行线性合并来检测差异呢？

我只是不相信，当考虑维护成本时，树形结构会提供任何节省的费用，而树叶上的线性遍历已经完成，只是为了在线路上对表示进行序列化 。

为了解决这个问题，一个稻草人的替代scheme可能是让节点交换哈希摘要arrays，这些哈希摘要是通过模数环位置递增更新和分段的。

我错过了什么？

Answer 1

Merkle树会限制同步时传输的数据量。 一般的假设是：

1. networkingI / O比本地I / O +计算哈希值更昂贵。
2. 传输整个sorting的密钥空间要比在几个步骤中逐步限制比较要昂贵。
3. 关键空间的差异性比相似性要less。

Merkle树交换看起来像这样：

1. 从树的根（从一个散列值列表）开始。
2. 原点发送当前级别的散列列表。
3. 目的地将散列列表与自己的散列列表区分开来，然后请求不同的子树。 如果没有差异，请求可以终止。
4. 重复步骤2和3，直到到达叶节点。
5. 原点发送结果集中的键的值。

在典型情况下，同步密钥空间的复杂度将是log（N）。 是的，在极端情况下，没有共同的键，操作将相当于发送整个sorting的哈希列表，O（N）。 人们可以通过dynamic构buildMerkle树来分摊开销，因为写入和保持序列化的forms在磁盘上。

我不能说Dynamo或Cassandra如何使用Merkle树，但Riak停止使用它们进行簇内同步（在大多数情况下，暗示的切换和读取维修已经足够了）。 我们有计划在内部架构位发生变化之后再添加它们。

有关Riak的更多信息，我们鼓励您join邮件列表： http : //lists.basho.com/mailman/listinfo/riak-users_lists.basho.com