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

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