Consistent Hashing

A placement rule should not move nearly every key whenever membership changes. With hash(key) modulo node_count, changing node_count changes many assignments. Consistent hashing places both keys and node tokens on a shared circular space and gives each key an owner according to an ordered rule. Its benefit is limited reassignment, not automatic fairness or replication correctness.

Learning goals

Membership changes; hash ring ownership; virtual nodes; key movement; replication placement; hot keys; ring metadata; failure detection.

The mechanism at a glance

Figure — Key hash 45 → Ring version 1 (lookup); Ring version 1 → B owns (20,60] (before); B owns (20,60] → Add D at 50 (membership change); Add D at 50 → D owns (20,50] (move interval); Add D at 50 → B keeps (50,60] (retain interval)

The numbered components identify responsibilities. Follow the labeled arrows rather than treating the numbers as a global execution order. The scenario later in this lesson shows one concrete sequence.

Step-by-step reasoning

1. Walk the ring

Hash a key to a position and walk clockwise to the first node token. That token owns the key under this convention. The last interval wraps around to the start. When a new token is inserted, it takes the interval immediately before it from the previous owner of that interval; unrelated intervals keep their owners.

2. Use virtual nodes for placement balance

One physical machine can own many tokens. This spreads a machine’s responsibility across the ring and helps smooth uneven token spacing. Weight token counts or placement for heterogeneous capacity if needed. Virtual nodes distribute many keys; they cannot split the traffic for one intensely popular key by themselves.

3. Place replicas across failure domains

Keeping additional clockwise copies is a possible replication rule, but skip tokens belonging to the same physical machine and consider rack or zone diversity. Ownership and replication are separate decisions. Define which copy accepts writes, what acknowledgments mean, and how an unavailable node is replaced or repaired.

4. Coordinate membership and movement

Clients need a coherent ring view or a router that owns it. Membership changes should carry a version, and data movement should be monitored. A returning node may hold stale data. For a cache, misses during movement may be acceptable if origin load is bounded; for authoritative storage, transfer and reconciliation need stronger guarantees.

Contracts and state

The following sketch makes the decision boundary concrete. Field names and capacity assumptions are illustrative; adapt them to the stated product contract.

Ring positions: A=20, B=60, C=90
key 45 -> B (first clockwise token)
Add D=50
key 45 -> D; key 55 -> B
Moved interval: (20, 50]
The diagram uses a linearized ring; right edge wraps to left.

Worked example

Suppose a cache has three nodes and a fourth is added. With a ring, only the new node’s acquired intervals need to warm on that node. Other owners retain their cached keys. However, the most popular homepage might lie in one acquired interval. Warm-up can still cause a large origin spike even though the percentage of moved keys is small. Measure moved request volume as well as moved key count.

Figure — Adding a token changes one interval. Trace key 45 before and after the membership change.

Failure walkthrough

Two clients disagree about membership and send the same key to different cache nodes. This can temporarily lower hit rate or return different cached versions. A versioned membership source, controlled rollout, and bounded TTL help. Do not call the ring a consensus protocol: it computes placement from membership but does not establish agreement about membership or the value of a key.

Figure — Publish new ring version → Move only acquired ranges → Warm popular moved keys → Bound origin miss traffic → Retire old routing version

Decisions and trade-offs

Check your understanding

With tokens A=20, B=60, C=90, where do keys 10, 45, and 95 go? What changes when D=50 joins?

Transfer to a new scenario

Add a cache node and identify only the ranges whose owner changes.

Do virtual nodes solve a single extremely popular key?

Continue the connection

Study Sharding and explain which guarantee from this lesson carries into that topic.

Separate placement from replication

Place server tokens around a hash ring and assign a key to the first token clockwise. Adding one token changes ownership of a neighboring interval rather than remapping every key as hash(key) modulo nodeCount can. With many virtual tokens, physical nodes receive several intervals, reducing placement imbalance across many keys.

Replication is a separate rule: for example, choose the next distinct physical owners while respecting failure domains. Two adjacent virtual tokens can belong to the same physical machine, so counting tokens as independent replicas is unsafe. Membership changes need versioned routing and actual data movement or cache refill.

For N equally weighted nodes and uniform keys, adding a node moves roughly 1/(N+1) of keys in expectation. This is not a guarantee about bytes or traffic. A single hot key still maps to one primary placement and may need read replication or a redesigned value.

Figure — A decision worksheet for Consistent Hashing: read the mechanism and its guarantee together.

Operational sketch

ring tokens: A20, B60, C90
key 45 -> B60
add D50: key 45 -> D50
interval (20,50] moves; other intervals retain owners

A tempting mistake

Consistent hashing does not choose a leader, detect failures reliably or make a stale replica safe to promote. It is a placement technique inside a larger protocol.

Transfer exercise

If one key receives half the traffic, will adding many virtual nodes solve the overload?