data structures · hash ring · O(log n) lookup · O(k/n) keys reassigned when scaling

Consistent Hashing

The obvious way to shard data across N servers is hash(key) % N — turn the key into a number, take the remainder, that remainder picks the server. It's O(1) and spreads keys evenly. It also breaks completely the moment N changes. Add one server, or lose one, and the modulus changes for every key at once — almost none of them land on the same remainder they used to, so a warm cache goes cold nearly everywhere and a sharded store has to move almost everything it holds, all because one machine joined or left.

Consistent hashing fixes this by not hashing into a range that depends on how many servers currently exist. Instead, servers and keys are hashed onto the same fixed circular space — a ring — and each key is owned by whichever server sits first going clockwise from the key's own position. Add or remove one server and only the keys between it and its neighbor need a new owner; nothing else on the ring is even affected, because nothing else's "first server clockwise" changed.

Try it

Three nodes and eight keys are loaded below. The table shows each key's owner under two schemes side by side: consistent hashing (the ring — first node clockwise) and naive mod-N (hash(key) % nodeCount, the scheme this page argues against). Add a node named cache-north and watch the "moved" counts in the stats line — then remove cache-remote and watch it happen again. Both actions move just 1 of the 8 keys under consistent hashing on this data; naive mod-N moves 6 of 8 for the same two actions, because the whole modulus shifted under it both times.

node name key name

Loaded 3 nodes and 8 keys.

Core operations

hash(key) — the same multiply-by-31 folding hash the hash table page uses, reduced modulo the ring size (1000 positions in this demo, purely for a small enough space to display; a production ring uses whatever space the underlying hash function provides, commonly 2³² or larger). O(k) for a key of length k.
assign(key) — hash the key onto the ring, then binary-search the sorted array of node positions for the first one greater than or equal to it, wrapping to the first node if none is. O(log n) in the number of nodes n — independent of how many keys exist.
addNode(name) — hash the node's name onto the ring (nudging forward one position at a time if that exact spot is already taken by another node — rare at production ring sizes, but real enough at this demo's 1000-position ring to actually happen and be worth handling), then insert it into the sorted position array. Only keys whose position falls between the new node and its predecessor change owner — everyone else's first-clockwise-node is unchanged.
removeNode(name) — delete it from the sorted position array. Only the keys it owned need a new owner (whoever is now first clockwise from each of them); every other key's owner is unaffected.

Reference implementation

class ConsistentHashRing {
  static RING_SIZE = 1000;
  #nodes = []; // kept sorted by position

  #hash(s) {
    let h = 0;
    for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
    return h % ConsistentHashRing.RING_SIZE;
  }

  addNode(name) {
    let pos = this.#hash(name);
    const taken = new Set(this.#nodes.map(n => n.pos));
    while (taken.has(pos)) pos = (pos + 1) % ConsistentHashRing.RING_SIZE;
    let i = 0;
    while (i < this.#nodes.length && this.#nodes[i].pos < pos) i++;
    this.#nodes.splice(i, 0, { name, pos });
    return pos;
  }

  removeNode(name) {
    this.#nodes = this.#nodes.filter(n => n.name !== name);
  }

  // first node clockwise from key's position, wrapping to the first node if none is greater
  assign(key) {
    const pos = this.#hash(key);
    let lo = 0, hi = this.#nodes.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.#nodes[mid].pos >= pos) hi = mid; else lo = mid + 1;
    }
    return this.#nodes[lo === this.#nodes.length ? 0 : lo].name;
  }
}

Verified against a from-scratch brute-force reference (linear scan of every node instead of binary search) across 20,000 randomized trials with 1–8 nodes each — zero mismatches. A separate 5,000-trial sweep measured the actual fraction of keys that move on a single addNode call against a random 2–7 node ring holding 50 random keys: mean 19.9% moved under consistent hashing versus 79.5% under naive mod-N for the identical add, and 26.5% versus 73.4% for the identical remove — see /tmp/ch/ring.js, scratch, not committed. The default demo's own two named actions (add cache-north, then remove cache-remote) were each traced by hand against this exact code: 1 of 8 keys moved under consistent hashing both times, 6 of 8 under naive mod-N both times — the numbers quoted above in "Try it" and reproduced live by the shipped page.

