What is Consistent Hashing?

Consistent hashing is how you spread keys or data across a set of servers so that adding or removing a server moves only a tiny fraction of the keys instead of almost all of them. It is the partitioning layer inside Cassandra, DynamoDB, Discord, and Akamai's CDN, and it is a common interview question on its own. To see why it matters, start with the naive approach and watch it fall apart.

The problem: plain modulo hashing

Say you have 4 cache servers and you spread keys across them with the obvious formula:

serverIndex = hash(key) % N   // N = number of servers

Hash the key, take it modulo 4, and that is the server. With N = 4 it works fine and the load spreads evenly. Here are 8 keys:

Key	hash(key)	hash % 4	Server
key0	18358617	1	s1
key1	26143584	0	s0
key2	18131624	0	s0
key3	35863496	0	s0
key4	34085998	2	s2
key5	27581815	3	s3
key6	38234801	1	s1
key7	32903924	0	s0

Now s1 goes offline, so N drops to 3 and the formula becomes hash % 3. The hashes did not change, but the modulo did:

Key	hash(key)	hash % 3	Server (was)
key0	18358617	0	s0 (was s1)
key1	26143584	0	s0 (was s0)
key2	18131624	2	s2 (was s0)
key3	35863496	2	s2 (was s0)
key4	34085998	1	s1... gone
key5	27581815	1	remapped
key6	38234801	2	s2 (was s1)
key7	32903924	2	s2 (was s0)

Almost every key moved, not just the ones that lived on the dead server. In a cache that is a disaster: every client now computes a different server for the same key, so almost nothing is where it is expected, and you get a storm of cache misses that all fall through to the database at once. The same thing happens when you add a server. Plain modulo hashing couples every key's location to the exact server count, so any change reshuffles everything. This is exactly the pain you hit when scaling a cache tier or sharding a database by simple modulo.

The core idea: a hash ring

Consistent hashing breaks that coupling. Formally, when the number of servers changes, only about k/n keys need to move on average (k = number of keys, n = number of servers) - not nearly all of them.

Here is how it works. Take your hash function's whole output range - for SHA-1 that is 0 to 2^160 - 1 - and bend that line into a ring, so the largest value wraps around to meet 0. Then:

1. Place the servers on the ring by hashing each server's IP or name. Each server lands at some point on the circle.
2. Place the keys on the ring with the same hash function (no modulo this time).
3. To find a key's server, walk clockwise from the key's position until you hit the first server. That server owns the key.

That clockwise-walk rule is the whole trick. A key belongs to whichever server is the next one clockwise. Nothing depends on the total server count, so changing that count no longer reshuffles everything.

Adding a server moves almost nothing

Add a new server s4 onto the ring. Only the keys sitting in the arc between s4 and the previous server change owners - everything else stays put:

Before, key0 walked clockwise to s0. Now s4 sits between key0 and s0, so key0 stops at s4. Just that one key moved. The other three never noticed.

Removing a server moves almost nothing

Remove s1. Only the keys that s1 owned need a new home - they simply continue clockwise to the next server. Every other key is untouched:

key1 used to stop at s1; with s1 gone it walks on to s2. That is the only key that moved. Compare this to the modulo version where the same event remapped almost every key. This is the property that makes horizontal scaling cheap: grow or shrink the cluster and you pay to move a small slice of data, not the whole dataset.

Two problems with the basic ring

The basic algorithm - introduced by Karger et al. at MIT - has two weaknesses once servers are placed at just one point each.

Uneven partitions. A server's share of the ring is the arc between it and the previous server, and hashing servers to single random points makes those arcs different sizes. Worse, when a server is removed its whole arc merges into its neighbor's, which can leave one server owning a huge slice.

Hotspots. Because the arcs are uneven, keys pile up unevenly too. One server can end up owning most of the keys while others own almost none:

Here s2 is overloaded and s0 and s3 are nearly idle. That defeats the point of spreading the load.

Virtual nodes fix the balance

