Merkle Tree with real world examples

Merkle Trees are used in popular software applications like Git, Amazon Dynamo DB and BlockChain. A merkle tree is a metadata-structure, which stores the hash of the combined children in each parent. Any change in a child requires a change in the parent node.

This property of identifying state changes is useful when validating the correctness of data, as calculating the inverse of a hash is computationally infeasible. The merkle tree's properties are suitable for applications where a malicious user must be stopped from changing data.

Git file creation details:
Git registers any change in a file as an entirely new file. It stores the content of the file with a filename of SHA1(fileContents). Let's say this SHA1(fileContents) = x. If x already exists in the git file system, it doesn't go ahead and create it. This avoids unnecessary recreations when metadata about a file is changed.

When a file is modified in Git, git creates a new (changed)file, and all it's changed parents. The root subsequently changes. It's like a branch of a Persistent Data Structure. If you want to go back a commit, you use the root of the previous commit, which still points to the old file.

In this way, Git takes snapshots of every point of change in the project. Perfect for a version control system.

It is also useful to find the points at which the data has changed, using a Merkle Tree. Amazon Dynamo DB uses merkle trees to reduce entropy (Anti-entropy technique) when a new node is added to the Dynamo DB cluster.

Amazon Dynamo DB data migration details:
When copying a range assigned to a node, we have to allow concurrent updates to keep the service available. But when the migration is in progress, concurrent updates lead to stale data in the destination node.

So we copy the data range multiple times. When there is no change in the two nodes, we declare the destination node as consistent. Since we want this to happen as fast as possible, we try to minimise the number of copy iterations. The procedure is explained in the video.

AlgoExpert:
http://www.algoexpert.io/gaurav

Made by engineers from Google and Uber, this site helps you build your algorithmic skills using code and white board explanations.
Be sure to use the code 'gaurav' for the discount. You get 30% off!

Preparing for design Interviews? Check out the "Grokking the system design interview" course:
https://www.educative.io/collection/5668639101419520/5649050225344512?affiliate_id=4793322061168640

System Design Playlist: https://www.youtube.com/playlist?list=PLMCXHnjXnTnvo6alSjVkgxV-VH6EPyvoX

Become a channel member!
https://www.youtube.com/channel/UCRPMAqdtSgd0Ipeef7iFsKw/join

References:
Git: https://stackoverflow.com/questions/46192377/why-is-git-not-considered-a-block-chain
Consistent Hashing: https://www.youtube.com/watch?v=zaRkONvyGr8
NoSQL: https://www.youtube.com/watch?v=xQnIN9bW0og
Amazon DB: https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
Anti Entropy without Merkle Trees: https://haslab.uminho.pt/tome/files/dotteddb_srds.pdf

You can follow me on:
Facebook: https://facebook.com/gkcs0/
Quora: https://www.quora.com/profile/Gaurav-Sen-6
LinkedIn: https://www.linkedin.com/in/gaurav-sen-56b6a941/
Twitter: https://twitter.com/gkcs_

Видео Merkle Tree with real world examples канала Gaurav Sen