How consistent hashing works

In this lesson, we’ll build the rule that decides which server stores which piece of data, and we’ll build it so that adding or removing a server moves as little data as possible. That rule is consistent hashing. By the end you’ll be able to explain why the obvious scheme shuffles almost the whole dataset when a single machine joins, why the ring moves the least data any scheme can, and what virtual nodes buy you and what they quietly cost.

The input is a key: the identifier of one piece of data, such as user:8842 or a photo’s filename. The output is the server that owns it, and, because real storage keeps several copies, the ordered list of the R distinct servers that should hold those copies, called the preference list:

lookup("user:8842")                 ->  "s11"
preference_list("user:8842", r=3)   ->  ["s11", "s4", "s15"]

Two properties make that function hard, not trivial. It must be computed locally (every client works it out from a small table in its own memory, with no network call and no coordinator to ask) and every client must get the same answer. And when the set of servers changes, the answers must change as little as possible, because every changed answer is a byte that has to move across the network.

A hash function underlies all of this: it turns a string of any length into a number that looks random but is completely determined by the input, so every machine computing it gets the same result. Writing hash(k) below always means the same fixed, agreed-upon function.

Three results follow, and they are the shape of the whole topic:

• the obvious rule, mod N, moves 94% of the data when the fleet grows by one machine;
• the ring moves 5.9%, and no scheme can beat that;
• virtual nodes (placing each server at many points around the ring instead of one) even out the load, at a cost in memory, gossip, and durability.

Symbols and terms

Two words are easy to blur. Latency is how long one operation takes; a lookup is a latency question, measured in nanoseconds. Throughput is how many operations complete per second; a migration is a throughput question, measured in bytes per second off a network card.

The problem is the migration, not correctness

You have N servers and a key space: the full set of possible keys, which for a 64-bit hash is every number from 0 to 2^64 - 1. Some function has to answer “which server owns key k”. The design decision is what that function is, and it has to survive three events. Only the third is hard.

A rehash (recomputing every key’s owner after the server set changes) can be perfectly correct and still move 94% of a 10 TB corpus (the whole body of stored data). That is a multi-day outage in slow motion. A real migration is a four-step sequence, and each step has a window in which a bug loses data:

flowchart LR
    D["dual-write<br/>every update to old AND new location"] --> B["backfill<br/>copy the history across"]
    B --> V["verify<br/>the two locations agree"]
    V --> F["flip<br/>readers to the new location"]

So the goal is stated in bytes moved. Everything below is about minimizing that.

Requirements

The partitioner needs:

• lookup(key) -> node: total (an answer for every key, no gaps), deterministic (same key always gives the same answer), and identical on every client.
• preference_list(key, R) -> [node_1 .. node_R]: an ordered list of R distinct physical nodes (real separate machines, not several ring points on one machine), so the layer above can keep R copies.
• add(node) / remove(node) with bounded, derivable movement.
• Weighting: a node with twice the disk should own about twice the key space.

The targets it must hit:

What a bad answer costs

Take one workload throughout: N = 16, 10 billion objects of 1,088 B each, so the logical corpus is 10.88 TB; RF 3; a 1 Gbps card pushes about 125 MB/s usable. At RF 3 a join actually moves replicas too, so the real figure is 3x everything (32.64 TB), but the ratio between schemes is unchanged by that factor, so the logical number is the one worth working.

Price the same event, growing from 16 servers to 17, under each scheme:

• mod N rehash moves 94% ≈ 10.23 TB. Every node both sends and receives, so the work genuinely spreads 16 ways: ~640 GB each, ≈ 1.4 h at a card’s line rate.
• Ring rehash moves 5.9% ≈ 0.64 TB, 16x fewer bytes. But a join is inbound to one node: all 0.64 TB enters the new machine through a single card, so its critical path is also ≈ 1.4 h. The 15 incumbents each send only ~40 GB (≈ 5 min).

The wall-clock times are the same. The ring’s win is not elapsed time; it is:

