Step 2 of 14 · 1 min

Why "mod N" moves almost everything

The trouble with hash(key) % N is that the server for each key depends on N. Change N, and most answers change.

Going from 4 to 5 servers: a key stays on the same server only if its hash gives the same remainder when divided by 4 and by 5. Out of every 20 consecutive hash values, only 4 do (0, 1, 2 and 3). So only 20% of keys stay put, and 80% move. Going from 10 to 11, about 91% move. The more servers you have, the worse it gets.

For a cache, "moving" means missing. For a database, it would mean copying 80% of the data between machines just to add one, which makes adding capacity a major event instead of a routine one.

What you want is a scheme where adding one server out of N moves only about 1/N of the keys: just enough to give the new server its fair share, and nothing else.

Step 3 of 14 · 2 min

Consistent hashing

The classic answer, published by Karger and colleagues in 1997, is consistent hashing.

Picture the hash values arranged in a circle, a ring, from 0 up to the maximum and wrapping back around to 0. Now:

1. Hash each server onto the ring, using its name. Each server lands at some point on the circle.
2. Hash each key onto the ring too.
3. A key belongs to the first server clockwise from it.

When you add a server, it lands somewhere on the ring and takes over only the keys between it and the server before it, keys that used to belong to the next server clockwise. Every other key stays exactly where it was. Removing a server is the reverse: only its keys move, to the next server along.

Adding a fifth server to four moves roughly a fifth of the keys, about the minimum possible.

Virtual nodes

There's a catch with the basic version: with only a few servers on the ring, their positions are random, so the gaps between them are uneven. One server might own 40% of the ring while another owns 10%. And when a server is removed, all its keys go to just one neighbour, which might double that neighbour's load at the worst moment.

The fix is to put each server on the ring many times: hash redis-1#0, redis-1#1, … redis-1#199, giving it 200 points instead of 1. These are virtual nodes. With hundreds of small slices each, every server's total share comes out close to even. When a server leaves, its many slices are spread across many different neighbours, so the extra load is shared too.

Virtual nodes also let you give a bigger machine a bigger share, by giving it more points on the ring. Amazon's Dynamo paper (2007), which inspired Cassandra and many others, used exactly this design.

Who uses it

