Architecture/Fundamentals/consistent-hashing

Consistent Hashing

Concept

The naive way to distribute keys across N cache or database nodes is hash(key) % N — simple, evenly distributed, and catastrophic the moment N changes. Add or remove a single node and N shifts, which changes the modulus for every key, which means almost every key now maps to a different node than it did a moment ago. In a cache, that's a near-total cache miss storm right when the system is already stressed (a node just failed, or capacity is being added under load). In a sharded database, that's a full data reshuffle across the fleet for what should have been a routine scaling event.

Consistent hashing fixes this by decoupling "which node owns this key" from the total node count. Both nodes and keys are hashed onto the same abstract structure — conventionally visualized as a ring spanning the hash space (0 to 2^32-1, say). A key is assigned to the first node found walking clockwise from the key's position on the ring. Adding or removing a node only moves the keys that fall in the arc immediately preceding that node — on average, roughly 1/N of all keys — instead of reshuffling the whole keyspace. That's the entire value proposition: node-count changes become a cheap, local, proportional operation instead of a global one.

The ring alone has a real flaw: with only a few nodes, their positions might cluster on the ring by chance, giving some nodes a much larger arc — and thus a much larger key share — than others. The standard fix is virtual nodes: each physical node is hashed onto the ring many times (100+ virtual points is typical) under distinct virtual identities, so its total key share is an average over many small arcs instead of one large one, smoothing the distribution close to even regardless of physical node count.

Tradeoffs

Approach	Keys remapped on node add/remove	Load distribution	Implementation complexity	Where it's used
`hash(key) % N`	Nearly all keys	Even (at a fixed N)	Trivial	Only viable when N is truly fixed and known in advance
Consistent hashing, no virtual nodes	~1/N of keys	Uneven with few nodes — ring position clustering causes hot/cold nodes	Moderate	Rarely used bare — the uneven-distribution flaw is well known
Consistent hashing + virtual nodes	~1/N of keys	Even, smooths out with more virtual points per node	Higher — extra bookkeeping per physical node	DynamoDB, Cassandra, Riak, most distributed caches and CDN routing layers

The core trade is upfront complexity against operational stability at scale: modulo hashing is trivial to write and reason about but turns every capacity change into a disruptive event, while consistent hashing costs more to implement (and virtual nodes add another layer of bookkeeping) in exchange for capacity changes that stay cheap and local no matter how large the fleet gets. Below a handful of nodes that rarely change, the simpler scheme is often good enough; the tradeoff tips hard toward consistent hashing the moment node count is expected to grow, shrink, or fail unpredictably.

When to use / when not to

Use for any distributed cache or data store where nodes are added, removed, or fail — the standard case for caching layers, sharded databases, and CDN/load-balancer routing at scale (see Database Sharding Strategies and CDN and Edge Caching).
Use when minimizing cache-miss or data-movement blast radius during scaling events or node failures is a real operational concern — which it almost always is once a fleet is large enough to have routine node churn.
Skip it for a small, genuinely fixed set of nodes that essentially never changes — the added complexity buys nothing if N never moves.
Skip bare consistent hashing (without virtual nodes) — the uneven-distribution problem it has with a small node count is well-documented enough that it's rarely the right implementation choice today.

Common pitfall

Implementing consistent hashing without virtual nodes and then being surprised by hot nodes. The ring's theoretical property — "adding a node only remaps ~1/N of keys" — holds regardless of virtual nodes, but even distribution doesn't, especially with a small physical node count where random ring placement can leave one node covering a disproportionate arc. The fix (100+ virtual nodes per physical node) is well known, but it's easy to ship a naive single-point-per-node ring, pass testing with a handful of keys, and only discover the imbalance once real traffic and a real key distribution hit it in production.

Principal Engineer Lens

Consistent hashing is a clean example of a pattern whose entire justification is "what does a routine operational event cost." Any distributed system will scale up, scale down, or lose a node eventually — the question that separates a resilient design from a fragile one is whether that ordinary event triggers a proportional, local cost or a global, disruptive one. That framing generalizes past hashing specifically: it's the same lens applied to schema migrations (can you add a column without locking the table), deploys (can you roll one instance without draining all traffic), or org changes (can one team's reorg avoid destabilizing every other team's roadmap). In a design review, being able to name the blast radius of your most common operational event — and show it's O(1/N) rather than O(N) — is a fast, concrete signal of design maturity that transfers cleanly across caching, storage, and infrastructure-scaling conversations in any domain.

Sources: