Merkle Tree with real world examples
Вставка
- Опубліковано 27 лип 2019
- 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.
System Design Playlist: • System Design for Begi...
Become a channel member!
/ @gkcs
References:
Git: stackoverflow.com/questions/4...
Consistent Hashing: • What is CONSISTENT HAS...
NoSQL: • Introduction to NoSQL ...
Amazon DB: www.allthingsdistributed.com/...
Anti Entropy without Merkle Trees: haslab.uminho.pt/tome/files/d...
You can follow me on:
Facebook: / gkcs0
Quora: www.quora.com/profile/Gaurav-...
LinkedIn: / gaurav-sen-56b6a941
Twitter: / gkcs_
Brilliant! Really enjoyed that - quick delivery, but engaging and lively. Already looking forward to more from this knowledgeable and gifted communicator.
"When you change the contents of the file the hash should also change", it's called Avalanche effect. Even a minute change in the input causes a very drastic change in the output, a very important characteristic of a a good cryptographic algo.
Something like Butterfly effect?
@@KejriwalBhakt yes, good analogy
And the best part is... "Ye to apne jaisa banda hain yaar".
Hence we all are able to absorb more from your videos, cause we are able to get sync in your explanation, which is kinda rare.
😁
This was by far the best explanation for Merkle Trees.. Thanks for making it easy, Gaurav!!!
It feels really awesome when you make me understand a new topic really well...
Thank you 😁
Great explanation. Thank you. I work in visual effects, and these is a great way to track the version of all assets that make the final frame going to out to client.
The video was great as usual. Keep making such amazing content. It took me some good amount of reading and coding to understand the implementation of this.
Thanks 😁
I like how you share your passion for problem solving although several things you say I do not understand 100% makes me excited to know more
Hahaha, thanks!
OMG your voice is so soothing to listen to ...feels like a friend is explaining
Looking sharp man. Great video as always.
Excellent video, great job explaining the information through examples.
It is nice having GOOD comments, but BAD comments are also required. My personal recomendation is slow down a little bit, explain step by step, because as not native american it is hard to understand FAST. I needed some time, but anyway thank you for video.
thank you so much! loved the energy and delivery.
Thank you!
Last month only wrote Merkle Tree library for blockchain application. I was not aware of usage of Merkle Tree in DynamoDB. Loved the video.
bro.., do you have the library on git?,
Very informative! Keep up the good work!
You're great at explaining things bro!
You have been really amazing. Thank you for all the content. :)
Thanks 😁
Nice one. Merkel trees are used in Dynamo category of databases and especially in Cassandra to handle something called Anti-Entropy(Basically to repair inconsistency during replication). Actually, even those handle anti-entropy using three strategies 1. Hinted Handoff 2.Read Repair and finally in background Merkel Tree kicks in for a wholistic repair
Yup, I read an article on this and found it brilliant. Thanks for mentioning it 😁
@@gkcs Yes .Especially the part where inconsistencies are handled in different ways in a different path. Read, write and then Whole.
Thank you, You make everything easy :D
Very Nice. Well explained! Keep up the gr8 job ...
Hey man, I was just thinking of such a data structure. Thanks for introducing it to me!
:D
Superb, keep on the great work !
Great explanation!
Hi gaurav, as always a great video. Just wanted to ask, what is your video making process. Like how much do you read, try out things practically before making a video on that topic?
Hey Rahul,
I think I'll make a video on this sometime 🙂
Love the way you explain :)
Thank you 😁
Awesome explanation Gaurav. Keep up the great content. 👍
Thank you 😁
Great explanation.
Hi Mate,
Had been watching your vedios and they seem great. Interestingly these have aroused in me a desire to learn software architecture. Just wanted to know any suggestions of any particular course or book to begin with?
Time for a new dry-erase marker 😆
Awesome vid!
amazing explanation
One of the best videos.
Keep making such videos
Awesome content bro..!!
Thank you!
Great video!
great interview questions
Thanks, Gaurav for sharing. I have a question regarding System Desing I think you might be able to help. How to go about designing a web portal which shows most reposted posts in the last 5 minutes 10 minutes and 20 minutes?
Keep up the good work man...
😁
Really... I learn so much from you and you really encourage me
great video,.. keep going
From your ring diagram of dynamodb use case, it looks like the synchronization is happening for any nodes. As I understand from dynamodb paper, the use case for merkle tree is for replication synchronization, so only for replicating nodes. Is that right?
I have a healthcare SaaS that deals with Electronic Medical Records, patients' data etc... Would it be a good idea to use Merkle trees ensure integrity of the data (pdf files, data...)?
What a video. Can you explain lazy indexing in Cosmos DB?
Hey Gaurav, your videos really helped me with my interviews these days. Recently in Morgan Stanley's interview, the interviewer asked me about what consistent hashing is and why would you use it. As I also did a project on Distributed Hash Key-value store, system design interview went for almost 45 minutes. One question which bothered me in the interview was, he asked me what if one of your clients comes up with 1lakh insert queries, as you are using consistent hashing, the query will be directed to only one of the server depending on the hash value. So just to get away from that question, I said that I will use consistent hashing for read queries only, as we will get results from the cache and it would be effective, but for insert query, I will distribute it on random servers. Can you please help me with the proper answer.
Have a look at how Cassandra does it.
Hint: Quorum.
Hey Archit.wont the consistent hash uniformly distribute the inserts ?
W=n, R=1 in Quorum consensus will solve it
Thanks for sharing! I have a question, how do you handle hash conflicting in Merkle tree? saying two different values are hashed to a same hash value?
What's the chance of that?
Thank you!
You're welcome!
How Merkle Hash Tree performs better when compared to other tree structures?
And in case of Dynamo DB. How the data is going to be transfered. Does it going to be transfered after comparison of two nodes Merkle Trees.
Really great. But yeah I want a video on BlockChain using mecle tree
is it possible to generate merkle tree with rootHash
i meant to get the values of merkle tree using rootHash ?
Great explanation! In the Nosql consistent hashing example, as the updates are continuous - wouldn't the merkle tree always be different between the two nodes? How would the system converge?
One way would be to block updates for a short while when the difference between them is small. The sync will finish quickly and then updates can resume.
@@gkcs temporary blocking and sparse Merle tree for transfer. Thanks Gaurav.
As we consider git as a tree data structure, will that use dfs or bfs?
awesome
Thanks Gaurav for explanation. One request, can you create separate system design video on git system design considering most powerful features of git ? This was asked to me in one of recent interview, I explained with DAG (as I was not aware about Markel Tree :P ) but it was not appropriate though.
I have done a lot of research on the git system, so it's possible...
I'll take a poll and see if it's what the viewers want 😁
@@gkcs : Sure !! Thanks :)
Great explaination :)
Thanks 😁
@Gaurav have you ever implemented a merkle tree from scratch ? Lets say even for a 1D array with 5 elements
What if React's Virtual DOM would be using this data structure behind the scenes like for updating the HTML tree for small UI change? It has react conciler measuring diffs only
Sounds interesting, and I have a feeling something like this is used in DOMs...
@@gkcs If you find out then please share, I am working on react and it seems nice.
your videos are really helping. also, System Design playlist is best on youtube.
And how do we figure out which Parent Merkle tree has to be compare with which Parent Merkle tree of another node.
If you only take 1/10 values for the Merkle tree, do you have to do this 9 more times to check the other values? And then repeat this looped process until the data has stopped updating? Great video by the way!
We take all the changed values, but that doesn't stop the data at the source being updated again. Which would need another round of copying to fix. But that one might have updates too, which would need another round. And so it goes...
Hey gaurav, make a video on merkle tree blockchain. thanks in advance , your videos are very helpful thanks in advance. great work keep going.
your linkedin ??
Just want to say thank you.
😁
Great video. Liked the github part.
Thanks!
very nice
hi gaurav, what are benefits of joining the channel for 4.99/month? do channel members get access to more videos?
Hello from Spain, I love your lessons but as a non-native English speaker understanding different accents is really challenging.
It will be great if you could subtitle the lessons.
Thank you for your time and effort.
Thank you! I'll try and subtitle the videos 👍
These videos you upload are awesome.
But why don't you upload videos of programming? I mean real time programming, not just ppts...
Good content Gaurav. I’m curious how git handles hash collisions, when changes of a file generate same hash. My naive idea is adding timestamp to the content and generating the hash.
It doesn't. If they match, the file is left unmodified.
The chances of that happening are lesser than an asteroid blowing Earth apart soon. So I feel rather safe 😛
@@gkcs best answer I ever have seen with an analogy. I am gonna use it in Interview. :P
So the directory above is pointing to the hash, which is a pointer? I thought the hash was just an encrypted version of the file; does it also act as a pointer?
The hash tells Git the name of the file, so it is a address/pointer for this 'content addressable system'.
Oh yeah ! Well groomed *gaurav* for first time.
#ourtylerdurden.
Hahaha!
Is it used in application like dropbox too?
yes i want to see merkle tree in blockchain use case
What soccer team does your shirt represent?
good video
whiteboard text is not visible @Guarav in 1020p streaming also
Gourav , actually I face difficulty in building up the recurrence relation
For the problem. Could you suggest something to improve this or do you have any trick for this ???
Which recurrence relation? Th subtrees of each node?
a malicious person like me😂
Thanks for the vid, tbh never even heard of merkle tree.
Very malicious 😛
best videos on youtube
good job
Thank you!
How can a hash point to a file?
thanks for the video! the resolution seems low for the texts on the whiteboard
Yes, I've fixed that in the last two videos 😁
Nice info, but there is one issue i.e., most of the times your camera goes out of focus. Please try to rectify it.
Yeah I think I'll fall back to the phone cam because this is so persistent. Thanks for the feedback 😊
so it's a type of content addressable storage.
Strongly request for the subtitles.
Hoping for some subtitles from the community!
where do you learn from ?...as this topic which you teach us🤗?
There are some links in the description 😁
Can merkel trees be used for effective datamasking in big data?
Can you elaborate with an example?
@@gkcs Like if i want my data to masked but in way that it still makes sense.I would most probably shuffle the data for example like i am trying to mask first names of customer but i want them that in original data a person having name Sam has name Tom in masked entry but the problem with this shuffle is when data is updated or changed the same name can be mapped to two entries leading to inconsistent data masking.
Well, masking using hashing is quite common. You shouldn't have any problems if you store x as sha1(x), except if you are looking to get back the original value of x from the mapped value.
Initial I read it has Miracle Tree. Now after seeing the Video, we can call it "Miracle Tree". Loll
I can't comprehend what you were saying in the intro "Hey Everyone this is .... CS"?
Gkcs is my pen name 🙂
@@gkcs I see! thanks
@8:37 shouldn't it be mod of 4 instead of 400?
The keyspace size is 400
That marker sucks but the content is Great! That marker does not do justice 😅
Can't this be solved using AKKA actor-based model?
How?
@@gkcs I think I replied when the there was a autoplay running 😂😂
@@gouthamnagraj5445 Hahaha cool 😛
Hey Gaurav, Can you advise how can I get a job in US from India. I have 6 years of experience, in Datawarehouseing initially and now in Big Data Analytics. I love programming and I am proficient in SQL and Python/Scala. Would appreciate your opinion on it.
PS : Love what you do brother.😘
Hello sir i had a doubt regarding placements.
I messaged you on LinkedIn but i think you didn't see it yet. Can you tell me the best forum to ask my doubt?
Bro, I love your channel. You are doing a great job. But please don't associate yourself with that idiot AlgoExpert Guy. His company's terms and conditions are as terrible as hell. Bought his course yesterday and now I am regretting since I can't get my money back. I know that you have a partnership with him or whatever but companies like AlgoExpert who don't even refund money to their customers on the same day of buying even if customers are not satisfied with their product are a big shame. Keep on making good content !!!!
It's a patch not a pack. Nice video though
Watch this video at 0.75x speed.. Thank me later
Too
Congrats for job at uber
Little less explauanation
Great explanation!