Consistent Hashing Explained Simply | System Design Fundamentals

[00:00:00]hello and welcome to pseudocode i know this must be a long awaited video and i wanted to do it uh properly so that it makes it easy for you guys to understand so let's dig in we are going to start today with consistent hashing i hope that you guys have already watched the hashing video if you haven't i would strongly recommend to watch that first because it will help you build the foundations of hashing and then it will make it much more easier for you to start with consistent hashing video so let's get started [Music] as you know in previous video when we were studying about hashing uh we calculate hashes for all the values that we want to save and there is an output range of numbers for which the those hashes are generated and then we map those numbers to different servers and hence we save the values in different servers right we found that the problem occurs whenever we want to add a server or remove a server when we have to do that we have to remap the existing keys right and consistent hashing solves that problem if you remember i also gave you guys an exercise to find out maximum number of keys that have to be replaced or remapped whenever a server is added or removed i hope you guys might have calculated that if not yet i'll add it in the description this time so we have to solve the problem of reducing the number of keys that have to be remapped whenever a server is added or removed from a cluster where we store all the key value pairs so let's start look at this circle over here we have 360 different angles on that circuit right what we try to do in consistent hashing is we try to put our hash generated values on a circle we try to map those values on this circle right as you can see the circle is going to have 360 different angles right we try to map those values as per these angles let's see how let's say that the hash output range that we have is 0 to 100 okay and the angles on the circle are 0 to 360. now what we are going to do is we are going to map the values generated from our hash functions to this different angles which will uh represent our values on that circle okay so let's see we are still using the same hash function as we used in the previous video and these are the values generated what we are going to do is these values will be mapped to different angles on this circle as you can see here right how these are mapped is hidden into the implementation details but the basic concept that i want you guys to understand here is that the output values which lie between a certain output range which is 0 to 100 are mapped or distributed over a circle right every value will be mapped to a certain angle and then that value will be represented on that circle so the output range can be represented uh on this whole circle itself this is the basic concept of putting the hash values of the input data on circle right up till here this is fine but now how are we going to map which server this value sits on or which server this particular key and its value goes to right because we are still discussing that how do we map the values to different servers right in the previous implementation of simple hashing we had different values sitting on different servers right now here the basic concept or the basic premise of consistent hashing is that you represent hash values which are these numbers and the servers itself which are these values on same circle okay that means that for every key value pair that you want to save there will be a hash generated and for every server also there will be a hash generated which will lie in the same output range okay so let's say that the hash generated for these four values are 1242 34 and 67 we will generate hash values for uh the servers also using the server's ip or the server names and those values are also going to lie between the range range of 0 to 100 and when they lie in the range of 0 200 and we map them on different uh angles of the circle this is how it will look the values as you can see are lying on the circle right the servers are also lying on the circle okay just like these names have different hash values 12 42 34 67 these servers also have some values let's say uh 25 or 64 or 75 in this range right these values are also going to sit on the circle okay now what we have done we have mapped the values on circle using the hash output and we have also mapped the servers on the circle right so half of our work is done we have made the premise that the servers and the input values all share the same output range right please remember this is the basic concept the server the server is the hash and the data's hash share the same output range and are represented on the same circle okay now comes the important part which is mapping these values to servers how are we going to know that where will 12 set variable 34 set level 67 set and so on right how do we know which server we have to store the value on for that there are two implementations either you can go clockwise or anticlockwise i'll show you what that means we can follow one convention right that every value if you want to find out on which server it has to be saved you have a convention like every value will sit on the next server that it finds in a clockwise direction it can be anti-clockwise also right let's say we are going to use clockwise here right so 42 is going to sit on s3 34 is going to sit on s2 67 is going to sit on s1 and if you look at 12 and you try to move clockwise s3 is the first server that 12 finds out so 12 also sits on s3 just so that it reinforces uh with you guys i am trying to repeat it again for every value we try to find out the closest server in the clockwise direction so for 42 that is s3 for 34 it is s2 for 67 it is s1 and for 12 it is s3 right so this way you map your values to servers and then again it becomes the same thing that these different values sits on different servers right up until here it's fine so this is how inconsistent hashing you map the key values to different servers right now comes the part where we were solving the actual problem the actual problem was that whenever we want to remove a server we have to remap a lot of keys so let's see what will happen if we remove a server from this circle right okay so let's say s3 has been removed if you remove s3 this is how the circle is going to look like right now see what will happen 34 will still belong to s2 it it was belonging to s2 here as well okay 67 will still belong to s1 it was belonging to s1 here as well right and 42 and 12 now since we have removed s3 now 42 and 12 both are going to belong to s2 itself right so we can see that out of these four keys 67 34 12 and 42 we didn't have to touch 67 and 34 at all only 12 and 42 got changed right so 50 percent of the keys have to be remapped if you remember our previous example where we were not using consistent hashing you saw that almost 100 of the keys got remarked right so here the movement of keys becomes less less number of keys have to be remapped why because only few keys which were sitting between s1 and s3 and now since s3 is not there i have to be remapped to s2 right but can you think about what is the problem with this approach i will put a 10 second timer for you guys to think about it the problem with this approach is as you can see when we have removed s3 you can see all the keys between s1 and s3 came to s2 right s2 earlier only had 34 and now s2 has 42 and 12 as well that means that s2 can get overloaded right imagine that there would have been many more keys here between s1 and s3 and once s3 is removed all those keys come to s2 that means s2 is going to have a lot of load right so then the distribution of keys is going to become uneven s1 has less keys but s2 because of s3's removal has more keys now right how do we solve this problem we solve the problem of remapping less number of keys but because of that we encountered another problem that now the keys are not evenly distributed right so for that what can we do if you're thinking about replicating s1 s2 and s3 then you're moving in the right direction that's what we are going to do let's see here what we are going to do is we are going to create replicas of s1 s2 and s3 so as you can guys see here i have made uh the naming convention as s1c s2c s2c s1c s3c s3c and s1c so if you note for every server there are two to three copies so let's see for s1 one two three three copies of s1 for s2 also let's see one two and three three copies for s2 and let's see for s3 as well one two okay two copies for s3 so what we are going to do we are going to have replicated servers we will generate hash for them and then we will distribute those servers as well on this circle right now let's see what happens when we are going to map these keys again we are going to map these keys to the next available server right let's see how so 12 is going to be mapped to s1c 42 is going to map to s1c 34 is on s1c and 67 is on s3c okay now let's say we have to get rid of s3 okay let's see what happens after we got rid of s3 we have removed all the replicas of s3 as well right now let's see what happens to these keys 42 goes to s1c 34 goes to s1c 67 goes to s1 and 12 goes to s1c now let's see how many keys are have been replaced if we look here 12 was at s1c 42 was at s1c 34 was at s1c and 67 was at s3c now moving on 12 is still at s1c 42 is still at s1c 34 is still at s1c and 67 from s3c it have has to move to now s1 so as you can see now only one key had to be demand so it must be very clear from this example that when we were not using replicated copies we had to remap 50 of the keys but when we are using different replicas we have to remap only 25 percent of the case again there is an exercise for you try to have more number of servers let's say instead of three servers try to have four servers instead of two copies try to have four copies and increase the number of keys like instead of having four keys maybe have ten keys and then do this exercise by yourself try to remove a server and see how many keys have to be remapped try to add a server and see how many keys have to be remapped try to do this whole exercise with different replicas and try to do this same exercise without any replicas just like with single notes and you will find out like as a proof that when you have no replicas you have to remap more keys but when you have replicas you have to remap less number of keys that's all about consistent hashing that's it we have reduced the number of keys that have to be remapped we have also reduced the uneven distribution of keys now the distribution is even and you again end up removing or remapping very very less number of keys as we saw here right i have tried to make this video as simple as possible and as plain as possible so that you guys get the hang of what consistent hashing is but the work doesn't stop here what you have to do is i am going to link an implementation in the description just after understanding this algorithm try to implement it on your own if you cannot go through the link that i am going to attach in the description and then read that code and then without looking at it try to implement it on your own see if you can make any improvements see if you can still find out any loopholes try to see how that code performs what is the complexity and then there is one more link that explains how consistent hashing is used in different caching solutions try to read up on that as well so that you will not not only understand the implementation of consistent hashing but you will also understand how it is applied on large solutions like redis or memcache and how it is so effective so that was all about consistent hashing i hope it will help you to understand the concept i hope it will help you to build your understanding of this topic very well apart from that uh i just wanted a feedback from you guys up until now we had been using whiteboard for explanations and for teaching and i have started with this kind of screen recording an ipad for just one or two videos let me know in comments if this looks better for you or was it better when we were using whiteboard depending on what uh the majority uh votes for we will try to switch the uh method or we will just try to go ahead with the ipad teaching itself check out description try to implement and i'll see you in the next video thank you