Consistent Hashing

Say you're sharding a cache across N servers, and the routing rule is the obvious one: server = hash(key) % N. It works, until N changes — a server dies, or you add one to handle more load. The moment N becomes N±1, almost every key's assigned server changes, because the modulus in hash(key) % N is different for nearly every key. A cache that was 95% warm is now 95% empty, and every one of those requests goes to the database at once. That's the problem consistent hashing exists to solve.

The ring

Instead of hashing keys onto a range of size N (the server count), hash both keys and servers onto the same large fixed range — conventionally visualised as a ring, 0 to 2³²−1 wrapping back to 0. Each server occupies one point on the ring (hash(serverId)). To find where a key lives: hash the key onto the same ring, then walk clockwise to the first server you hit.

Drawn as a cycle rather than a physical circle (a flowchart diagram doesn't lay out in the round, but the connectivity is the same thing a true ring drawing shows — server C's clockwise neighbour is A, wrapping back around):

Each key follows the dotted arrow to the first server it reaches going clockwise — user-42 hit the ring between A and B, so it belongs to B. Now remove server B: user-42 recomputes to the next clockwise server, C — while user-7 and user-99 are completely unaffected, because nothing about their position or C's and A's positions changed.

That's the entire idea, generalised: adding or removing a server only moves the keys on the arc between that server's position and its counterclockwise neighbour. Everything else keeps its nearest clockwise server exactly as before. Removing one server of five moves roughly 1/5 of the keys, not (N-1)/N of them the way the modulus scheme would — only the keys adjacent to the change are affected, everything else stays put.

TreeMap<Long, String> ring = new TreeMap<>(); // position -> server id

String serverFor(String key) {
    long h = hash(key);
    Map.Entry<Long, String> e = ring.ceilingEntry(h); // first server clockwise
    return e != null ? e.getValue() : ring.firstEntry().getValue(); // wrap around
}

TreeMap here isn't incidental — it's the same reason a database reaches for a B-tree (see Indexing and B-Trees): the ring needs "find the smallest key ≥ this value" in O(log n), which is exactly what an ordered structure gives you and a plain hash map can't.

The load-imbalance problem, and virtual nodes

A ring with only a few real servers on it isn't evenly spaced — one server might, by chance, own a much larger arc than another, taking a disproportionate share of the traffic. The fix is virtual nodes: instead of placing each physical server once, place it at many points on the ring (100–200 is typical), each labelled distinctly (hash("server-3-vnode-17"), etc.). Now every physical server owns many small, scattered arcs instead of one large one, and the law of large numbers does the rest — with enough virtual nodes, each server's total share converges close to 1/N regardless of where the hash function happened to place any individual point. It also fixes a second problem: when a server does join or leave, its virtual nodes are scattered around the ring, so the extra load from a departure lands on many servers a little each, instead of dumping entirely onto whichever one server happened to be its single clockwise neighbour.

Real-world use

• Amazon's Dynamo paper (2007) is where this technique entered mainstream distributed-systems practice, specifically to let the cluster add and remove nodes without a full reshuffle; Cassandra and Riak both inherited the same approach directly from it.
• Memcached client libraries (the "ketama" scheme) use consistent hashing entirely on the client side — the cache servers themselves know nothing about it, each client just needs the same ring to agree on where a key lives.
• CDNs and load balancers use it to route a given request key (a user id, a session, a cache key) to the same backend consistently, so that backend's local cache stays warm across requests — "consistent" here means the same key keeps landing on the same node, not that every node sees the same data.
• Database resharding — Cassandra's and DynamoDB's own partition placement is consistent hashing under the covers, which is why adding a node to either only requires copying roughly 1/N of the data rather than rebalancing the whole cluster.

What interviewers push on

• "Why not just rehash everything when N changes?" — because for a cache, that's indistinguishable from a full cold start under load, and for a database, it's a full data migration under load. The whole point is avoiding exactly that.
• "What about hot keys?" Consistent hashing balances key space, not traffic — a single extremely popular key still sends all its traffic to one node regardless of how evenly the ring is spaced. That needs a different mechanism (request-level caching in front of the shard, or splitting that one key's data further) — noticing consistent hashing doesn't solve this is a real signal in an interview.
• Replication factor. Real systems usually don't stop at the first clockwise server — they replicate to the next R−1 servers walking the ring, so one node's failure doesn't lose the data outright. Mentioning this is the difference between describing the routing trick and describing the system that's actually built on it.

Practice it

There's no problem here that asks you to implement the ring itself — the skill this shows up in is recognising, on a caching or sharding brief, that "add a node" and "the cache goes cold" don't have to be the same event.

System-design problems