Consistent hashing architecture — ring, virtual nodes, bounded loads, variants

Why architecture matters here

Consistent hashing is elegant but not maintenance-free. Naive rings produce uneven distribution — some nodes get 30% of keys, others 5%. Adding a node triggers migration; if not throttled, it saturates the network. Removing a node without gossip agreement causes double reads or lost writes.

The architecture matters because virtual nodes solve distribution, bounded loads prevent hotspots, cluster management provides consistent membership, and the client library caches topology for fast routing.

Understanding the pieces lets you scale linearly and rebalance safely.

The architecture: every piece explained

The top strip is the core algorithm. Key hashes to a point on the Hash ring. Nodes own arcs of the ring; the key is assigned to the next node clockwise. Virtual nodes — each physical node registers many random points — smooth distribution and reduce jitter on membership changes.

The middle row is the extensions. Replica walk assigns the next K distinct nodes clockwise for replication. Add / remove node reassigns only the arcs of the affected node's neighbors. Bounded loads caps how much any one node owns; overflow spills to the next node. Variants — Anchor, Jump, Rendezvous (highest random weight) — each optimize for different properties (memory, evenness, minimal disruption).

The lower rows are management. Cluster manager handles membership via gossip or a coordination service. Client library caches the topology and refreshes on version bumps. Ops covers rebalance windows, hotspot mitigation, and drift detection when clients see stale topology.

What plain modulo sharding costs on a resize

The naive shard function is node = hash(key) % n. It is uniform, it is one instruction after the hash, and it is correct right up until n changes. When n changes it is catastrophic, and the reason is arithmetic rather than engineering: a key keeps its home across the change only when h % n == h % (n+1), which holds for roughly one key in n+1. Going from 10 nodes to 11 leaves about 9% of keys where they were and relocates the other 91%. Going from 10 to 20 -- the doubling you might expect to be the friendly case, since it is friendly for a hash table -- still moves about half.

What that costs depends on what the shard holds. For a cache tier it is a miss storm: 91% of lookups miss at the same instant and fall through to the origin, which then sees its read load multiplied by whatever the hit rate was hiding. A 95% hit rate means the backing store briefly absorbs roughly 20x its steady-state traffic, and it absorbs it precisely when you are already short of capacity, because being short of capacity is why you were adding a node. For a data tier it is worse: the keys do not merely miss, they are on the wrong machine, so the resize is a near-total reshuffle that has to complete before the new mapping is even correct.

The bar to clear is easy to state. With K keys and n nodes, a new node has to receive about K/n keys or it is not carrying its share, so K/n is a lower bound on how much data any correct scheme moves. Consistent hashing meets that bound: adding the (n+1)-th node moves about K/(n+1) keys, and it moves them only from existing nodes to the new one, never between existing nodes. Modulo hashing moves K*n/(n+1). The gap is a factor of n, and closing it is the entire point of the algorithm.

The ring, and where the K/n bound comes from

Take the hash output as a fixed-width unsigned integer and treat that space as a circle, so that 0 follows 2^64 - 1. Hash every key into the circle. Hash every node identifier into the same circle. A key belongs to the first node found walking clockwise from the key's position, its successor. Nothing is stored anywhere: ownership is a comparison between two numbers, so any process holding the node list computes it without asking a coordinator.

Now perturb the membership. Adding node X drops one new point onto the circle. The only keys whose successor changes are the ones lying in the arc between X and the node that previously preceded X; every key outside that arc still meets the same first node clockwise. Those keys come from exactly one node -- X's successor -- and every one of them goes to X. With n points placed pseudo-randomly, the expected length of that arc is 1/(n+1) of the circle, so about K/(n+1) keys move and no other node-to-key pairing is disturbed. Removing node Y is the mirror image: Y's arc merges into its successor's arc, about K/n keys move, one node absorbs all of them, and nothing else is reassigned.

Two properties fall out, both easy to state and easy to forget under pressure. Movement is minimal, matching the K/n lower bound. And movement is local: a change at one point on the circle cannot reassign a key on the far side of it. That locality is what makes rolling membership changes survivable, because the blast radius of a node event is one arc rather than the cluster. The construction is from Karger et al. (1997), where the motivating problem was spreading web pages over a changing set of caches with no coordinator -- still the shape of problem it fits best.

