Consistent Hashing

Consistent hashing maps keys to nodes on a ring so adding or removing a node moves only a small fraction of keys instead of reshuffling the whole dataset.

distributed-systems

Definition

Consistent hashing places both keys and nodes on a circular hash space. A key belongs to the first node clockwise from its hash. When a node is added or removed, only the keys in the arc owned by that node move, rather than every key being remapped by a modulo operation. Virtual nodes improve balance by giving each physical node many positions on the ring.

Context and scope

Consistent hashing is used in distributed caches, sharded databases, load balancers, and peer-to-peer systems where membership changes must not cause a full data reshuffle or a cache miss storm.

Common misconceptions

Consistent hashing eliminates rebalancing — it reduces the fraction of keys moved, but joins and leaves still require data transfer
Hash ring positions guarantee equal load — without virtual nodes, physical nodes can own very different arc sizes
A hot key becomes fast automatically — one key still maps to one node, so skew must be handled separately

Anti-patterns

Using modulo hashing for a cache cluster that scales horizontally
Adding a node without planning how its new keys will be populated
Ignoring hot keys that dominate traffic regardless of ring balance

Related concepts

Related examples

Authoritative source

https://www.tom-e-white.com/2007/11/consistent-hashing.html

Why modulo breaks at scale

With hash(key) % N, changing N remaps almost every key. A cache cluster that grows from four to five nodes loses most of its cache at once, which can overload the origin. A sharded database must move nearly all rows. Consistent hashing places nodes and keys on a ring. A key belongs to the next node clockwise. Adding a node only takes the arc between its predecessor and itself; the rest of the keys stay put.

import { createHash } from 'node:crypto';

function position(value: string): number {
  const digest = createHash('sha256').update(value).digest();
  return digest.readUInt32BE(0);
}

function owner(key: string, nodes: string[]): string {
  const keyPos = position(key);
  const ring = nodes
    .map((node) => ({ node, pos: position(node) }))
    .sort((a, b) => a.pos - b.pos);
  return ring.find((entry) => entry.pos >= keyPos)?.node ?? ring[0].node;
}

This minimal ring has no virtual nodes and no replication. It illustrates the lookup, not a production implementation. Use a proven library for real systems, especially when membership changes concurrently.

Virtual nodes and balance

A physical node placed once on the ring may own a large or tiny arc. Virtual nodes give each physical node many positions, which smooths the distribution. The trade-off is more memory and slightly more lookup work. Measure the actual key distribution: a uniform hash does not guarantee uniform traffic because some keys are much hotter than others.

Membership changes are still work

When a node joins, it takes ownership of an arc and must load or fetch those keys. During that window, requests may miss the cache or route to the old owner. Plan for a warm-up period, replicate keys for availability, and avoid moving more than one node at a time in a small cluster. Removing a node requires its keys to be served elsewhere; if they are not replicated, they are lost.

When to use it

Use consistent hashing when the set of nodes changes and remapping all keys would be expensive or disruptive. The advantage is locality of movement; the drawback is a more complex membership and rebalancing story. Compared to a centralized directory, it avoids a lookup service but gives up fine-grained control over placement.