Consistent hashing

The rehash-everything problem

The previous lesson named this in passing; here is why it’s so violent. With shard = hash(key) mod N, the assignment of a key depends on N — the number of nodes. Change N and you change the divisor for every key at once. Going from mod 10 to mod 12 doesn’t just reassign the keys that “should” move to the new nodes; it reshuffles nearly the entire keyspace, because hash(key) mod 10 and hash(key) mod 12 disagree for the vast majority of keys.

key "user:42" → hash = …739
  mod 10 = 9   → node 9
  mod 12 = 7   → node 7   ← moved, and so did almost everyone else

For a sharded database this means a near-total data migration. For a cache it’s worse and faster: every key now hashes to the wrong node, so every lookup misses, and the full read load slams the backing store — the hook’s outage. The root cause is that the routing function has N baked into it, so capacity changes are global, not local.

The hash ring

Consistent hashing breaks that coupling by hashing nodes and keys into the same space and arranging that space as a ring (a circle of hash values, say 0 to 2^32 − 1, wrapping around).

• Hash each node (by its name/IP) to a point on the ring.
• Hash each key to a point on the ring.
• A key belongs to the first node found by walking clockwise from the key’s position.

        node A
      ·──────·                 walk clockwise from a key
   ·            ·              to the next node on the ring:
  ·   k1→A       node B        k1 → A,  k2 → B,  k3 → C
  ·              ·
   ·   k3→C   k2→·
      ·──────·
        node C

Now add a node D. It lands somewhere on the ring and takes over only the keys in the arc between its predecessor and itself — the keys that used to walk clockwise past that arc to the next node. Every other key still walks to the same node it did before. Removing a node is the mirror image: only that node’s keys move, to the next node clockwise. A membership change disturbs roughly 1/N of the keys, not all of them — that single property is the whole point, and it turns “add a node” from a global reshuffle into a local handoff.

Virtual nodes for balance

Plain consistent hashing has a flaw: with only a handful of node points scattered randomly on the ring, the arcs between them are uneven. One node might own a 40% arc and another 5%, so load is lopsided — and when a node dies, its entire arc dumps onto the single next node clockwise, which can then tip over (a cascading failure).

The fix is virtual nodes (vnodes): instead of placing each physical node once, place it at many points on the ring (say 100–200 each, via hash(node + "#0"), hash(node + "#1"), …). Now each physical node owns many small arcs scattered around the ring. Two benefits fall out:

• Balance: many random small arcs average out, so each physical node ends up with a near-equal share of the keyspace (the law of large numbers).
• Smooth failure: when a node dies, its many small arcs are inherited by many different successors, spreading the orphaned load across the cluster instead of dumping it all on one neighbour.

Vnodes also let you weight heterogeneous hardware: give a bigger box more virtual points so it owns proportionally more of the ring. This is how Dynamo-style systems and Cassandra distribute data; the number of vnodes per node is a real tuning knob (too few → imbalance, too many → a bigger ring to manage).

Bounded-load, and where it’s used

Consistent hashing balances the keyspace, but the previous lesson’s lesson still bites: even arcs don’t mean even load if one key is a celebrity. A refinement, consistent hashing with bounded loads (the approach Google described and that backs some load balancers), adds a cap: each node may hold at most c × average load; if a key would land on a node already at its cap, it spills clockwise to the next node with room. This keeps any single node from being overwhelmed by a hot arc while preserving the “move only a little on membership change” property — a direct answer to the hot-shard problem for request routing.

Where you’ll meet consistent hashing in practice:

• Distributed caches (Memcached/Redis client-side sharding) — so adding a cache node doesn’t blow the hit rate, the hook’s exact fix.
• Dynamo-style key-value stores (DynamoDB, Cassandra, Riak) — to place partitions on nodes and rebalance cheaply when the cluster grows or a node fails. (Dynamo combines this ring with the quorum replication of lesson 01.)
• Load balancers — to map a request (often by a session or client key) to a consistent backend, so sticky routing survives backend pool changes.

When you see any of these systems add or remove a node, what you’re watching is the ring performing a local arc handoff — not a global reshuffle. Without the ring, each of those capacity changes would have been the outage described in the hook.