Design Consistent Hashing

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 5 — rewritten and condensed for teaching.

Horizontal scaling only works if requests and data are spread evenly across servers, and if the spread doesn't fall apart when servers come and go. Lesson 1 sharded users with user_id % 4 and promised that resharding would be handled by consistent hashing. This lesson delivers on that promise.

What you'll be able to do after this lesson:

• Explain why hash(key) % N causes a storm of cache misses when N changes.
• Place servers and keys on a hash ring and look up a key's server by walking clockwise.
• Use virtual nodes to fix uneven partitions and skewed load.
• Identify exactly which keys move when a server is added or removed.

---

The Rehashing Problem

With N cache servers, the obvious way to balance load is:

serverIndex = hash(key) % N

Take 4 servers and 8 keys:

Key	hash(key)	hash % 4	hash % 3 (after server 1 leaves)	Moved?
key0	18358617	1	0	yes
key1	26143584	0	0
key2	18131146	2	1	yes
key3	35863496	0	2	yes
key4	34085809	1	1
key5	27581703	3	0	yes
key6	38164978	2	1	yes
key7	22530351	3	0	yes

With a fixed pool and evenly spread data, this works well: key0 hashes to 18358617, 18358617 % 4 = 1, so clients fetch it from server 1.

Now server 1 goes offline and N becomes 3. Every key keeps the same hash, but % 3 gives a different index for most of them. Six of eight keys move, not just the two (key0, key4) that lived on the failed server. Most clients now look for their data on the wrong server, and the cache suffers a storm of misses that falls through to the database all at once.

flowchart LR
  subgraph Before["N = 4"]
    direction TB
    A0["server 0: key1, key3"]
    A1["server 1: key0, key4"]
    A2["server 2: key2, key6"]
    A3["server 3: key5, key7"]
  end
  subgraph After["N = 3 (server 1 removed, indexes 0–2)"]
    direction TB
    B0["index 0: key0, key1, key5, key7"]
    B1["index 1: key2, key4, key6"]
    B2["index 2: key3"]
  end
  Before --> After

In general, going from N to N + 1 servers with modulo hashing moves about N/(N + 1) of all keys. That is close to all of them. The Rebalancing and Request Routing lesson measures this churn in detail.

Practice: measure modulo churn

Implement moved_keys(hashes, old_n, new_n). It returns the indexes of keys whose server changes when the pool goes from old_n to new_n servers under hash % N.

Input: line 1 is old_n new_n, and line 2 is the key hashes. The wrapper prints the moved indexes and the count.

Adding just one server to four (the second test) moved 16 of 20 keys, which is 80%, exactly the N/(N + 1) = 4/5 predicted above. The goal of consistent hashing is to bring that down to about 1/N.

---

Consistent Hashing

Wikipedia's definition, paraphrased: with consistent hashing, resizing the table remaps only k/n keys on average (k keys, n slots). A traditional hash table remaps nearly all of them.

The hash space and the ring

Take a hash function such as SHA-1, whose outputs range from 0 to 2¹⁶⁰ − 1. Lay that range out as a line, then join the two ends. The result is a hash ring: a value just past 2¹⁶⁰ − 1 wraps around to 0.

Placing servers and keys

1. Hash each server (by IP address or name) with the same function. Each server lands at a position on the ring.
2. Hash each key onto the same ring. There is no modulo step. The key's position is simply its hash.
3. Lookup: starting from the key's position, walk clockwise until you reach a server. That server owns the key.

The figure below uses a toy ring with positions 0–99. Servers are squares and keys are circles:

Toy hash ring (positions 0–99). Each key belongs to the first server clockwise from it.

Key (position)	Walk clockwise to…	Owner
k0 (5)	15	s0
k1 (30)	40	s1
k2 (55)	65	s2
k3 (80)	90	s3

Adding a server

Add s4 at position 10. Walking clockwise from k0 (5), the first server is now s4, so only k0 moves (s0 → s4). k1, k2, and k3 still reach the same servers as before.

Removing a server

Remove s1. k1 (30) now walks past the empty spot at 40 and stops at s2 (65), so only k1 moves (s1 → s2). Every other key is unaffected.

Practice: ring lookup

Implement lookup(servers, key_pos) on a ring of positions 0–99. servers maps names to positions. Return the server at the smallest position ≥ key_pos. If there is none, wrap around to the server with the smallest position overall.

Input: line 1 is name:position pairs, and line 2 is key positions. The wrapper prints the owner of each key.

---

Two Problems With the Basic Ring

The original algorithm, from Karger et al. at MIT, comes down to two steps: map servers and keys onto the ring with a uniformly distributed hash, and assign each key to the first server clockwise. That leaves two problems:

1. Uneven partitions. A partition is the stretch of ring between a server and the server before it, and its owner receives every key that hashes into it. As servers join and leave, partitions can't stay equal in size. In the toy ring, removing s1 doubles s2's partition, from 40–65 to 15–65, so s2 now covers twice as much ring as s0 or s3.
2. Uneven key distribution. Even with fixed servers, random placement can bunch them together. If s0, s1, and s3 happen to land close together, most of the ring belongs to s2. s2 then holds most of the data while some servers hold almost none.

The fix for both is virtual nodes.

Check: rehashing and the ring

