Hashing Schemes

Consistent Hashing

Spread keys over a ring of servers so that adding or removing one moves almost nothing.

Servers (ticks) and keys (dots) sit on one hash ring; each key is owned by the next server clockwise and colored to match. When a server joins, only the keys in its arc — ringed in white — change hands. Each server has several virtual nodes to even the load.

What you're seeing

The naive way to shard K keys across n servers is server = hash(key) mod n. It balances well — until n changes. Add or remove one server and nearly every key's mod n result changes, so almost the whole dataset has to move: catastrophic for a cache or a distributed store. Consistent hashing fixes this by placing both servers and keys on a circular hash space, the ring. A key belongs to the first server you meet going clockwise from the key's position. Now adding a server only steals the keys in the arc just behind it; everyone else stays put. Watch each new server light up only a handful of keys (ringed white) as it joins.

The rule

place each server at hash(server) on the ring [0, 2^m)
lookup(key):
    h = hash(key)
    return the first server at position ≥ h  (wrapping around the ring)
add/remove server:  only the keys between it and the previous server move

Lookups use a sorted structure of server positions and a binary search, so they cost O(log n).

The invariant

The guarantee that makes it "consistent" is about change, not correctness: adding or removing a server reassigns only the keys in that server's arc — about K/n of them — leaving the rest untouched. A key moves only if the set of servers in the clockwise arc from it changes, and inserting one server can only affect keys that now find it first; removing one sends only its keys to the next server clockwise. In expectation each server owns a 1/n fraction of the ring, so a membership change touches an expected K/n keys — versus the (n−1)/n that mod n reshuffles. The trade-off is balance: with one point per server the arc lengths are uneven (some servers get far more than K/n), so each server is hashed to several virtual nodes scattered around the ring; the more replicas, the tighter the load concentrates around K/n — a direct consequence of averaging many independent arcs. Slide the virtual-node count up and watch the per-server loads converge.

The cost

lookupkeys moved on resize Consistent hashingO(log n)≈ K/n hash mod nO(1)≈ K·(n−1)/n

Lookup is a binary search over the (n · vnodes) ring positions; insert/delete of a server is O(vnodes · log n). The headline win is the resize cost: from "move almost everything" to "move one server's share." The cost is some metadata for virtual nodes and slightly slower lookups than a plain modulo. Variants trade off further: rendezvous (HRW) hashing gets the same minimal-movement property without storing ring positions, and jump consistent hash is a tiny, fast, memory-free version when servers are numbered 0..n−1.

In the wild

Consistent hashing (Karger et al., 1997, originally for web caching) is foundational distributed-systems infrastructure. It places data in Amazon Dynamo and its descendants Cassandra and Riak, distributes keys in client-side memcached sharding, routes requests in load balancers and service meshes, and underlies content-addressing in CDNs and peer-to-peer DHTs (Chord). Any system that adds and removes nodes while serving a partitioned dataset reaches for it, precisely because rebalancing is cheap.

Try this

Step through the servers joining: the readout's "keys moved" stays near K/n each time, never the whole set. Then push Virtual nodes each from 1 upward and watch the per-server loads in the legend converge toward an even split — that's the law of large numbers smoothing out the arc lengths. Drop it back to 1 and the imbalance returns.

References

  1. Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M. & Lewin, D. "Consistent Hashing and Random Trees…" STOC, 1997.
  2. DeCandia, G. et al. "Dynamo: Amazon's Highly Available Key-value Store." SOSP, 2007 — consistent hashing with virtual nodes in production.
  3. Lamping, J. & Veach, E. "A Fast, Minimal Memory, Consistent Hash Algorithm" (jump hash), 2014; Thaler & Ravishankar, rendezvous (HRW) hashing, 1998.