Consistent Hashing: Scaling Caches Without Remapping Every Key

You have four cache servers and route each key with hash(key) % 4. It works perfectly—until you add a fifth server.

Almost every key maps somewhere new. The cache miss rate explodes, the database absorbs the refill traffic, and adding capacity causes the outage it was meant to prevent.

Consistent hashing was designed for exactly this problem.

Why Modulo Hashing Breaks

const server = servers[hash(key) % servers.length];

With four servers, a key whose hash is 14 goes to index 2:

14 % 4 = 2

After adding a server:

14 % 5 = 4

The same key moves. Because the divisor changed, most remainders change. Adding one node can remap roughly N / (N + 1) of the keys—80% when moving from four nodes to five.

That is acceptable for a one-time batch partition. It is painful for a live cache or distributed store.

Put Nodes on a Ring

Consistent hashing maps both nodes and keys into the same fixed hash space.

             0 / 2^32
                ● A
           ↗           ↘
       D ●               ● B
           ↖           ↙
                ● C

To place a key:

1. Hash the key to a point on the ring
2. Walk clockwise
3. Choose the first node token encountered

If the key lands between A and B, it belongs to B. The number of nodes is never part of the hash calculation.

Adding a Node Moves One Range

Insert node E between A and B:

before: keys in (A, B] → B
after:  keys in (A, E] → E
        keys in (E, B] → B

Only the range that E takes from B moves. Other nodes keep their keys. With evenly distributed nodes, adding one to an N-node cluster moves about 1 / (N + 1) of the keys.

Removing a node has the same local property: its range moves to the next node clockwise.

One Token Per Node Is Not Enough

Hashing each physical node once can produce badly uneven ranges:

A owns 8% of ring
B owns 51% of ring
C owns 17% of ring
D owns 24% of ring

Cryptographic hashes are uniform over many samples, but four samples are still four random points. Use virtual nodes: place each physical server on the ring many times.

A#0 A#1 A#2 ... A#199 → physical server A
B#0 B#1 B#2 ... B#199 → physical server B

Hundreds of smaller ranges average out the imbalance. Virtual nodes also support capacity weighting: a server with twice the capacity can receive roughly twice as many tokens.

A Small Implementation

import crypto from 'node:crypto';

function hash32(value) {
    const digest = crypto.createHash('sha256').update(value).digest();
    return digest.readUInt32BE(0);
}

class HashRing {
    constructor(nodes, virtualNodes = 200) {
        this.ring = [];

        for (const node of nodes) {
            for (let i = 0; i < virtualNodes; i++) {
                this.ring.push({
                    token: hash32(`${node}#${i}`),
                    node,
                });
            }
        }

        this.ring.sort((a, b) => a.token - b.token);
    }

    getNode(key) {
        if (this.ring.length === 0) throw new Error('empty hash ring');

        const token = hash32(key);
        let low = 0;
        let high = this.ring.length;

        // Find the first ring token >= the key token.
        while (low < high) {
            const mid = Math.floor((low + high) / 2);
            if (this.ring[mid].token < token) low = mid + 1;
            else high = mid;
        }

        // Wrap past the largest token to the beginning of the ring.
        return this.ring[low % this.ring.length].node;
    }
}

const ring = new HashRing(['cache-a', 'cache-b', 'cache-c']);
ring.getNode('user:42');

Production implementations handle duplicate tokens, membership changes, node health, weights, and replication. Use a mature library unless building the ring is the point of the project.

Every client must also agree on the hash function, token encoding, node names, and membership view. A mixed deployment with different ring definitions silently routes the same key to different servers.

Replication

One owner is not enough for durable data. To choose replicas, continue clockwise and select the next distinct physical nodes.

key owner:    A#37 → server A
replica 1:    C#91 → server C
replica 2:    B#12 → server B

Skip other virtual tokens belonging to A. Otherwise several "replicas" could land on the same machine.

Real systems also spread replicas across failure domains—different hosts, racks, or availability zones. A ring that ignores topology can lose every copy to one power failure.

Rebalancing Is Still Work

Consistent hashing minimizes movement; it does not move the data for you.

For a cache, the new node can fill lazily as requests miss. That is simple but can create a database spike. Prewarming or rate-limited migration may be safer.

For durable storage, the system must stream ownership ranges, verify replicas, handle writes during transfer, and only then remove old copies. Membership changes need a controlled protocol, not merely an updated array in each client.

Hot Keys Ignore a Balanced Ring

Equal key counts do not mean equal load.

10 million cold keys → almost no traffic
one celebrity key    → 40,000 requests/second

Consistent hashing sends the hot key to one owner. Virtual nodes cannot split one key across servers.

Mitigations include:

• Replicate hot read-only values and choose among replicas
• Add a small local cache in each application instance
• Split an aggregatable hot key into shards with a suffix
• Coalesce concurrent cache misses
• Detect hot keys and apply special routing deliberately

Monitor requests, bytes, CPU, and latency per node—not only number of assigned tokens.

Rendezvous Hashing: A Useful Alternative

Rendezvous, or highest-random-weight hashing, scores every (key, node) pair and chooses the highest score.

function chooseNode(key, nodes) {
    return nodes.reduce((best, node) => {
        const score = hash32(`${key}:${node}`);
        return !best || score > best.score ? { node, score } : best;
    }, null).node;
}

It also minimizes movement and makes selecting the top N replicas straightforward. The naive version hashes every node per lookup, while a ring performs a hash plus binary search. For a small node set, rendezvous hashing is often simpler.

The Bottom Line

Consistent hashing decouples key placement from the number of servers.

The rules:

• Avoid modulo hashing when live membership changes are expected
• Use many virtual nodes to smooth random range sizes
• Weight token counts for meaningfully different node capacities
• Keep hash and membership definitions identical across clients
• Choose replicas on distinct physical and failure-domain nodes
• Plan the actual data transfer during membership changes
• Monitor workload balance, not only key-space balance
• Consider rendezvous hashing for small clusters and simple replication

The ring does not make distributed storage easy. It solves one precise problem: changing the cluster without changing almost every answer.