Consistent Hashing

Say you run a cache, and one machine is too small to hold everything. So you run three cache servers and spread the data across them. Now the question is simple, and it comes up in almost every system design interview: when a request for user:42 arrives, which of the three servers holds it?

Whatever answer you pick has to be the same every time, from every app server, without anyone asking a central list. The first idea most people try works fine until the day you add a fourth server. This note is about why it breaks on that day, and the neat fix that makes adding servers cheap.

The first idea: hash and mod

A hash function takes any input (a string, a number) and turns it into a big number. The same input always gives the same number, and different inputs give numbers that look random. That is all we need from it.

The obvious plan is to hash the key, then take the remainder after dividing by the number of servers.

server = hash(key) mod N

With N = 3 you get 0, 1 or 2, which is the server number. It spreads keys evenly, it needs no lookup table, and every app server computes the same answer. It looks perfect.

What happens when N changes

Traffic grows, so you add a fourth server. N goes from 3 to 4, and the formula now gives different answers for most keys. Let us see it with small numbers. Pretend that the hash of each key is just a number from 1 to 12.

Nine of the twelve keys land on a different server. That is 75 percent. It is not bad luck with this small sample. Going from N to N + 1 servers, only about 1 out of N + 1 keys stays where it was, so with 3 going to 4, only a quarter stays. I also ran this with 10,000 real looking keys such as user:0 to user:9999, and 7,538 of them moved.

Now think about what that means for a cache. Those moved keys are not lost, they are just on the wrong server now. The app asks server 2 for a key that lives on server 0. Server 2 says "never heard of it", which is a cache miss, so the app goes to the database. Three quarters of your traffic is suddenly hitting the database, at the exact moment when traffic was high enough that you needed another server. That is a classic way to turn a scaling step into an outage.

If the servers hold real data (a sharded database), it is worse. Three quarters of the data has to be physically copied between machines.

The same thing happens when a server dies and N goes from 4 to 3. Almost everything moves.

What we want is a way to place keys so that adding a server moves only the keys that the new server should own, about 1 out of every N + 1. That is consistent hashing.

The ring

Here is the trick. Stop thinking of hash values as a line, and bend the line into a circle. The smallest hash value sits right next to the biggest one. This circle is the ring.

Now do two things with it.

1. Hash each server's name and put the server on the ring at that position.
2. Hash each key and put the key on the ring at that position. The key is owned by the first server you meet when you walk clockwise from the key.

To keep the numbers small, imagine the ring has positions 0 to 99 (a real one is much bigger, usually 0 to 2^64 or more). Say three servers landed here.

Then keys 1 to 25 go to A (the first server at or after them is A at 25). Keys 26 to 50 go to B. Keys 51 to 80 go to C. And keys 81 to 99, plus 0, wrap around the top of the circle and go to A, which is the first server after the wrap.

The picture to keep in your head is a clock face with servers sitting at some of the hours. A key is a person standing somewhere on the clock, walking clockwise until they bump into a server. That server is theirs.

Nobody needs a central table to know this. Every app server just needs the list of server names. They all hash the same names to the same positions, so they all agree.

Adding a node

Now add server D at position 65. Who is affected?

Only keys that sit between the previous server (B at 50) and D (65). Those are keys 51 to 65. They used to walk on to C at 80, but now they bump into D first. Everyone else is untouched.

Out of 100 positions, 15 keys moved, which is 15 percent. Compare that with 75 percent for hash mod N. And notice the direction: keys moved only from C to D. A, B and the rest of C kept everything. The new server takes a slice from one neighbour, nothing else is shuffled.

Removing a node

Say B dies. Its keys 26 to 50 now continue clockwise and bump into the next server, C. Nothing else moves. A's keys stay on A. C's old keys stay on C. C simply gets a larger slice.

This is also why it is called "consistent": when the set of servers changes a little, the mapping of keys changes only a little.

A problem: uneven slices

Look back at our numbers. With A at 25, B at 50 and C at 80, the slices are not equal. A owns 45 positions (81 to 99, then 0 to 25), B owns 25 and C owns 30. A carries almost twice what B does.

That is what happens with random positions, and with only three servers it can be a lot worse. Hash the names of three servers and they might bunch up in one corner of the ring, leaving one server with half of everything.

There is a second, nastier part. When a server dies, all of its load goes to one neighbour. That neighbour now carries its own load plus the dead server's load. If it was already running warm, it may fall over too, and then its neighbour gets double, and so on. People call this a cascade.

Virtual nodes

The fix is to give each real server many positions on the ring, not one. These extra positions are called virtual nodes (or vnodes). Instead of hashing A, you hash A#0, A#1, A#2 and so on, up to maybe 100 or 200 names, and put each of those on the ring. All of them point back to server A.

Think of cutting a cake. If you cut three big slices, they will almost never be equal. If you cut each of the three people's share into 100 tiny pieces and scatter them around the plate, each person ends up with close to a third, because the little differences average out.

Virtual nodes fix both problems.

The load evens out. In the Java run below, with 100 virtual nodes per server and 10,000 keys, the three servers held 3,232, 3,370 and 3,398 keys. Far from perfect, but close to a third each.

A dead server's load is also spread out. Its hundreds of small slices each have a different next neighbour, so the load goes to many servers a little at a time, and no single neighbour is crushed.

You also get a free knob. A bigger machine can have more virtual nodes than a smaller one (300 for a big box and 100 for a small one), so it takes a bigger share. That is the same idea as weights in a load balancer.

The cost is memory and a slightly bigger structure to search, which is tiny. Even 1,000 servers with 200 virtual nodes each is 200,000 entries, which fits easily in memory.

A small Java sketch

A sorted map is exactly the structure you need. TreeMap keeps keys in order, and its ceilingEntry method returns the first entry at or after a given position, which is "walk clockwise to the next server". If there is none, we wrap round to the first entry.

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.*;

public class HashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int virtualNodes;

    public HashRing(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void addNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.put(hash(node + "#" + i), node);
    }

    public void removeNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.remove(hash(node + "#" + i));
    }

    // The first node clockwise from the key's position.
    public String nodeFor(String key) {
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
        return (e != null ? e : ring.firstEntry()).getValue();
    }

    // The owner plus the next distinct nodes clockwise, for replication.
    public List<String> nodesFor(String key, int count) {
        Set<String> found = new LinkedHashSet<>();
        for (String node : ring.tailMap(hash(key)).values()) {
            if (found.size() == count) break;
            found.add(node);
        }
        for (String node : ring.values()) {
            if (found.size() == count) break;
            found.add(node);
        }
        return new ArrayList<>(found);
    }

    private static long hash(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
            return h;
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }
    }
}

A few notes on it. MD5 is fine here because we want a well mixed number, not security. The hash must spread evenly, so do not use Java's String.hashCode(): it is weak for names that look alike, such as A#0 and A#1. The nodesFor method is the replication part, and it skips repeats so that you get distinct real servers, which I explain below.

Using it looks like this.

HashRing ring = new HashRing(100);
for (String n : List.of("A", "B", "C")) ring.addNode(n);

String owner = ring.nodeFor("user:42");
ring.addNode("D");   // only the keys D takes over will change owner

I ran this with 10,000 keys, first on A, B and C and then after adding D. The number of keys that changed owner was 2,448, about 24 percent. The perfect answer is 25 percent (D should take a quarter), and every one of those keys moved to D, none moved between the old servers. Hash mod N moved 7,538 of the same keys.

The sketch leaves out thread safety. In a real client you would build a new ring when the server list changes and swap it in, instead of editing a map that other threads are reading.

Replication to the next nodes

So far each key lives on exactly one server. If that server dies, the key is gone (or at least unavailable). Stores that care about data keep copies.

