Consistent Hashing

Consistent hashing is a way to decide which node owns a key so that adding or removing a node moves only a small share of the keys, instead of reshuffling most of them. Keys and nodes are hashed onto the same circular space, and each key belongs to the nearest node in a fixed direction, usually the first one clockwise. What you get is placement stability under membership change. You do not get fault tolerance, an even load, or any movement of data for free.

The mental model: ownership is a pure function of a key and a membership snapshot. Any client holding the same snapshot computes the same owner without asking anyone. When membership changes, the function changes for as few keys as possible, and only in one direction: keys move onto a joining node, or off a leaving node, never between two nodes that did not change. Everything else in this lesson is about the gap between that function and a working system: how evenly the function spreads load, how data physically follows it, how copies are placed, and what happens while clients disagree about the snapshot.

A cache is the cleanest example. Placement decides which server holds the cached copy of each object, so a placement change is a cache miss for every object that moved. The same function also routes requests in partitioned databases, object stores, and load balancers that want requests for the same key to land on the same backend. How a database partitions data in general belongs to Database Scaling and Distributed Data; this lesson owns the placement function itself.

The obvious placement rule is nodes[hash(key) % N]. It is stateless, uniform, and one line long. It is also tied to N: the owner of a key is a function of the divisor, so changing the divisor changes the owner of almost every key.

Go from 3 nodes to 4. A key keeps its owner only if h % 3 and h % 4 give the same index. For a uniformly distributed hash, look at h % 12: the residues 0, 1 and 2 agree under both divisors and the other nine do not. So 3 of every 12 keys stay put and 75% move. In general, growing from N to N+1 nodes keeps about 1 in N+1 keys, and moves N/(N+1) of them. The larger the cluster, the closer that gets to everything. Removing a node has the same effect, and so does reordering the node list.

For a cache this is damaging in a specific way. The new owner of a moved key has never seen it, so the next read is a miss and goes to the backing database. Capacity you added to reduce load briefly increases it, usually at the moment the system was already under pressure. The worked example below puts numbers on that.

The lower bound is worth knowing. If the new node must end up with a fair share of the keys, then at least 1/(N+1) of the keys have to move to it, whatever scheme you use. Consistent hashing does not beat that bound; it gets close to it, while modulo placement moves N times more. The figure measures both on real hashed keys, so you can move the sliders and watch the gap.

Modulo placement remains a sensible choice when the node set is fixed for the life of the data, for example a handful of shards you resize only by a planned migration. If membership never changes, you pay for a ring and get nothing back. Fixed partition counts, where you have many more partitions than nodes and move whole partitions between nodes, solve the same problem differently and are covered under other placement schemes.

A hash function maps any string to an integer in a fixed range, say 0 to 2³²−1. Treat that range as a circle: after the largest value comes 0 again. Hash each node identifier onto the circle, and hash each key onto the same circle. The common convention is that a key belongs to the first node you meet walking clockwise from the key's position; a node therefore owns the arc between its predecessor's position (exclusive) and its own (inclusive).

A small worked ring

Use a simplified ring with positions 0 to 99 and three nodes at positions 10, 40 and 80. These are made-up numbers chosen so the arithmetic is easy to follow; the figure further down uses real hashes.

Adding a node at 30 takes the positions in (10, 30] from the node at 40, which was their clockwise successor. Keys 12 and 27 move. Nothing else moves, and no key moves between the nodes at 10, 40 and 80. Removing the node at 40 would do the opposite: its arc (10, 40] falls to the next node clockwise, the one at 80, and every other key keeps its owner. That one-directional, local effect is the whole point.

The figure above is drawn from real data. Four nodes named host-a to host-d are hashed with a 32-bit function, 32 sample keys are hashed with the same function, and the colours and arcs come from the lookup rule rather than from a drawing. Because each node has a single position here, the arcs are uneven and D's slice is not exactly a quarter, and the node that loses it (the next one clockwise from D) can shrink a lot. The key point survives that: every moved key moves to D. The bars underneath compare against modulo placement over 10,000 keys.

What every participant has to agree on

