Consistent Hashing: Adding Nodes Without Losing the Cache

Introduction

Consistent hashing is a method for assigning keys to servers so that adding or removing a server moves only a small share of the keys instead of nearly all of them. Every server and every key is hashed into the same numeric range, that range is treated as a circle, and each key belongs to the first server found moving clockwise from the key's own position. When a server is added, it takes over only the keys sitting between itself and the previous server on the circle. Every other key stays where it was.

That property is the whole reason the technique exists. The obvious alternative, hash(key) % serverCount, reassigns almost every key the moment the server count changes: going from eight cache nodes to nine moved 88.8% of a million keys in the measurements below, while a hash ring moved 11.8%. For a cache in front of a database, the first number is an outage and the second is a Tuesday.

This post builds a working hash ring in TypeScript, measures both approaches, shows why virtual nodes are mandatory rather than optional, and covers what the technique does not solve. It follows the same thread as the last three posts: the LRU cache decides what one node keeps, rate limiting decides what gets in, Bloom filters decide what to skip looking up, and consistent hashing decides which node holds the key at all.

Why Modulo Hashing Falls Apart

Spreading keys across N servers has an obvious first answer: hash the key, take the remainder modulo N, and use that as the server index. It distributes keys evenly, it needs no coordination, and every server computes the same answer.

It fails on the day the server count changes. The remainder depends on N, so changing N changes the answer for almost every key at once. Hashing a million keys and comparing the assignment before and after shows the scale:

modulo hashing, 1,000,000 keys

  4 -> 5 nodes    80.0% of keys move
  8 -> 9 nodes    88.8% of keys move
  8 -> 7 nodes    87.5% of keys move   (a node crashing counts too)

Consider what those percentages mean for a cache. Almost every key now hashes to a node that has never seen it, so almost every request misses, and all of that traffic arrives at the database at once. The cache does not warm up gradually; it empties in an instant. A routine capacity increase and a single node failure produce the same result, which is the worse half of the problem: the failure case is when the database can least afford the extra load.

The Hash Ring

Consistent hashing removes the dependency on N by giving each server a fixed position that does not move when other servers come and go.

Hash the server's name into the same 32-bit space the keys use, and treat that space as a circle whose end wraps around to its start. A key is owned by the first server position at or clockwise from the key's own position. Adding a server inserts one new position on the circle, which captures only the keys between it and its counter-clockwise neighbor.

hash space: 0 .......................................... 4,294,967,295 (wraps)

server positions      cache-A at 0.4 billion
                      cache-B at 1.9 billion
                      cache-C at 3.1 billion

hash("user:42") = 2.2 billion   first position clockwise is cache-C
hash("user:99") = 3.6 billion   nothing clockwise, so it wraps to cache-A
hash("cart:7")  = 0.1 billion   first position clockwise is cache-A

now add cache-D at 2.6 billion:

  "user:42" (2.2b)   cache-D now comes first       moves to cache-D
  "user:99" (3.6b)   unaffected                    stays on cache-A
  "cart:7"  (0.1b)   unaffected                    stays on cache-A

Only keys in the arc that cache-D captured from cache-C were reassigned. No other pair of servers exchanged anything. That locality is what modulo hashing cannot offer, because a modulus has no notion of position.

A Hash Ring in TypeScript

The ring is a list of positions sorted ascending. Lookups binary search for the first position at or past the key's position, wrapping to index 0 when the key sits past the last entry.

// src/utils/hash-ring.ts
function hash32(value: string): number {
  let h = 0x811c9dc5; // FNV-1a offset basis
  for (let i = 0; i < value.length; i++) {
    h = Math.imul(h ^ value.charCodeAt(i), 0x01000193);
  }
  // Avalanche step (the murmur3 finalizer). FNV-1a alone leaves nearly
  // identical inputs such as "cache-0#1" and "cache-0#2" clustered, and
  // the ring depends on those positions being spread evenly.
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

interface RingEntry {
  position: number;
  node: string;
}

export class HashRing {
  private ring: RingEntry[] = [];

  constructor(private readonly virtualNodes = 150) {}

  addNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      this.ring.push({ position: hash32(`${node}#${i}`), node });
    }
    this.ring.sort((a, b) => a.position - b.position);
  }

  removeNode(node: string): void {
    this.ring = this.ring.filter((entry) => entry.node !== node);
  }

  getNode(key: string): string | undefined {
    if (this.ring.length === 0) return undefined;
    const position = hash32(key);
    let low = 0;
    let high = this.ring.length;
    while (low < high) {
      const mid = (low + high) >>> 1;
      if (this.ring[mid].position < position) low = mid + 1;
      else high = mid;
    }
    // low === ring.length means the key sits past the last entry: wrap to 0.
    return this.ring[low % this.ring.length].node;
  }
}

Lookups are O(log V) over the total number of ring entries, which is the server count times virtualNodes. Membership changes re-sort the ring, which is fine because servers join and leave far less often than keys are looked up. The assignment depends only on the set of server names, never on the order they were added, so every client that hashes the same names independently agrees on the same layout with no coordination.

Virtual Nodes Are Not Optional

Giving each server one position on the circle distributes servers randomly, and random points on a circle leave gaps of wildly different sizes. The server that happens to follow a large gap owns all the keys in it.

The fix is to give each server many positions, called virtual nodes, by hashing name#0 through name#149. Every server then covers many small arcs scattered around the circle instead of one arbitrary arc, and the law of large numbers flattens the distribution. Measuring the share of a million keys landing on each of eight servers shows how much this matters:

