Database Reference
In-Depth Information
The hinted handoff works well if the number of nodes in a cluster is limited. Also, it
might be the case that before the hinted replicas are replaced to the original intended node,
the temporary node fails to handle such permanent failures. DynamoDB uses a very inter-
esting replica synchronization technique for better results.
DynamoDB uses
Merkle tree
to maintain the replica synchronization. Comparing all ex-
isting replicas and updating replicas with the latest changes is called
AntiEntropy
. A
Merkle tree is an algorithm used to store and compare objects. In a Merkle tree, the root
node contains the hash of all children, and if the hash values of the root nodes of two trees
are the same, then it means those two trees are equal. In the case of DynamoDB, we create
a Merkle tree of the replica on each node and compare them. If the root hashes of trees are
the same, then it means the replicas are in sync, whereas if the root hash is not the same,
