Consistent Hashing

Consistent hashing is a strategy for dividing up keys/data between multiple machines.

It works particularly well when the number of machines storing data may change. This makes it a useful trick for system design questions involving large, distributed databases, which have many machines and must account for machine failure.

Dividing hash values between machines

Ideally, we want a division strategy that lets us add or remove machines without reassigning lots of keys.

Remember, the big benefit of consistent hashing is that it can handle machines being added or removed. That may seem like an edge case, but in large systems with thousands of machines, failure is normal.

Let's compare a few different options:

Option 1: Mod the hash value by the number of machines.

With this strategy, if we have N machines, we compute hash % N to figure out the machine responsible.

So, with 3 machines, a hash value of 0 would map to machine A, 1 maps to machine B, and 2 maps to machine C. If we keep counting up, we start to repeat machines. So, 3 maps to machine A, 4 maps to machine B, and 5 maps to machine C.

Visually, we've divided up our number line like this:

IMAGE EDIT: Machine A, Machine B, Machine C

Now, say we add another machine. Now, we're computing hash % 4 instead of hash % 3.

Here's how our assignments along the number line change:

IMAGE EDIT: Machine A, Machine B, Machine C, Machine D.

Look at how our number line changes! Lots of keys are now assigned to different machines. To accommodate this, we need to send data from its old machine to its new one—that's lots of network traffic and could take a long time with large amounts of data.

Option 2: Divide the number line into N even chunks.

If we have three machines, our number line would look like this:

IMAGE EDIT: Machine A, Machine B, Machine C

What happens when we add another machine?

We'll have to re-divide our number line, taking a bit from each of the three old machines to give to the new one. Here's what that looks like.

IMAGE EDIT: Machine A, Machine B, Machine C, Machine D.

This seems like we're on the right track. We still have a lot of the number line that's been reassigned, but not as much as with the mod operator.

Option 3: Hash the machines, and assign keys to the next machine on the number line.

Here's what that looks like with 3 machines:

IMAGE EDIT: Machine A, Machine B, Machine C

There's a corner case though. What about numbers that appear above the highest-hashed machine?

We'll say that if you walk off one end of the number line ...

IMAGE EDIT: Machine A, Machine B, Machine C

... that you end up at the other end.

IMAGE EDIT: Machine A, Machine B, Machine C

Putting things together, we end up with a ring. Here's what it looks like with three machines.

IMAGE EDIT: Machine A, Machine B, Machine C

Okay. What happens when we add a fourth machine?

It gets hashed, placed along the number ring, and takes some of the keys from the machine that appears after it.

IMAGE EDIT: Machine A, Machine B, Machine C, Machine D.

Nice. We're not reassigning lots of data. In fact, only one machine needs to send data to the new machine.

This is the strategy used by consistent hashing.

Like we said above: the secret sauce of consistent hashing is how we assign keys to machines. Our assignment strategy works well for large systems where the number of machines can change, because it doesn't reassign too many keys every time we add or remove a machine.

What happens if a machine leaves?

With consistent hashing we're assuming that machines can leave and join over time. If a machine leaves, won't we lose data?

To avoid this, we'll usually have machines act as backups for each other. One strategy is to have each machine replicate the data stored on the machine behind of it, giving us a backup copy.

Again, this is the sort of implementation detail you'll want to mention to your interviewer, even if you won't draw out the entire implementation.