Why Adding 1 Server Can Remap 80% of Your Keys

You have four cache nodes, and everything is working fine. Then traffic grows, you add a fifth node, and suddenly a huge chunk of your keys point to different servers.

That can mean cache misses everywhere, more traffic hitting your database, and large amounts of data moving between nodes, which can overload disks and networks. If the system handles it badly, you have an incident.

Consistent hashing is designed to shrink that problem. To see how, start with the way most systems decide which server owns a key.

Say you have four cache servers, Node 0 through Node 3, and you need to store user_12345. The system needs a repeatable way to pick the owner. A very common approach is:

The hash function turns the key into a number, and the remainder picks the node:

As long as the node count stays the same, the same key always lands on the same server. It's simple and fast, and it works well until the cluster size changes.

Say one node is getting full, so you add a fifth. The rule goes from hash(key) % 4 to hash(key) % 5.

It looks like a tiny change, but changing the divisor changes the result for most keys. Take 100 keys numbered 0 to 99 and, to keep it simple, treat each key's number as its hash. Compare key % 4 with key % 5, and 80 of the 100 keys end up on a different node.

It depends on what the servers hold.

A moved key is usually a cache miss. One miss is harmless, but millions of keys remapping at once is not. The new owners don't have those values yet, so requests fall through to the database, and a routine scaling event turns into this:

This is one reason cache scaling needs care.

Now it gets harder. If a key moves from Node A to Node B, Node B can't serve that record until the data is copied over. While the copy runs:

Changing the routing formula is easy. Safely moving the state behind it is the hard part.

Modulo sharding works fine when the shard count is fixed. It gets expensive when nodes are expected to join and leave regularly.

Consistent hashing changes the placement model. Instead of computing hash(key) % number_of_nodes, you put nodes and keys in the same hash space and wrap that space into a circle, usually called a hash ring. A key belongs to the first node you reach moving clockwise from the key's position.

Take a tiny ring with positions 0 to 100 and put four servers on it:

Then hash each key to a position on the ring:

So the ownership ranges look roughly like this:

This is where consistent hashing becomes useful.

Now add E at position 62.5. Before E joined, D owned (50, 75]. After:

Only the keys in that one slice of the ring change owners, and everything else stays where it was. With our 0 to 99 keys, keys 51 through 62 move from D to E. That's 12 keys.

The 12 comes from where we deliberately placed E. In a well-balanced five-node ring, adding one equally weighted node would typically move roughly one-fifth of the keys. Whatever the exact share, adding a server only touches part of the keyspace, and the rest of the cluster keeps serving the same keys. That stability is the "consistent" in consistent hashing.

Instead of giving each physical server one position on the ring, give it several. These positions are called virtual nodes, or vnodes. So instead of:

you get something closer to:

There are still only four physical servers, but each one owns several smaller ranges instead of one large one. That improves distribution, and it helps when a server joins. The new server takes small ranges from several existing servers instead of one giant range from a single neighbour, which spreads the rebalancing work across the cluster. Systems inspired by Dynamo and Cassandra have used this idea extensively.

If more vnodes means better distribution, why not use as many as possible? Because every extra token adds metadata and more range relationships for the system to track. In replicated systems, it can also add work during data streaming, repair, node replacement, membership changes, and failure recovery.

The right vnode count depends on cluster size, replication factor, the implementation, node capacity, migration bandwidth, and operational overhead.

Say one key is customer_123, and that customer suddenly produces 40% of all requests. That key still has one primary owner. You can spread a million normal keys perfectly and still overload one server because a single key is extremely hot.

The same goes for bytes stored, CPU usage, latency, and request rate. A ring can look perfectly balanced by key count while one node is melting.

Most explainers stop at "add a node, only some keys move." That covers the placement algorithm, but it doesn't explain how the system survives the move. A distributed system has three separate problems here.

Who should own this key? Consistent hashing helps answer that: user_123 --> Node C.

Say you want three copies of every key. Where do the other two live? You can't just pick random nodes without thinking about failure domains. Three replicas in the same rack or availability zone don't protect you much if that whole zone goes down. Real systems may account for physical hosts, racks, availability zones, and regions. Consistent hashing alone doesn't handle this.

This is the operational part. A key used to belong to Node D, and after a new node joins it belongs to Node E. That doesn't mean E has the data yet. The system still has to move it safely. A simplified migration might look like this:

Different databases do this differently. Some use redirects, routing-table updates, streaming, write fencing, dual writes, or background repair.

Consistent hashing limits what has to move. It doesn't do the moving. That distinction comes up a lot in both system design and production debugging.

"Consistent hashing" is often used loosely, and different systems solve this problem in different ways.

Cassandra is heavily influenced by Dynamo-style partitioning. Nodes own token ranges, and replication decides which other nodes store copies. Modern Cassandra deployments may use multiple tokens per physical node.

Redis Cluster works differently. It divides the keyspace into 16,384 fixed hash slots. Keys map to slots, and slots map to nodes. When the cluster changes, Redis moves specific slots and their keys between nodes. That gives operators explicit migration units instead of a plain ring.

Ceph adds another layer of indirection. Objects map to placement groups, and placement groups map to storage devices. The goal is still to change the cluster without moving everything.

Different system, same underlying distributed-systems problem.

Modulo hashing isn't bad. It's a good choice when your shard count rarely changes, migrations are planned, simplicity matters, or you can afford to reshuffle now and then.

Consistent hashing becomes more attractive when nodes regularly join or leave, remapping keys is expensive, cache misses are costly, or large-scale data movement is undesirable.

Other strategies fit other requirements:

No placement algorithm wins everywhere. The right one depends on your workload.

👋 Find me on Twitter | Linkedin | Connect 1:1

Thank you for supporting this newsletter.
Y’all are the best.