Modulo hashing couples every key to the node count#
node = hash(key) % 4
Add one node:
node = hash(key) % 5The remainder changes for many keys, forcing broad movement or cache misses. That is expensive when nodes join and leave in a distributed cache, partitioned store, or request-routing pool.
The ring is a keyspace model, not a network topology#
Place node positions and key hashes in a circular hash space. A key belongs to the next node clockwise. Adding or removing one node changes ownership mainly for a neighboring interval rather than remapping nearly every key.
A changing hash ring
Keys belong to the next node clockwise. Add or remove a node to see which sample keys actually move.
| Key | Position | Owner |
|---|---|---|
profile:42 | 4 | Node A - unchanged |
video:91 | 18 | Node B - unchanged |
feed:17 | 37 | Node B - unchanged |
image:63 | 57 | Node C - unchanged |
session:8 | 72 | Node C - unchanged |
post:29 | 91 | Node A - unchanged |
Virtual nodes improve placement flexibility#
One physical node can own many positions, helping smooth random imbalance and represent heterogeneous capacity in some implementations. Virtual nodes add metadata and migration work; they do not make a heavily requested key divisible.
Use these prompts to extend the design. The useful answer is a reasoned change, not a memorized sentence.
- What changes when a node joins?
- How is a failed node handled?
- Why use virtual nodes?
- What happens to one extremely hot key?
- Does this workload actually have a changing node set?
Related practice problems
Use the manifest-backed prompts below to apply this lesson in a complete design.
- Consistent Hashing and Random TreesKarger et al., STOC 1997