Skip to content

CONCEPT Cited by 2 sources

Consistent hashing

Consistent hashing maps keys to buckets (shards, servers, cohorts) in a way that minimises re-mapping when the bucket set changes. Adding or removing a bucket moves only a 1/N fraction of keys — not the whole keyspace as with naive hash(key) % N.

Originally an Akamai / Karger et al. construction (1997) for distributed web caching. The canonical implementation places buckets at hashed positions on a ring; each key maps to the next bucket clockwise. Modern variants use bounded-load, rendezvous (HRW), or jump consistent hashing.

Why it matters beyond sharding

The same "adding a bucket keeps most keys where they were" property is load-bearing in two very different contexts:

  • Sharding / partitioning — consistent hashing means scaling a cache or database cluster doesn't evict the whole cache or rehash the whole dataset.
  • Percentage rollouts — with consistent hashing on a context attribute, raising the rollout from 5% to 10% keeps every already-rolled-out user rolled out; it just admits a new 5% slice.

This second use is the one called out directly in Cloudflare Flagship:

"Rollouts use consistent hashing on the specified context attribute. The same attribute value (userId, for example) always hashes to the same bucket, so they won't flip between variations across requests. You can ramp from 5% to 10% to 50% to 100% of users, so those who were already in the rollout stay in it."

The property the post needs is weaker than the full distributed-sharding ring — it just needs hash(userId) % 100 to be stable across calls. But "consistent hashing" is the industry-standard name for the whole property cluster.

Core properties

  • Stable mapping — hash(k) is a pure function; the same key always produces the same position.
  • Minimal disruption on resize — adding or removing one bucket moves ~1/N of keys.
  • Balanced load — with a good hash, keys distribute approximately uniformly across buckets (virtual nodes / multiple hash positions per physical bucket improve this).

Common use cases on this wiki

  • Distributed caches (memcached clients, Redis Cluster).
  • Request routing to stateful shards ( Durable Objects route by hashed ID → single-writer instance).
  • Partitioned streaming (Kafka partitioning by key).
  • Percentage rollouts in feature flags — the 2026-04-17 Flagship launch made this a first-class on-wiki instance.

Seen in

  • sources/2023-02-22-highscalability-consistent-hashing-algorithm — canonical distributed-systems primer for this concept page. High Scalability / systemdesign.one (2023-02-22) walks the full partitioning-problem taxonomy (random / single-global / key-range / static-hash / consistent) and derives consistent hashing plus its two Google-paper variants (multi-probe 2015, bounded-load 2017). Names the canonical production lineage: Memcached Ketama clients, Amazon Dynamo / DynamoDB / Apache Cassandra / Riak, Vimeo LB, Netflix Open Connect CDN, Discord server-to-node mapping, HAProxy bounded-load. Adds the k/N average movement property, the BST-over-ring-positions implementation with O(log n) operations, the readers-writer lock for concurrent membership change, and the non-cryptographic hash recommendation (MurmurHash / xxHash / MetroHash / SipHash1-3 over MD5 / SHA-1 / SHA-256).
  • sources/2026-04-17-cloudflare-introducing-flagship-feature-flags-built-for-the-age-of-ai — canonical wiki instance of consistent hashing as the bucketing primitive under feature-flag percentage rollouts; the load-bearing property is "same attribute value always hashes to the same bucket" across ramps.
  • — Zalando's PRAPI uses Consistent Hash Load Balancing (CHLB) at the Skipper ingress to partition 10M products across backend pods, so each pod owns a deterministic slice of the catalogue in its local Caffeine cache. Two upstream Skipper contributions come from this deployment: fixed-100-position placement (skipper#1712) reduces cache invalidation on pod scale events to 1/N; bounded-load (skipper#1769) caps per-pod traffic at 2× average so limited-edition product drops can't overload their ring owner. See patterns/bounded-load-consistent-hashing.
Last updated · 542 distilled / 1,571 read