Consistent Hashing

Problem Statement We need to distribute keys (data, requests, cache entries) across multiple servers. A common approach is: bucket = hash(key) % N Where N is the number of servers. The Problem? When N changes (a server is added or removed), almost all keys get reassigned. This causes? Massive data movement Cache invalidation Network overhead We need a way to minimize key movement when servers change. The Solution: Consistent Hashing Instead of modulo arithmetic, consistent hashing: Maps both servers and keys onto a circular hash space (a ring). Assigns each key to the next server clockwise. This small change ensures that when servers are added or removed, only a small subset of keys move. Example Step 1 — Create the Hash Ring Assume hash space = 0 to 99 (circular). Place 3 servers: A → 10 B → 40 C → 80 0 ----10(A)----40(B)----80(C)----99 -> back to 0 Step 2 — Add Keys Key Hash K1 5 K2 25 K3 50 K4 85 Assignment Rule : Move clockwise → first server you hit owns the key. Result: K1 (5) →