The interview question. A cache cluster has four servers. Its routing code chooses hash(key) % server_count. You add a fifth server to gain 25 percent more capacity. Most requests suddenly miss the cache, the database is flooded, and the new server is barely warm. Explain what changed. Design a placement scheme that moves substantially fewer keys when nodes join or leave.
Assume keys hash uniformly for this calculation, each server has the same capacity, and replicas are outside the first part of the exercise. We are discussing which server owns a key, not how its value is copied safely to that server.
Think first
A cache with four equally sized servers uses hash(key) % 4. You add a fifth and want the same key ownership stability that a much larger cluster provides. Estimate movement for the old scheme and propose two better placement policies. Then explain what happens if half the clients are still running the old router.
Take a few minutes to form an approach, then compare it with the worked explanation.
Reveal the worked explanation
A tiny formula made membership expensive
Modulo looks like a reasonable distribution mechanism. With four servers, hash(key) % 4 gives a bucket from zero to three. Over many keys, each bucket receives roughly a quarter of the hash space.
But after adding a server, the denominator changes. A key whose hash was 18 used to go to bucket 2 because 18 % 4 = 2. Now 18 % 5 = 3, so it goes somewhere else. This is not a balancing adjustment at the margin. Almost every bucket calculation is being replaced.
For uniformly distributed integer hashes, compare the mappings over any twenty consecutive hash values. Old and new bucket numbers agree for only four of those twenty values. About 80 percent of keys move when going directly from four buckets to five. That fraction is for this modulo scheme and membership change, not a universal law about sharding.
The same keys map to mostly different owners under modulo four and modulo five, while stable hash-space partitions allow only selected ownership ranges to move
On a cache, movement often means cold misses. On a durable store, it means physically transferring data while requests continue. The formula changes quickly, but the bytes and the old clients do not.
Keep key placement stable while membership changes
Consistent hashing starts with a stable hash space. Hash both keys and server positions into that space. Walking clockwise from a key position finds its owner. When a new server is placed on the ring, it takes the keys in its newly owned arc. Other arcs remain with their previous owners.
For an evenly balanced five-server ring, the new server should own about one fifth of the key space. In expectation, roughly 20 percent of keys change owners, rather than 80 percent. The important distinction is that a node addition changes ownership of a portion of the stable space, not the calculation for every key. Real ring placement may be uneven.
There is a catch. With only one randomly chosen ring position per physical server, one machine may get a huge arc while another gets a tiny one. Virtual nodes improve the granularity. Instead of putting one token on the ring for each server, put multiple tokens per server and distribute those tokens around the ring. This typically smooths ownership and allows capacity weighting.
More tokens do not make the system free. They increase the number of ownership ranges, which affects routing metadata and the work of moving or repairing ranges. For servers of unequal capacity, allocate ownership weights deliberately rather than assuming the same virtual-node count always works.
Also consider whether a ring is the simplest solution. A stable set of logical hash buckets can be mapped through a small placement directory onto physical servers. Redis Cluster, for example, uses 16,384 hash slots rather than a consistent hash ring. Moving some slots changes their physical owners without changing the way every key computes its logical slot. Redis Cluster scaling
Both approaches separate stable key identity from changing server membership, but their metadata and routing tradeoffs differ. A directory supports explicit placement. A ring computes ownership from membership and tokens. Neither makes data migration automatic.
The rollout needs more than a new hash function
You cannot introduce a new placement scheme by silently deploying new routing code to half the clients. Old clients may send writes to the previous owner while new clients use the new one. That is dangerous even before anyone moves a byte.
For an existing modulo cluster, I would treat the change as an explicit migration. Establish a versioned placement map, migrate keys under a controlled ownership protocol, and teach clients how to refresh or redirect when their map is stale. If this is only an expendable cache, an intentional staged cold start may be acceptable, but admission control and origin protection must be sized for it. For durable data, you need a migration with no conflicting write owners. A later lesson will walk through that cutover.
During a cache expansion, measure keys remapped, bytes scheduled to transfer, misses by key group, origin QPS, and cache hit recovery. A dashboard showing that the new server is healthy does not tell you whether the database is about to drown in misses.
If you benchmark, use a real key distribution, not just a uniform random stream. Stable placement controls how many keys move after membership changes. It cannot promise that a popular key suddenly uses several machines. One key may still receive a large share of traffic regardless of the number of servers.
That distinction leads to the next interview question: We fixed how keys move. Why is one shard still overloaded while the others are quiet?
Go deeper
Go deeper: the costs hidden by a pretty hash ring
Lookup alternatives. Rendezvous hashing assigns each key to the server with the highest key-server score. It also limits remapping when membership changes. A naive lookup evaluates every server, although optimizations and hierarchy can change the cost. A ring can use a sorted token map and a successor lookup. Neither algorithm removes the need to distribute a consistent membership view.
Placement versus replicas. A production cluster often chooses several distinct replica owners in different failure domains. Consistent hashing alone does not ensure two selected replicas are in separate racks or availability zones. Replica selection and placement constraints need additional rules. The movement fraction for multiple replicas is more complicated than the simple single-owner example.
Cache safety. Replacing a cache fleet in one burst can multiply misses at the origin. Warm target owners gradually, bound refill concurrency, and consider serving old placements briefly while transitioning. For data requiring strong write ownership, do not let "serve old placements" quietly become accepting writes on two owners.
One number to remember. The 80 percent calculation assumes old bucket h % 4, new bucket h % 5, equal hash likelihood, and matching numeric bucket identities. Relabeling the same four existing servers across four of the five new numeric buckets does not change this fraction for uniform hashes: each old/new bucket pair occurs once per twenty hash values. Nonuniform hashes, non-bijective owner assignments, or a different membership change require a new calculation. This example illustrates a bad dependency on membership count, not a universal expectation for arbitrary mapping tables.
Check your reasoning
Calculate roughly 80 percent remapping for uniform integer hashes when going from modulo 4 to modulo 5.
Explain why consistent hashing moves only affected key ranges and why virtual nodes help uneven ownership.
Offer stable logical buckets mapped to servers as a separate option rather than incorrectly calling Redis Cluster a hash ring.
Distinguish routing-change math from physical key copy, replication, and cache warming.
Describe versioned placement and stale-client behavior during migration.
Common mistake: Claiming a consistent hash ring automatically migrates bytes or guarantees uniform load for a very hot key.
Read the answer explanation
About 20 percent. — Over 20 consecutive hash values, only four produce matching bucket numbers under both moduli.
Apply it elsewhere
A serverless job scheduler places tenants using hash(tenant) % worker_count. Auto-scaling doubles workers every morning. What changes beyond a new hashing function?
Compare your approach
Keep a stable assignment layer and migrate or drain ownership deliberately. A scheduled job must not run concurrently on old and new owners.
One more constraint
The new server has double the RAM of the others. How should placement account for unequal weights?
Quick revision
With hash(key) % N, changing N changes the destination of many existing keys. For four to five buckets, uniform hashes preserve the same numeric bucket only 20 percent of the time. Consistent hashing or stable logical hash slots keep most key ownership unchanged and move a smaller fraction of keys when a node joins. Virtual nodes or weighted slots improve balancing, but routing stability does not itself copy data, preserve replica placement, or stop a hot key. Old clients and write ownership still require a migration protocol.