Lookup is a successor query on a sorted set

Once you accept the ring, the implementation question is narrow: given a hash position, find the smallest node position greater than or equal to it, wrapping to the first if there is none. That is a successor query over a mostly-static sorted set, and the default answer is a sorted array plus binary search.

import bisect, hashlib

def h64(b: bytes) -> int:
    return int.from_bytes(hashlib.blake2b(b, digest_size=8).digest(), "big")

class Ring:
    def __init__(self, nodes, vnodes=256):
        self.vnodes = vnodes
        self.build(nodes)

    def build(self, nodes):
        pairs = []
        for node in nodes:
            for i in range(self.vnodes):
                # separator matters: "node1"+"0" == "node10"+"" without it
                pairs.append((h64(f"{node}#{i}".encode()), node))
        pairs.sort()
        self.pos    = [p for p, _ in pairs]      # nV sorted ring positions
        self.owner  = [o for _, o in pairs]

    def locate(self, key: str) -> str:
        i = bisect.bisect_right(self.pos, h64(key.encode()))
        return self.owner[i % len(self.owner)]   # the modulo IS the wraparound

    def replicas(self, key: str, k: int):
        i = bisect.bisect_right(self.pos, h64(key.encode()))
        distinct = len(set(self.owner))          # precompute; owners are static
        out, seen = [], set()
        while len(out) < k and len(seen) < distinct:
            o = self.owner[i % len(self.owner)]
            if o not in seen:                    # skip vnodes of a node already picked
                seen.add(o); out.append(o)
            i += 1
        return out

Cost: with n nodes and V virtual points each, the array holds nV entries, a lookup is log2(nV) comparisons -- 15 for a 100-node cluster at V=256 -- and the index modulo is the whole of the wraparound logic. Build is O(nV log nV), which is a real cost rather than a footnote: that same 100-node ring re-sorts 25,600 entries every time gossip reports a node up or down. If membership churns often enough for rebuild to show in a profile, swap the array for a balanced tree or a skip list and insert the joining node's V points in O(V log nV) instead of rebuilding from scratch. Note also the replicas walk: virtual nodes force a distinctness check, because the next several points clockwise are frequently more vnodes of the same machine.

A third representation changes the asymptotics rather than the constants: precompute a table. Slice the circle into a fixed number of equal buckets, resolve each bucket's owner once at build time, and a lookup becomes an array index -- O(1), no comparisons, no cache-missing binary search over a large array. You pay in memory proportional to the table size and in a full rebuild on membership change. Google's Maglev hashing is this idea done carefully, filling a fixed-size table (a prime; 65537 in the published system) so entries divide near-evenly and a backend change perturbs few of them. Redis Cluster's 16384 hash slots are the same representation with the assignment made explicit and administrative instead of hashed. The tradeoff is consistent across all of them: table designs buy O(1) lookup and give up the exact minimal-movement guarantee, because quantising the arcs into buckets rounds the boundaries.

Virtual nodes and the variance you are actually buying

One point per node distributes badly, and the failure is statistical rather than a bug you can find. n pseudo-random points on a circle do not cut it into n equal arcs; the arcs are close to exponentially distributed, and the expected largest gap is the harmonic number H_n / n, roughly ln(n)/n. At n=10 that is about 29% of the keyspace sitting on one node against a 10% mean. At n=100 it is about 5.2% against a 1% mean -- five times its fair share, permanently, decided by nothing but where the hash happened to place that node's identifier. You cannot fix it by adding nodes, and there is nothing to rebalance, because the position is a pure function of the node name.

Virtual nodes fix it by averaging. Give each machine V independent points and its share becomes the sum of V arcs instead of one. The coefficient of variation of that sum falls as 1/sqrt(V), so the relative spread in a node's load is approximately:

