Explain Merkle Trees for use in Eventual Consistency-allqahome-开发者的问答家园

English 中文(简体)

Explain Merkle Trees for use in Eventual Consistency

原标题：

Merkle Trees are used as an anti-entropy mechanism in several distributed, replicated key/value stores:

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.
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.

What am I missing?

最佳回答

Merkle trees limit the amount of data transferred when synchronizing. The general assumptions are:

Network I/O is more expensive than local I/O + computing the hashes.
Transferring the entire sorted key space is more expensive than progressively limiting the comparison over several steps.
The key spaces have fewer discrepancies than similarities.

A Merkle Tree exchange would look like this:

Start with the root of the tree (a list of one hash value).
The origin sends the list of hashes at the current level.
The destination diffs the list of hashes against its own and then requests subtrees that are different. If there are no differences, the request can terminate.
Repeat steps 2 and 3 until leaf nodes are reached.
The origin sends the values of the keys in the resulting set.

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.

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.

For more information about Riak, we encourage you to join the mailing list: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com

问题回答

暂无回答

上一篇：C++:如何检查外部方案是否运行?

下一篇：无法连接到服务器数据库系统的启动包的无效长度已被关闭, 收到快速关闭请求( pgadmin postgres docker)

相关问题

How to add/merge several Big O s into one

If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...

Finding the spin of a sphere given X, Y, and Z vectors relative to sphere

I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...

Grokking Timsort

There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...

Manually implementing high performance algorithms in .NET

As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...

Print possible strings created from a Number

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...

Enumerating All Minimal Directed Cycles Of A Directed Graph

I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...

Find number of permutations of a given sequence of integers which yield the same binary search tree

Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...

Quick padding of a string in Delphi

I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...

热门标签

友情链接

Allggapp Alljchome-教程家园 mvfinale.com-影视剧情大结局大全