Anti Entropy

Is a mechanism that can be used to detect inconsistency between a replica system.

The mechanism uses Merkle tree to compare the differences in different level of nodes

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.