Consistent Hashing

Consistent Hashing

One-liner: Map keys and nodes onto a ring so adding or removing a node remaps only ~1/N of keys instead of nearly all of them.

ArticleConcepts© Arthur Bernier Jr551 words1 code block

Say this#

SAY THIS

Hash ring — hash space (e.g. 0..2^32−1) treated as a circle.
Node / server placement — each node hashed to one or more points on the ring.
Key → first node clockwise — the lookup rule.
Virtual nodes (vnodes) / replicas — each physical node gets many ring points to smooth load.
Rebalancing — only keys between the departed node and its predecessor move.
Mod-N hashing — hash(key) % N; changing N remaps almost everything.
Hot spot / skew — uneven key distribution; vnodes and good hash functions fix it.
Replication along the ring — store a key on the next K distinct nodes clockwise.
Rendezvous (HRW) hashing — alternative: pick node with highest hash(key, node); no ring needed.
Jump consistent hash — Google's O(1)-memory variant for numbered buckets.
Where used — Cassandra, DynamoDB, Riak, Memcached clients (ketama), Envoy/Nginx LB, Akamai, Discord.

How it works#

TEXT

        0   D         A      key k hashes to 73 -> walk clockwise -> node B     \     /        remove B -> k goes to C; only B's range moves  C ---- + ---- B     /     \       ...        0
   D         A      key k hashes to 73 -> walk clockwise -> node B
     \     /        remove B -> k goes to C; only B's range moves
  C ---- + ---- B
     /     \
       ...

Hash each node ID (plus vnode index) to points on the ring.
Hash the key; walk clockwise to the first node point; that node owns the key.
Add node: it takes over a slice from its clockwise successor; ~K/N keys move.
Remove node: its slice falls to the successor.
Virtual nodes: 100-200 points per physical node so load variance is a few percent and heterogeneous nodes can get proportional weight.

Why not mod N: going from N to N+1 remaps roughly N/(N+1) of all keys (near 100%), causing cache misses or data movement everywhere.

Trade-offs#

Choice	Pro	Con
Consistent hashing with vnodes	Minimal remap, balanced load, weighted nodes	Ring metadata; lookups O(log N) via sorted array / binary search
Mod N	Trivial, O(1)	Near-total remap on resize
Rendezvous hashing	No ring state, naturally balanced	O(N) per lookup unless optimized
Few vnodes	Less metadata	Load imbalance, slow rebalancing
Many vnodes	Smooth load	Larger routing table; more replication streams

Numbers#

Adding one node to N moves ≈ 1/(N+1) of keys; mod-N moves ≈ N/(N+1).
Without vnodes, load imbalance between nodes can be 2x+; with ~100-200 vnodes the standard deviation drops to roughly 5-10%.
Cassandra default: 256 vnodes per node historically (now commonly 16 with the newer allocation algorithm); DynamoDB and Riak partition the ring into fixed partitions (Riak default 64).

Say this#

How it works#

Trade-offs#

Numbers#

In the interview#