Consistent Hashing: Keys to Nodes Without Global Reshuffles

TL;DR: Consistent hashing maps keys to nodes so that adding or removing a node moves only ~1/N of keys, not nearly all of them.^[1] Virtual nodes are mandatory at real scale to smooth load variance from ~100% down to ~10% standard deviation at V=100.^[2] Bounded-load consistent hashing caps any single node at c times the average, eliminating hot-node cascades. Rendezvous hashing is simpler for small N. Maglev hashing gives O(1) lookup for L4 load balancers at 10 Gbps line rate.^[3] Pick the variant that matches your constraints on memory, lookup time, and arbitrary-node removal.

Learning Objectives#

After this module, you will be able to:

• Place keys on a hash ring and find the owning node via successor lookup
• Explain why virtual nodes are needed for even load distribution
• Implement bounded-load consistent hashing to cap per-node imbalance
• Compare ring-based consistent hashing with rendezvous hashing (HRW)
• Choose between ring hash, Maglev, jump hash, and HRW for a given workload
• Apply consistent hashing to caches, sharded databases, and sticky load balancing

Intuition#

Imagine a roulette wheel with four numbered pockets. Each pocket represents a server. You spin a ball (the key) and it lands in a pocket. Simple, predictable.

Now the casino adds a fifth pocket. With modulo hashing, you would renumber every pocket and re-spin every ball. Nearly every ball lands somewhere new. Gamblers riot.

With consistent hashing, you slide the new pocket into the wheel between two existing ones. Only the balls that would have landed in that specific gap move to the new pocket. The rest stay put. One-fifth of the balls move, not four-fifths.

Virtual nodes are like giving each server multiple pockets scattered around the wheel instead of one contiguous wedge. If a server goes down, its scattered pockets distribute their balls to many different neighbors rather than dumping everything on a single successor.

This is the entire value proposition: when the node set changes, most keys stay where they are. The rest of this chapter unpacks the six major variants and when to use each.

Theory#

Why modulo hashing breaks#

The simplest key-to-node mapping is node = hash(key) % N. It is uniform, O(1), and requires zero state. It works perfectly when N never changes.

The moment N changes, nearly everything moves. Scaling a memcached fleet from 9 to 10 nodes remaps approximately 9/10 of all keys.^[4] Richard Jones at Last.fm described this failure mode when introducing the Ketama library: "everything hashed to different servers, which effectively wiped the entire cache."^[4:1] The backing database absorbs a cold-cache storm of the full request rate simultaneously.

For sharded databases, the same arithmetic means moving ~90% of all data on a single topology change. This is not an edge case. It is the expected behavior of modulo hashing under any membership change.

Use modulo hashing only when N is fixed and known at compile time: parallel worker bucketing, in-memory lock tables, static shard counts that never grow.

The hash ring (Karger 1997, successor lookup)#

Karger et al. introduced consistent hashing at STOC 1997.^[1:1] The idea: map both keys and nodes onto a ring of integers [0, 2^m). Each key belongs to the first node encountered clockwise from its hash position.

Each key walks clockwise to the first node it encounters; Node B owns keys in the arc from A's position to B's position.

Lookup: Binary-search the sorted array of node positions for the smallest position >= key hash. Wrap to position 0 if the key hash exceeds all node positions. This is O(log(V * N)) where V is virtual nodes per physical node.

Key property: Adding a node steals only the arc between it and its predecessor. Expected fraction of keys moved: 1/N.^[1:2] Removing a node hands its arc to its successor. All other keys stay put.

The 1997 paper proved that with high probability each node receives O((log N)/N) fraction of keys. But with only one hash point per physical node, the variance is large. This is why virtual nodes are mandatory in practice.

Adding Node E between D and A steals only the arc from D to E; all keys owned by A, B, and C stay put. Expected fraction of keys moved: 1/N.

Virtual nodes (Ketama, Cassandra 256 default, heterogeneous capacity)#

Without virtual nodes, each physical node owns one contiguous arc. Arc lengths are highly non-uniform. Worse, when a node fails, its entire arc dumps onto a single successor, potentially overloading it and triggering a cascade.

Virtual nodes solve both problems. Hash each physical node V times onto the ring (e.g., nodeA-0, nodeA-1, ..., nodeA-V). Now each physical node's load is the sum of V small arcs scattered around the ring. Failure distributes load to V different successors instead of one.

Each physical node maps to V virtual positions scattered around the ring; on failure, load spreads to V different successors rather than one.

