Consistent Hashing — Notes

Problem solved

Plain hash(key) mod N reshuffles ~all keys when N changes. Consistent hashing moves only K/N keys.

Algorithm

1. Hash each server → place on ring (with V virtual copies).
2. Hash each key → find first server clockwise.
3. To replicate, take next R-1 distinct servers.

Properties

• Movement on add/remove: K/N keys.
• Load skew without vnodes: high; with V≈200 vnodes, std-dev tolerable.
• Lookup: O(log V·N) with sorted positions + binary search.

Failure handling

• Hinted handoff (Dynamo): if replica down, neighbor stores hint, replays later.
• Anti-entropy: Merkle trees compare ranges and repair drift.

Alternatives & when to use

Algorithm	Pros	Cons
Mod-N	trivial	massive remap on change
Consistent hash + vnodes	flexible	needs lookup table
Jump hash	O(1), no metadata	only sequential nodes
Rendezvous (HRW)	easy weights	O(N) per lookup
Maglev	uniform, fast	needs table reseeding

Refs

• Karger et al. 1997 paper; Dynamo (Amazon); Akamai paper; Maglev (Google 2016).