Consistent hashing is everywhere keys must be spread across machines that come and go, without a central list of who owns what: client libraries for cache clusters, load balancers that keep each user on the same backend (lesson 2.2's hashing option), and peer-to-peer and leaderless databases such as Cassandra.

A close cousin, rendezvous hashing (also called highest random weight hashing), skips the ring: for each key, compute a score for every server from hash(key, server), and pick the highest. Adding a server only takes the keys for which it now scores highest, so it has the same "move only 1/N" property, with no ring to manage.

Step 4 of 14 · 1 min

What most databases actually do: fixed logical shards

Consistent hashing is elegant, but most sharded databases use something even simpler, and it's what Chirp chose in lesson 5.1.

Pick a large, fixed number of logical shards up front, many more than you'll ever have machines. Hash each key to one of them. Then keep a small table saying which machine holds which logical shard:

key → hash → logical shard (0 to 4,095) → physical database (via a lookup table)

The number of logical shards never changes, so a key's logical shard never changes either. Adding a database means moving a few logical shards onto it, changing their entries in the table, and nothing else. Each logical shard moves as a whole, and only the shards you choose move.

You'll see this design all over:

• Redis Cluster splits keys into 16,384 hash slots, and each node owns a set of slots.
• Couchbase uses 1,024 vBuckets.
• Vitess, Citus and many in-house systems at large companies use the same idea under various names.

Compared with a consistent-hashing ring, a fixed set of logical shards is easier to reason about (you can list exactly what lives where), lets you move or split individual hot shards deliberately, and makes the plan for each move explicit. The cost is choosing the number up front. Too few, and each logical shard becomes huge and slow to move. Too many, and the lookup table and the per-shard overhead grow. Chirp's 4,096 meant that even at 4,096 databases, each would still hold one logical shard; until then, each database held many.

Splitting by range instead

Databases that partition by range (lesson 5.1) handle growth differently: when a range gets too big or too busy, it splits in two, and one half moves to another machine. Bigtable, HBase, CockroachDB and others do this automatically, so the number of partitions grows with the data rather than being fixed up front.

Step 5 of 14 · 2 min

Moving a shard while it's in use

Whatever scheme you use, adding capacity eventually means copying a shard from one machine to another, while it's still receiving reads and writes. Chirp did this dozens of times in the year after sharding. The steps:

1. Copy a snapshot. Start copying the logical shard's rows to the new database. This can take a while for a big shard, and writes keep arriving at the old one in the meantime.
2. Catch up. Before taking the snapshot, note the current position in the old database's change log. Once the snapshot is copied, replay every change since that position (change data capture, lesson 3.4) onto the new copy, and keep replaying until it's only a fraction of a second behind.
3. Switch. Briefly pause writes to that one logical shard (requests wait, rather than fail). Let the last few changes replay. Update the lookup table so the shard points to the new database. Resume.
4. Verify, then clean up. Compare row counts and checksums between the copies, keep the old copy for a short while just in case, then delete it.

The pause in step 3 is short (Chirp's were typically under 300 ms), and it only affects one logical shard out of 4,096, so almost all users never notice.

Clients with an old map

During and after a move, some app servers may still have the old routing table cached, and send queries for that shard to the old database. The system needs to handle that gracefully:

• The old database refuses writes for a shard it no longer owns, and replies "not mine any more, here's where it went." The client refreshes its map and retries. Redis Cluster works exactly this way, with MOVED and ASK replies.
• Routing tables carry a version number, so a client can tell its map is out of date and fetch a new one.

Without these, a client with a stale map could write to the old copy after the switch, and that write would be silently lost when the old copy is deleted.

Step 6 of 14 · 1 min

Balancing load, not just data

Moving the same number of logical shards to each database balances data. It doesn't necessarily balance load. Remember shard 14 and the cricket commentator (lesson 5.1): one logical shard can be ten times busier than another.

So Chirp tracked load per logical shard (queries per second and CPU time), not just size, and balanced on that. A very hot logical shard could be moved onto a database of its own. Systems that rebalance automatically need the same information. Rebalancing purely by data size can easily make load worse, by pairing two busy shards on the same machine.

And move gradually. Rebalancing copies a lot of data, which uses disk and network on the very databases that are already busy. Moving too much at once can cause the overload you're trying to fix.

Step 7 of 14 · 1 min

What happened to the cache

Back to the cache cluster. Chirp switched its Redis client library to consistent hashing with virtual nodes, and later moved to Redis Cluster's hash slots. The next time the cache grew from 8 servers to 10, about a fifth of keys missed briefly, and the hit ratio dipped from 97% to about 80% for a minute before recovering. The database didn't notice.

Step 8 of 14 · 1 min

From the real world: when one key is too popular for its server

The "balancing load, not just data" section described the problem consistent hashing doesn't solve: it spreads keys evenly, but one key can carry far more load than the others. Vimeo hit this directly, and the fix it adopted is now built into HAProxy.

Vimeo's video packaging servers (which turn stored video into the segments players download) were chosen by consistent hashing on the video. That's great for caching: the same video always goes to the same server, so its pieces stay warm in that server's cache. But when a video got popular, all of its requests went to that one server, which overloaded while others had spare capacity.

In 2016, Google researchers published an algorithm called consistent hashing with bounded loads. The idea is small: choose a cap, say 125% of the current average load per server. Each request goes to its usual server on the ring, unless that server is already at the cap, in which case it moves to the next server clockwise that has room. Most keys never move. Popular keys spill onto a few neighbours, which then cache them too. The paper proves that, with a cap like this, very few keys have to move when servers come and go.

A Vimeo engineer implemented it in HAProxy (the hash-balance-factor setting), and Vimeo reported that it greatly reduced the uneven load on its packaging servers. It's a good pattern to know: keep the stickiness of hashing for cache locality, but put a ceiling on how much any one server can be given.

Step 9 of 14 · 1 min

Going deeper: the minimum number of keys to move

When you add a server to N servers, the new one should end up with 1/(N+1) of the keys. That means at least 1/(N+1) of the keys must move. The question for any placement scheme is how close it gets to that minimum, and what it costs.

• Hash mod N moves N/(N+1) of the keys: going from 4 servers to 5 moves 80% of them. That's what emptied Chirp's cache at the start of this lesson.
• Ring-based consistent hashing moves close to the minimum, with some unevenness that virtual nodes smooth out, at the cost of memory for the ring.
• Rendezvous hashing moves exactly the minimum, but computes a score for every server on every lookup, which is fine for tens of servers and slow for thousands.
• Jump consistent hash, published by Google in 2014, moves exactly the minimum, needs no memory at all, and gives nearly perfect balance. The whole algorithm is a short loop:

int32 jump(uint64 key, int32 num_buckets):
    b = -1; j = 0
    while j < num_buckets:
        b = j
        key = key * 2862933555777941757 + 1
        j = (b + 1) * (2^31 / ((key >> 33) + 1))
    return b

The catch is in its contract: buckets are numbered 0 to N−1, and you can only add or remove the last one. That fits a fixed set of storage shards that grows over time (shard 0, 1, 2, …), where you never remove one from the middle. It doesn't fit a pool of cache servers where any machine can die. So: jump hash for numbered shards, ring or rendezvous hashing (with bounded loads) for pools of machines that come and go.

Step 10 of 14 · 1 min

What Chirp changed

• Cache: replaced hash % N with consistent hashing (200 virtual nodes per server), later with Redis Cluster's slots.
• Databases: kept the fixed 4,096 logical shards from lesson 5.1, with a versioned lookup table.
• Built a shard mover: snapshot, catch up through change data capture, sub-second switch, verify. Moves run one at a time, with a limit on copy speed.
• Old owners refuse writes for shards they've given away and tell the client where to go.
• Track load per logical shard, and balance on load, not just size.

Step 11 of 14 · 1 min

In the simulation

Stage 4 asks you to add database capacity as Chirp grows. If your design maps keys with hash % N, the simulation shows the cost of adding a single machine: a huge copy, or a cache that's suddenly cold. With consistent hashing or logical shards, adding capacity is a small, routine change. The simulation also includes a hot logical shard to see whether you balance by data or by load.

Open the simulation →

Step 12 of 14 · 1 min

If you're here for an interview

Consistent hashing is one of the most-asked topics in system design interviews, often inside "design a distributed cache" or "design a key-value store." Strong answers:

• Explain why hash % N fails when N changes, with the rough fraction that moves.
• Describe the ring: servers and keys hashed onto it, keys going to the next server clockwise, only neighbouring keys moving.
• Add virtual nodes for even balance and to spread a failed node's load.
• Mention fixed logical shards (hash slots) as the common production alternative, and why they're easier to operate.
• Explain how data moves live: copy, catch up, brief switch, and clients with stale maps.

Step 13 of 14 · 2 min

Try these yourself

Step 14 of 14 · 1 min

Further reading

• David Karger et al., "Consistent Hashing and Random Trees," STOC 1997.
• Giuseppe DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store," SOSP 2007, especially the sections on partitioning and virtual nodes.
• Redis documentation, "Scale with Redis Cluster," on hash slots and MOVED and ASK redirections.
• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 6, on rebalancing strategies.
• Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam, "Consistent Hashing with Bounded Loads," SODA 2018 (preprint 2016), and Google's research blog post about it.
• Andrew Rodland, "Improving load balancing with a new consistent-hashing algorithm," Vimeo Engineering blog, 2016; HAProxy documentation for hash-balance-factor.
• John Lamping and Eric Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm," 2014.