Merkle Trees: Its usage in distributed systems
Merkle trees are balanced binary trees, used specifically to detect changes in data and point to the exact change location but not exactly the change contents.
It is one of ways to detect change locations.
- Each parent stores the hash values of the hash of its leaf nodes. Any change in the leaf node contents, the parent hash changes and hence propagating the change to the tree root.
- Using DFS, can pin-point exactly the location of change in a short amount of time.
- Use cases:
- Git: To pin-point changes in files
- DynamoDB: Detect changes in data across nodes as the parent hash change indicates that data has been changed and needs to be refreshed across nodes.
- NOTE: This method has its own issues, such as the merkle tree becoming too big, etc. There exists a solution Anti entropy without merkle trees by HASLab.
