Consistent Hashing

When data or requests are spread across N nodes, you need a rule: which node owns key K? The naive rule breaks badly when N changes.

flowchart LR
  K["key: user:42"] --> H["hash(key)"]
  H --> RING["Position on the ring 0 … 2³²"]
  RING --> CW["Walk clockwise"]
  CW --> NODE["First node found owns the key"]
  ADD["Add a node"] -.->|"takes keys only from its neighbour"| NODE
  %% step K: Keys can be cache keys, user IDs or session IDs.
  %% step H: A hash function turns the key into a number.
  %% step RING: Nodes are hashed onto the same ring, usually many times each (virtual nodes).
  %% step CW: From the key's position, walk clockwise to the next node.
  %% step ADD: A new node takes over only the keys between it and its predecessor — about 1/N of them.

Why modulo hashing fails

node = hash(key) % N. With 4 nodes, key 42 → node 2. Add a fifth node: % 5 changes the answer for about 80% of keys. For a cache cluster that means a sudden flood of misses hitting the database — often right when you added capacity because load was high.

Consistent hashing

• Nodes and keys share one hash ring.
• Each key belongs to the first node clockwise.
• Adding or removing a node moves only the keys in one arc: about 1/N of all keys.

Virtual nodes

With few nodes, arcs have random sizes and one node gets too much. Place each physical node at many points (100–200 virtual nodes). Load evens out, and when a node leaves, its keys spread across all the others instead of one neighbour. Bigger machines can get more virtual nodes.

Where you meet it

Replication on the ring

Store each key on the next R nodes clockwise (R = 3 is common). Losing one node then loses no data, and reads can use a quorum (module 3).

Traps: using % N for a cache cluster you plan to resize; no virtual nodes, so one node is a hotspot; hot keys (one celebrity user) — consistent hashing balances key count, not traffic per key.