Consistent hashing

The problem with `hash(key) % N`

Modulo sharding is the obvious first idea: map each key to a node by hash(key) % N. It works perfectly while N is fixed. The moment a node joins or leaves, N changes, every key’s owner shifts, and the system has to move ~(N-1)/N of its data — nearly everything.

For a 10-node cache, adding one node moves about 90% of the keys. The thundering rebuild stampedes the cache, the upstream database, and the network. For a sharded store, it is an outage in slow motion.

Consistent hashing solves this by making the mapping decouple from N. Adding or removing a node moves roughly 1/N of the keys — the share the new node now owns, or the share the leaving node used to own — and nothing else.

Concept

Map keys and nodes onto the same circular hash space; each key belongs to the next node clockwise. Adding or removing a node disturbs only its immediate neighbourhood.

The defining property: when the set of nodes changes by one, the expected fraction of keys that change owner is 1/N, not (N-1)/N. This is what makes it the standard primitive for distributed caches (Memcached clients, DynamoDB-style stores) and sharded systems where membership churns.

The ring

Hash both keys and nodes into the same large space — conventionally a 32-bit or 64-bit integer treated as a ring (so the largest value wraps back around to zero). Each key is owned by the first node encountered when walking clockwise from the key’s position.

The walkthrough below positions three nodes and three keys on a ring. Step through it to see how each key finds its owner, what happens when a node leaves, and — the key property — that the remaining keys do not move.

Consistent hashing ring — assign keys, then drop a node

Three nodes hashed onto a ring at positions 0x10, 0x60, 0xB0. Each key is owned by the next node clockwise. When a node leaves, only the keys in its arc move.

0 / 5

The general rule the walkthrough demonstrates: when node-B leaves, only the keys it owned (those between 0x10 and 0x60) move, and they all go to the next node clockwise. When a new node-D joins at hash 0x40, it takes over the slice between 0x10 and 0x40 from node-B; everything else stays put.

Why “virtual nodes” are non-negotiable

The plain ring above has a problem: with only three real nodes, the slices between them are uneven by accident of the hash function. One node ends up with 60% of the keys, another with 15%. This skew compounds — the overloaded node is also slowest, which makes its tail latency dominate.

The fix is virtual nodes (often called vnodes or replicas in this context — not to be confused with data replicas). Each physical node is hashed into the ring at many positions, typically 100–200. With 200 vnodes per physical node, the law of large numbers smooths the slice sizes to within a few percent of the mean.

Axis	1 vnode per node (naive)	100–200 vnodes per node
Load balance	Up to 4× skew between nodes for small clusters	Typically <5% deviation from mean
Memory for ring metadata	Trivial — N entries	Still trivial — 100N entries, a few KB
Re-balance granularity when a node joins	One contiguous range — coarse	Many small ranges spread across all other nodes — fine and parallelisable
Worst-case node loss	Successor inherits one large range, may overload	Load spreads evenly across remaining nodes

Lookup

To find a key’s owner, binary-search the sorted vnode positions for the first one ≥ hash(key), wrapping to the start of the array if none. That is O(log V) where V = N × vnodes-per-node. The ring itself is a tiny sorted array of (hash, node) tuples, cheap to keep in memory on every client.

Ring.java

class Ring {
  private final NavigableMap<Long, String> ring = new TreeMap<>();
  private static final int VNODES = 150;

  void add(String node) {
    for (int i = 0; i < VNODES; i++) {
      ring.put(hash(node + "#" + i), node);
    }
  }

  String owner(String key) {
    long h = hash(key);
    Map.Entry<Long, String> e = ring.ceilingEntry(h);
    return e != null ? e.getValue() : ring.firstEntry().getValue();
  }
}

ceilingEntry is the clockwise walk; the wrap to firstEntry is the “past the end of the ring” case.

The decision: where the ring lives

Decision

Chose: Depends on what owns membership

2026-05-25

If membership rarely changes and clients can tolerate brief inconsistency, the client-side ring is simplest. If you already run a control plane that knows membership (e.g. a service-discovery system), put the ring there. Don't reach for gossip until cluster size makes a coordinator a real bottleneck.

Client-side ring (Memcached-style)

Pros

Zero coordinator
Each client routes directly to the owning node — one network hop

Cons

Membership changes must reach every client
Stragglers route to old owners until they refresh

Coordinator-side ring (DynamoDB-style)

Pros

Single source of truth for membership
Clients don't need to know the topology

Cons

Coordinator becomes the routing hop — extra latency
Coordinator availability matters

Gossip-distributed ring (Cassandra-style)

Pros

Self-healing
No central coordinator

Cons

Convergence is eventual — brief windows of disagreement
Operationally complex

The footguns

Anti-pattern

Treating hot keys as a hashing problem

Smell

“The ring is uneven — one node is at 90% CPU.” But the ring is fine; it’s that 60% of traffic hits a single celebrity key.

Why it happens

Consistent hashing balances key space, not traffic. A single popular key still lands on one node no matter how many vnodes you add.

Fix instead

Detect hot keys separately and shard them at the application layer — replicate to N nodes, route reads round-robin. Or move them to a small in-process cache in front of the ring.

Other things that bite:

Using a weak hash function. CRC32 has too few output bits and visible clustering on structured keys (user:1, user:2, …). Use MD5 or MurmurHash3 — speed matters more than cryptographic strength here, but distribution matters most.
Forgetting replication. A single owner per key means a single point of failure. The standard pattern is to walk the next R-1 nodes clockwise and store replicas there. Reads can hedge across them; writes use quorum.
Resizing vnodes per node mid-flight. Changing the vnode multiplier rehashes the entire ring. Pick a number once (150 is a reasonable default), commit to it, and use weighted vnodes if you need to give a bigger node more share — assign it weight × vnodes-per-node positions.

What to remember

This pairs naturally with 0003 Idempotency keys on write endpoints · System Design on the write path: consistent hashing decides where a write lands, idempotency keys decide whether the write happens twice. Both are about surviving an unreliable substrate without losing or duplicating work.

The problem with hash(key) % N