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

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

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

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

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

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

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

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

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

我错过了什么?

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