Consistent Hashing: Easy Explanation for System Design Interviews

[00:01] including the problem it solves how it works and when it might come up in a system design interview now consistent hashing is easiest learned via an example so imagine we host a simple events website

[00:13] something like Ticket Master it starts really small so we only need a single server and a single database that stores all of our event information now as the too many events to store on that single database so we add two additional

[00:28] databases but there's a problem for each given event how do we know which database that event should be stored in is it stored in one 2 or three we all three databases every time a client requests some information for a given

[00:43] event simply because we don't know which database it's actually stored in one approach as shown here is to Hash the event ID with some hash function this can be an md5 murmur whatever it may be and this will give us some large number

[00:58] we can then take that large number and mod it by the number of database servers that we have in this case three that will return a number between 1 and three indicating which database that event should live on and so in our case event

[01:13] should live on and so in our case event 1 2 3 4 when hashed is 67211 mod 3 equal 1 2 3 4 when hashed is 67211 mod 3 equal 2 and so it should be stored on database 2 this hash with modulo approach worked great to start but the site continued to

[01:27] grow and when we went to add a fourth database We R ran into a really big problem see by changing the number of database servers that we had we've also now changed the modulo in the function it's gone from Mod 3 to mod 4 the issue

[01:42] with this is that this means almost all data now needs to be redistributed not just data that should be in our new database for this example makes that really clear so if you remember before event 1 2 3 4 existed on database 2

[01:55] because we had this function where we modded by three now if we instead run this by uh with the new setup modding by four now it should exist on database 3 and so that means event 1 2 3 4 would need to be move from database 2 to

[02:09] database 3 and 1 12 3 4 isn't alone it's not an isolated incident almost every single event in our database needs to be moved or redistributed the this redistribution is really bad it creates a surge in database activity and this

[02:23] can slow down or in some cases even crash our site the problem didn't stop let's say that we needed to decommission database 3 maybe it was getting old so we would need to move the data from database 3 over to both one and two

[02:38] respectively but since our modulo has changed again we've not only redistributed all of the data from database 3 but we also redistributed all of the data once more and so looking back at our example uh event 1 2 3 4

[02:53] which was on database 2 in theory shouldn't need to move but now it's shouldn't need to move but now it's moved to database 1 problem let's go ahead and introduce the solution consistent hashing and so

[03:07] consistent hashing uh consists of three steps the first step is that we create what's called a hash ring that has a fixed number of points and so to keep it simple we've Illustrated here just 0 to 100 now in reality this is 0 to 2 32

[03:22] basically the full integer space uh but the concept is entirely the same so we'll stick with 0 to 100 now we then evenly distrib our databases across this hash ring so in our case we have four databases we could Point them at 1 25 50

[03:37] and 75 respectively and now in order to know which database a particular event should be stored on we first hash the ID just like we did before imagine that event number two hashed is 16 we then find

[03:51] number two hashed is 16 we then find that point on our ring 16 is here and we walk clockwise until we hit a database so in this case we hit database 2 and we're going to store event two on database number two now this might seem

[04:04] obvious but this ring isn't physical of course it's just the mathematical construct that's programmed into your code um but let's take a look at how this solved our problems from earlier and so if we want to go ahead and add

[04:17] our fifth database like we did before look at what happens let's say we add that database and we put it at 0 90 on the ring we could put it anywhere but we'll say 90 now the only events that need to be distributed are any events

[04:31] that hashed to the range 75 and 90 these are events that were previously on database 1 and they now need to be on database 5 but all other events stay exactly where they were there's no longer this Mass

[04:45] redistribution now the exact same thing is true when we try to remove a database as well and so in this case we can remove database 2 and only events that hash to uh a spot on the ring between 0 and 2 5 like event 2 which hashed to 16

[05:02] before need to be moved they were previously on database 2 and now they need to be moved over to database 3 Okay so we've solved for most of our problems up until this point but there's one last thing to take care of and so

[05:15] ideally if we remov database 2 we wouldn't store all of the data from database 2 on database 3 as we're doing now this means that database 3 has 2x the amount of data as database 1 and database 4 so the question becomes how

[05:30] do we make sure that the data is more evenly distributed when a database exits the ring and the solution is something called virtual nodes and so instead of on the ring we can put it at multiple

[05:44] database 1 we don't only put it at position zero we can also put it at position zero we can also put it at position 20 and 40 and 60 and 80 for database 2 we don't only put it at 25 we can also put it at 5 and 45 65 and 85

[06:00] and so on for each of the other databases and so what this means is that now if database 2 is removed instead of all the data all the events that hashed database 3 some of them are going to go to database 3 those between 0 and 10 but

[06:15] between 10 and 15 they're going to go to database 4 and between 15 and 20 they'll go to database 1 and 20 to 25 will end up falling on database 3 and so as you even redistribution so now you know what

[06:29] consistent hashing is but when does it come up in a system design interview the services use it behind the scenes to scale each of redus Cassandra datam modb uh most CDN and many more all use consistent hashing now in an interview

[06:44] you might make a nod to this when you introduce any of these Technologies but need to go deep into describing the algorithm is if you're designing a something like design and distributed cache design and distributed database uh

[06:58] design and distributed message CU or so on uh lastly if you really like this help you prepare for your software engineering interviews head over to hello interview.com we have everything you need over there good luck with your

[07:12] you need over there good luck with your interviews bye-bye