Practical numbers:

• Ketama (libketama) hashes each server 40 times with MD5, extracting 4 points per digest, yielding 160 ring points per server.^[5]
• Cassandra's default num_tokens was 256 in versions 2.x through 3.x. Starting with Cassandra 4.0, the default is 16 with the token allocation algorithm.^[6][7]
• Damian Gryski's simulations show standard deviation of ~10% at V=100 and ~3.2% at V=1000.^[2:1]

Heterogeneous capacity: Give bigger machines more virtual nodes. Envoy's ring-hash load balancer gives a weight-2 host twice as many ring entries as weight-1.^[8]

Bounded-load variant (Mirrokni 2016, capacity cap c)#

Classic consistent hashing balances keys, not requests. If 50% of traffic targets one key, that key's node sees 50% of traffic regardless of how many virtual nodes you have.

Bounded-load consistent hashing adds a hard capacity cap: each node accepts at most c * (total_load / N) requests, where c > 1 is the balancing factor (typically 1.25 to 2). When a key's preferred node is full, probe clockwise to the next node with capacity.^[9][10]

Mirrokni, Thorup, and Zadimoghaddam proved that each insertion or deletion causes only O(1/e^2) key movements (where e = c - 1), independent of N or total keys.^[10:1] At e = 0 the algorithm degenerates to least-loaded; as e approaches infinity it becomes plain consistent hashing.

The algorithm preserves cache locality: for the same preferred host, the same fallback sequence is used on overflow. This means a hot key's overflow traffic still benefits from caching on a predictable set of nodes.

Rendezvous / HRW hashing (O(N) lookup, simpler for small N)#

Rendezvous hashing (Thaler and Ravishankar, 1996) predates Karger's ring by a year.^[11] For a key k, compute h(k, node_i) for every node i and assign k to argmax_i h(k, node_i). No ring. No virtual-node table. No preprocessing.

Trade-offs:

• O(N) per lookup, but the inner loop is tight: one XOR and a cheap integer hash (xorshift-multiply) per node. For N up to ~1000, this is competitive with ring-hash binary search.^[2:2]
• Adding a node: only keys whose new hash beats the current owner's move (probability 1/N). Disruption is provably minimal.^[12]
• Weighted HRW scales each score by -weight / log(h) so weights compose cleanly.^[12:1]

Production users: GitHub's load balancer, Apache Ignite, Apache Druid, Tahoe-LAFS, IBM Cloud Object Storage, and Apache Kafka clients.^[12:2]

Use rendezvous hashing when N is small (under ~1000), you want zero preprocessing, and you value implementation simplicity over lookup speed.

Maglev hashing (connection-consistent L4 LB, lookup table)#

Google's Maglev (NSDI 2016) builds a fixed-size lookup table of size M (a prime, typically 65,537).^[3:1] Each backend fills in its preferred slots via a permutation sequence until the table is full. At lookup time: hash the 5-tuple, index into the table. O(1).

Each backend claims its most-preferred empty slot in round-robin turns; lookup is a single array index into the filled table.

Performance: Maglev saturates a 10 Gbps link with small packets on a single commodity server.^[3:2] Envoy benchmarks show Maglev is ~5x faster for host selection and ~10x faster for table build compared to a 256K-entry ring hash.^[8:1]

Disruption: Roughly double that of ring hash on backend changes. Envoy's docs note "approximately double the keys will move" compared to ring hash.^[8:2] This is acceptable for L4 load balancers where connection tracking handles the common case.

Deployments: Google (since 2008), Meta's Katran (XDP-based, kDefaultChRingSize = 65537), Envoy (configurable up to 5,000,011), and Cilium's eBPF datapath.^{[13][8:3][14]}

Jump hash (Google 2014, O(1) space O(log N) time)#

Lamping and Veach published jump consistent hash in 2014.^[15] It uses the key as a PRNG seed and "jumps" forward through bucket indices probabilistically. Five lines of code. Zero memory. O(log N) time. Standard deviation of bucket sizes: ~0.000000764%.^[2:3]

func Hash(key uint64, numBuckets int) int32 {
    var b int64 = -1
    var j int64
    for j < int64(numBuckets) {
        b = j
        key = key*2862933555777941757 + 1
        j = int64(float64(b+1) *
            (float64(int64(1)<<31) / float64((key>>33)+1)))
    }
    return int32(b)
}

