1. One-Liner
Consistent hashing places both keys and servers on a ring so adding/removing a server only moves keys in its arc neighbors, not the whole cluster.
2. The Problem It Solves
Classic hash(k) % n reshuffles almost everything when n changes; distributed caches and CDNs need stable key→server mapping under membership churn.
3. The Core Idea
Hash servers to points on a circle; hash each key and walk clockwise to the first server ≥ key (with virtual nodes to balance skew).
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | Build sorted ring of server hashes |
| 2 | For key k, find successor server on ring |
| 3 | Node add/remove → only keys between predecessor/successor migrate |
| 4 | Virtual replicas per physical node improve balance |
5. Dry Run Example
Ring 0…360: servers at 60,180,300; key at 100 maps to 180; remove 180 → key 100 slides to 300 only.
6. Key Properties
| Property | Value |
|---|---|
| Remapping | O(keys/node) local, not global |
| Balance | Improved with virtual nodes |
| Hotspots | Mitigate with replicas & weights |
7. Where It Is Used
| Domain | Use |
|---|---|
| Dynamo / Cassandra | Partitioning & replication |
| CDN / caches | Memcached clients, load balancers |
8. Interview Tips
Ring + successor, virtual nodes, fault tolerance with replication—classic system-design topic.
9. Comparison with Other Algorithms
| Scheme | Node change |
|---|---|
| Mod hashing | Massive remap |
| Consistent | Local remaps |
| Rendezvous | Different tradeoff |
10. Complexity
| Metric | Value |
|---|---|
| Lookup | O(log n) with balanced tree of points |
| Updates | Local key migration |
Implementation Example (PYTHON)
import bisect
class ConsistentHash:
def __init__(self, nodes, v=100):
self.ring = []
self.m = {}
for n in nodes:
for i in range(v):
h = hash(f'{n}#{i}') % (2**32)
self.ring.append(h); self.m[h] = n
self.ring.sort()
def node(self, key):
h = hash(key) % (2**32)
i = bisect.bisect(self.ring, h) % len(self.ring)
return self.m[self.ring[i]]