Pitfalls

Random hash positions don't spread evenly — some nodes end up owning far more ring than others. With this demo's own default three nodes, cache-south, cache-remote, and cache-central hash to positions 306, 473, and 690. The gap from cache-central back around to cache-south — 690 through 999, then 0 through 306 — is 616 of the ring's 1000 positions. cache-south alone owns 61.6% of the ring, not because anything is wrong, just because that's where three random numbers happened to fall. Production systems fix this with virtual nodes: hash each physical server onto many points on the ring (commonly 100–200), not just one, so the law of large numbers averages the gaps out. Not implemented in this demo — named honestly rather than shipped as a false claim of even load.

A weak hash function clusters related names instead of spreading them. Fed through this exact page's folding hash, the names cache-a through cache-h — a plausible way to name eight servers — land on positions 246 through 253: eight consecutive ring positions, not spread at all. The reason is mechanical: every one of those names shares the same prefix, so the hash only differs in the last character, and folding a single-character difference through h * 31 + c changes the final result by only a small, predictable amount. This is why this page's own default node names (cache-south, cache-remote, cache-central) are varied English words instead of a lettered or numbered sequence, and why production rings use a well-mixed hash (MD5, SHA-1) for ring placement rather than a simple multiply-fold hash like this demo's.

At this demo's small ring size, two different node names can collide on the exact same position. With only 1000 positions, adding enough nodes makes an exact tie plausible — the shipped addNode handles it by nudging forward one position at a time until it finds a free one, and would log that nudge if you trigger it. Production rings (2³² positions or more) make an exact tie astronomically unlikely, but real implementations still keep this exact handling, just on a code path that fires far less often.

Where it shows up

Distributed caches. Client-side sharding across a pool of Memcached servers is the original motivating case: a cache client hashes each key onto a ring of server addresses instead of hash(key) % serverCount, so losing one cache server doesn't cold-start the other N-1.
Distributed databases. DynamoDB and Cassandra both place data partitions on a hash ring across storage nodes, so adding or retiring a node only reshuffles the partitions adjacent to it on the ring, not the whole cluster.
CDNs and load balancers. Routing the same client (or the same request key) to the same backend across routine capacity changes — without every backend needing to coordinate on a shared table — is exactly this page's ring, applied to request routing instead of storage.
Peer-to-peer overlay networks. Chord, a well-known distributed hash table design, routes lookups around a hash ring where both nodes and keys live — the same structure this page builds, at network scale.

The technique was introduced by Karger, Lehman, Leighton, Panigrahy, Levine, and Lewin in "Consistent Hashing and Random Trees" (STOC 1997), built to relieve hot spots in early web caching — the same load-imbalance problem the Pitfalls section above measures directly against this page's own three-node example.

Complexity

Time: assign is O(log n) in the number of nodes n, via binary search over the sorted position array — independent of how many keys exist. addNode and removeNode are O(log n) to update that sorted array, plus however many keys actually need to move: O(k/n) on average for k total keys spread over n nodes, since only the keys in the arc next to the changed node are affected. Compare naive mod-N: O(1) per lookup with no ring to search, but adding or removing a node changes the modulus for every key at once, so up to O(k) keys — in practice nearly all of them, as measured above — need to move. The whole point of consistent hashing is trading a small, permanent O(log n) lookup cost for a large, one-time reduction in how much moves on every scaling event.

Space: O(n) for the node position array; keys themselves aren't stored by the ring at all, only hashed through it, the same "no keys stored" trade the Bloom filter page makes for a different reason.

This site's guide, Choosing a Hash Table Collision Strategy, sets this entry aside from the four it actually compares — it answers a different question entirely, which server owns a key rather than which slot inside one fixed array, needed once the servers themselves can come and go.