Clockwise-successor is a convention. Some systems assign the arc to the predecessor, and a few use a different geometry altogether. What matters is that every router and every node computes the same answer, which requires agreement on five things:

• The hash function and its seed. Use a stable, well-mixed, non-cryptographic hash such as MurmurHash3, xxHash or a similar function. Never use a language's built-in hash for objects: some, like Python's hash() on strings, are deliberately randomised per process, so two clients would disagree immediately. Poor mixing also clusters positions, and the ring is only as even as the hash is.
• Node identity. Tokens are derived from the node identifier. If you derive them from an IP address and the address changes on restart, the node's tokens move and its keys with them. Use a stable logical name or persisted identifier.
• The membership snapshot. Two clients with different member lists compute different owners even though both implementations are correct. How the snapshot is distributed is covered in the next sections.
• Token derivation. node#0, node#1, … must be generated the same way everywhere, including how many tokens a node gets.
• Tie-breaking. Two tokens can land on the same position, and a key can hash exactly onto a token. Define a total order, for example by position and then node name, and a rule for whether a key at a token position belongs to that token. The sample code below does both.

A credible first implementation

The data structure is a sorted array of tokens and a binary search. A lookup is O(log T) for T tokens, which is microseconds even for tens of thousands of tokens, and routing needs no network call because the ring is local to the client. Rebuilding on a membership change is O(T log T) in this simple version, which is fine because membership changes are rare; larger systems keep a balanced tree or apply incremental updates.

// Runnable (Node 18+). A minimal ring with virtual nodes; MD5 is used only as a convenient, stable, well-mixed hash.
import { createHash } from 'node:crypto';

const hash32 = (s) => createHash('md5').update(s).digest().readUInt32BE(0);

class HashRing {
  constructor(tokensPerNode = 128) {
    this.tokensPerNode = tokensPerNode;
    this.tokens = []; // sorted [{ pos, node }]
  }
  add(node) {
    for (let i = 0; i < this.tokensPerNode; i++) {
      this.tokens.push({ pos: hash32(node + '#' + i), node });
    }
    this.tokens.sort((a, b) => a.pos - b.pos || (a.node < b.node ? -1 : 1)); // total order: ties are deterministic
  }
  remove(node) {
    this.tokens = this.tokens.filter((t) => t.node !== node);
  }
  owner(key) {
    if (this.tokens.length === 0) throw new Error('empty ring');
    const pos = hash32(key);
    let lo = 0, hi = this.tokens.length;          // first token with pos >= key position
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.tokens[mid].pos < pos) lo = mid + 1; else hi = mid;
    }
    return this.tokens[lo % this.tokens.length].node; // past the last token wraps to the first
  }
}

const ring = new HashRing();
['cache-a', 'cache-b', 'cache-c'].forEach((n) => ring.add(n));

const keys = Array.from({ length: 10000 }, (_, i) => 'user:' + i);
const before = keys.map((k) => ring.owner(k));
ring.add('cache-d');
const moved = keys.filter((k, i) => ring.owner(k) !== before[i]);

console.log(moved.length / keys.length);                          // near 0.25 (about 0.29 with these names)
console.log(moved.every((k) => ring.owner(k) === 'cache-d'));    // true: keys only ever move to the new node

One detail matters more than it looks. Lookup returns the first token at or after the key position, and the index wraps with lo % tokens.length. Forgetting the wraparound is the classic off-by-one: keys that hash past the highest token throw or return nothing, and only about 1/T of keys hit it, so tests with a handful of keys often miss it.

With one position per machine, ownership is decided by the gaps between a few random points on a circle, and random gaps are very uneven. Three nodes can easily split the ring 55/40/5, and with a handful of nodes the largest arc is often twice the average or more. A node with a large arc takes more keys and more traffic and runs hot while another sits nearly idle.

Virtual nodes, often called tokens or vnodes, give each machine many independent positions derived from identifiers like host-a#0, host-a#1, and so on. The machine owns the union of all the arcs that end at its tokens. Because each machine now owns many small arcs, the large and small ones average out: the relative spread of a node's share shrinks roughly with the square root of the number of tokens, so 64 tokens are about eight times tighter than one token, and going from 64 to 256 buys a further factor of two.

