Consistent hashing

Gatepass keeps hot booking data in three cache servers. The night before a big sale you add a fourth one for headroom, and the database falls over at 10:00 anyway. Nothing crashed. The new server simply made most of the cache forget where everything was.

This lesson builds the fix, consistent hashing, and lets you run it. You will add and remove servers, count how many keys move, and see why real systems give every server a hundred places on the ring instead of one.

The trouble with hash mod N

The obvious way to spread keys over servers is server = hash(key) % N. It is fast, needs no lookup table and spreads keys evenly. It also has one terrible property: the answer depends on N.

Go from 3 servers to 4 and almost every key lands somewhere new. A key whose hash is 17 lived on server 17 % 3 = 2 and now lives on 17 % 4 = 1. On average only about 1 key in N+1 stays where it was, so going from 3 to 4 servers moves roughly 75% of keys.

For a cache that means a 75% miss rate the moment you scale, which is exactly when you can least afford one. For a database spread over shards it is worse: 75% of your data has to be copied across the network before reads are correct again.

Put servers and keys on a ring

Consistent hashing changes the question. Instead of asking "which of N servers?", it asks "which server comes next?"

1. Take the whole output range of a hash function, 0 to 2³² − 1, and bend it into a circle.
2. Hash each server's name to get its position on the circle. That position is called a token.
3. Hash each key the same way. The key belongs to the first token you meet walking clockwise from it.

Now add server D. It lands at one spot on the ring and takes over only the keys on the arc just before it, which used to belong to the next server along. Every other key keeps its owner. With N servers, adding one moves about 1/(N+1) of the keys, the theoretical minimum, since the new server has to own something.

Removing a server is the mirror image. Its keys slide clockwise to the next server; nobody else notices.

Run it

The ring below holds 300 real booking keys hashed with FNV-1a (plus a mixing step so similar names spread out). Every change is replayed against hash % N on the same keys, so the two numbers at the bottom are a fair fight.

Simulation · consistent hashing

300 bookings on a hash ring

Each dot is a booking key, coloured by the node that owns it: the first node token clockwise from it. Add or remove nodes and watch how few dots change colour. Then turn on virtual nodes.

Look up a key

hash = 0x9cdd22c1 → walk clockwise → node A

Nodes

ABC Add node

Virtual nodes per server

1832128

Keys per node

• A137
• B82
• C81

Thin line: a fair share (100 keys).

Busiest node

1.37× fair share

Last change

–

the share of keys that has to move

Moved on the ring

–

consistent hashing

Moved with hash % N

–

same keys, same change

Try this sequence:

• Add node D. The ring moves roughly a quarter of the keys. hash % N moves around three quarters.
• Remove B. Only B's dots change colour. With hash % N, removing a server from the middle of the list shifts every index after it.
• Look at "Busiest node" with 1 virtual node. One server probably owns far more than its fair share. That is the next problem.

Virtual nodes fix the lumps

With one token per server, the arcs between tokens are random lengths. Three random points on a circle almost never cut it into equal thirds. In the simulation, one server will often hold 40–50% of the keys while another holds 25%. In production that server runs hot, fills up first and pages someone at 3 a.m.

The fix is to give every server many tokens, called virtual nodes. Server A hashes A#0, A#1, … A#127 and appears at 128 places on the ring. Each server's share is now the sum of many small random arcs, and sums of many random pieces are very close to their average. Switch the simulation to 128 virtual nodes and the bars line up near the fair-share line.

Virtual nodes buy two more things:

• Smoother failure. When a server with one token dies, one neighbour inherits its whole load and may tip over next. With 128 tokens, its load is spread across all the survivors.
• Weights. A server with twice the memory gets twice the tokens. Capacity planning becomes a number in a config file.

The cost is a bigger routing table (servers × tokens entries, still tiny) and a binary search per lookup, which takes nanoseconds.

Check yourself

Gatepass runs 4 cache servers with 1 token each. One server holds 45% of keys. What is the most direct fix?

ASwitch to hash mod N, which spreads keys evenlyBGive each server many virtual nodes on the ringCAdd a fifth serverDUse a longer hash, like SHA-256 instead of 32 bits

Where you will meet it

Consistent hashing sits under a lot of systems you already use:

• Amazon Dynamo, Cassandra and Riak place data on a token ring. To keep 3 copies, a key is stored on the first 3 distinct servers clockwise from it, a list Dynamo calls the preference list. Cassandra assigns each node many tokens (256 by default for years, fewer with its newer allocator).
• Memcached and Redis clients use it to pick a cache server, so adding a server only cools a slice of the cache. The classic "ketama" library did exactly this with 100–200 points per server.
• Load balancers such as Envoy's ring-hash and Google's Maglev use variants of it to keep a user's requests on the same backend while the backend pool changes.
• Gatepass can lean on it in two places you have already met: picking which cache server holds a booking (the Caching module), and deciding which partition owns a key so that adding a node is cheap (the Rebalancing lesson).

Where it still hurts

Consistent hashing spreads keys evenly, not traffic. If one event page gets half of all reads, its key lives on one server no matter how many tokens you add. Hot keys need a separate fix: replicate the hot key, cache it locally in each app server, or add a random suffix and spread copies.

Two other limits are worth knowing:

• Data still has to move. A quarter of the keys moving is better than three quarters, but in a database that might be terabytes. Systems stream that data in the background and keep serving reads from the old owner until the copy is done.
• Everyone must agree on the ring. If two app servers have different views of membership, they send the same key to different places. Real systems spread ring changes with a coordination service or a gossip protocol.

Check yourself

A ring with 9 servers and plenty of virtual nodes gets a 10th server. Roughly what share of keys moves?

AAbout 10%BAbout 50%CAbout 90%DNone, until the cache expires

Key takeaways

• hash % N balances well but moves almost every key when N changes. For a cache that is an instant stampede.
• On a ring, a key belongs to the next server clockwise, so adding or removing a server moves only about 1/N of the keys.
• One token per server gives lumpy load. Many virtual nodes per server even it out, spread failover load and let you weight bigger machines.
• It balances keys, not traffic. Hot keys and data copying still need their own plans.