Consistent hashing

Problem

You need to shard keys across N nodes, but N changes over time (nodes added, removed, or failed). Naive hash-mod-N reshuffles almost everything on every change — cache is wiped, migration cost is huge.

Context

This is the mathematical foundation for scalable distributed caches (Memcached, Redis Cluster) and for wide-column stores (Cassandra, DynamoDB, Riak). Anywhere you need consistent placement of keys across a fluctuating fleet.

Solution

Instead of hash(key) mod N, project both keys and nodes onto a ring. To find the node for a key, hash the key and walk clockwise until you find a node. When a node is added or removed, only the keys in its arc move — a fraction 1/N of total keys. Virtual nodes (each physical node owns many small arcs) smooth out imbalance.

Trade-offs

• Adds a lookup step (find the successor on the ring) — negligible cost
• Uneven load without virtual nodes; use ~200 virtual nodes per physical node
• Replication (put keys on N successors of the ring) adds complexity
• Hot key still lives on one node — consistent hashing doesn't solve celebrity-user hot spots

Failure modes

• Without virtual nodes, adding a small number of physical nodes creates uneven arcs — one node gets 5× the load
• Ring drift on cluster restart if nodes hash their identities inconsistently — all keys shift
• Replication factor smaller than expected failure count → data loss during multi-node outage
• Client-side inconsistent view of the ring (some clients haven't heard about the new node) → mismatched routing

When to use

• Any distributed cache with N > 1 nodes and expected churn
• Wide-column stores where keys must map deterministically to a partition
• CDN edge selection (routing users to the nearest healthy PoP)

When NOT to use

• You have a fixed, tiny N and no churn — mod-N is simpler
• You need to co-locate specific groups of keys — directory-based sharding gives you more control