Set the slider to one token and the six nodes are visibly lopsided; the strip at the top has a few huge colour blocks. At 64 or 256 tokens the strip dissolves into fine stripes and the shares converge toward an even split, although not exactly: the figure is a real hash of real names, so some residual skew remains even at the high end. That residue is the honest answer to “is it balanced now?”: mostly, not perfectly.

A failure is spread across survivors

The second bar group in the figure answers a different question. When a machine leaves, each of its arcs falls to whichever token follows it clockwise. With one token the whole range falls onto a single neighbour, which suddenly carries its own load plus a full machine's worth, and may be pushed over the edge. With many tokens the machine's arcs sit next to tokens of many different survivors, so each of them absorbs a small increment. That is the more important operational benefit of vnodes, more than the average-case smoothness.

What tokens do not fix

• Capacity differences. A machine with twice the memory or throughput can be given twice the tokens, and its expected share doubles. That is a rough control, not a guarantee, since the actual share still varies with where the tokens land, and it only works if the resource that limits you is proportional to key count.
• Key popularity. Hashing balances where keys sit, not how often they are read. See hot keys.
• Costs that grow with token count. The ring metadata gets larger, a join or leave touches many small ranges on many peers instead of one large one, so streaming, repair and range-scan logic involve more, smaller pieces. Replica placement also gets harder, because neighbouring tokens often belong to the same machine (see replication). This is why no single token count is right. Cassandra historically defaulted to 256 tokens per node and, from version 4.0, moved to a default of 16 together with a token-allocation algorithm that places new tokens to even out ownership instead of choosing them at random; that trade-off was made deliberately, for operational cost and availability reasons.

A lookup tells you that key K now belongs to node D. It does not put K's bytes on D. When D joins, the system has to copy or stream the affected ranges, keep serving writes that arrive while the copy runs, verify that D has everything, and only then switch ownership. Route to D too early and clients see misses or stale values. Stop serving from the old owner too early and the range is unavailable for a while.

The sequence above is one common shape, not the only one. D is first admitted in a joining state where it owns nothing. The old owner B streams the range and, because writes continue during the copy, forwards the writes that arrive after the snapshot point. When D reports it has caught up and the data verifies, the membership store publishes a new ring version, the epoch, in which D owns the range. Clients that adopt the new epoch route to D. B keeps the old data until a grace period passes, so a client still holding the old ring can be redirected rather than receive a wrong answer. Routing changes in step 7 of the figure; the bytes move in steps 3 and 5. Variants include dual reads (ask both owners during the transition and take the newer value), dual writes, and handing the range over in many small pieces so only a small slice is ever in flight.

Clients that disagree about the ring

There is no instant at which every client switches. For some window, client X routes a key to D while client Y, still on the old ring, routes it to B. In a cache this causes duplicate entries and, worse, stale reads: Y writes through B, X reads from D and sees the old value. In a primary store it can cause lost or split writes. Three mechanisms keep this safe:

• Versioned ring. Every ring configuration has a monotonically increasing epoch, kept in a coordination service such as etcd or ZooKeeper, or spread by gossip as Dynamo-style stores do. Clients stamp requests with the epoch they used.
• Epoch enforcement at the owner. A node rejects or redirects a request stamped with an epoch older than the one under which it owns the range. This is the same idea as fencing tokens, in which the resource, not the caller, refuses stale authority; the argument for why that check has to live at the resource is in Distributed Locks.
• Time-bounded staleness. For a pure cache you can accept the window and rely on TTLs, as long as stale entries expire sooner than the staleness you can tolerate. One trap: a node that loses a range keeps its old copies, and if ownership later returns (a flapping node, a rolled-back change), those stale copies are served again. Delete or expire relinquished ranges.

What the ring buys you depends on what is behind it. For a cache, a miss during a move is tolerable because the database refills the entry, so a simple scheme can be enough as long as the refill load is bounded. For a primary data store, rebalancing has to preserve durability, consistency and availability throughout, and the ring specifies none of those. It also does not decide who is a member: if two halves of a partition each conclude the other has left, you have two rings. Membership agreement is a consensus problem, separate from placement.

