Merkle Tree

Is a binary hash tree. Where for each value we take the hash of that value to build a tree. We recursively do that until we have 1 hash at the root of the tree.

If this hash is modified, that means there is at least 1 value that's changed.

Git also use Merkle tree to resolve difference detection.

See: Merkle Tree vs Vector Clock

Example

For example in our Design Key-Value store problem, we have the key from 1 to 12, which is replicated in 2 servers.

First we want to divide into 4 buckets because building with 12 keys will make it too big.

Supposed in Figure 6-13, node 8 is not synchronised.

Now we want to create the hash of each value of each key in the bucket.

Same concept, we do the same thing up until the root by creating hash value of the hash.

Detect inconsistency

To detect inconsistency, we simply traverse top down of the tree and find the differences.

So in Figure 6-16 keep traversing down the tree, we detecting that node 8 is inconsistent. So we can update the value of node 8 in server 2.