Quiz

Rehashing vs. the ring

1 / 3

With hash % N, one of 4 cache servers fails. Why does the database suddenly get hammered?

Pick an answer to see if you are right.

---

Virtual Nodes

Instead of putting each physical server on the ring once, put it on many times. Each copy is a virtual node (or replica) that points back to the real server. For example, server 0 might appear as s0_0, s0_1, s0_2, and server 1 as s1_0, s1_1, s1_2. Real systems use far more than three each.

• Each server now owns many small partitions scattered around the ring, rather than one large one.
• Lookup is unchanged: walk clockwise from the key to the first virtual node, then map it to its physical server. A key that reaches s1_1 lives on server 1.

flowchart LR
  K0((k0)) -- clockwise --> V11["s1_1"] --> S1[Server 1]
  V00["s0_0"] & V01["s0_1"] & V02["s0_2"] --> S0[Server 0]
  V10["s1_0"] & V11 & V12["s1_2"] --> S1

Why it works: each server's share of the ring is now the sum of many random slices, and sums of many random pieces vary much less than a single piece does. The standard deviation of load shrinks as virtual nodes increase. One published experiment found it was about 10% of the mean with 100 virtual nodes and about 5% with 200.

The trade-off: more virtual nodes give better balance but need more memory for the ring's metadata. Tune the count to fit your system.

Practice: a ring with virtual nodes

Build a HashRing with virtual nodes. Use the provided h32 hash (MD5 reduced to 32 bits) and name each virtual node f"{server}#{i}" for i in range(vnodes).

• add(server) inserts that server's virtual nodes.
• remove(server) deletes them.
• get(key) returns the physical server of the first virtual node clockwise from h32(key), wrapping around at the end. A key hashing exactly onto a virtual node belongs to that node.

The wrapper builds a ring of 4 servers, assigns 1,000 keys, and prints how many each server holds. It then adds a 5th server and reports how many keys moved, and whether every moved key went to the new server.

Input is one line: the number of virtual nodes per server.

Compare the outputs:

• Balance. With 1 virtual node, s2 holds just 156 keys while s1 holds 307. With 200, every server is within about 7% of the ideal 250.
• Minimal movement. The ideal share for a new 5th server is 1/5 of 1,000, or 200 keys, and the many-vnode rings move close to that. Modulo hashing would move about 4/5 of them, roughly 800 of 1,000, as the first exercise showed on a small scale. In every case, the only keys that move are the ones s4 takes over.

---

Finding the Affected Keys

When a server joins or leaves, which keys need to move?

• Server added (s4): start at s4 and walk counter-clockwise until you hit the previous server (s3). Keys in (s3, s4] move to s4. Nothing else changes.
• Server removed (s1): start at s1 and walk counter-clockwise until you hit the previous server (s0). Keys in (s0, s1] move to the next server clockwise, s2.

In the toy ring: adding s4 at 10 affects positions 91–99 and 0–10 (the wrap from s3 at 90), which holds only k0. Removing s1 affects positions 16–40, which holds only k1, and those keys go to s2.

With virtual nodes the same rule applies once per virtual node, so a joining server takes small slices from many servers. The load of a rebalance is spread out instead of landing on one neighbor.

Check: virtual nodes and affected ranges

Quiz

Virtual nodes and rebalancing

1 / 3

Why does giving each server 200 virtual nodes balance load better than 1?

Pick an answer to see if you are right.

---

Wrap Up

Benefits of consistent hashing:

• Minimal key movement when servers are added or removed.
• Easier horizontal scaling, because data spreads evenly.
• Less hotspot pressure. Recall Lesson 1's celebrity problem: if Katy Perry, Justin Bieber, and Lady Gaga all landed on one shard, it would be overwhelmed. A more even spread reduces the chance of hot keys piling up together. A single extremely hot key still needs extra measures such as replication or splitting that key.

Consistent hashing in production:

• The partitioning component of Amazon's Dynamo
• Data partitioning in Apache Cassandra
• Discord's chat application
• The Akamai content delivery network
• Google's Maglev network load balancer

Related lessons: Partitioning of Key-Value Data, Rebalancing and Request Routing, and Sharded Services.

---

Key Takeaways

• hash % N remaps nearly every key when N changes, causing a cache-miss storm.
• A hash ring maps servers and keys into the same space. A key belongs to the first server clockwise, and a membership change moves only about 1/N of the keys.
• The basic ring suffers from uneven partitions and skewed load. Virtual nodes fix both, at the cost of more metadata.
• The keys affected by a change are the range from the changed node counter-clockwise to the previous node.

Previous lesson: Design a Rate Limiter.

Next lesson: Design a Key-Value Store — consistent hashing put to work: replication, quorums, vector clocks, failure handling, and Cassandra-style read/write paths.

---

Reference Materials

1. Consistent hashing — Wikipedia
2. Consistent Hashing — Tom White
3. Dynamo: Amazon's Highly Available Key-value Store
4. Cassandra — A Decentralized Structured Storage System
5. How Discord Scaled Elixir to 5,000,000 Concurrent Users
6. CS168: The Modern Algorithmic Toolbox, Lecture #1: Introduction and Consistent Hashing — Stanford
7. Maglev: A Fast and Reliable Software Network Load Balancer — Google