System Design · Core

Consistent Hashing

Map keys to nodes so that adding or removing a machine moves only a small fraction of keys — the hash ring and virtual nodes.

1. The problem with mod N

shard = hash(key) % N N = 3: key K → shard 2 N = 4: key K → shard 1 # almost ALL keys remap when N changes

When you scale the cluster from N to N+1, hash % N reshuffles nearly every key. Caches go cold; databases need massive data movement. That is unacceptable for large KV stores and cache fleets.

2. The hash ring

Imagine a circle of hash values from 0 to 2^m - 1. Place both nodes and keys on the circle by hashing their IDs. A key belongs to the first node clockwise (or counterclockwise — pick one and stay consistent).

hash space as a ring N2 / \ K_a N3 / \ N1 ------- K_b Rule: walk clockwise from hash(key) until you hit a node. K_a → N2, K_b → N1 (example depending on positions)

When you add node N4, only keys that now fall in the arc ending at N4 move. Expected fraction moved ≈ 1/N for balanced placement — far better than remapping everything.

3. Virtual nodes (vnodes)

A few physical nodes on the ring leave large uneven arcs → hotspots. Give each physical node many virtual nodes: hash nodeId#1, nodeId#2, … onto the ring. Arcs become smaller and load more uniform. Removing a physical node removes all its vnodes.

Physical A → vnodes A0, A1, A2, ... A99 Physical B → vnodes B0, B1, B2, ... B99 More vnodes → smoother load, more metadata to store

4. Lookup algorithm (sketch)

nodes_sorted = sorted list of (vnode_hash → physical_node) function locate(key): h = hash(key) i = first vnode_hash >= h # binary search on ring if none: i = first vnode (wrap around) return physical_node(i)

5. Replication on the ring

For durability, store N replicas on the next N distinct physical nodes clockwise (skip vnodes of the same physical host). Preference lists in Dynamo-style systems come from this walk.

key K → primary = next node replica2 = next distinct physical replica3 = next distinct physical

6. Use cases

System	Why consistent hashing
Distributed cache (Redis Cluster-ish ideas, Memcached clients)	Minimize cache miss storm on scale-out
Dynamo / Cassandra / Riak	Partition data + replica placement
CDN / request routing	Sticky-ish mapping with churn
Load balancing by key	Same user/session → same backend often

7. Limitations

Hot keys still hammer one node — need key splitting or local replication.
Imperfect balance without enough vnodes.
Gossip/membership must propagate ring changes carefully.
Range queries by key order are unnatural (hash destroys locality).

8. Interview one-liner

“Mod N reshuffles almost all keys when the cluster size changes. Consistent hashing puts keys and nodes on a ring so only neighboring keys move; virtual nodes keep load even.”

Quick revision

hash % N remaps most keys when N changes — bad for caches/DBs.
Ring: key maps to next node clockwise.
Add/remove node moves only ~1/N of keys (ideally).
Virtual nodes smooth load across physical machines.
Replicas = next distinct physical nodes on the ring.
Used in KV stores, caches, and some LB designs.
Does not solve hot-key skew by itself.