Consistent hashing

Why it matters

Any system that spreads keys over nodes faces the same moment: a node is added or fails, and the mapping must change. With naive hashing almost every key moves, which empties a cache or triggers a massive data migration. Consistent hashing is the technique that bounds the movement to roughly the share of the node that changed. It is the mechanism under distributed caches, Dynamo-style databases, Cassandra's token ring and many load balancers, and it is a near-certain interview question because the idea is simple and the consequences are large.

The idea

Hash both nodes and keys onto the same circular space (say 0 to 2^32). A key belongs to the first node clockwise from its position. When a node joins, it takes over only the arc between its predecessor and itself; when a node leaves, its arc goes to its successor. Everything else stays where it was. Expected movement on a change with N nodes is about 1/N of the keys, instead of nearly all of them with mod N.

Virtual nodes

With a handful of physical nodes placed randomly, arcs are very uneven: one node might own 40 percent of the ring. The fix is virtual nodes: each physical node is hashed onto the ring at many points (100 to 200), so its total share is the sum of many small arcs and evens out statistically. Virtual nodes also let a more powerful machine take more points, and when a node leaves, its arcs are spread across many successors rather than dumped on one.

Replication along the ring

Dynamo-style stores replicate each key to the next R distinct physical nodes clockwise from its position, so a key's replicas are its owner and the owner's successors. When a node fails, its successor already holds a copy and traffic shifts naturally; hinted handoff lets a temporary stand-in hold writes for a down node and deliver them when it returns.

Variants

	Ring with virtual nodes	Rendezvous (highest random weight)	Jump consistent hash
How	Nodes and keys on a circle; next clockwise owns the key	For each key, score every node with hash(key, node); the highest score wins	Arithmetic function mapping key to bucket index in [0, N)
Movement on change	~1/N	Exactly the removed node's keys	Minimal, provably
Balance	Good with enough virtual nodes	Excellent	Excellent
Cost per lookup	O(log V) binary search over virtual nodes	O(N) over nodes	O(log N), no state
Fits	Large clusters, weighted nodes, Cassandra, caches	Small node sets, load balancers, picking k replicas	Fixed-size bucket arrays that only grow at the end

Where it fits and where it does not

Consistent hashing shines when membership changes are frequent and unplanned (cache nodes, stateless-ish storage nodes, request routing to sticky backends) and when data can move on its own as a side effect of the mapping. For a relational shard set with heavy migrations, directory-based routing (a table from logical bucket to physical shard) gives explicit control: you move a bucket when you decide to, not when the hash says so, and you can place a hot tenant deliberately. Many systems combine them: many fixed logical buckets assigned by hash, with a directory mapping buckets to nodes.

Trade-offs

Consistent hashing buys bounded rebalancing and decentralised routing (any node can compute the owner) and pays with the statistical unevenness that virtual nodes mostly fix, the inability to place specific keys deliberately, and the lookup structure that must be kept in sync across routers. Directory routing is the explicit alternative with central state; the right choice depends on how much control over placement you need.

In an interview

Show the mechanism and the refinement: "Cache keys are placed with consistent hashing, 150 virtual nodes per server, so adding a server moves about one-N-th of keys and the miss burst is bounded. For the database shards we use 1,024 logical buckets with a directory, because we want to move hot tenants deliberately." Knowing both tools and when each applies is the senior answer.