That table is the right way to answer "what should V be": pick the imbalance you are willing to operate at and read off V, rather than copying someone's default. The costs are the ones from the previous section -- nV entries resident in every client, a longer binary search, a bigger sort on every membership change -- and they are why nobody sets V=10000. At n=1000 and V=1000 the ring is a million entries, tens of megabytes in every process that routes, re-sorted on every gossip event.

There is a second cost that has nothing to do with memory. Raising V enrols each machine in more distinct replica sets, so a simultaneous multi-node failure becomes far more likely to take out every replica of some range; pulling the other way, more tokens means a failed node's ranges have many different successors and the rebuild runs in parallel. That failure-domain argument is worked through in Distributed Hash Table Architecture in Depth and is not repeated here. Cassandra's history is the practical summary: it shipped num_tokens = 256 for years, then moved to a much smaller default (16) paired with a token-allocation algorithm that chooses positions to balance the ring instead of drawing them at random -- buying the smoothing of a high V at a low V's cost.

Weighted nodes

Capacity is rarely uniform, particularly in a cluster that has been grown over three hardware generations. The ring expresses weight through token count: a machine with twice the disk claims 2V points and takes twice the keyspace in expectation. The limitation is granularity. Token counts are integers, so at V=8 the finest weight ratio you can express is 9:8, and expressing a 1.15x difference means raising V for every node in the cluster. Changing a weight also means redrawing that node's points, which moves keys. If your weights are continuous and change often -- autoscaled instances of mixed size, for example -- rendezvous hashing expresses them exactly and with no rebuild at all, which is a better reason to choose it than any lookup-cost argument.

Choosing the hash function

The ring needs uniformity and avalanche. It does not need cryptographic strength, and the three requirements that actually matter get conflated constantly.

Distribution quality. Structurally similar keys -- user:1000 and user:1001, or paths sharing a long prefix -- must land far apart on the circle. Java's String.hashCode, a 31-multiplier polynomial, does not clear this bar: its avalanche in the high bits is weak and short similar strings cluster tightly, so truncating it to a ring position produces visible, reproducible skew. MurmurHash3, xxHash, and the SipHash and BLAKE families all clear it comfortably; Cassandra's default Murmur3Partitioner is the same choice. A bare CRC32 is a checksum, not a hash function for placement, and it should not be used here either.

Cost at the call site. Hashing runs per request, sometimes per replica candidate. For the short keys typical of a cache or a partition key the number that matters is latency per call, not streaming throughput: MD5 or SHA-1 over a 32-byte key costs on the order of a hundred nanoseconds where xxHash costs a few. Cryptographic hashes are not wrong here -- the output gets truncated to 64 bits anyway -- they are simply paying for collision resistance against an adversary, a property ring placement never uses.

Determinism across every process that computes the ring. This is the requirement that causes incidents. The key hash and the node-point hash must be the same function over the same space in every client, in every language, at every version. A client library that quietly switches hash implementations on upgrade, or that seeds from something process-local, computes a different ring and routes to a machine that does not hold the data -- and it does so silently, returning a miss rather than an error. Pin the algorithm and the seed in configuration, treat both as part of the wire contract, and version the ring so a mismatch is detectable instead of invisible.

One implementation detail with teeth: derive virtual-node points from a separated string such as node + "#" + i, never bare concatenation. "node1" + "0" and "node10" + "" are the same bytes, so two machines claim the same ring point and which one wins depends on sort stability. And note that the double-hashing shortcut from Bloom filter implementations -- deriving many indices as h1 + i*h2 -- does not transfer to generating V ring positions. Those positions come out evenly spaced and correlated, which destroys the independence the 1/sqrt(V) variance argument depends on. Hash node#i properly for each i.

End-to-end flow

End-to-end: a Cassandra cluster uses vnodes with 256 tokens per node. A key hashes to a point; ring lookup finds the owner; replica walk finds the next 2 replicas for RF=3. Query routes to the coordinator, then to the owners. A new node joins; gossip propagates; each existing node hands over its share of arcs. Migration is throttled to preserve throughput. Client libraries observe the topology change and refresh caches. Bounded load prevents any single node from being overwhelmed; the cluster stays balanced during the rebalance.

Rendezvous hashing: no ring at all