The fix is virtual nodes: instead of placing each server at one point, place it at many. Server s0 is hashed to several positions - s0_0, s0_1, s0_2, and so on - and so is every other server, all interleaved around the ring. Each server now owns many small arcs scattered around the circle rather than one big one:

A key still just walks clockwise to the first virtual node it meets, and that virtual node maps back to a real server. Because each server is sprinkled across the ring in many pieces, the load evens out - and it evens out more as you add virtual nodes, since the variation in each server's total share shrinks. An experiment by Tom White found the standard deviation of the load drops to about 10% of the mean with 100 virtual nodes per server and about 5% with 200. The trade-off is memory: more virtual nodes means more position data to store, so you tune the count to balance evenness against overhead. Real systems use anywhere from a hundred to a few hundred per server.

Implementing it

Put it together and it is a sorted ring of virtual-node hashes plus a binary search for the clockwise lookup:

import { createHash } from "crypto";

class ConsistentHash {
  // Sorted list of hashes on the ring, and a map from hash -> real server.
  private ring: number[] = [];
  private nodeForHash = new Map<number, string>();

  constructor(private virtualNodes = 150) {}

  private hash(value: string): number {
    // Use the first 8 hex digits of a SHA-1 as a 32-bit ring position.
    const digest = createHash("sha1").update(value).digest("hex");
    return parseInt(digest.slice(0, 8), 16);
  }

  addServer(server: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const h = this.hash(server + "#" + i); // one hash per virtual node
      this.nodeForHash.set(h, server);
      this.ring.push(h);
    }
    this.ring.sort((a, b) => a - b);
  }

  removeServer(server: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const h = this.hash(server + "#" + i);
      this.nodeForHash.delete(h);
    }
    this.ring = this.ring.filter((h) => this.nodeForHash.has(h));
  }

  // Walk clockwise from the key's hash to the first virtual node on the ring.
  getServer(key: string): string {
    if (this.ring.length === 0) throw new Error("no servers");
    const h = this.hash(key);

    // Binary search for the first ring position >= h.
    let lo = 0, hi = this.ring.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.ring[mid] < h) lo = mid + 1;
      else hi = mid;
    }
    // If h is past the last node, wrap around to the first (the ring closes).
    const pos = this.ring[lo] >= h ? lo : 0;
    return this.nodeForHash.get(this.ring[pos])!;
  }
}

The lookup is O(log V) where V is the total number of virtual nodes, and adding or removing a server only rehashes that one server's virtual nodes.

The limits - what consistent hashing does not solve

It is not magic, and an interviewer may probe the edges:

• It spreads keys, not a single hot key. If one specific key is red-hot (a celebrity's profile, a viral tweet), consistent hashing still sends every request for that key to one server. Virtual nodes balance many keys; they do nothing for one overloaded key. That needs a different tool - caching that key, or replicating it across nodes.
• Rebalancing still moves data. "Only k/n keys move" is small, but it is not zero. Adding a node triggers real data transfer for its arc, and that has to be throttled so it does not swamp the cluster.
• Virtual nodes cost memory and bookkeeping. Hundreds of positions per server add up in a large cluster, and every node has to know the ring.
• It relies on a good hash. A poorly distributed hash function clumps servers and keys together and brings back the uneven-partition problem, virtual nodes or not.

Where it is used

Consistent hashing is not a textbook curiosity - it is load-bearing in systems you use every day:

• The partitioning layer of Amazon Dynamo and Apache Cassandra, deciding which node owns which key.
• Discord, to route millions of concurrent users to the right servers.
• Content delivery networks like Akamai, to map content to edge caches.
• Google's Maglev network load balancer.

Wrap up

Consistent hashing exists to solve one specific pain: with plain hash(key) % N, changing the server count remaps almost every key and triggers a cache-miss storm. Put the servers and keys on a ring and assign each key to the next server clockwise, and now a server joining or leaving only disturbs its own arc - about k/n keys. Sprinkle each server across the ring as many virtual nodes and the load evens out. That combination - cheap rebalancing plus even distribution - is why it sits under the partitioning layer of nearly every large distributed data store. It is the building block that makes those systems scale horizontally without reshuffling the world every time a node changes.