Consistent Hashing

Consistent hashing was introduced by David Karger et al. in their 1997 paper as a solution for distributing web cache content across a changing set of servers. The core insight is that both keys and nodes are mapped onto the same circular hash space (a ring from 0 to 2^m - 1), and each key is assigned to the first node encountered when walking clockwise from the key's position on the ring. When a node is added, it takes over a portion of the ring from its clockwise neighbor, and only the keys in that portion need to be moved. When a node is removed, its keys fall to the next clockwise node. In either case, only K/N keys are redistributed on average (where K is total keys and N is total nodes), compared to the nearly complete reshuffling that hash(key) mod N requires when N changes.

The naive implementation of consistent hashing has a significant problem: with a small number of physical nodes, the ring segments are likely to be uneven, causing some nodes to own far more keys than others. Virtual nodes (vnodes) solve this by assigning each physical node multiple positions on the ring -- typically 100 to 256 virtual nodes per physical node. Each virtual node is a point on the ring that maps back to its physical host. With enough virtual nodes, the statistical variation in segment sizes shrinks dramatically, producing near-uniform distribution. The Dynamo paper (2007) used 150 virtual nodes per physical node, and Cassandra defaults to 256.

Several important variants and alternatives have emerged since the original paper. Jump consistent hashing (Lamping and Veach, 2014 from Google) uses zero memory -- it computes the assigned bucket using only arithmetic, with perfect distribution across N buckets. However, it only supports appending or removing the last bucket, making it unsuitable for arbitrary node failures. Bounded-load consistent hashing (Google, 2017) addresses load imbalance by capping the maximum load any single node can handle at (1 + epsilon) times the average load, redirecting overflow to the next node on the ring. Rendezvous hashing (also called Highest Random Weight or HRW hashing) takes a different approach entirely: for each key, it computes a score for every node using hash(key, node_id), and assigns the key to the node with the highest score. This achieves similar redistribution properties to consistent hashing without needing a ring abstraction.

Consistent hashing is a foundational building block for modern distributed infrastructure. CDNs like Akamai (the company co-founded by Karger himself) use it to route requests to cache servers, minimizing cache misses when servers are added or removed. Distributed databases like DynamoDB and Cassandra use it for data partitioning. Load balancers use it for sticky session routing. Discord uses it to assign guilds (servers) to backend processes. In every case, the value proposition is the same: the ability to add and remove nodes from a cluster with minimal data movement, enabling elastic scaling without the thundering-herd cache-miss storms that plague mod-N approaches.

Imagine a circular parking lot with spots numbered 0-359 (like degrees on a compass). Four attendants are stationed at positions 0, 90, 180, and 270. When a car arrives, the driver is given a ticket with a random number from 0-359. The driver parks at the first attendant's section they reach by driving clockwise from their number. Car #45 drives to the attendant at 90. Car #200 drives to the attendant at 270. Now a fifth attendant is added at position 135. Only cars parked between 90 and 135 need to move to the new attendant -- everyone else stays put. If attendant 90 goes on break, only their cars (parked between 0 and 90) move to attendant 135. The lot keeps working smoothly with minimal car shuffling.