Consistent Hashing | The Backend Engineering Show
ฝัง
- เผยแพร่เมื่อ 10 มิ.ย. 2024
- In this episode of the backend engineering show I discuss consistent hashing a very important algorithm in distributed computing specially in database systems such as Apache Cassandra and DynamoDB.
0:00 Intro
2:00 Problem of Distributed Systems
5:00 When to Distribute
7:00 Simple Hashing
9:30 Where Simple Hashing Breaks
11:40 Consistent Hashing
18:00 Adding a Server
21:15 Removing a Server
22:30 Limitations
Fundamentals of Networking for Effective Backends udemy course (link redirects to udemy with coupon)
network.husseinnasser.com
Fundamentals of Database Engineering udemy course (link redirects to udemy with coupon)
database.husseinnasser.com
Introduction to NGINX (link redirects to udemy with coupon)
nginx.husseinnasser.com
Python on the Backend (link redirects to udemy with coupon)
python.husseinnasser.com
Become a Member on TH-cam
/ @hnasr
Arabic Software Engineering Channel
/ @husseinnasser
🔥 Members Only Content
• Members-only videos
🏭 Backend Engineering Videos in Order
backend.husseinnasser.com
💾 Database Engineering Videos
• Database Engineering
🎙️Listen to the Backend Engineering Podcast
husseinnasser.com/podcast
Gears and tools used on the Channel (affiliates)
🖼️ Slides and Thumbnail Design
Canva
partner.canva.com/c/2766475/6...
Stay Awesome,
Hussein - วิทยาศาสตร์และเทคโนโลยี
Learn about the fundamentals of Database Engineering Get my course database.husseinnasser.com
I scoured internet to understand this for last 2 hours. And i stumbled upon hussein's video's again... everything is crystal clear now.
Excited for your new course on OS , bought it but need to go through it 😁😁😁😁
Hussein, you explain things so nicely! The depth of your knowledge can be easily seen. Keep doing the great work :)
My mind is blown the way you explained this topic
Excellent explanation! Seen many videos but this one cleared everything....
This explanation is so beautiful man, loved it. Consistent Hashing feels like magic
Great topic, its amazing to see great products such as Dynamo and Cassandra use this advanced ideas!
Would like to see more topics like that
Possibly the best explanation for Consistent Hashing. :)
Beautiful explanation of this complicated topic :) Thank you Hussein !
What a great effort to explain all this!!
You have incredible talent to teach
What an amazing explanation without any fancy writing and animation
i finally get it thanks! everytime i visit your channel i'm rest assured that im going to actually understand what you're teaching :)
Amazing explanation, Thank You.
Thank you so much sir for making this concept super simple
and now this is what we call a state of art
Nicely explained.
nice video understood perfectly, thnx
great video as always. thank you
I was avoiding this topic from a very long time due to complexity, you explained it so well. Thanks.
very interesting. thanks hussein! i do something similar for flat file db's. similar that is in ranging. so for every object between numbers n and n, find them in file x.
Great explanation!
What a great talk Hussain. ❤
Awesome content. Keep doing it!
Great explanation
Nicely described your struggle show in this video keep it up bro
Awesome video!!. One question with the ring topology, how can we mantain a “right” amount of load through the servers?. In your example if you add servers that go around the same degrees you might have a debalanced system (like 4 servers between 0-90 and just 2 between 180-270).
Is this a limitation or I dont quite get it right? 🤔
in real life there are virtual nodes for each servers like s0_0, s0_1, s0_2..and so on. These are distributed in the ring, so eventually you will have a more balanced distribution
Beautiful.
After watching gaurav sen video. I would say, hussain nesser is best👍💯 🙏
🤣
What would happen if your server count goes above 360 in the above scenario? Do you have to reshuffle all keys one time using higher number?
Can you talk about virtual nodes and data replication as the next part of this video ?
NIcely explained
In consistent hashing , if one datanase is full and goes to read only mode but can't insert new data, how does this works?
are you reading my mind, I was just writing a hashtable for my opengl renderer to cache unifroms :)
Well taking this example, you cannot have more than 360 servers, right? What if the number of servers increases to 361, how will we handle such complexities? Even if we change the modulo to, lets say, 720: this will add up more to complexities, like earlier result was 1 (when we did %360) now it will be 361. How would we handle such scenarios?
Some ideas:
1. While adding server: we can have dedicated slave for each server and we can promote the slave as master like in this case slave of S90 will act as S50.
2. When removing server: instead of dedicated server we can also have slave on adjacent nodes for eg S90 slave will be in S0 and S180 and if we want to remove S90 then slave data of S90 in S180 will act as leader.
Can you elaborate the slave idea? Would the slave be another server along with S90 called S90slave (for example)? And when a new one is added (S50 in this case), the S90slave becomes S50 but with only the values that belong to S50?
@@shahman1 Yes S90slave will act as leader for S50 and can discard data outside the degree.
very important algorithm in distributed computing specially in database systems such as Apache Cassandra and DynamoDB.
I did not understand why to use consistent hashing, after watching this I now understand why and also only noticed why it is called consistent. The hashing that is consistent even when adding new nodes.
Almost consistent
Thx for the cupon
Index 3!
When we add another server to the ring, won’t that server and the next server in the ring get half the load? I.e the loads are now unbalanced.
Is there a solution for this or is this a given caveat?
Interesting trade off… adding a server moves less data, but you end up with an unbalanced load
But I guess in the first place, if your load is initially balanced and you start running out of space, you run out of space on all the servers, not just one. So you would add N servers and your load is balanced again.
3 comments instead of just editing the first for that sweet sweet youtube algorithm :) great vid!
They add the concept of virtual nodes mean multiple virtual nodes are associated with one physical node and are distributed along the hash ring. Hence it may reduce the uneven distribution of moving data.
@@hoangnguyendinh1107 That is very very clever! I could see how that solves the problem. Thanks!
Does introducing a new server in your example not result result in the load being unevenly distributed? With 4 nodes, each node is receiving an equal proportion of the total range 0-360. Adding a node between S0 and S90 means that the range between S270 and S90 is served by 3 nodes while the rest of the hash range is still served by 2 nodes. It sounds like one needs to add 4 new nodes to get an even distribution of load.
The most common way to mitigate this is using more than one hash function for the servers. A good value could be log(M), where M is the max number in the circle, in this case 360. This way you "ensure" the are not big chunks without a server in the circle and keys get distributed uniformly. Off course you pay the price of complexity, and when remove/add a server, you need to reallocate log(M) times. Cheers!
wow
when we add a new server, rather than new server talking to next server to transfer keys, how about it gets populated lazily as and when cache miss happens
If you really think about it, that's not only about system design but also some algorithmic stuff that many people hate on the coding interviews.
Please make more videos related to system design, there are a lot of interesting things(you probably covered most of them ahaha).
I was nostalgic watching this video if you know what I mean. 😊
Rendezvous hashing is more simple than consistent hashing and solves the same problem. But there are other tradeoffs.
Another problem is that data load not evenly distributed if many servers are close on the ring
Right! Hot spots.
@@hnasr a way to mitigate that is to have multiple hash functions for the servers.Cheers!
this is like a HEX
So this video doesn't discussion V-Nodes yet?
Somebody shall ping the data number destribution when have an issue there you can't guess on that or just turn a script look for every single one in the array do there can be said upgrade to that do I can't spoil it, bc it is coming 👍
Hussein I am a fan. Please pin this comment.
and then we play endless snake that consume more and more trouble how we explain it XD
first
🎖️this for your
Now enjoy
Expected a better explanation. Expect a long follow up video.