Consistent Hashing

You have three cache nodes. Keys go to hash(key) % 3. You add a fourth node. Almost every key’s remainder changes. Yesterday’s warm entries sit on the wrong boxes. Today every GET misses. The cache is cold. The database is on fire.

The main design question is:

How do we add or remove a cache node without moving nearly every key?

This is the partitioning chapter of Design a Distributed Cache, pulled out so you can practice it alone. Walk a live ring in the Consistent Hashing Visualizer while you read — add a node and watch which keys actually move.

We will start with three boxes and modulo. The ring appears only after that placement rule fails.

1. Clarify what we are partitioning

“Explain consistent hashing” can mean a cache fleet, a user-sharded database, a request router, or a gossip membership protocol. The ring is the same idea. The object on the ring is not.

I would ask one question at a time:

• Are we placing cache keys, users, tenants, or database rows?
• Is the data disposable (a cache) or the source of truth (a shard)?
• How many physical nodes today, and how often does membership change?
• Must a key have replicas, or is a miss acceptable?
• Do clients talk to nodes directly, or through a proxy?
• Are nodes equal, or do some boxes have more RAM?

If the interviewer gives no extra constraints, I would state:

Object on the ring     Cache keys (opaque strings)
Nodes                  Equal-capacity in-memory cache boxes
Source of truth        Product DB; cache is derived and disposable
Operations             GET, PUT, DELETE on one key
Membership             Nodes join and leave during traffic
Replicas               Optional; start with 1, then R = 2
Lookup                 Client library, not a hop through every node
Excluded               Range scans, multi-key transactions, SQL

The rest of this walkthrough partitions cache keys. The same ring can place users onto application shards. It is a weaker fit for “all orders for user 100–200” — that is range sharding, and we contrast it after the ring is solid.

If the data is the source of truth, a remap is a migration. If it is a cache, a remap is a miss storm. Both hurt. The recovery story is different.

2. Requirements

The interviewer is not asking you to recite a circle. They want a placement function that survives membership change.

Functional requirements

The system must:

1. Map every key to exactly one primary owner at a given membership.
2. Keep that mapping stable when unrelated nodes join or leave.
3. Move only the keys that the new (or dead) node should own.
4. Balance keys across equal-capacity nodes, within a measured skew.
5. Answer “who owns this key?” in well under a millisecond on the client.
6. Optionally place R replicas on distinct physical nodes.

Out of scope for v1: global LRU, range queries, two-key transactions, and spreading one celebrity key.

Non-functional goals