Highest random weight hashing (Thaler and Ravishankar, 1996) does the same job with no ring, no virtual nodes, no build step and no state beyond the node list. For key k and every node i, compute w_i = h(k, node_i), and assign k to whichever node produced the largest w.

import math

def hrw(key, nodes):
    return max(nodes, key=lambda n: h64(f"{key}|{n}".encode()))

def hrw_weighted(key, nodes):            # nodes: {name: weight}, exact continuous weights
    def score(n):
        u = h64(f"{key}|{n}".encode()) / 2**64      # uniform in (0,1)
        return -nodes[n] / math.log(u)
    return max(nodes, key=score)

def hrw_replicas(key, nodes, k):         # full failover order falls out for free
    return sorted(nodes, key=lambda n: h64(f"{key}|{n}".encode()), reverse=True)[:k]

It has the same minimal-disruption property. Removing a node only affects keys whose maximum was that node -- about K/n of them -- and each moves to whichever node held the second-largest weight, a node the removal did not touch. Adding a node only captures keys where its weight is the new maximum. Same K/n bound, reached without the ring's variance problem at all: distribution is exactly as uniform as the hash function, because every node draws an independent weight for every key instead of owning an arc whose length was decided by luck.

Two things it gives you that a ring does not. Sorting the weights yields a complete ranked ordering of all n nodes for that key, so the replica set is simply the top k -- no clockwise walk, no deduplicating virtual nodes of the same machine, and the failover order for a request is free. That is why it shows up in proxy upstream selection and in cache client libraries. And weights are continuous: score node i as -w_i / ln(u_i) with u_i the hash mapped into (0,1), and a node with weight 2.7 receives exactly 2.7 times the share, with no token granularity and no rebuild.

The cost is O(n) hashes per lookup, and that is far less disqualifying than it sounds. With a fast hash at a few nanoseconds per short input, a 20-node cluster resolves in well under a microsecond -- in practice often faster than a binary search that cache-misses its way through a 25,000-entry ring array, because the node list fits in L1 and the ring array does not. At 1000 nodes it is microseconds per lookup and clearly the wrong structure. Skeleton-based rendezvous restores O(log n) by arranging nodes in a virtual hierarchy and running HRW at each level, giving up some of the exact minimal-movement property in exchange. The rule of thumb: rendezvous below a few dozen nodes, especially when you want ranked failover or exact continuous weights; a ring above that.

Jump consistent hash: no node list either

int32_t jump_hash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1));
    }
    return (int32_t) b;
}

Lamping and Veach's algorithm maps a key to a bucket in [0, num_buckets) using no memory whatsoever -- no ring, no table, not even the list of node names -- in about ln(n) loop iterations. Its balance is essentially perfect, far better than any practical vnode ring, and its movement on a resize is exactly optimal rather than approximately: growing from n to n+1 relocates precisely the 1/(n+1) fraction that has to move.

The constraint is severe, and it is why this is not simply the default everywhere. Buckets are ordinal, and the only bucket you can remove is the last one. There is no node identity inside the function, so there is no way to express "node 3 of 10 has died". You can only shrink to 9 buckets, which relocates bucket 9's keys and leaves bucket 3's keys still pointing at a dead machine. Weights cannot be expressed either.

The pattern that makes it genuinely useful is indirection. Use jump hash to map keys to a fixed, generous number of logical shards -- 4096, say -- and keep a separate shard-to-node table owned by the cluster manager. Key placement then never changes at all, and a node failure edits a small table that is cheap to distribute and cheap to version. This is exactly the shape of Redis Cluster's fixed slot map and of Maglev's lookup table, and it is the right structure whenever shard count is a planning decision and node membership is an operational one. Jump hash is excellent at the first job and structurally incapable of the second, so do not ask it to do both.

Bounded-load consistent hashing

Uniform in expectation is not uniform in the moment. Even a well-tuned ring leaves some node tens of percent above the mean at any instant, and key popularity is nowhere near uniform, so whichever node owns a popular arc runs hot while others idle. Consistent hashing with bounded loads (Mirrokni, Thorup and Zadimoghaddam) adds a single rule: compute a capacity cap = ceil(c * average_load) for some c > 1, and when the clockwise walk arrives at a node already at cap, keep walking to the next node below its cap.

