- We implement an anti-entropy protocol to keep replicas in sync.
- Anti-entropy involves comparing each piece of data on replicas and updating each replica to the newest version.
- A Merkle tree is used for inconsistency detection and minimizing the amount of data transferred.
Demonstrating Merkle Tree
- Assume a key space from 1 to 12
- Divide the key space into buckets (4 in our case).
- Each key in a bucket is hashed using a uniform hashing method.
- Create a single hash node per bucket
- Build the tree upwards till root by calculating hashes of children
- Two merkle trees (nodes) have the same data if the root hashes of both nodes match.
- If root hashes disagree, then the corresponding child hashes are compared to find the un-synchronized buckets.
Sources