解释用于最终一致性的默克尔树 [英] Explain Merkle Trees for use in Eventual Consistency
问题描述
Merkle Trees 在多个分布式、复制的键/值中用作反熵机制商店:
Merkle Trees are used as an anti-entropy mechanism in several distributed, replicated key/value stores:
毫无疑问，反熵机制是一件好事 - 在生产中会发生瞬态故障.我只是不确定我是否理解为什么 Merkle Trees 是流行的方法.
No doubt an anti-entropy mechanism is A Good Thing - transient failures just happen, in production. I'm just not sure I understand why Merkle Trees are the popular approach.
向对等节点发送完整的默克尔树涉及向该对等节点发送本地密钥空间，以及每个键值的哈希值，存储在树的最低层.
Sending a complete Merkle tree to a peer involves sending the local key-space to that peer, along with hashes of each key value, stored in the lowest levels of the tree.
区分来自对等方的 Merkle 树需要您拥有自己的 Merkle 树.
Diffing a Merkle tree sent from a peer requires having a Merkle tree of your own.
既然两个对等点都必须已经有一个排序的键/值哈希空间，为什么不进行线性合并来检测差异?
Since both peers must already have a sorted key / value-hash space on hand, why not do a linear merge to detect discrepancies?
我只是不相信当您考虑维护成本时，树状结构可以节省任何形式的费用，事实上在树叶上的线性传递已经完成，只是为了在电线上序列化表示.
I'm just not convinced that the tree structure provides any kind of savings when you factor in upkeep costs, and the fact that linear passes over the tree leaves are already being done just to serialize the representation over the wire.
为了解决这个问题，一个稻草人的替代方案可能是让节点交换散列摘要数组，由模环位置增量更新和分桶.
To ground this out, a straw-man alternative might be to have nodes exchange arrays of hash digests, which are incrementally updated and bucketed by modulo ring-position.
我错过了什么?
推荐答案
Merkle 树限制同步时传输的数据量.一般假设是:
Merkle trees limit the amount of data transferred when synchronizing. The general assumptions are:
- 网络 I/O 比本地 I/O + 计算哈希值更高.
- 传输整个排序的键空间比逐步限制多个步骤的比较成本更高.
- 关键空间的差异比相似性要少.
默克尔树交换看起来像这样:
A Merkle Tree exchange would look like this:
- 从树的根(一个哈希值的列表)开始.
- 源发送当前级别的哈希列表.
- 目标将哈希列表与其自身进行比较，然后请求不同的子树.如果没有差异，请求可以终止.
- 重复第 2 步和第 3 步，直到到达叶节点.
- 源发送结果集中键的值.
在典型情况下，同步密钥空间的复杂度将是 log(N).是的，在没有共同键的极端情况下，该操作将等效于发送整个已排序的哈希列表，O(N).可以通过在写入时动态构建 Merkle 树并将序列化形式保留在磁盘上来分摊构建 Merkle 树的费用.
In the typical case, the complexity of synchronizing the key spaces will be log(N). Yes, at the extreme, where there are no keys in common, the operation will be equivalent to sending the entire sorted list of hashes, O(N). One could amortize the expense of building Merkle trees by building them dynamically as writes come in and keeping the serialized form on disk.
我不知道 Dynamo 或 Cassandra 如何使用 Merkle 树，但 Riak 停止将它们用于集群内同步(在大多数情况下，提示切换和读取修复就足够了).我们计划在一些内部架构位发生变化后稍后将它们添加回来.
I can't speak to how Dynamo or Cassandra use Merkle trees, but Riak stopped using them for intra-cluster synchronization (hinted handoff and read-repair are sufficient in most cases). We have plans to add them back later after some internal architectural bits have changed.
有关 Riak 的更多信息，我们鼓励您加入邮件列表:http://list.basho.com/mailman/listinfo/riak-users_lists.basho.com
For more information about Riak, we encourage you to join the mailing list: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com
这篇关于解释用于最终一致性的默克尔树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