Remap on +1 node     about 1/(N+1) of keys, not ~N/(N+1)
Remap on -1 node     about 1/N of keys (the dead node's slice)
Lookup               O(log V) on the client, no extra network hop
Balance              no node stuck with a huge idle arc
Failure              one node death is a slice miss, not a full flush
Operability          membership can change without a synchronized restart

V is the number of virtual nodes — we need those after one point per box proves lumpy.

Assumptions and edge cases

Hash function     good 32-bit or 128-bit mix; not "first 4 chars"
Nodes             fail independently; start in one region
Clients           may hold a slightly stale membership map
Retention         cache entries are evictable; DB can refill

Name before drawing: add/remove during traffic, planned drain vs crash, two clients on different epochs, a celebrity key, an empty new node, and a dead control plane.

3. Scale, and why this matters

Use round numbers that make the incident visible.

Keys in cache                 100 million
Average value                 1 KB
Working set in RAM            on the order of 100 GB plus overhead
Physical cache nodes          3 today, growing to 4
Peak GET rate                 2 million / second
Hit rate when warm            ~90%
Product DB comfortable load   a few hundred thousand QPS, not millions

Three nodes hold the working set. Hit rate 90% means the database sees about 200,000 QPS of misses — painful, survivable.

Now add a fourth node because RAM or CPU is tight. If placement is hash % N, roughly three quarters of keys change owner. Those keys are still in RAM — on the wrong node. The new mapping does not know that.

Warm cluster, N = 3
  2,000,000 GET/s × 10% miss → ~200,000 DB QPS

After hash % 4, ~75% of keys "vanish"
  2,000,000 GET/s × ~80% miss → ~1,600,000 DB QPS

The cache did not lose its memory. It lost its addresses. Product DB absorbs a miss storm that looks like a launch-day outage.

If placement is a ring, adding the fourth node should move about 1/4 of keys. The database sees a bump on that slice, then the new node warms. That is an operational event. A full remap is a self-inflicted outage.

A cache key can die. The database cannot absorb every key dying at once. Minimize remaps to protect the source of truth, not because cache bytes are precious. Membership change is normal; the placement function has to treat it that way.

4. The % N problem

Start with the design everyone reaches for:

owner = hash(key) % N

While N is 3, this is fine. Keys spread. Lookups are one modulo. Then N becomes 4.

Work a small catalog. The “hash” column is the integer the hash function returned — we pick easy numbers so the remainders are visible. A real hash is large and messy; the remainder math is the same.

N = 3 nodes: n0, n1, n2
N = 4 nodes: n0, n1, n2, n3

Six of eight keys changed owner. That is 75%.

Why that fraction? A key stays only when hash % 3 == hash % 4. For a uniform hash those remainders agree about 1/4 of the time, so about 3/4 move.

In general, when N grows by one:

expected keys that move   ≈  N / (N + 1)
expected keys that stay   ≈  1 / (N + 1)

Three nodes to four: ~75% move. Ninety-nine to one hundred: still ~99% move. Adding capacity does not save you. A lookup table of “node 0 is host A” does not either — the index changed. Host A still has cart:alice in RAM; the client now asks host B.

Keys and nodes must live in a space that does not depend on N.

5. The ring: map nodes and keys, first clockwise owner

Fix a large integer circle — in production, 0 .. 2^32-1 or a 128-bit space. In this article we use 0 .. 99 so a diagram fits on a page. The rule does not change.

Hash nodes onto the circle (hash the node id, or assign positions). Hash keys onto the same circle. A key belongs to the first node clockwise from its point. If you walk off 99, you wrap to 0.

That clockwise successor is the owner.

                    0
                    n1
                    ●
               95         5  order:3
             .               .
           .                   .
     85  user:bob               10  product:p_42
           .                   .
             .               .
               .           .
        72                   28
      sku:100               product:p_7
             .           .
               .       .
         70 ●             ● 35
           n3             n2
               .       .
                 .   .
              60       40
           feed:home  cart:alice
                 .   .
                   ●
                  55
              session:s9

Walk clockwise from n1 at 0. Keys just after 0 do not belong to n1 — they walk forward to n2. order:3 (5), product:p_42 (10), and product:p_7 (28) stop at n2 (35). cart:alice (40), session:s9 (55), and feed:home (60) have passed n2 and stop at n3 (70). sku:100 (72) and user:bob (85) have passed n3; the next node wraps to n1 at 0.

Each node owns the arc from the previous node (exclusive) to itself (inclusive):

n2 owns  ( 0, 35]   →  order:3, product:p_42, product:p_7
n3 owns  (35, 70]   →  cart:alice, session:s9, feed:home
n1 owns  (70, 99] ∪ {0}  →  sku:100, user:bob

The hash of a key never mentions N. Adding a node inserts a new point. Removing a node deletes a point. Unrelated arcs do not move.

Play the same placements in the visualizer — amber keys, next clockwise owner.

6. Add a node: only one arc is stolen

Capacity is tight. We add n4 at position 20.

                    0
                    n1
                    ●
               95         5  order:3
             .               .
           .                   .
     85  user:bob               10  product:p_42
           .                   .
             .               ● 20
               .            n4
        72                   28
      sku:100               product:p_7
             .           .
               .       .
         70 ●             ● 35
           n3             n2
               .       .
                 .   .
              60       40
           feed:home  cart:alice

What changed?

n4 sits on the arc that used to end at n2. Keys on (0, 20] now stop at n4 instead of walking to 35.

Before add                         After add

n2 owns ( 0, 35]                   n4 owns ( 0, 20]
                                   n2 owns (20, 35]
n3 owns (35, 70]                   n3 owns (35, 70]   unchanged
n1 owns (70, 99] ∪ {0}             n1 owns (70, 99] ∪ {0}  unchanged

Two of eight keys move. That is 25% — about 1/(N+1) with N = 3. The other six still hit a warm box.

Expected keys that move when adding 1 node  ≈  1 / (N + 1)

One hundred nodes, add one: on the order of 1% of keys rematerialize, not 99%.

n4 owns product:p_42 but is empty. First GETs miss and refill from Product DB (or, in a store, copy from n2). n2 still has the bytes until clients pick up the new map. Caches often skip the copy and accept lazy fill. Databases usually cannot.

7. Remove a node

Planned removal and a crash use the same placement rule. The traffic story differs.

Remove n2 from the original three-node ring (no n4 yet). Every key that walked to 35 now keeps walking to n3 at 70.

                    0
                    n1
                    ●
               95         5  order:3
             .               .
     85  user:bob               10  product:p_42
           .                   .
        72                       28  product:p_7
      sku:100                      .
             .                   .
               .               .
         70 ●                 (n2 gone)
           n3
               .       .
              60       40
           feed:home  cart:alice

Before remove                      After remove

n2 owns ( 0, 35]                   (gone — arc merges into n3)
n3 owns (35, 70]                   n3 owns ( 0, 70]
n1 owns (70, 99] ∪ {0}             n1 owns (70, 99] ∪ {0}  unchanged

Three of eight keys move — n2’s entire slice, about 1/N.

Expected keys that move when removing 1 node  ≈  1 / N

Planned drain: stop new writes to n2, let n3 take the arc, optionally copy hot keys, then drop n2 from the map. Crash: no copy. Every GET for n2’s keys misses unless you already have replicas (section 9). n3 owns twice the arc and a refill spike. One physical point per node dumps the whole failure on one neighbor. n1 did not move.

8. Virtual nodes: one point is a bad lottery

The three-node ring above looks fair because we placed n1, n2, and n3 35 units apart. Real hash positions are not equally spaced.

Give each box one random point and you will eventually draw this:

     n1 ●                                 ● n2
        |                                 |
        |<---------- huge arc ----------->|
        |                                 |
                         n3 ●  (tiny arc)

n2 owns most of the circle. It runs hot. n3 sits idle. The hash function is not broken: a handful of random points on a circle cluster. Even at N = 100, one unlucky node can own a double share.

Give each physical box many points. Those points are virtual nodes (tokens).

Physical n1  →  n1-v0, n1-v1, n1-v2, ...  n1-v199
Physical n2  →  n2-v0, n2-v1, ...
Physical n3  →  n3-v0, n3-v1, ...

Each virtual node owns a small arc. A physical node’s load is the sum of its tokens. Sums of many small random pieces concentrate around the mean.

        n2-v1 ●
               \
    n1-v0 ●     \      ● n3-v0
           \     \    /
            \     \  /
    n3-v1 ●--\-----●---● n1-v1
              \   n2-v0
               \
                ● n1-v2

product:p_42 hashes to a point, walks to the first virtual node clockwise, then uses that token’s physical owner.

How many? A common interview range is 100–200 virtual nodes per physical server. Too few and arcs stay lumpy. Too many and the placement map is large. Measure max load / mean load on a real key sample; do not worship 200. Weighted nodes get more tokens if they have more tested capacity — advertised RAM is a weak weight.

Failure spreads. This is the second reason virtual nodes exist.

Without them, n2 dies and one neighbor inherits the entire slice. With 200 tokens, each small arc goes to a different clockwise neighbor. The miss storm spreads.

n2 dies, one point     n3 takes 100% of n2  →  n3 is the new outage
n2 dies, 200 vnodes    n1, n3, n4 each take some tokens

Open the visualizer, set virtual nodes to 1, then raise the count. Load flattens. Remove a node and watch stolen keys spray outward instead of piling on one neighbor.

9. Replication clockwise

A cache is disposable. A node crash is still a miss storm into Product DB. If n2 held a quarter of the hot keys, the database sees a quarter-traffic spike plus reconnects.

Place extra copies on the ring. The usual interview rule: store the key on the primary owner and the next R − 1 distinct physical nodes clockwise. Skip other virtual nodes that hash back to the same box. Skip the same rack or zone if the map has topology.

R = 2, key product:p_42, primary = n2

        n1          n2          n3          n4
        ●           ●           ●           ●
                    ▲           ▲
                    │           │
                 primary     replica
                 (owner)    (next distinct
                             physical clockwise)

Walk: hash the key, take the first vnode clockwise as primary, then keep walking until you have R distinct physical boxes (skip same-box vnodes and, if the map has topology, the same rack).

Reads can go to the primary only, or to any replica (more availability, stale if replication is async). This is placement, not consensus.

If they ask about N / W / R — write to W of N, read R, require R + W > N — that is a different contract. Dynamo-style stores use it so a read overlaps a write. A product cache usually does not wait for a quorum on GET. It replicates so a crash is not a full-slice miss.

Play the numbers in the N/W/R visualizer:

Clockwise replicas    where the copies live
N, W, R               how many copies a read or write must see

For this cache: R = 2, async, primary-first reads, Product DB remains truth. Virtual nodes spread which neighbor takes the extra copy. Topology-aware skips stop both copies landing in one rack.

10. Lookup algorithm

Nobody stores a circle in memory. The ring is a sorted array of virtual-node points.

points[] = [
  ( 0, n1-v0),
  (12, n3-v4),
  (20, n4-v17),
  (28, n2-v1),
  (35, n2-v0),
  ...
  (97, n1-v33)
]

Lookup:

h = hash(key)          // same hash space as the points
i = first index with points[i].token >= h   // binary search
if no such index: i = 0                     // wrap around
return points[i].physical_node

On the section 6 ring (n4 at 20): product:p_42 at 10 → first token >= 10 is 20 → n4. user:bob at 85 → no token >= 85 → wrap to 0 → n1.

Binary search is O(log V) with V = nodes × vnodes_per_node. At 100 nodes and 200 vnodes, V = 20,000. A 14-step search is noise next to a network GET.

Who runs this search?

Product Service
      │
      ▼
Cache Client
      │  binary search on cached placement map
      ├── n1
      ├── n2
      ├── n3
      └── n4

Three routing designs appear:

The baseline for a cache interview is a client library plus a cached placement map (tokens, node addresses, a monotonically increasing epoch). GET does not call the control plane. If the control plane is down, the last good map still routes.

A stale client may hit the old owner. That node can serve during a drain, return MOVED(new_owner, epoch), or reject a write if it has been fenced. The client refreshes once with jitter and keeps the original deadline. Unbounded redirects are a bug.

The application calls GET("product:p_42"). It should not choose a node.

11. What consistent hashing does not fix

The ring balances keys, not QPS, and it does not invent new query types.

Hot key

user:taylor or product:viral still hashes to one primary. A million fans produce a million GETs at one box. Virtual nodes do not help: every GET for that key walks to the same point.

You need an L1 on the app host, request coalescing, extra read copies, or shard suffixes. Design a Distributed Cache treats this as its own section: hashing will not save Node 7.

The same shape appears in YouTube view shards: one Redis key video:{hot}:views concentrates INCR, so the counter is split into video:{id}:views:0 .. :15. The client increments a random shard and reads the sum. That is manual partitioning of one logical key. The ring did not do it.

Range scans

“All keys from user:100 to user:200” has no meaning on a ring. Adjacent user ids land on unrelated nodes. You would fan out to the whole fleet. That wants range sharding (next section).

Cross-key transactions

cart:alice and product:p_42 sit on different nodes. Hashing does not give you a distributed transaction. Keep multi-key atomicity in the database, or colocate keys you control — a different design than hashing opaque strings.

The ring also does not give you global LRU, perfect balance, or a zero-miss add. Say that out loud. You chose the tool and you know its edge.

12. Compare to range sharding

Range sharding assigns contiguous keys to a shard:

Shard A    user_id [       1,  1_000_000]
Shard B    user_id [1_000_001,  2_000_000]
Shard C    user_id [2_000_001,  3_000_000]

A query “users 1,200,000 to 1,200,500” hits one shard. An incrementing id or a celebrity range can pin all new writes to the last shard. Splitting that range is a migration, not “insert a point on a circle.”

Need                          Prefer
------------------------------------------------------------
Point lookup by opaque key    Hash ring (this article)
Add/remove cache boxes        Hash ring + virtual nodes
Range scan / ORDER BY key     Range sharding
Time-series by timestamp      Range or time buckets
Hot partition of new ids      Hash, or a better partition key

Worked contrast: “orders for user 100–200” is one shard if the key is user_id. On a ring, hash("order:100"), hash("order:101"), … scatter, and a scan becomes scatter-gather.

Some systems use both: hash a partition key so one user’s data colocate, then range-sort inside the partition. Mention that if they ask. Do not bolt Cassandra repairs onto a Memcached fleet.

Consistent hashing wins for point reads and writes and membership change. Range sharding wins for ordered scans if you will split hot ranges.

13. Failure and rebalance operations

Placement is the easy half. The interview is won on what happens while the map is wrong.

Node crash

n2 disappears

Clients with a fresh map
  → keys on n2's tokens go to clockwise neighbors
  → miss + refill (or read replica if R > 1)

Clients with a stale map
  → still dial n2
  → timeout, not "miss"
  → retry after refresh; do not loop forever

A timeout is not a miss. Treating it as one stampedes Product DB. Bound retries. Prefer a replica if you have one. Virtual nodes spread the refill; without them, one neighbor is the incident.

Planned add and remove

Add n4     start empty → assign tokens → publish epoch K+1
           clients refresh with jitter → n4 receives its slice
           optional: copy the stolen arc *before* flipping (stores)
           a cache can skip the copy and pay lazy misses

Remove n2  mark draining → neighbors take tokens (K+1)
           wait for in-flight GETs → then kill the process

Do not kill first and publish later unless you want a crash-shaped event. 1/(N+1) of 100 million keys is still a lot of DB reads if every client flips in the same millisecond.

Stale membership

Two pods can disagree for a few seconds:

Pod A (epoch 41):  product:p_42 → n2
Pod B (epoch 42):  product:p_42 → n4

For a cache, both may be briefly right enough — serve stale or miss; do not wedge. For a source-of-truth store, fence the old owner. “I used to own this key” is not a write permit.

A bad “fix” is modulo plus a secondary host table — that table becomes a new N. Another is an overnight full rehash. The ring exists so you never schedule that job.

Degraded behavior

One cache node down       Slice misses or replica reads; DB bump on that slice
New node empty            Expected misses on 1/(N+1) keys; jitter clients
Client map stale          Timeout / MOVED; refresh once
Control plane down        Keep last map; do not block GET
Whole cache fleet down    Shed; do not replay peak QPS into Product DB
Replica behind            Serve stale or miss; DB is truth
Network partition         Some clients hash to unreachable owners; fail that GET

Name the signals: keys per vnode, QPS per node, miss rate, epoch skew, max/mean load. If you cannot see a lumpy vnode, you will not add tokens.

14. Final architecture: a cache fleet on a ring

Put the pieces on one diagram. Product DB never leaves the picture — the ring only places copies.

                         Product Service
                               │
                               ▼
                        Cache Client
                     placement map epoch=42
                     hash + binary search
                               │
              ┌────────────────┼────────────────┐
              │                │                │
              ▼                ▼                ▼
           ┌─────┐          ┌─────┐          ┌─────┐
           │ n1  │          │ n2  │          │ n3  │
           │ RAM │          │ RAM │          │ RAM │
           └──┬──┘          └──┬──┘          └──┬──┘
              │                │                │
              │   consistent-hash ring (vnodes) │
              ●────●────●────●────●────●────●────●
             n1   n2   n3   n1   n2   n3   n1   n2
             v0   v0   v0   v1   v1   v1   v2   v2

              primary ──► next distinct node = replica

              miss / invalidate
                               │
                               ▼
                          Product DB
                        source of truth

Request path for GET product:p_42:

1. Client hashes the key onto the ring.
2. Binary search finds the first vnode clockwise → physical n2.
3. Client GETs n2 (deadline set).
4. Hit: return bytes.  Miss: client reads Product DB, PUT to n2.
5. n2 may async-copy to the next clockwise replica.
6. Application never picks a host by hand.

Add n4 and only tokens behind its new points change owner. About 1/(N+1) of keys refill. The rest stay warm.

Product DB       source of truth
Cache / replica  derived, evictable; replica may lag
Placement map    derived membership, cached on clients
Control plane    epoch only — not on the GET path

The ring does not authenticate. Bound key and value size. Random-key scans are cache penetration, not a hashing bug — see distributed cache. Multi-region: independent rings per region. Do not walk clockwise from us-east into eu-west. Replicate the database; let each region warm its own cache.

15. Interview-ready summary

The compact mental model:

Three nodes, hash % 3
      ↓ add a fourth node
Almost every key remaps; cache goes cold; DB burns
      ↓ put keys and nodes on a circle
First clockwise owner; add/remove steals one arc
      ↓ one point per box is lumpy; death dumps on one neighbor
100–200 virtual nodes; failure spreads
      ↓ node death is still a miss storm
Clockwise replicas (placement), not automatically N/W/R
      ↓ celebrity key, scans, multi-key tx
Hashing does not help; pick another tool

Key decisions to remember

1. Clarify what is on the ring: cache keys are not users, and a cache remap is a miss storm.
2. Reject hash % N once membership can change.
3. Owner = first node (vnode) clockwise; wrap from the last token to the first.
4. Adding a node moves about 1/(N+1) of keys; removing moves about 1/N.
5. Use 100–200 virtual nodes per box so load is even and failures spread.
6. Put the lookup in a client library: sorted tokens + binary search, cached epoch.
7. Replicate clockwise to distinct physical nodes if a crash must not spike the DB.
8. Do not call that quorum unless you actually chose N/W/R.
9. Hot keys, range scans, and cross-key transactions are out of scope for the ring.
10. The new owner is empty until refill or copy; jitter map updates.

Likely interviewer follow-up questions

• Why not hash % N plus a static table of hosts?
• How many virtual nodes, and how do you measure imbalance?
• Who computes the hash — client, proxy, or a random node?
• What happens if two clients have different epochs?
• How do you copy data when the cluster is a database, not a cache?
• Where do replicas sit, and is replication sync or async?
• How is this different from N/W/R? (Open the quorum visualizer.)
• How do you handle a hot key the ring pinned to one box?
• When would you pick range sharding instead?
• What is rendezvous hashing / Maglev, and do I need them here?
• How does a node drain without a thundering refill?
• What if the hash function is weak (IDs that cluster)?

Senior-level points that differentiate the answer

• Teach % N with a table of real keys before drawing a circle.
• Quote N/(N+1) versus 1/(N+1) so the remap math is not a vibe.
• Separate balance (vnodes) from failure spread (also vnodes) — two reasons, one mechanism.
• Call the new node empty. Lazy fill versus pre-copy is a cache-versus-store fork.
• Timeout ≠ miss; stale maps need MOVED or fencing, not unbounded redirects.
• Clockwise replicas are placement; N/W/R is a read/write contract.
• Hot keys need extra treatment — point at YouTube view shards or an L1.
• Independent regional rings; one global circle is a latency bug.
• Measure max/mean load. Do not ship 200 vnodes as folklore.

A 1–2 minute verbal answer

I would partition cache keys, not treat the cache as source of truth. The naive placement is hash(key) % N. With three nodes that works; adding a fourth remaps about three quarters of keys, the cache goes cold, and the database takes a miss storm.

Instead I put nodes and keys on a hash ring. A key belongs to the first node clockwise. Adding a node steals only the arc behind it, about 1/(N+1) of keys. Removing a node moves about 1/N. One point per box is uneven and dumps a failure onto a single neighbor, so each physical server gets 100–200 virtual nodes. Lookup is a binary search on a sorted token array in the client library, using a cached membership epoch.

I would replicate a couple of hops clockwise so a crash is not a full-slice miss, without pretending that is a Dynamo quorum. Consistent hashing does not fix a celebrity key, a range scan, or a two-key transaction. For those I would shard the hot key, use range partitioning, or keep the transaction in the database.

Open the visualizer and add a node while you talk. For the broader cache design, see Design a Distributed Cache. For more prompts, use the questions hub and the System Design Interview Complete Guide.