• 16x fewer bytes on the wire and off disk, both shared, metered, and contended with live traffic.
• one machine degraded instead of sixteen. During the ring migration the fleet is essentially unaffected, and the one saturated machine is the joiner, which has no live traffic on it yet.

The ratio 0.94 / 0.059 = 16 is exactly N, so the ring saves a factor of N, and the saving grows with the fleet.

Two practical notes. Nobody moves data at line rate: throttling the copy to 20–30% of a card (so it does not starve live traffic) multiplies both times by three or four. And because the receiver is the bottleneck, real systems stream a joiner from many senders at once and add nodes in batches, so the inbound work lands on several cards instead of arriving serially at one.

The partitioner as code

The interface is five methods:

class Partitioner:
    def lookup(self, key: bytes) -> str: ...
    def preference_list(self, key: bytes, r: int) -> list[str]: ...
    def add(self, node: str, weight: float = 1.0) -> None: ...
    def remove(self, node: str) -> None: ...
    def load_shares(self) -> dict[str, float]: ...

Two decisions inside it are load-bearing:

• preference_list returns physical nodes, not ring positions. With many virtual nodes per server, the next few points clockwise often belong to the same machine. Removing those duplicates is the difference between three copies on three machines and three copies on one machine that can die all at once.

• There is no rebalance() method. The ring is a pure function of the current server set (same inputs, same output, no stored state of its own), so there is nothing to trigger and nothing that can drift. That is what “consistent” means here: consistent across clients and across time. It is not the database sense of the word (that every reader sees the same value for a key); it is a claim about the function, that two clients asked “who owns user:8842” get the same name back. The three machines that name can still hold three different values.

The ring is a sorted array

The ring is a picture, but the implementation is three plain arrays. M is the total number of ring points, N x V:

positions   uint64[M]   sorted, M = N x V
owners      uint16[M]   parallel array, index into a node table
node table  N entries   id, address, weight, state

Two parallel arrays instead of one array of records, because the binary search touches only positions: it never reads an owner until the search finishes. Keeping positions packed tightly puts more of them in each cache line, so the search stays fast. At the running example’s M = 3,200, the positions array is 25.6 KB, small enough to live entirely in L2 cache and be read in a few nanoseconds.

A lookup follows five steps: a key goes in, an ordered list of replicas comes out.

flowchart LR
    K(["key"]) --> H["1. hash the key<br/>xxhash64, ~2 ns"]
    H --> B["2. binary search positions<br/>first point >= hash<br/>ceil(log2(N x V)) probes"]
    B --> V["3. that point = owning vnode"]
    V --> P["4. owners array -> physical node<br/>one memory read"]
    P --> R["5. walk clockwise, skip repeats<br/>of the same machine -> R replicas"]
    R --> O(["preference list"])

The hash is a fixed ~2 ns and is deliberately non-cryptographic: built for speed and even spreading, not for resisting an attacker. The binary search costs a logarithm because each probe halves the range. The clockwise walk in step 5 is a short linear scan whose length depends on how many neighbouring points happen to belong to the same machine, which is why deduplication is mandatory once V is large.

Why mod N moves 94%

The obvious scheme is server = hash(k) mod N, mapping the hash into 0 .. N-1. It spreads keys evenly and costs one instruction, and it is the wrong answer for one reason.

The failure is easiest to see with three keys. Take a four-server fleet, add one machine to make five, and follow three keys through the change. Pretend the hash hands us these small numbers so we can do the arithmetic in our heads:

We added a single server and two of the three keys changed owner. Nothing is special about 17 and 18: changing N re-divides every hash, so almost every key lands on a new remainder. That is the whole failure. Now count it exactly.

Go from N = 16 to N = 17. A key stays put only if hash(k) mod 16 == hash(k) mod 17. Because 16 and 17 are coprime (share no factor above 1), the Chinese remainder theorem says the pair (h mod 16, h mod 17) is spread uniformly over all 16 x 17 = 272 combinations. The two remainders are equal only when their common value is a valid remainder for both, meaning it is below 16: that is 16 of the 272 combinations. So 16/272 = 5.9% of keys stay and 94.1% move.