Critical limitation: Buckets are indexed 0..N-1. You can only add or remove at the top end. Removing an arbitrary bucket in the middle is not supported.^[15:1] This makes jump hash unsuitable for caches where any node can crash. Use it for sharded databases where replication handles failure and the shard set grows monotonically.

Real-World Example#

Vimeo's bounded-load consistent hashing in HAProxy (2016)

Vimeo's Skyfire video-packaging service routes requests through a shared memcached layer. With standard consistent hashing, autoscaling the application tier caused cache-hit-rate instability: each scale event moved keys, triggered cache misses, and forced memcached to re-fetch from origin.

Andrew Rodland implemented bounded-load consistent hashing in HAProxy (released in HAProxy 1.7, November 2016).^[16] The algorithm caps each backend at c times the average load. When a backend hits capacity, requests overflow to the next node in the ring's clockwise sequence.

Results: Shared-cache outbound bandwidth dropped from 400 to 500 Mbit/s per server at peak (~8 Gbit/s total across the fleet) down to below 100 Mbit/s per server, a 4-5x per-server reduction (~8x fleet-wide).^[16:1] Cache-hit rate stabilized and became insensitive to autoscaling-driven fleet size changes.

The key insight: standard consistent hashing moves ~1/N of keys on a topology change, but if those keys are hot, the cold-cache storm on the new node is disproportionate to the fraction moved. Bounded-load CH prevents any single node from absorbing more than c times the average, so even hot-key overflow distributes predictably.

Google deployed the same algorithm in Google Cloud Pub/Sub.^[9:1] Envoy's documentation recommends Maglev as "very likely a superior drop-in replacement for ring hash" for Redis-like caches, but bounded-load ring hash remains the best choice when you need both cache locality and hard load caps.^[8:4]

Trade-offs#

Common Pitfalls#

Exercise#

You run a distributed cache of 20 memcached nodes serving 1M RPS. You plan to scale to 40 nodes over the next quarter. Design the client-side routing: pick consistent hashing vs rendezvous, choose virtual-node count, bounded-load factor, and describe the cache-hit-rate behavior during the scale-out.

Key Takeaways#

• Consistent hashing minimizes data movement when the node set changes: ~1/N of keys move per addition or removal, not ~(N-1)/N.
• Virtual nodes are not optional at any real scale. Start with V=100 to 200 for caches; tune based on observed load variance.
• Bounded-load consistent hashing (c = 1.25 to 2) prevents hot-node cascades and stabilizes cache-hit rates under autoscaling.
• Rendezvous hashing is simpler than ring-based for small N (under ~1000 nodes). Do not default to ring hash if HRW suffices.
• Maglev hashing gives O(1) lookup for L4 load balancers but moves ~2x more keys than ring hash on topology changes.
• Jump hash has near-perfect distribution and zero memory, but cannot remove arbitrary nodes. Use it only for monotonically-growing shard sets.
• Ketama-style client libraries (libketama, Envoy ring_hash, Redis Cluster) give you consistent hashing for free. Read their docs before reinventing.

Further Reading#

• Consistent Hashing and Random Trees (Karger et al., STOC 1997) - The original paper proving the K/N bound and defining ring construction; read at least the theorem statement on balance and spread.
• Consistent Hashing: Algorithmic Tradeoffs (Damian Gryski, 2018) - The single best practitioner comparison of jump, multi-probe, Maglev, HRW, and bounded-load with benchmarks and standard-deviation measurements.
• Improving load balancing with a new consistent-hashing algorithm (Andrew Rodland, Vimeo 2016) - How bounded-load CH went into HAProxy and cut Vimeo's cache bandwidth 8x; the most persuasive production case study.
• Maglev: A Fast and Reliable Software Network Load Balancer (Eisenbud et al., NSDI 2016) - Google's L4 LB architecture including the permutation-table algorithm.
• A Fast, Minimal Memory, Consistent Hash Algorithm (Lamping and Veach, 2014) - Jump hash in five lines of code; read for the elegance and the limitation.
• Consistent Hashing with Bounded Loads (Mirrokni, Thorup, Zadimoghaddam, 2016) - The theoretical foundation for bounded-load CH with the O(1/e^2) movement proof.
• Envoy supported load balancers - Operational guidance on ring hash vs Maglev vs P2C with configuration examples.
• libketama: Consistent Hashing library for memcached clients (Richard Jones, 2007) - The post that popularized consistent hashing for caches; includes the cold-cache storm motivation.

Flashcards#

References#