Basics of consistent hashing in plain english | System Design fundamentals
ฝัง
- เผยแพร่เมื่อ 28 เม.ย. 2021
- In this video, we talk about one more important component of System Design: Consistent Hashing!
We want software engineers and aspiring software engineers to develop basics and get ready for the world of interviews as well as excelling as a Software Engineer.
Reference: www.toptal.com/big-data/consi...
------------------------------------------------------------------
Recommendations
------------------------------------------------------------------
Our full courses on youtube:
✒ System Design Primer Course: • System Design Primer C...
✒ REST APIs made easy: • REST APIs MADE EASY
Some paid courses that we recommend:
✒Educative.io: bit.ly/3qnW5ku
✒Interviewready.io: get.interviewready.io/ (Use coupon code SUDOCODE for extra discount)
------------------------------------------------------------------
About Us
------------------------------------------------------------------
Created and Instructed by:
Yogita Sharma
✒ LinkedIn - / yogita-sharma-83400b55
✒ Instagram - / sudo.code1
✒ Facebook - / sudo.code
✒ Medium - / yogita088
Post-production(editing, thumbnail etc) managed by:
CiKi
✒ Website: www.ciki.co.in
✒ LinkedIn: / 74735937
Colors and design by:
Naini Todi
✒ LinkedIn - / nainitodi
Both Arpit and Yogita are software engineers and want to help other software engineers become better by providing high quality and well researched content by adding their creativity and teaching twist.
------------------------------------------------------------------
Join Us
------------------------------------------------------------------
Hangout with sudoCode:
✒Discord Server: / discord
For business:
✒Email: sudocode.yogita@gmail.com
Minor correction: what you are calling clockwise is actually anti-clockwise :)
Also. can you please share details of how rebalancing is achieved in real-life? What happens if it gets a req while it was rebalancing?
It can be clockwise or anticlockwise as per the implementation. Resource attached. The request will probably drop or get enqueued, again depending on implementation.
@@sudocode The point which Kanika brought is , you are calling clockwise but you are serving requests anti-clockwise
It is actually clockwise if you think about it. The misunderstanding happened because she drew the line from the data point to the server, which is anti-clockwise (to indicate where the data is going to sit), making you think the key association is anti-clockwise.
Server copies here are actually called Virtual Nodes! Each virtual node gets their hash code from the same hash function. When a server dies, all the virtual nodes also die, and with random distribution of the other virtual nodes from the active servers, the hope is that the data movement would be minimal. In addition, the virtual nodes can also hold replica of other node’s data for high availability & reliability.
Also we should note that the problem was of uneven distribution of data not the number of remaps that would have to happen if a node goes down, hence it leads to confusion for some people.
Hey, I haven't found any link regarding implementation in description
Thanks Yogita. You made it look simple.
I have some queries.
1. So the consistent hashing comes at the cost of horizontal scaling, is this a correct statement?
2. We are going to increase replicas so how is it decided that how many replicas of s1 and s2 only are required to be created. I am thinking if there is this resource not utilised even after creating replicas. (i.e. s1-c and s2-c suppose are created but not used and only s1 and s2 served the purpose)
3. Where is the implementation link you mentioned about?
How are the s1-c, s2-c, s3-c distributed in the circle? They did not seem to be distributed evenly in the circle.
As always, great content Yogita. Your video production skills have improved a lot since the very beginning of the series. Regarding the direction forward, why not take that approach which allows you to be more creatively expressive in your discourse, may whatever that be... :)
Instead of replica's been placed, it can be like generating multiple hash codes for the same servers itself. like
S1 = 20deg(29373), 60deg(87644), 90deg(49649), 170deg(23933). Something like alias Hashcodes and place it in the circle. This would suffice is what I think.
Thanks Yogita! You have explained it so nicely and the best thing was visualization.
I would request you to make the video on various distributed rate limiting algorithms.
Is the replicas put in random order on the circumference of the circle?
consistent hashing 1:39
concept (anti clock example) 6:30
problem with consistent hashing 8:45
how did you decide which replica will be placed at which position ?
Hi Yogita,
Hope you are doing good.
The video was excellent as usual.
About using IPad to generate video, it seems the sides are switched between what you see on IPad and what we see on the screen.
In video you mentioned about some link for implementation. I don't see it in description.
Are those video's also hosted on some other website than TH-cam?
Thanks.
How do you resolve situation when two of your servers have the same hash?
Like it’s on your picture - servers S1,S2,S3,S4 mapped to hashes 25,67,49.
this way is amazing , thank you for the wonderful explanation.
its amazing.
Thanks for the detailed explanation.
Few queries on replica :
Are replica's actual servers or just virtual entity to map requests?
Also, how are replicas mapped on the circle?
I also have same question. Did you get the answer ?
Those are just the virtual representations of server_ids and client_ids over the consistent hashing ring.
These are called virtual nodes rather than replicas as pointed out by other subscribers.
I want to ask one thing i.e, you have talked about how the key remapping is reduced by establishing replicas distributed according to hash value. My concern is, what about data consistency how this replicas maintain their consistent states along with the actual server nodes ?
still not clear, let's say we saved 32 at the server (S1) and now (S1) is down. Next server on the ring is (S2) but (S2) doesn't have 32 since it was stored on (S1). Does it mean that when (S1) crashed, we have to migrate all data including 32 on (S2)?
Thanks! That was very useful and the explanation straightforward!!
Really amazing video ! the way u explains the topic it becomes more intresting and less boring . thanks a ton!
Just discovered your channel, keep uploading really helpful content ❤️
Thanks Vikram!
I just want to know what's your process about making these videos, from where do you study about the concepts of system design, does DDIA plays a big part in it? I have been reading DDIA since last month, to me it does take time to grasp what's written in it.
It is books, practical experience, masters degree and a lot of reading.
Superb...both whiteboard and iPad screen recording explanation style is awesome
u can mix up both
Best explanation of consistent hashing. Thank you Yogita 🙏
Hi Yogita, Thanks for the awesome content you have created. It would be great if you can go with the white board approach.
Which one suits best when designing a system Python or Java
We are moving to consistent hashing to lessen the cost occurred by moving the keys around in sharding.If we use many replicas of servers in consistent hashing, how is it reducing the cost?
You have explained everything in a very clear and simple way. You deserve more views and more subscribers.
Mam I have one doubt what do we actually mean by virtual server ????
Do virtual server serves the request themselves or do they transfer it to the original server ?
Do they take space on the ring ?
thank you for the video. After the remapping, the replicas are no longer replicas right? how does it work then? they will be partial replicas. Instead of this why not simply have more servers and/or use a load balancer?
Top-notch explaining of Consistent Hashing with great examples.
I enjoyed it so well. Able to picturize all your concepts. thanks much Yogita..
Thanks Yogita.
What is your plan to upload in future.
Are you going to post full system design videos?
Can you provide in advance what we can expect from this channel?
You mentioned u would attach code reference to implement consistent hashing.. can u please point me to that please ?
@sudoCode Please upload full video on UBER/Whatsapp or any system so that in the system design round we can perform well..Also I would like you to cover some LLD concepts or share some LLD resources as well, that will really be quite helpful. Thanks a lot for your time and effort.
Yes that will be good
yes!
Great explanation, Thank you!. Question: When you say replica server for S3, by very definition of replica, each replica of S3 will store the same data. In this example, each replica of S3 stores different keys. So Why do you call it replica. Why not say instead of 3 servers S1 through S3, to solve the issue of loading one server too much we are introducing more servers. After all, each replica server ID is also hashed and stored on the circle? Maybe I am missing something here
@sudoCODE: Same question, I have,
@@HamidrezaFarhidzadeh Here, replica servers of S3 doesn't mean that they are different servers. But, different values for S3 servers after passing its IP address or name through different hash functions. This is done so that the S3 server has more presence on the circle. This is done for all the servers so that when a particular server fails, not all the load goes back to just one server whichever is next.
@@VikramKumar-qo3rg yes here replica is slightly confused . slave represents 100% replica
Missing the link for implementing consistent hashing. Can you send please interested to implement and test?
Excellent video, can you please post a series about LLD and Machine coding ?
i am still not able to understand how it is balancing the load.. since after remapping S1 servers and its replicas have all the key and S3 doesn't have any.
I have a major query. Even after creating replicas, we didn't solve the problem of overloading on a single server, AT ALL? Majority of the load was on s1-c.
thats a very good point, @sudoCode Can you help us on this ?
We were not solving problem of overloading. We were solving problem of moving minimum number of keys around.
@@sudocode Oh yes, I'll look up how to fix this problem and add here. Btw love the content!
@@AniketSomwanshi-ll7mz I believe that on creating server replicas onto the hash ring itself solves that problem.
@@sudocode I don't understand. In the above example , if the server S1 was removed , the number of keys have to be moved would have been more right , even with server replicas ? Explanation of Server replica part is not very clear about what it is achieving
I understand that when we remove server values we are going to new server, but are we going to move the existing values in that server to next server, or the new keys only will start going to new server. This is applicable in case the server also goes down
Yes same doubt.. in case if we are adding a server then will we place the new server next to removing server ? Or the new server is introduced after copying datas to existing next server from the removing server? Plz clarify @sudoCode
Apart from few terminologies error like clockwise anti clockwise, rest was nicely explained. Thanks
where is the link to implementation as told at the end of video @13:20
Thank you for the great explanation! I have a question, who manages this consistent hashing? Is it some central master server?
It can be application server or a central server.
@@sudocode thank you for responding!!
What if one user has 1k insert query requests then the load will be on one single server where the user is mapped to by hashing....how to reduce that load? Please answer. The mapping of request to server mapping is done by user info or each specific request. Am I missing something here?
That can be handled by back pressure or queuing of requests.
I feel like it is very expensive because totally you are using 10 servers here one way or other. And if you take large count of values remapping percentage also increases correct me if I am wrong
It seems that you use those replicas(as you call them) as regular shards/partitions. Essentially instead of 3 shards/partitions you do have 11 of them distributed along the circle and of cause it’s reduces impact of required rebalancing (shifting data around).
If you actually use replicas, then data propagation would be still required to copy moved data to all replicas.
Really awesome explanation.
Can anyone explain me how the replication is working among the servers? Will there be any latency among the replicas, If so, how its going to impact us? Also when a server is removed (due to any reason) it's replicas are also removed from the hash ring? Why so? And if we dont remove them what could happen?
in my opinion, they are not replicas, they are virtual nodes, which just map to their associated server
Please make a video about how to design Facebook or Twitter with the concepts you taught us from video 1..24.
This would be very helpful 🙏
What is a replica in this context?
Very clean !! thank you!
Thank you so much for this.
Hi mam , I am confused how chatting application keeps the users informed about his connection/friend online status as broadcasting the message is most resource intensive , can you please suggest any article or make a video on this
Heard of sockets?
@@sudocode yes , socket is used for connection. My question was facebook have 5OM active users or more , on a average lets suppose 2 friends come online per sec for each user. So we need to send 10 M requests/second to notify a user about his/ her friend status .how to optimise this solution
Thanks for the video. So I get the concept of hashing to a place on the circle. But how do you derive where the nearest server is on the circle? Back when we were using a linear map (in your previous video), you compute what server your key belongs to using modulus formula (e.g. %4 for 4 servers. super easy to understand, so far, so good). But in the consistent caching, how do we determine that the next server in the circle is S3 for Neha (in your example) since there's no "algorithmic" direct way like a modulus formula? Does the cache client have information on what ranges each server is assigned to? Take Ankit and Neha, whose key hashes to 12 and 42, respectively. Can you provide a concrete example of how S3 is determined to be responsible for key range 0-42, and hence how we know Ankit and Neha is in it? And if that's how it works, why is Ankur (34) mapped to S2 instead of S3 (since it's between 0-42)? Is that an error on your part? Like I said, I get the circle concept. I'm just not connecting the dots because unlike your previous video where you used a concrete method to determine S0,S1,S2,S3 (even if it's a contrived one like modulus, it helps), you skipped how S1,S2,S3 were placed on the circle in this video. Say we use server name like you mentioned to do this. So is it like, based on server name, we compute S1,S2,S3 to fall on angle 0, 120, 240 respectively (let's say clockwise). And then for Ankit, we determine that the angle his key maps to is 140. So then we know that S3 is the server it maps to since it's the nearest server clockwise (240) after 140? Is that how it works?
The hint is the angle of the sector created by two serves adjacent to each other.
Hi, the slack workspace link isn't working, could you please update it
Yes
How did the approach solve even distribution? Still 3 keys are at S1C.
The approach minimises the key redistribution.
Thanks for this amazing and simple explanation.
I did not get the idea of replicated servers. Isn’t it like having new physical servers? How is it a replica then, it will be an independent server. Someone please clarify my doubt 🙂
at 12:00 what if you remove S1 , we will have 75% of remapping ........... then how it wil solve the problem ..... to get even distribution we are getting more remap percentage @
I was able to understand this concept very well thank you
Got it completely thank you
Great explanation. Please provide the solution to the question in previous video
Agreed. Explanation was good
Very well explained! Thanks
Thanks for the great explanation!
06:37 Anti Clockwise Direction
Certainly the easiest explanation to consistent hashing around
Quality 👌🏻
Great video, thanks!
Yogita , 1. this is the best teaching method ever 2. very nicely explained 3. keep on posting such amazing videos . BTW where is the link that says implementation of consistent hashing
Very good explaination. Liked it :)
nice
Nothing for reference in desciption
This was a great explanation.
At the end of the video all keys are mapped to s1c server, so here it seems uneven distribution.
We were solving to minimise the keys which are moved around from deleted server to non deleted ones. Consistent hashing helps us optimise that.
@@sudocode I think by rearranging replica server positions (names) on circle, would solve the S1 server overloading problem.
Slack link is invalid. It says - To join this workspace, you’ll need to ask the person who originally invited you for a new link.
I have doubt regarding caching
Consider I have "cache aside pattern" and "in memory cache" in application server is used. I'm looking for Invalidation logic when there is an update. This was the context.
I read for critical data like password/financial information we use Write Back policy to ensure consistency. In write through one instance's in memory cache entry gets updated and others can remain stale. So, there is inconsistency in write through
My question is same can happen in Write Back, one instance's in memory cache entry gets deleted(invalidated) and we update DB..other instances in memory cache still have that entry. So there is inconsistency in write Back as well? Why do we prefer write back for critical data because same issue is there in write back.
If answer is invalidate all instances' in memory cache entry then same can be done for Write through. Which makes me ask question 2.
My another question is : We can update all instances' in memory cache entry and then update DB. In this way consistency is maintained so why not we use Write through for critical data like password financial information?
join.slack.com/t/sudocode-workspace/shared_invite/zt-qa184kms-XlGUrx2BbxHfdOc1XYznBw
The iPad teaching is excellent and completely a replacing choice with whiteboard.
Excellent .
wow
Nicely explained.
What's the point of having replicas? This is just like having more number of DBs
I am a new subscriber.
Nice intro. However, it has a lot of misleading information.
1) How does adding new replicas different from adding new nodes. Your example sounds like there is no difference.
2) Are you sure all replicas are write enabled replicas? How do you maintain the consistency( or even eventual consistency) then ? Generally, one (master) server is write enabled node that propagates the data to slave servers.
First thing:- iPad works far better. And its ood for you because you don't have to stand all the time.
Second thing:- I don't have to search for theoretical explanation of consistent hashing anymore because this was the last video i needed to understand the conecpt. Thank You so much.
Good and Simple Explanation of good Concept
yes I am also thinking about replicating s1,s2,s3. Because I am watching this video 2nd time :D
Great explanation! I would suggest you to move forward with the iPad method of teaching. Thanks for you content once again. :)
its not replica, its called virtual node or virtual labels.
calling virtual nodes as replicas confused 99% of the people
you looks good in lampblack 😘😅
Again replicated servers Lso you need to spend money. Hence you are spending dollars to reduce the key distribution when a server is removed. End of the day money matters and we are losing money in the name of replication. Isn't it ?
Please go read some books on computer science and business.
White board was better
whiteboard
no virtual whiteboard :)
iPad teaching is better
I am a new subscriber.
Great