A common way to replicate on a ring is to store each key on its owner and on the next replicas along the walk: the primary and then the following N−1 candidates. This is simple and local, since a key's replica set depends only on the key and the ring, and it means a failed owner's successor already holds the data. It goes wrong in two ways.

• The same machine twice. With vnodes, the next token clockwise frequently belongs to the machine that owns the first token, particularly when tokens per node are few. “The next three tokens” is not “three replicas”; it can be two machines or even one. The walk has to skip tokens of machines already chosen. Dynamo describes exactly this as building its preference list.
• Distinct machines, same blast radius. Three different machines in the same rack or availability zone are still a single failure away from losing all copies. Placement has to be topology aware: distinct machines, then racks, then zones, and for some data, regions.

The figure uses six machines, two per zone, three tokens each, and one deterministic key chosen because the naive rule fails on it. Switch the rule and watch the readouts. “Next 3 tokens” repeats a machine. “Next 3 distinct machines” fixes that but can still land two copies in one zone. Only the zone-aware walk guarantees three zones, at the cost that the chosen replicas are no longer simply the next three nodes on the ring. Cassandra's NetworkTopologyStrategy does this with racks and data centers.

// Illustrative pseudocode: choose N replicas for a key, one per failure domain.
function replicas(ring, key, n, domainOf):
    chosen  = []
    domains = set()
    start   = ring.first_token_at_or_after(hash(key))
    for token in ring.walk_clockwise_from(start):          // visits each token at most once
        node = token.node
        if node in chosen:        continue                 // another token of a machine we already use
        if domainOf(node) in domains: continue             // zone/rack already holds a copy
        chosen.append(node); domains.add(domainOf(node))
        if len(chosen) == n: return chosen
    // Fewer than n domains exist: decide explicitly. Either fail, or relax to distinct machines
    // and alert, rather than silently placing two copies in one zone.
    return relax_to_distinct_machines(ring, key, n, chosen)

What a replica count does not give you

Replication factor N determines storage cost, repair and recovery traffic, and how many failures you can survive before data is lost. It says nothing about consistency. Which replicas a read or write must contact, who is the leader if any, how concurrent writes are reconciled, and how divergent copies are repaired are separate decisions. A quorum rule such as R + W > N makes read and write sets overlap, but it is not a universal linearizability guarantee. It assumes a fixed replica set, no membership change in flight, strict rather than sloppy quorums (hinted handoff deliberately breaks the overlap to improve availability), and a version-reconciliation rule that picks the right value. Treat the formula as one ingredient, and look at Distributed Data for how replication and quorums are reasoned about in full.

Suppose a cache holds a million keys spread evenly across four nodes, and a celebrity profile receives 20% of all requests. The node that owns that one key serves 20% of the traffic for it, plus its quarter of everything else: 40% of the cluster's requests, against an even share of 25%. Another way to say it: the node is 1.6 times busier than a perfect split would make it, while the other three sit at about 20% each. Virtual nodes cannot help, because a key has exactly one position and therefore exactly one owner.

Raise the hot share in the figure and the owner's load climbs; raise the number of copies serving the key and it falls. The model is deliberately simple: every other key is lumped together as evenly spread background load, so treat the numbers as illustration. The real options all share one idea, which is to stop the hot key from being served by a single owner or to make each request cheaper:

• Replicate read-hot objects. Store copies under derived keys (profile:42#0 … profile:42#3), spread reads across them, and update or invalidate all copies on a write. You are trading a short consistency window and more write work for read capacity, so apply it only to keys that have earned it.
• Local near-cache. A small, short-TTL cache inside each application instance removes most reads before they reach the ring.
• Request coalescing. When many requests miss on the same key at once, let one go to the origin and have the rest wait for its result, so the owner and the database see one request, not hundreds.
• Edge or CDN caching for content that is the same for everyone.
• Split a hot aggregate by subkey, such as a counter sharded into many counters that are summed on read, when writes are the problem and correctness allows it.
• Protect the owner when it still saturates. Rate limiting, load shedding and backpressure keep one overloaded node from turning into a cluster-wide incident; see Rate Limiting, Load Shedding and Backpressure.

If hot-key skew is severe and persistent, an explicit shard map, where you assign specific heavy tenants or keys to dedicated nodes, can beat any hash-based placement, because you can place using knowledge the hash cannot have.

What to monitor

Token count is a configuration value, not a health signal. Watch the quantities that actually hurt: request rate and bytes per physical node (and the ratio of the busiest to the median), ownership skew, the top few keys by request rate, key movement and the rebalancing backlog during a change, cache hit rate and origin load, and during a join the miss amplification described below.

Rendezvous hashing, also called highest-random-weight hashing, needs no ring. For a key, compute a deterministic score for every (key, node) pair and give the key to the node with the highest score. When a node leaves, only the keys it owned move, and each goes to the node with the next-highest score for that key; keys owned by other nodes are untouched, because their scores did not change. When a node joins, it takes exactly the keys for which it now scores highest.

The cost shape differs. A naive lookup scores every node, so it is O(N) in the number of nodes with no per-membership data structure to build or keep in sync. A ring lookup is O(log T) after the sorted tokens have been built. For tens of nodes, rendezvous is often simpler and fast enough; for thousands, you want a ring, a hierarchical variant, or a fixed-slot scheme. Rendezvous also handles weights cleanly: the score is scaled by a node weight so a node with twice the weight wins about twice the keys, which is easier to reason about than adjusting token counts. And its balance is statistical in the same way a ring's is, but without the large-arc problem of a one-token ring, because every key is decided independently.

Other schemes you will meet

• Fixed partitions with a partition map. Hash keys into many more partitions than nodes (Redis Cluster uses 16,384 slots, assigned with CRC16 of the key modulo 16,384) and keep an explicit table from partition to node. Joining a node means reassigning some slots; rebalancing is moving named slots, and Redis uses MIGRATING/IMPORTING states and ASK/MOVED redirections to do it safely. This is not a ring, but it solves the same problem, and the explicit map makes the movement plan easy to see and control. The Dynamo paper itself later describes moving from random tokens toward equal-sized partitions for similar operational reasons.
• Jump consistent hash. A tiny, memory-free function mapping a key to one of N sequentially numbered buckets, moving a minimal fraction when N grows. It cannot express an arbitrary node leaving from the middle, so it fits systems where shards are added and removed in order.
• Maglev hashing. Builds a fixed-size lookup table of backends with near-even distribution and low (not zero) disruption when backends change, designed for software load balancers where lookup speed matters most.
• Bounded-load consistent hashing. Caps each node at a multiple of the average load, such as 1.25 times, and when the owner is full forwards the key to the next node clockwise. This limits how unbalanced the cluster can get under skew, at the price that a key's placement now depends on current load; it is used for load balancing in front of caches, as in HAProxy's consistent hashing with a balance factor.

Choose on membership scale, whether you need weights, how much machinery you want for membership state, and what your infrastructure already provides. None of these schemes by itself solves replication, hot keys, cross-zone placement or split-brain membership.

A service caches 10 million objects on servers A, B and C and has a 95% hit rate, so 5% of requests reach the database. Traffic is high, so you add D. Assume, to keep the arithmetic clean, that requests are spread evenly across keys and that the cache was fully warm; real traffic is skewed and your numbers will differ.

The arithmetic: with 25% of entries still warm, the hit rate is 0.95 × 0.25 ≈ 24%, so about 76% of requests go to the database against 5% before, roughly fifteen times more. With the ring, 0.95 × 0.75 ≈ 71% hit, 29% miss, about 5.8 times the database load. Two honest conclusions follow. Consistent hashing cuts the damage by about a factor of 2.6 here, which can be the difference between an incident and a blip. And even the ideal ring does not make adding a node free: the new node is cold, and about a quarter of the working set is cold with it. That is why the rollout matters as much as the algorithm.

D's share is also not exactly a quarter. If D is given virtual nodes in proportion to a quarter of the cluster's desired capacity, then in a balanced configuration roughly that share of the hash space becomes its responsibility; the realised value depends on where its tokens fall and on the existing ownership.

Rolling it out

• Prewarm where you can: copy the hot part of the moving ranges, or replay recent reads against D before it takes traffic, so the first requests are not all misses.
• Limit concurrency of moves and consider adding capacity in small steps rather than doubling at once, so refill load stays within what the database can absorb. Combined with request coalescing, a burst of misses on one key becomes one database read.
• Measure miss amplification during the change: cache miss rate, origin queries per second and latency, and the share of requests carrying an old ring epoch. Pick the stop condition in advance.
• Keep a rollback plan. Removing D returns its arcs to their previous owners, whose old entries may be stale or evicted; know which is acceptable.
• Never change the hash function or node identifiers in the same change. The ring prevents mass remapping only while those stay fixed. A deployment that swaps the hash algorithm, changes how tokens are named, or renames nodes remaps nearly every key and reproduces the modulo outage on purpose. A cheap guard is to shadow-compare the old and new rings on sampled production keys before switching.

// Illustrative pseudocode: shadow-compare an old and a new ring before switching routing.
for key in sampled_production_keys(rate = 0.001):
    old = ring_v7.owner(key)
    new = ring_v8.owner(key)
    record("ring.shadow.total")
    if old != new:
        record("ring.shadow.moved", labels = { from: old, to: new })
// Expect moved/total near 1/(N+1) for a join and only "to = new node" for a join.
// A fraction near 1.0 means the hash function, node identifiers or token derivation changed.

Bursts of misses from the move are also a retry hazard: clients that time out against a loaded database and retry make it worse, so the usual protections apply, namely retries with backoff and jitter and a circuit breaker in front of the origin.

The technique was published by Karger and colleagues at MIT in 1997 to spread web-cache load over changing sets of servers; Akamai grew out of that research. Since then it has become a standard building block, with variations that are worth keeping straight:

• Dynamo-style stores and Cassandra. The 2007 Dynamo paper popularised a ring with virtual nodes and preference lists for replica placement. Cassandra partitions rows by a hash token, supports vnodes, and places replicas with topology-aware strategies. The managed AWS DynamoDB service shares a name and a lineage of ideas, but its internal partitioning is not documented as a ring, so do not read its behaviour off the paper.
• Memcached clients. Memcached servers know nothing about each other; the client library hashes keys onto the server list. Ketama-style consistent hashing in clients is the classic deployment, and is why a client-side ring and server-side data movement are separate concerns there: no data moves at all, it is simply refilled.
• Redis Cluster. Hash slots with an explicit slot map, as described above, not a ring.
• Load balancers and proxies. Envoy's ring-hash and Maglev policies, HAProxy's consistent hash type and NGINX's consistent hashing upstream give affinity without shared session state: requests with the same key, such as a session or tenant id, reach the same backend while the backend set is stable. If that backend is removed, only its keys re-home.
• Object stores and distributed hash tables use the same idea at much larger scale, usually with extra layers for membership and replica repair.

Reach for it when membership is expected to change (autoscaling, node replacement, failures), when stable placement has real value (warm caches, data that is expensive to move, session affinity), and when you route in the client or a proxy and want no central lookup per request. That covers distributed caches, partitioned stores, and routing layers.

Consider something else when:

• The system is small and the database already partitions for you. A managed database that handles sharding and rebalancing gives you the result without you owning the ring.
• The cluster size never changes. hash(key) % N is simpler and produces an equally good distribution.
• Skew dominates. If a few tenants or keys carry most of the load, explicit placement or a workload-aware scheme beats hashing.
• You need range scans. Hash placement scatters adjacent keys by design; range partitioning keeps neighbours together at the cost of hot ranges.

Before you adopt it, you should be able to answer: who owns each key during a transition, how does the data follow, how do clients learn the new ring, and what happens if two clients disagree for a while? If the answers are vague, the ring is not the hard part yet.

The epoch checks in key movement are the same defence as fencing tokens, which Distributed Locks develops from first principles. The decisions about replicas and quorums continue in Distributed Data, and the wider picture of sharding, read replicas and rebalancing is in Database Scaling. If a placement change floods your origin, the defences are Load Shedding and Rate Limiting.

• Karger et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web” (ACM STOC, 1997) — the original paper (no link given)