The ring gives a natural rule. The key belongs to the first server clockwise. Put copies on the next servers after it as well. With a replication factor of 3, a key lives on the first three distinct servers you meet walking clockwise.

key at position 42, replication factor 3
walk clockwise: B (owner), C (copy), A (copy)

Notice the word distinct. With virtual nodes, the next three points on the ring may all belong to the same machine, and three copies on one machine protect you from nothing. So you skip virtual nodes whose machine you already have, which is what nodesFor does above. Real systems go one step further and also skip machines in the same rack or zone.

This has a nice effect. When server B dies, the key at 42 is still on C and A. Reads carry on, and the system can quietly make a new third copy on the next node.

The Amazon Dynamo paper calls the list of servers responsible for a key the preference list, and that is the name you will hear in interviews.

Where it is used

Caches. A group of memcached servers is a classic case. The client library hashes the key on a ring and picks the server, so adding a cache server invalidates only a small part of the cache. This is the original reason the idea was invented.

Dynamo style stores. Dynamo, Cassandra and Riak spread data over nodes with a ring and virtual nodes, and copy each key to the next nodes. Cassandra calls the positions tokens.

Sharded databases. When you split a big table over many machines, the shard key decides where a row goes. A ring lets you add a shard and move only a slice of the data.

Load balancing with affinity. Earlier we saw IP hash breaking when servers change. Using a ring instead keeps most clients on the same server after a change, which is why some load balancers offer a "ring hash" option.

CDNs and object storage use it too, to decide which edge or storage box holds a file.

One honest note: it is not the only way. Redis Cluster does not use a ring. It splits the key space into 16,384 fixed slots and assigns slots to servers, and moving a slot is the unit of rebalancing. The goal is the same, which is moving little data when servers change, but the mechanism is a fixed table. If an interviewer asks, you can say both exist.

Things people get wrong

Using it when you do not need it. If you have one database, or a handful of servers that almost never change, plain hash mod N is fine and simpler. Reach for the ring when the number of servers really does change, or when moving keys is expensive.

Forgetting virtual nodes. A ring with one point per server looks fine in a drawing and is uneven in real life. If you draw a ring in an interview, say "with virtual nodes" in the same breath.

Thinking it solves hot keys. If one key, say a celebrity's profile, gets a million requests, it still lives on one server (plus copies). The ring spreads keys, not the load of a single key. For that you need extra copies of the hot key, or a local cache in front.

Thinking that data moves by itself. In a cache, a moved key is just a miss and fills in again. In a database, someone has to copy the slice to the new server, and that takes time and bandwidth. The ring tells you what moves, it does not do the moving.

Interview talking points

A short script that works: "If I use hash of the key mod the number of servers, adding one server remaps most keys, which would flush the cache or force a huge data move. So I would use consistent hashing. Servers and keys are hashed onto a ring, and a key belongs to the next server clockwise. Adding a server only takes keys from its neighbour, around 1 over N of the total. I would give each server many virtual nodes to even out the load, and replicate each key to the next distinct servers on the ring."

That is about 30 seconds, and it covers the problem, the idea, the fix for uneven load, and the replication.

Interview questions to check yourself

"Why does hash(key) mod N cause trouble when N changes?"

The remainder changes for most keys. Going from 3 to 4 servers, only about a quarter of keys keep their server, so in a cache three quarters become misses at once.

"On a ring, which keys move when you add a server?"

Only the keys between the new server and the previous server on the ring, taken from the next neighbour. About 1 out of N + 1 keys in total.

"Why do we add virtual nodes?"

One point per server gives uneven slices and sends a dead server's whole load to one neighbour. Many points per server even out the load and spread a failure's load around.

"How does a ring give you replication?"

Store each key on the first few distinct servers clockwise from it, such as three. If the owner dies, the next ones still have the data.

"Does consistent hashing fix a hot key?"

No. It spreads keys, but one very popular key still lives on one server and its copies. You need extra copies of that key or a local cache in front.