80

Merkle 树在多个分布式、复制的键/值存储中用作反熵机制：

毫无疑问，反熵机制是一件好事——瞬态故障只是在生产中发生。我只是不确定我是否理解为什么 Merkle树是流行的方法。

  • 将完整的 Merkle 树发送到对等点涉及将本地密钥空间以及存储在树的最低级别中的每个键值的散列发送到该对等点。

  • 区分从对等点发送的 Merkle 树需要拥有自己的 Merkle 树。

既然两个对等点必须已经有一个排序的键/值哈希空间，为什么不进行线性合并来检测差异呢？

我只是不相信当您考虑维护成本时，树结构会提供任何形式的节省，并且已经完成了对树叶的线性传递这一事实只是为了序列化网络上的表示。

为了解决这个问题，一个稻草人的替代方案可能是让节点交换散列摘要数组，这些散列摘要通过模环位置进行增量更新和存储。

我错过了什么？

4

1 回答 1

89

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

于 2011-03-30T17:18:01.603 回答