Consistent Hashing: How Distributed Systems Distribute Data

The problem

Naive sharding with hash(key) mod N works fine until N changes. Add one node and ~80% of keys remap — every cache miss, every data migration, all at once. A 5-9 minute outage during resizing is normal with naive hashing.

The solution — the ring

Map both keys AND nodes onto the same circular hash space (typically 0 to 2^32 wrapping). A key is owned by the first node clockwise from its hash. Lookup is O(log N) via binary search on the sorted node hashes.

When you add a node, it takes over only the arc between itself and the previous node clockwise — no other node is affected. K/N keys move, not K × (N-1)/N.

When you remove a node, the next clockwise neighbor inherits its keys.

The big problem with the naive ring — load imbalance

With 4 nodes randomly placed, one might end up with 60% of the keyspace by bad luck. Variance is huge with small N.

Virtual nodes solve it

Each physical node maps to 100-1000 ring positions (Cassandra default 256). Variance shrinks roughly as 1/√V. Three more wins:

• Faster rebalancing: failed node's vnodes spread across many remaining nodes; each picks up a slice in parallel
• Weighted nodes: more disk = more vnodes; ring weights itself
• Smoother failure recovery

Replication on the ring

Consistent hashing locates the primary; for N replicas, walk N more physical nodes clockwise (skipping vnodes of the same physical node). Topology-aware variants ensure replicas land on different racks or AZs.

The ring tells you the replica set; consistency level (ONE, QUORUM, ALL) governs reads/writes — separate concerns.

Node lifecycle

• Joining: new node generates vnode positions, streams data from predecessors, ring updated, clients learn
• Graceful leaving: announce shutdown, next clockwise takes over each vnode, stream forward
• Sudden failure: heartbeat timeout, replicas take responsibility, hinted handoff buffers writes for replay when node returns
• Throttle rebalances — they move TBs and saturate network if unrestricted

Variants worth knowing

• Bounded-load (Google 2017): cap each node at (1+ε) × average, spill excess. Used in Maglev.
• Rendezvous hashing (HRW): O(N) lookup, no ring metadata, easy weighted, good for small N
• Jump consistent hash (Google 2014): O(log N), O(1) memory, but only append-only topology
• Maglev hashing: precomputed lookup table with bounded disruption

Where it's used

• Cassandra, DynamoDB, Riak — data sharding + replica placement
• Memcached clients (Ketama), Redis Cluster (slot variant)
• L4 load balancers (Envoy ring hash) for sticky sessions
• CDN edge selection
• Application-level sharding by user ID

Implementation sketch

NavigableMap<Long, Node> ring = new TreeMap<>();
for (int i = 0; i < V; i++) ring.put(hash(node + "#" + i), node);
// lookup
Map.Entry<Long, Node> e = ring.ceilingEntry(hash(key));
if (e == null) e = ring.firstEntry();   // wrap

Use Murmur3 or xxHash; cryptographic hashes are slower with no benefit here.

Recommendation

Use consistent hashing whenever you have N stateful nodes and the set of N changes over time. Always use 100-1000 virtual nodes per physical node — not negotiable for load balance. Walk clockwise for replication, with topology awareness for AZ/rack separation. For load balancers needing strict per-node load bounds, look at Google's bounded-load variant (Maglev). For append-only sharding with O(1) memory, jump consistent hash. Otherwise the standard ring + vnodes is the workhorse used by Cassandra, DynamoDB, Memcached clients, and most CDN routing.