load across 8 servers, 1,000,000 keys, even share = 12.5%

  virtual nodes    lightest    heaviest    heaviest / lightest
      1               3.3%       30.0%           9.09x
     10               7.6%       20.8%           2.75x
    150              11.0%       13.6%           1.25x
    500              11.2%       13.4%           1.20x

With one position per server, the busiest node carries nine times the load of the quietest, which in practice means it falls over first while another node idles. At 150 virtual nodes the spread is down to 1.25x, and going to 500 buys almost nothing. Somewhere near 100 to 200 is the standard choice, and the memory cost is small: 150 entries per server is a few kilobytes of positions for a cluster of ten.

Virtual node counts also give you weighting for free. A server with twice the memory of its peers can be given twice the virtual nodes, and it will receive roughly twice the keys.

The Hash Function Has to Avalanche

The first version of the ring for this post used plain FNV-1a with no finalizer, and the numbers came out wrong in a way worth showing.

150 virtual nodes, 8 servers, 1,000,000 keys

  FNV-1a alone            spread 1.72x     8 -> 9 nodes moved  7.3%
  FNV-1a + finalizer      spread 1.25x     8 -> 9 nodes moved 11.8%

Two symptoms, one cause. Virtual node names differ only in their last characters, so cache-0#1 and cache-0#2 should land far apart on the circle but instead landed near each other, clustering each server's positions into clumps and leaving the uneven spread. The second symptom is the more instructive one: the new node captured only 7.3% of the keys when its fair share was 11.1%, because its clustered positions covered less of the circle than they should have. A number below the theoretical ideal looked harmless and was in fact evidence of a broken distribution.

Adding the murmur3 finalizer, five instructions that mix the high bits down into the low ones, fixed both. The requirement is not a cryptographic hash; it is avalanche, meaning a one-bit change in the input flips about half the output bits. When ring positions come out lumpy, suspect the hash before the algorithm.

What Actually Moves

With the ring working, the movement numbers are the ones the technique promises, measured over the same million keys and eight servers:

consistent hashing, 150 virtual nodes, 1,000,000 keys

  add a 9th server        11.8% of keys move   (ideal 1/9 = 11.1%)
                          100% of them move to the new server
                          0 keys move between existing servers

  remove 1 of 8 servers   12.9% of keys move   (ideal 1/8 = 12.5%)
                          0 keys on surviving servers move

The second line of each block matters as much as the first. Not only is the volume of movement small, it is confined: a joining server pulls keys only from its neighbours on the circle, and a leaving server's keys are absorbed by the next servers clockwise. Servers that were not involved see no change at all, so a failure in one part of the cluster cannot ripple into cache misses everywhere else.

Limits and Variants

Consistent hashing solves key placement under membership change. It does not solve several adjacent problems that look similar.

• Hot keys. One key receiving a tenth of all traffic lands on exactly one server, and no amount of virtual nodes helps. That is a job for replicating the hot key or caching it in the client.
• Load beyond placement. Even distribution of keys is not even distribution of work, since keys differ in size and request rate. Consistent hashing with bounded loads extends the walk clockwise past any server already over a load threshold, capping how overloaded a single server can get.
• Replication. Storing a key on several servers is the same walk continued: take the next N distinct servers clockwise. Dynamo-derived systems such as Cassandra and Riak place replicas exactly this way.
• Simpler alternatives. Rendezvous hashing scores every server for a key and picks the highest, giving the same movement guarantees with no ring to maintain, at O(N) per lookup instead of O(log V). For small clusters that is often the better trade. Maglev hashing builds a fixed-size lookup table for constant-time lookups when routing at very high rates.

When You Do Not Need It

The technique costs a ring to maintain and a hash to agree on, so it earns its place only when membership actually changes and no one is tracking assignments centrally.

• A single cache node. There is nothing to distribute.
• A fixed cluster that never changes. Modulo hashing is simpler and distributes just as evenly, though a node failure is still the bad day it always was.
• A system with a coordinator. If a control plane already assigns partitions to nodes and clients look up that mapping, an explicit table gives exact placement and is easier to reason about.
• Managed stores. Cassandra, DynamoDB, and most Redis clients already do this internally. Understanding the mechanism is what tells you how they behave when a node joins; implementing your own is only for when you are the one routing.

Conclusion

Consistent hashing replaces a global function of the server count with a fixed position per server, and that single change turns "almost every key moves" into "only the affected arc moves." The measurements make the difference concrete: 88.8% of keys reassigned by modulo hashing when a ninth node joins, against 11.8% for a ring, with none of that movement touching uninvolved servers. Virtual nodes are what make the ring's distribution usable rather than theoretical, and the quality of the hash underneath decides whether the virtual nodes spread at all.

Key Takeaways

• Consistent hashing assigns each key to the first server clockwise of it on a hashed circle, so membership changes move only a bounded share of keys.
• Modulo hashing moved 88.8% of a million keys when one node joined; a hash ring moved 11.8%, and none of it between existing servers.
• Virtual nodes are required, not an optimization: one position per server measured a 9.09x load spread, while 150 positions brought it to 1.25x.
• Virtual node counts double as capacity weights for servers of different sizes.
• The hash must avalanche. Without a finalizer, virtual node positions cluster, and the tell is a new node receiving less than its fair share.
• The ring does not fix hot keys or uneven per-key load; those need replication, bounded-load variants, or client-side caching.