important senior · part of Skills & Topics · Senior SWE Roadmap · related: Caching Strategies · Database Sharding & Replication · Design a Distributed Cache · question form: Design Consistent Hashing
The problem: naive modulo hashing
The obvious way to distribute keys across N servers is server = hash(key) % N. This works fine as long as N never changes — the problem is that in any real system, servers get added (scaling up, or replacing a failed one) or removed (scaling down, a crash), and the moment N changes, % N changes for almost every key at once.
Worked example. Four servers, S0–S3, eight keys with these (illustrative) hash values:
| Key | hash(key) | % 4 → server (N=4) |
|---|---|---|
| k1 | 23 | 3 → S3 |
| k2 | 48 | 0 → S0 |
| k3 | 61 | 1 → S1 |
| k4 | 77 | 1 → S1 |
| k5 | 94 | 2 → S2 |
| k6 | 118 | 2 → S2 |
| k7 | 142 | 2 → S2 |
| k8 | 169 | 1 → S1 |
Now add a fifth server, S4, to handle more load — everyone recomputes % 5:
| Key | hash(key) | % 5 → server (N=5) | Changed? |
|---|---|---|---|
| k1 | 23 | 3 → S3 | same |
| k2 | 48 | 3 → S3 | moved |
| k3 | 61 | 1 → S1 | same |
| k4 | 77 | 2 → S2 | moved |
| k5 | 94 | 4 → S4 | moved |
| k6 | 118 | 3 → S3 | moved |
| k7 | 142 | 2 → S2 | same |
| k8 | 169 | 4 → S4 | moved |
Five of eight keys (62.5%) now map to a different server, despite only one server being added. For a sharded database this means a massive, mostly-unnecessary data migration; for a cache it means a near-total cache wipe — every one of those keys now misses on the “wrong” server and has to be refetched from the source of truth, often all at once (compounding into the cache-stampede problem — see Caching Strategies). This gets worse, not better, as N grows: the fraction of keys that move on a %N → %(N+1) change trends toward “almost everything.”
flowchart TD subgraph Before["4 servers — hash(key) % 4"] S0["S0"] S1["S1"] S2["S2"] S3["S3"] end subgraph After["5 servers — hash(key) % 5"] T0["S0"] T1["S1"] T2["S2"] T3["S3"] T4["S4"] end S3 -.->|"k1: unchanged"| T3 S0 -.->|"k2: S0→S3"| T3 S1 -.->|"k3: unchanged"| T1 S1 -.->|"k4: S1→S2"| T2 S2 -.->|"k5: S2→S4"| T4 S2 -.->|"k6: S2→S3"| T3 S2 -.->|"k7: unchanged"| T2 S1 -.->|"k8: S1→S4"| T4
Consistent hashing exists specifically to make “add or remove a node” cheap by bounding how many keys move, instead of scrambling the whole keyspace.
The hash ring mechanism
Instead of hashing into a fixed-size % N space, consistent hashing hashes into a large, fixed, N-independent space — typically visualized as a ring of values from 0 to 2^32 - 1 (or 2^160 - 1 for SHA-1). Both servers and keys are hashed into this same space:
- Hash each server’s identifier (e.g., its hostname or IP) to get its position on the ring.
- Hash each key the same way to get its position on the ring.
- A key belongs to the first server found walking clockwise from the key’s position.
flowchart LR K1["key1 @ 12"] -.->|"walk clockwise →"| A["Node A @ 20"] K2["key2 @ 45"] -.->|"walk clockwise →"| B["Node B @ 50"] K3["key3 @ 55"] -.->|"walk clockwise →"| C["Node C @ 80"] K4["key4 @ 95"] -.->|"walk clockwise, wraps past 99 → 0 →"| A A --> B --> C --> A
Node A owns every key whose position falls in (C, A] going clockwise (including the wraparound past the top of the ring back to 0) — here that’s key1 (12) and key4 (95, which wraps). Node B owns (A, B] — key2 (45). Node C owns (B, C] — key3 (55). Lookup is O(log N) with the server positions kept in a sorted structure (binary search for “smallest position ≥ key’s position”).
Adding a node — only the adjacent range remaps
This is the payoff, and it’s worth walking the numbers to see exactly why it’s so much cheaper than the modulo case.
Ring positions 0–99. Three nodes: A @ 10, B @ 40, C @ 75. Six keys: k1@5, k2@25, k3@50, k4@60, k5@85, k6@95.
flowchart LR A["Node A @ 10<br/>owns (75,10] = k1(5), k5(85), k6(95)"] --> B["Node B @ 40<br/>owns (10,40] = k2(25)"] B --> C["Node C @ 75<br/>owns (40,75] = k3(50), k4(60)"] C --> A
Now add a fourth node, D @ 55, between B and C:
flowchart LR A2["Node A @ 10<br/>owns (75,10] = k1, k5, k6 — UNCHANGED"] --> B2["Node B @ 40<br/>owns (10,40] = k2 — UNCHANGED"] B2 --> D["Node D @ 55 (NEW)<br/>owns (40,55] = k3 — MOVED here from C"] D --> C2["Node C @ 75<br/>owns (55,75] = k4 — UNCHANGED"] C2 --> A2
Only k3 (position 50, which now falls before D at 55 instead of continuing on to C at 75) moves. One key out of six — about 17% — versus 62.5% in the modulo example for a comparable single-node change, and critically, the fraction that moves only gets smaller as the cluster grows, because it’s always bounded to the arc between the new node and its immediate predecessor, not the whole ring. This is the concrete mechanism behind the “adding/removing one node only affects ~1/N of the keys” claim: exactly one node’s worth of range shifts, everyone else is untouched.
Removing a node is the mirror image: its entire arc gets absorbed by its immediate clockwise neighbor, and every other node’s ownership is unaffected.
Virtual nodes
There’s a gap in the story above: server positions come from hashing a server identifier, which places them at essentially random points on the ring. With only a handful of real servers, random placement is often not evenly spaced — some node ends up owning a tiny arc, another ends up owning most of the ring, purely by chance of where the hash landed.
flowchart LR A["Node A @ pos 10<br/>owns 91–99, 0–10<br/>(20% of ring)"] --> B["Node B @ pos 15<br/>owns 11–15<br/>(5% of ring — underloaded)"] B --> C["Node C @ pos 90<br/>owns 16–90<br/>(75% of ring — overloaded)"] C --> A
Three nodes, “fair share” would be ~33% each, but node C ends up with 75% of the keyspace just because of where its hash happened to land relative to A and B. This gets worse with fewer nodes (small clusters are exactly where this bites hardest) and doesn’t reliably fix itself by adding more real servers, since each new server is just one more random point.
The fix: give each physical server many points on the ring instead of one — hash serverA-0, serverA-1, … serverA-149 (commonly 100–200 virtual nodes per physical node) and place all of them. A physical node’s total load is now the sum of many small, independently-random arcs instead of one single large-or-small arc — by the law of large numbers, that sum concentrates much closer to the mean as the virtual-node count grows, so load balances out across physical nodes.
flowchart LR A1["A-v1 @ 8"] --> B1["B-v1 @ 15"] --> C1["C-v1 @ 22"] --> A2["A-v2 @ 30"] --> C2["C-v2 @ 38"] --> B2["B-v2 @ 47"] --> A3["A-v3 @ 55"] --> C3["C-v3 @ 63"] --> B3["B-v3 @ 71"] --> A4["A-v4 @ 80"] --> C4["C-v4 @ 88"] --> B4["B-v4 @ 95"] --> A1
With virtual points interleaved around the ring, each physical node (A, B, C) ends up owning several small, scattered arcs whose total length converges toward roughly 1/3 of the ring each — instead of one node accidentally owning 75%. Virtual nodes also make adding/removing a physical server smoother: instead of one large chunk of keys moving to/from a single neighbor, the change is spread across many small chunks distributed among many different existing nodes.
Bounded-load and weighted variants
Two refinements worth knowing exist, even briefly:
- Weighted consistent hashing: not all nodes are equal — a server with 2x the RAM/CPU of another should handle roughly 2x the load. Give it 2x as many virtual nodes, and it ends up owning roughly 2x the arc, proportionally. This is how heterogeneous-capacity clusters (common after incremental hardware upgrades) stay balanced without a separate load-balancing mechanism.
- Bounded-load consistent hashing: even with plenty of virtual nodes, statistical balance is an average-case guarantee — a burst of traffic skewed toward a specific key range can still overload a specific node in the short term. Google’s “Consistent Hashing with Bounded Loads” approach caps how far any node’s load can exceed the cluster average (e.g., no more than 1.25x average); once a node hits that cap, the next key that would have landed on it instead continues clockwise to the following node. Used in systems like Envoy and Vimeo’s request routing where short-term load spikes, not just steady-state distribution, matter.
Real-world usage
| System | How it uses consistent hashing |
|---|---|
| DynamoDB | Core partitioning mechanism inherited from the original Dynamo paper — a ring of token ranges assigned to storage nodes, with virtual nodes to smooth load across heterogeneous hardware and to spread the impact of a node’s data across many peers when it’s added or fails. |
| Cassandra | Same Dynamo-derived ring model — each node owns one or more token ranges; virtual nodes (vnodes, default in modern versions) improve balance and dramatically speed up bootstrap/repair by spreading a joining/leaving node’s data across many existing nodes instead of one or two neighbors. |
| Memcached (client-side) | Memcached servers are unaware of each other — there’s no server-side ring at all. The client library (e.g., libketama) hashes both keys and the list of server addresses onto a ring, so adding or removing a memcached server from the client’s config only remaps ~1/N of keys instead of invalidating the entire cache. |
Interview angles
- “Design Consistent Hashing” is itself a standalone interview question (see Design Consistent Hashing) — be ready to derive the ring + virtual nodes mechanism from scratch on a whiteboard, including working a small numeric example, not just naming it.
- “Why not just use
hash(key) % N?” → walk through the concrete remap-percentage numbers (worked example above) rather than asserting “it doesn’t scale.” - “What happens when you add a node?” → only the arc between the new node and its predecessor remaps; state the bound explicitly (~1/N of keys) and explain why that bound holds (the ring structure, not luck).
- “With only a few nodes, is the load actually balanced?” → no, not without virtual nodes — this is the follow-up that separates a memorized answer from an understood one; explain the random-arc-length problem and how summing many virtual arcs fixes it.
- Comes up as a load-bearing component whenever you’re sharding a cache or a distributed store — e.g. Design a Distributed Cache, Design a Key-Value Store (DynamoDB-like) — mention it proactively as the mechanism behind “add a node without a full resharding storm,” rather than waiting to be asked.
- “What if node capacities aren’t equal?” → weighted virtual node counts; “what if load is bursty, not just unevenly distributed?” → bounded-load consistent hashing — both are good “I know there’s more depth here” signals even in a two-sentence mention.