Consecutive integers are always coprime, so the same argument gives the general result:

P(stays) = 1/(N+1)      P(moves) = 1 - 1/(N+1)

Note the direction: mod N gets worse as the fleet grows. The intuition “one node in seventeen, so about one seventeenth of the data” is the exact complement of the truth. The reason is that mod N does not assign keys to servers, it assigns keys to residues, and changing N renumbers every residue class at once.

There is one real escape hatch. Going from N = 16 to N = 32, every key’s new owner is either h mod 16 or h mod 16 + 16 and nothing else, so exactly 50% move and each old node splits with one new node. If your fleet only ever doubles, mod N with a power-of-two N is fine and needs no ring.

The ring, and why 1/(N+1) is optimal

Build the ring in four moves:

1. One number space for two kinds of thing. Hash both keys and server names into the same 64-bit space.
2. Bend that space into a circle so the largest number sits next to zero. That circle is the ring.
3. Ownership rule: a key is owned by the first ring position clockwise from hash(k), wrapping over the top.
4. Put each server at many points. A server places V positions by hashing "server#0" through "server#V-1". One name yields V positions that look unrelated.

The M = N x V positions cut the circle into M arcs. An arc is the unit of ownership: every key in an arc belongs to the server owning the arc’s clockwise endpoint, so an arc’s length is the share of key space it carries.

The diagram below reads clockwise, with the top the point where 2^64 wraps back to 0. A key hashes to a spot on the circle, and its owner is the next server point clockwise; s3 and s11 each show up at more than one point, which is move 4 doing its job:

flowchart LR
    TOP(["0 = 2^64<br/>top of ring"]) --> A(["s3 @ p1"])
    A --> B(["s11 @ p2"])
    B --> KEY{{"hash(user:8842)<br/>lands here"}}
    KEY --> C(["s7 @ p3<br/>first point clockwise = owner"])
    C --> D(["s3 @ p4"])
    D --> E(["s11 @ p5"])
    E --> TOP

A single join makes the ring’s advantage concrete. Add a server with its V points. Each new point lands inside an existing arc and splits it: the keys on the counter-clockwise side of the new point now reach it first and move to the new server; the keys on the other side do not move at all. Across all V points:

one new point  ->  steals exactly one arc, from exactly one incumbent
V new points   ->  steal V arcs, from at most V incumbents
no arc ever changes hands between two incumbents

That last line is the property mod N lacks, and it is what makes the migration bounded.

The fraction that moves works out to 1/(N+1). After the join the ring holds (N+1)V positions, all from the same hash and therefore statistically interchangeable. So no arc is special: each has the same expected length, 1/((N+1)V) of the circle. The new server owns V of them:

E[fraction moved] = V / ((N+1) x V) = 1/(N+1) = 5.9% at N = 16

Notice that V cancels: the expected movement is 5.9% whether you use 1 virtual node or 1,000. Virtual nodes are not what makes the movement small; the ring’s ownership rule is.

That fraction is also the floor. Any scheme that ends with N+1 equally-loaded servers must give the new server 1/(N+1) of the keyspace, and every one of those keys is currently stored elsewhere, so it must move. At least 1/(N+1) must move, and the ring moves exactly that. There is no cleverer scheme to find; the interesting question is what the ring costs to achieve the floor.

Removal is the mirror image: each departing node’s V arcs are absorbed by their clockwise neighbours, so 1/N = 6.25% of keys move and again nothing moves between survivors. The asymmetry priced earlier lives here, since a join is inbound to one node (one machine absorbs everything through one card), while a departure is outbound to up to V nodes (the load is spread).

flowchart TD
    subgraph BEFORE["before: three arcs, three owners"]
        A1["arc owned by s7"] --> A2["arc owned by s3"] --> A3["arc owned by s11"]
    end
    subgraph AFTER["after: s16 joins, one point lands in the middle arc"]
        B1["arc owned by s7"] --> B2["split: left part now s16"] --> B3["right part still s3"] --> B4["arc owned by s11"]
    end
    BEFORE --> AFTER
    N1["Only the split part moves, and it moves ONTO s16.<br/>s7 and s11 are untouched; no key passes between incumbents."] -.-> AFTER

