You have a cluster. You add a node. Half your cache misses. You remove a node. The other half misses. You’ve just experienced the canonical distributed systems pain point that consistent hashing was invented to solve — and after twenty years, most engineers still reach for the ring algorithm by default, even when it’s the wrong tool.
There are three serious consistent hashing algorithms in wide use: ring (Karger et al., 1997), rendezvous (HRW, Thaler & Ravishankar, 1996), and jump (Google, 2014). They solve the same core problem — map keys to nodes such that only k/n keys move when you add or remove a node — but they have wildly different properties around balance, memory, speed, and tolerance for node heterogeneity. Picking the wrong one means either reimplementing it later under pressure, or shipping subtle load imbalance into production.
This article is the thing I wish existed when I was architecting my first distributed cache layer. We’ll implement all three, profile them against each other, and be blunt about where each one bites you.
The Naive Approach and Why It Doesn’t Scale
Before getting into consistent hashing, let’s be clear about what we’re replacing.
The textbook approach: node = hash(key) % num_nodes. Fast, simple, dead on arrival the moment your cluster changes size. When n becomes n+1, nearly every key % n changes its remainder. You’re not moving 1/n of your keys — you’re moving (n-1)/n of them. For a 10-node cluster, adding one node moves roughly 90% of your data. For a distributed cache, that’s a thundering herd. For a distributed database shard, that’s a migration nightmare.
Consistent hashing fixes this by decoupling the key space from the node count. The core guarantee: when the number of nodes changes by 1, only O(1/n) keys need to remap. This is the property all three algorithms provide. The differences start after that.
Ring Consistent Hashing
Ring hashing (Chord-style, as popularized by Amazon’s Dynamo paper) maps both nodes and keys onto a circular hash space — the "ring" — typically the full 64-bit integer range. Each node gets assigned one or more positions on this ring. A key is assigned to the first node clockwise from its position on the ring.
The "virtual nodes" trick is critical here. Without it, a 3-node cluster with random positions creates a badly uneven split. Every production ring implementation uses virtual nodes: each physical node gets hashed multiple times (with different salts or indices), occupying many positions around the ring. With 150–200 virtual nodes per physical node, the distribution converges toward even.
import hashlib
import bisect
class RingHash:
def __init__(self, nodes: list[str], replicas: int = 150):
self.replicas = replicas
self.ring: dict[int, str] = {}
self.sorted_keys: list[int] = []
for node in nodes:
self.add_node(node)
def _hash(self, key: str) -> int:
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node: str) -> None:
for i in range(self.replicas):
virtual_key = self._hash(f"{node}#{i}")
self.ring[virtual_key] = node
# Rebuild sorted key list — O(n log n), only on topology change
self.sorted_keys = sorted(self.ring)
def remove_node(self, node: str) -> None:
for i in range(self.replicas):
virtual_key = self._hash(f"{node}#{i}")
del self.ring[virtual_key]
self.sorted_keys = sorted(self.ring)
def get_node(self, key: str) -> str:
if not self.ring:
raise ValueError("Ring is empty")
h = self._hash(key)
# Binary search for first position >= h (clockwise lookup)
idx = bisect.bisect_left(self.sorted_keys, h)
if idx == len(self.sorted_keys):
idx = 0 # Wrap around the ring
return self.ring[self.sorted_keys[idx]]
Lookup complexity: O(log n) — binary search on the sorted virtual-node list.
Memory: O(n * replicas) — with 1000 nodes at 150 virtual nodes each, that’s 150K entries in the ring dict. Negligible in practice.
Key movement on add/remove: O(1/n) of keys, affecting only the adjacent arc on the ring.
Where Ring Hashing Shines
Ring is the right call when your cluster changes slowly and unpredictably — nodes added one at a time, removed one at a time, sometimes with partial failures. Cassandra, DynamoDB, Riak, and most "AP" distributed databases use this model. The ring structure lets you easily reason about replication: "store key on this node and the next two clockwise nodes." That replication semantics falls out naturally from the ring topology.
Gotchas
Virtual node count is a tuning knob that bites you. Too few virtual nodes and your distribution has outliers — one node ends up holding 15% of the data while another holds 5%. Too many and your ring operations get slower and your memory footprint grows. The "right" number depends on node count and acceptable variance. For small clusters (under 20 nodes), you need more virtual nodes, not fewer. Test your distribution with a histogram before going to production.
Heterogeneous capacity is clunky. Want to give a new node 2x the capacity of the others? You have to give it 2x the virtual nodes. That works, but it couples your ring configuration to your hardware specs, and you’ll need to reconfigure every time you resize a node class. Rendezvous handles this more cleanly.
Non-deterministic across languages/libraries. If you’re routing in a Go service and reading in a Python service, and they hash virtual nodes differently, they’ll disagree on placement. I’ve seen this bug in production twice. Lock your hash function and virtual node naming scheme and test cross-language consistency explicitly.
Rendezvous Hashing (HRW — Highest Random Weight)
The rendezvous algorithm is conceptually simpler than the ring. For each key, you compute a score for every node — score(key, node) = hash(key + node) — and assign the key to the node with the highest score. That’s the whole algorithm.
import hashlib
import struct
class RendezvousHash:
def __init__(self, nodes: list[str]):
self.nodes = list(nodes)
def _score(self, key: str, node: str) -> int:
combined = f"{key}:{node}".encode()
digest = hashlib.sha256(combined).digest()
# Use first 8 bytes as uint64 for fast comparison
return struct.unpack(">Q", digest[:8])[0]
def add_node(self, node: str) -> None:
self.nodes.append(node)
def remove_node(self, node: str) -> None:
self.nodes.remove(node)
def get_node(self, key: str) -> str:
if not self.nodes:
raise ValueError("No nodes configured")
return max(self.nodes, key=lambda node: self._score(key, node))
def get_top_k(self, key: str, k: int) -> list[str]:
"""Useful for replication: returns k nodes in score order."""
scored = sorted(self.nodes, key=lambda n: self._score(key, n), reverse=True)
return scored[:k]
Lookup complexity: O(n) — you score every node for every lookup.
Memory: O(n) — just the node list.
Key movement on add/remove: O(1/n) of keys, identical guarantee to ring.
Where Rendezvous Hashing Shines
Rendezvous is the cleanest algorithm when your node list changes rarely (or is pre-loaded from a config), when you have a small-to-medium node count, and especially when nodes have different weights.
Weighted rendezvous is straightforward: assign weight w to a node by scaling the hash output. One common approach is to use -w / log(uniform_score) (the "exponential distribution" trick from the original HRW paper extensions), which makes higher-weight nodes win proportionally more keys without any virtual-node bookkeeping.
import math
def _weighted_score(self, key: str, node: str, weight: float) -> float:
combined = f"{key}:{node}".encode()
digest = hashlib.sha256(combined).digest()
score = struct.unpack(">Q", digest[:8])[0] / (2**64) # Normalize to [0,1)
# Avoid log(0) — score is never exactly 0 with a good hash, but be safe
score = max(score, 1e-10)
return -weight / math.log(score)
Varnish Cache uses rendezvous hashing for backend selection. CDN edge layers use it for origin affinity. Anywhere you’re routing requests to backends with different capacities or health weights, rendezvous gives you a knob that ring makes awkward.
Gotchas
The O(n) lookup is the killer. With 10 nodes it’s invisible. With 1000 nodes it starts to matter. With 10,000 nodes (think a large CDN PoP cluster, or a storage fleet), you’re computing 10K hashes per request. That’s 10–50 microseconds of pure CPU per lookup, which adds up fast on a hot path. There are approximate schemes that use a two-level hierarchy to reduce this to O(sqrt(n)), but they’re non-trivial to implement correctly.
Concurrency on node mutation. The node list is mutable — add/remove are common. Without a read-write lock protecting self.nodes, you have a race condition between a lookup iterating the list and a topology update modifying it. The ring approach has the same issue, but it’s more commonly called out in ring tutorials. Don’t skip the locking.
Jump Consistent Hash
Jump hash (Lamping & Veach, Google, 2014) takes a completely different approach. It uses no data structures at all. Given a 64-bit integer key and a bucket count n, it computes a bucket assignment in O(log n) time with a small constant factor, using a random-walk algorithm over bucket counts.
The full paper is five pages and worth reading. The core insight: as n grows from 1 to n, a key’s assigned bucket is stable unless the new bucket is the one the key "jumps" to. The algorithm simulates this jump sequence deterministically.
def jump_hash(key: int, num_buckets: int) -> int:
"""
Google's jump consistent hash.
key: 64-bit integer key (hash your string key first)
num_buckets: number of buckets/shards (must be >= 1)
Returns: bucket index in [0, num_buckets)
"""
b, j = -1, 0
while j < num_buckets:
b = j
key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF # LCG step
j = int((b + 1) * (1 << 31) / ((key >> 33) + 1))
return b
def jump_hash_str(key: str, num_buckets: int) -> int:
"""Convenience wrapper for string keys."""
import hashlib, struct
digest = hashlib.sha256(key.encode()).digest()
int_key = struct.unpack(">Q", digest[:8])[0]
return jump_hash(int_key, num_buckets)
That’s the entire implementation. Ten lines. No data structures, no configuration.
Lookup complexity: O(log n) — the number of jumps is proportional to log(n).
Memory: O(1) — literally nothing stored, not even the bucket count between calls.
Key movement on resize: Minimal, but only supports adding buckets to the end. Removing an arbitrary bucket is not directly supported.
The distribution quality is exceptional — provably uniform with very low variance, better than ring with virtual nodes.
Where Jump Hashing Shines
Jump hash is purpose-built for systems that grow by adding shards sequentially and rarely shrink. Database sharding where you add read replicas or shard groups in sequence. Batch processing pipelines where work is partitioned across workers numbered 0 to N. Anywhere the "I can only add to the end" constraint fits your operational model.
It’s also the right call when you need the same bucket mapping across many services written in different languages — the algorithm has no configuration state, so cross-language consistency is trivial. Implement the ten-line function in each language, test with a handful of known inputs, done.
Gotchas
You cannot remove a bucket from the middle. If you have 8 buckets and bucket 4 fails, you cannot tell jump hash "skip bucket 4." You’d have to map the output through an indirection layer (physical_node = live_nodes[jump_hash(key, len(live_nodes))]), which breaks the consistency guarantee. This is the hard limitation that eliminates jump hash from any system that needs arbitrary node removal — which is most databases.
Integer keys only. Jump hash takes a 64-bit integer. You need to pre-hash your string/UUID keys. The choice of pre-hash matters — use a uniform 64-bit hash (Murmur3, xxHash64, SipHash). MD5 truncated to 8 bytes works, but it’s slower than it needs to be.
Bucket boundaries shift on resize. When you go from n to n+1 buckets, all 1/n keys that map to bucket n were previously mapped to some bucket in [0, n). Those other buckets each lose 1/(n*(n+1)) of their keys. This is correct and optimal — but it means monitoring your per-shard load during a resize event, because the transition period isn’t instant.
Side-by-Side Comparison
| Property | Ring | Rendezvous | Jump |
|---|---|---|---|
| Lookup time | O(log n) | O(n) | O(log n) |
| Memory | O(n × replicas) | O(n) | O(1) |
| Distribution quality | Good (with replicas) | Excellent | Excellent |
| Weighted nodes | Clunky (virtual nodes) | Native, clean | Not supported |
| Arbitrary remove | Yes | Yes | No |
| Cross-language | Tricky (naming scheme) | Easy | Trivial |
| Replication locality | Natural (ring neighbors) | Explicit top-k | No native concept |
| Common use cases | Distributed DBs, caches | CDNs, load balancers | Sharding, batch partitioning |
Production-Ready Patterns
Measure your distribution before shipping. For ring and rendezvous, generate a histogram of how many keys land on each node for a representative sample size (10K–100K keys). A coefficient of variation above 5% with ring hashing usually means you need more virtual nodes. With rendezvous, distribution is nearly perfect regardless of node count — but weighted rendezvous needs its own verification.
from collections import Counter
import random
import string
def distribution_stats(hasher, sample_size: int = 50_000) -> dict:
counts = Counter()
for _ in range(sample_size):
key = ''.join(random.choices(string.ascii_lowercase, k=16))
counts[hasher.get_node(key)] += 1
values = list(counts.values())
mean = sum(values) / len(values)
variance = sum((v - mean)**2 for v in values) / len(values)
cv = (variance**0.5) / mean # Coefficient of variation — lower is better
return {
"per_node": dict(counts),
"cv": round(cv, 4),
"min_pct": round(100 * min(values) / sample_size, 2),
"max_pct": round(100 * max(values) / sample_size, 2),
}
Put an indirection layer over jump hash if you use it. Even if your system only adds buckets sequentially, hardware fails. Maintain a mapping from logical bucket index to physical node identity. Jump hash assigns to logical buckets; your routing layer resolves those to actual endpoints. This also gives you a manual override path for maintenance windows.
Version your ring configuration. When using ring hashing in a multi-service system, the ring state (node list + virtual node count + hash function) must be consistent across all services. Treat this config as a versioned artifact. A deploy that changes ring config without coordinating all consumers will cause key placement disagreements — two services will route the same key to different nodes. That’s worse than a cache miss; for storage systems, it’s data loss or corruption risk.
Health-aware routing without breaking consistency. The temptation is to remove a failing node from your hasher when health checks fail. Resist it. For caches, yes — a failing node should be skipped and the key served (with a miss penalty) from the next node. For storage, removing a node from the hash ring while it’s flapping means keys bounce between placement on every health check flip. Use a separate "dead node" set and implement the skip logic outside the core hasher.
Picking One
If you’re sharding a database or a storage system with replication, and you need to tolerate arbitrary node failures without a full reshard: ring hashing. It’s battle-tested, every distributed database already implements it, and its operational characteristics are well-understood.
If you’re routing requests to backends that have different capacities or health weights, or if you need the cleanest possible O(n) implementation with minimal state: rendezvous. The O(n) lookup cost is real, but below a few hundred nodes it’s negligible, and the weight support pays for itself in heterogeneous fleets.
If you’re partitioning work across a fleet that only grows (more shards, more workers), you need cross-language consistency, and arbitrary removal is not a hard requirement: jump hash. The zero-configuration, zero-memory-overhead properties make it the default in Google’s internal sharding infrastructure, and it shows in the quality of the code.
Most engineers learn the ring and stop there. The ring is fine. But there’s a reason the other two exist, and knowing when to reach for them separates systems that stay stable under load from systems that get redesigned six months after launch.