The guarantee is that no node exceeds c times the average, for any c > 1 you pick, while the amortised number of reassignments per node or key event stays bounded -- degrading as c approaches 1, on the order of 1/(c-1)^2. That is why c = 1.25, a 25% tolerance, is a common practical setting: tight enough to matter, loose enough that churn stays cheap. HAProxy exposes precisely this as hash-balance-factor on its consistent-hash balancer, and it is the standard answer to "my consistent-hash upstream selection keeps overloading one backend".

Understand one thing before adopting it: it makes ownership stateful. The owner of a key is now a function of the key, the ring, and the current load vector, so two routers with different views of load will disagree about where a key lives. For request routing that is acceptable, because a disagreement costs a cache miss or slightly worse affinity. For data placement it is not, because a writer and a reader that disagree touch different machines and the spilled key still has to be findable later -- which means either one router owns the decision or you are storing a real mapping and no longer doing pure consistent hashing. Bounded load is a load-balancing policy layered over consistent hashing, not a replacement placement rule.

Failure modes

Skew from too few virtual nodes. The symptom is one node whose disk usage, p99 latency or CPU sits persistently above the others and does not improve when you add capacity, because the new node lands at random positions and need not relieve the hot arc at all. Measure the actual key or byte distribution rather than assuming the ring is even -- at V=16 a 25% spread is expected behaviour, not an anomaly, and chasing it as a bug wastes a day.

Cascading load on node failure. With one token per node, everything the failed node held lands on exactly one successor, whose load roughly doubles. If that successor was running above 50% utilisation it now fails too, its combined share lands on the next node, and the ring unzips one machine at a time. This is a real production pattern, not a thought experiment. Virtual nodes are the structural fix: a failed machine's V arcs have V different successors, so its load spreads across the cluster rather than concentrating. Capacity headroom, bounded load, and shedding at the node are the other layers. For a pure cache tier, an explicit "on node down, fail through to the origin rather than reassign" policy is often better than reassigning, since a reassignment buys you a cold miss anyway and permanently disturbs the mapping.

Hot keys, which no partitioner fixes. A single key that is 20% of traffic is a single point on the circle, and the only lever the algorithm has is which node that point lands on. Bounded load helps when many keys make a node hot and does nothing when one key does: the cap pushes other keys off the node while the hot key stays exactly where it was. Every real fix lives above the algorithm -- split the key into key#0 .. key#N and fan out reads, replicate the hot entry to every node under a short TTL, or put a small client-side cache in front of the ring, which absorbs a Zipfian head far more effectively than any partitioner change. Detecting which keys are hot needs per-key frequency counters at a footprint you can afford, which is what a Count-Min Sketch is for.

Topology drift. Every process computing the ring must agree on membership as well as on the hash function. A client with a stale node list computes a stale owner, and the symptom is a wrong answer rather than an error: a read that misses, or a write accepted by a node that no longer owns the range. Version the membership, stamp the version on requests, and have the server redirect or reject on mismatch instead of serving. Redis Cluster's MOVED redirect is this pattern made explicit; a client that caches the ring and never revalidates it is the version that pages you at 03:00.

Membership flap. Consistent hashing makes a membership change cheap, which tempts a system into reacting to every failure-detector blip. Each flap still relocates K/n keys and starts streaming. Separate the two decisions: routing around an unresponsive node should be immediate, while reassigning its ranges should require it to have been down for a settled interval.

Choosing between the variants

Read the table as a decision rather than a menu. If the node set is small, stable and heterogeneous, and you want a ranked failover order, rendezvous is simpler and more accurate than a ring and its O(n) lookup is irrelevant. If the node set is large or churns, the ring with a V chosen from the variance table is the workhorse, and it is what Dynamo-derived stores use. If your real unit of placement is a shard rather than a machine, put jump hash or a slot table between keys and shards and keep a small mutable shard-to-node map -- that is the design that makes node replacement a table edit instead of a data migration. Bounded load layers on top of any of them, and belongs on the request path, not the storage path.