Virtual nodes buy variance, not mean

Raising V does not change how much data moves (V cancels) and does not change the average load a server carries (always 1/N). What it changes is the spread around that average.

A server’s load is the sum of its V arc lengths, a random quantity because the arcs come from hashing. When M points are dropped uniformly on a circle, the arc lengths are the spacings of a uniform sample, and any server’s total share follows a Beta distribution, Beta(V, M - V), the standard distribution for a random fraction between 0 and 1. Its mean is V/M = 1/N (as expected), and its spread has a closed form:

CV = sqrt( (N - 1) / (N V + 1) )     exact
   ~=  1 / sqrt(V)                    for large N

The coefficient of variation (CV) is the standard deviation divided by the mean, so it expresses the spread as a fraction of the average and is comparable across fleet sizes. A CV of 0.94 means a typical server’s share is off by about 94% of the average, enormous; 0.07 means 7%, fine.

The CV of per-server load falls as 1/sqrt(V), and V is the only term that matters. At N = 16:

Read the first and last rows together: without virtual nodes, a 16-server ring has a busiest server holding 3.38x the average keyspace. Since you provision for the peak, a plain ring at V = 1 costs 3.4 machines for every machine of useful capacity. At V = 200 the peak is 1.13x and the overprovisioning is 13%.

The V = 1 peak is exactly the harmonic number H_N = 1 + 1/2 + ... + 1/N, because at V = 1 the busiest server owns the largest of N uniform spacings, whose expected length is H_N / N against a mean of 1/N. H_16 = 3.38, and H_1000 = 7.49, so V = 1 fails worse the bigger the fleet gets. This mirrors the movement result: the mean a server owns is 1/N at every size and never degrades; it is the spread that does.

Three consequences:

1. V = 1 is not “consistent hashing without an optimization.” It is unusable. The paper that introduced consistent hashing introduced virtual nodes in the same breath, for exactly this reason.
2. The returns shrink quadratically. Halving the imbalance costs four times the virtual nodes, because CV falls as 1/sqrt(V). Past V ≈ 200 you are buying single-digit percentages of capacity with a ring that grows linearly, which is why real systems use 100–256 virtual nodes, never 10,000.
3. The randomness has an effective sample size of V, not the key count. A billion keys average nothing out here, because the whole assignment is fixed by just N x V arc boundaries; the keys are along for the ride.

The core of the implementation, which the numbers above are measured against:

import bisect, hashlib

