Speaker A
Let's talk about consistent hashing, 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, something like Ticketmaster. 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 site becomes more popular, we have way too many events to store on that single database, so we add two additional 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, two, or three? We certainly don't want to have to query all three databases every time a client requests some information for a given 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. 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 one and three, indicating which database that event should live on. And so, in our case, event 1234, when hashed, is 67211 mod 3 equals 2, and so it should be stored on database 2. This hash with modulo approach worked great to start, but the site continued to grow, and when we went to add a fourth database, we 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 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, it makes that really clear. So if you remember before, event 1234 existed on database 2 because we had this function where we modded by three. Now, if we instead run this with the new setup, modding by four, now it should exist on database 3, and so that means event 1234 would need to be moved from database 2 to database 3. And 1234 isn't alone; it's not an isolated incident. Almost every single event in our database needs to be moved or redistributed. This redistribution is really bad. It creates a surge in database activity, and this can slow down or, in some cases, even crash our site. The problem didn't stop there either. 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 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, event 1234, which was on database 2, in theory shouldn't need to move, but now it's moved to database 1. Okay, so now that we understand the problem, let's go ahead and introduce the solution: consistent hashing. And so, consistent hashing 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, basically the full integer space, but the concept is entirely the same, so we'll stick with 0 to 100. Now, we then evenly distribute our databases across this hash ring. So, in our case, we have four databases. We could point them at 1, 25, 50, 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 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 obvious, but this ring isn't physical, of course. It's just the mathematical construct that's programmed into your code. But let's take a look at how this solved our problems from earlier. And so, if we want to go ahead and add 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 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 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 a spot on the ring between 0 and 25, like event 2, which hashed to 16 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 most of our problems up until this point, but there's one last thing to take care of. And so, ideally, if we remove 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 twice the amount of data as database 1 and database 4. So the question becomes, how 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 putting each database at just one point on the ring, we can put it at multiple points. And so, for example, if you take database 1, we don't only put it at position zero. We can also put it at position 20, 40, 60, and 80. For database 2, we don't only put it at 25. We can also put it at 5, 45, 65, and 85, 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 to this point on the ring going to database 3, some of them are going to go to database 3, those between 0 and 10, but 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 can see, it ends up being a much more even redistribution. So now you know what consistent hashing is, but when does it come up in a system design interview? The reality is most of your favorite services use it behind the scenes to scale. Each of Redis, Cassandra, DynamoDB, most CDNs, and many more all use consistent hashing. Now, in an interview, you might make a nod to this when you introduce any of these technologies, but the only time you're really going to need to go deep into describing the algorithm is if you're designing a single scaled backend component, something like design and distributed cache, design and distributed database, design and distributed message queue, or so on. Lastly, if you really like this video and you want more free content to help you prepare for your software engineering interviews, head over to hellointerview.com. We have everything you need over there. Good luck with your interviews. Bye-bye.