class HashRing:
    """A key belongs to the first ring position clockwise from hash(key),
    wrapping at the top. That convention is what makes a join steal exactly
    one arc per virtual node."""

    def __init__(self, nodes=(), vnodes=200):
        self.vnodes = vnodes
        self._owner = {}          # ring position -> physical node
        self._pos = []            # sorted ring positions
        for n in nodes:
            self.add(n)

    @staticmethod
    def _h(s):
        return int.from_bytes(
            hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

    def add(self, node):
        for i in range(self.vnodes):
            p = self._h(f"{node}#{i}")
            if p in self._owner:
                continue          # collision: drop the duplicate point
            self._owner[p] = node
            bisect.insort(self._pos, p)

    def remove(self, node):
        for i in range(self.vnodes):
            p = self._h(f"{node}#{i}")
            if self._owner.get(p) == node:
                del self._owner[p]
                self._pos.pop(bisect.bisect_left(self._pos, p))

    def get(self, key):
        i = bisect.bisect(self._pos, self._h(key))
        return self._owner[self._pos[i % len(self._pos)]]   # wrap at the top

    def preference_list(self, key, r):
        """First r DISTINCT physical nodes clockwise. Skipping repeats is
        mandatory: with V=200 the next point is very often another vnode of
        the same machine."""
        i = bisect.bisect(self._pos, self._h(key))
        out = []
        for j in range(len(self._pos)):
            n = self._owner[self._pos[(i + j) % len(self._pos)]]
            if n not in out:
                out.append(n)
                if len(out) == r:
                    break
        return out

Measured over 200,000 keys, a 16 -> 17 join moves 0.0593 (predicted 1/17 = 0.0588), every moved key lands on the new server and none is shuffled between incumbents, and the mod N control over the same keys moves 0.9406 (predicted 0.9412).

What V costs

There are four costs: two are negligible, one binds only at large fleets, and the fourth is a durability problem most explanations never mention.

Memory comes first. The ring holds N x V entries at 16 bytes each:

N = 16,     V = 200      51 KB    L2-resident
N = 1,000,  V = 200      3.2 MB   L3
N = 10,000, V = 200      32 MB    spills to main memory

So the ring stays in fast on-chip cache until the fleet reaches thousands of nodes.

Lookup is the second. A binary search over M entries costs ceil(log2 M) probes. At M = 3,200 that is 12 probes, all in L2, about 48 ns. Even at M = 2,000,000 where the lower levels miss to main memory, the worst case is ~844 ns, 0.17% of the 500,000 ns network round trip that follows every lookup. Lookup cost is never the reason to limit V.

Gossip is the first cost that is real. Every client and server holds its own copy of the ring, so the full list of N x V positions and owners has to be shipped to everyone on every membership change:

N = 1,000, V = 200:  ring is 3.2 MB -> 3.2 GB broadcast -> 25.6 s of a saturated 1 Gbps link
N = 1,000, V = 16:   ring is 256 KB -> 256 MB broadcast -> 2.05 s

This is why Cassandra’s num_tokens (its name for V) default dropped from 256 to 16 in 4.0. The balance gets worse (CV rises from 0.07 to 0.25 at N = 1,000), but a large cluster gets its balance from a deliberate token allocation algorithm that chooses positions to even out the arcs, so it no longer needs a large V to average the randomness away.

Durability is the cost nobody names. With replication factor R, a key’s copies live on the next R distinct nodes clockwise, its replica set. Data is lost only when every member of some replica set fails at once, so the question is how many distinct replica sets exist across the ring. Few means most multi-node failures hit machines that never shared data. Many means almost any combination destroys something.

V = 1,   N = 16, R = 3:  16 arcs -> 16 replica sets
V = 200, N = 16, R = 3:  3,200 arcs, far more than C(16,3) = 560 possible
                         triples, so essentially EVERY triple is a replica set

C(16,3) = 560 is the number of ways to choose 3 of 16 machines. Turn the count into a probability: fail 3 random machines at once, and the chance you destroyed data is the chance that triple happens to be a replica set:

V = 1     16 / 560   =  2.9%
V = 200   essentially every triple  ~=  100%

Raising V from 1 to 200 takes an arbitrary 3-node failure from a 2.9% chance of data loss to a near-certain one. The expected bytes lost are unchanged (the same data sits on the same machines), but the probability of any loss at all went to one, and outages are counted by incidents, not by expected bytes.

The fix is not fewer virtual nodes; it is constraining which nodes may share a replica set. A rack is a cabinet of machines sharing power and a switch, so they fail together; an availability zone is the same idea one scale up. Rack- and AZ-aware placement skips any candidate replica whose rack already appears in the preference list, collapsing the replica-set count back to something structured and guaranteeing the copies land on independent failure boundaries. The correct statement is “virtual nodes plus rack awareness,” not virtual nodes alone.

The verdict, all at N = 1,000:

What consistent hashing does not fix

The technique has a boundary: it balances the keyspace. It does not balance bytes, and it does not balance requests. Three balance problems get conflated, and only the first is solved by the ring:

A hot key is a single key taking a wildly disproportionate share of requests: a celebrity profile, a viral post. With 100,000 QPS over 16 servers (6,250 each on average) and one hot key taking 30,000, the server owning it sees 30,000 + 70,000/16 ≈ 34,375 QPS, or 5.5x the mean. A single key has exactly one hash, falling in one arc, belonging to one server. V = 10,000 changes nothing, because the variance argument was about many keys, not one.

The three real fixes, in the order to reach for them:

1. Cache in front, and coalesce. A hot key is hot because it is read constantly, which makes it the easiest thing to cache. Give the front tier a copy with a short TTL (time to live, after which it is refetched): one fetch per second per front-end turns 30,000 QPS into ~20 QPS reaching the ring across 20 front-ends. Add single-flight so that when the copy expires only one request refills it while the rest wait. Otherwise expiry sends 30,000 concurrent requests through at once (a cache stampede). This lives entirely outside the partitioner and is usually the answer.
2. Split the key. Store the value under R derived names k#0..k#R-1, writing all and reading a random one. At R = 8 that is 3,750 QPS per copy, below the mean. Costs: writes fan out eight ways, and the copies go stale independently: right for a hot counter, wrong for a hot document.
3. Bounded-load consistent hashing. Cap each node at c x mean and, when the natural owner is full, probe clockwise for one that is not (about 4 probes at c = 1.25). This bounds imbalance from many warm keys but cannot help a single hot key, and it makes the assignment depend on live load, so the lookup is no longer a pure function of the key. That is why it lives in load balancers, not storage.

Real traffic follows a Zipf distribution (the most popular item gets roughly twice the requests of the second, three times the third), so one key holding 30% of traffic is a normal Tuesday, and no ring parameter repairs it.

Which assumptions are load-bearing

Every scheme here is correct only in a world that behaves a certain way. An assumption is load-bearing when its failure forces a change of algorithm, not a tuned parameter.

Bottlenecks and scaling

Which constraint binds depends on the fleet size, and for small fleets nothing binds.

Adding k nodes at once moves k/(N+k), which is nearly identical to k separate joins in total bytes: 16 -> 18 in one batch is 11.1% against 11.4% sequentially. So the argument for batching is not bytes; it is that each rebalance has its own correctness window and throttling budget, and that the inbound work then lands on k receiving cards instead of arriving serially at one. Scale in batches sized to the migration window, not to the capacity deficit.

Failure modes

Alternatives

Move from the ring to fixed logical shards if you find yourself building a rebalancing tool anyway. At that point you already have the routing table, and the ring’s only remaining advantage is that it needs no coordination.

Conclusion

• mod N moves 1 - 1/(N+1) of the corpus on a join: 94% at 16 nodes, worse as the fleet grows, because it maps keys to residues and changing N renumbers them all. The exception is a fleet that only ever doubles.
• The ring moves 1/(N+1) (5.9% at 16 nodes), and that is the information-theoretic floor, not just a small number. But a join is inbound to one node, so the ring’s real win over mod N is fewer bytes on the wire and fewer machines degraded, not faster wall-clock.
• Virtual nodes buy variance, not mean. V cancels out of the movement; what it changes is load spread, as CV ≈ 1/sqrt(V). V = 1 is unusable (peak is H_N); the useful range is 100–256, past which returns shrink quadratically.
• The real cost of V is gossip and durability, not memory or lookup. Large V makes nearly every triple of nodes a replica set, so the fix for correlated failure is rack-aware placement, not a smaller V.
• Consistent hashing balances the keyspace, nothing else. A hot key is a request-distribution problem, solved by caching and key splitting outside the partitioner.

One line to remember: the ring exists to move as few bytes as possible when membership changes, and it does nothing else for you.

Further reading

• Karger, Lehman, Leighton, Panigrahy, Levine, Lewin, Consistent Hashing and Random Trees, STOC 1997: the original paper, which introduces virtual nodes alongside the ring.
• DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007: virtual nodes and preference lists in a production system.
• Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm arXiv:1406.2294 (2014): jump consistent hash.
• Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016.
• Mirrokni, Thorup, Zadimoghaddam, Consistent Hashing with Bounded Loads, arXiv:1608.01350 (2016).
• Apache Cassandra, CASSANDRA-13701, “Lower default num_tokens”: the gossip-versus-balance trade in practice.

The preference list produced here is consumed by the key-value store design, where the R returned replicas become a quorum and are allowed to disagree until enough of them confirm a write.