Back to System design

Consistent Hashing

medium
Scale: O(log V) lookup with sorted ring (V = vnodes); ring size 2^32 typical Storage: O(V) tokens stored; usually small (KB-MB) Amazon, Netflix, Cloudflare
FundamentalsHashingDistributed Systems

Consistent hashing is a partitioning technique that minimizes how many keys move when nodes join or leave a cluster. It's the default for caches, KV stores, service-mesh routing, and any system that has to deal with elastic membership.

ScaleO(log V) lookup with sorted ring (V = vnodes); ring size 2^32 typical
StorageO(V) tokens stored; usually small (KB-MB)

Key Concepts

1
1. The naive problem. Modulo hashing (shard = hash(key) mod N) sends almost every key to a new shard when N changes. In a 10-node cache, adding an 11th node remaps roughly all keys — instant cache cold-start, DB stampede.
1. The naive problem.shard = hash(key) mod N
2
2. The trick: a circular hash space. Hash both node IDs and keys onto a ring of size 2^32 (or 2^64). A key is owned by the next node clockwise. Adding a node assigns it a random position; it takes a contiguous arc from one neighbor — only those keys move (about 1/N of total).
2. The trick: a circular hash space.1/N
3
3. Virtual nodes balance the load. Random positions cause skew — one node might own a much larger arc than another. Virtual nodes (vnodes): each physical node owns many random tokens (Cassandra default: 256). Each physical node owns many small arcs scattered around the ring; load evens out. Bonus: scale-up spreads the migration across many existing nodes.
3. Virtual nodes balance the load.
4
4. Replication and hot keys. For replication factor R, place replicas on the next R distinct physical nodes clockwise (skipping vnodes of already-chosen nodes). Rack-awareness extends this. Consistent hashing solves placement skew but not workload skew — one hot key still saturates one node. Bounded-load (Maglev-style): cap any node at C × average load; overflow routes to the next.
4. Replication and hot keys.
5
5. In production. Memcached client libraries (ketama, dalli). Cassandra: vnodes = 256, rack-aware replicas. DynamoDB: bounded-load consistent hashing. Akamai invented the technique for CDN routing. Envoy / Maglev use it for service-mesh routing. Rendezvous (HRW) hashing is a simpler alternative — no ring, optimal balance, O(N) lookup — used at Discord.
5. In production.

Related Problems

CAP Theorem and PACELCeasyLoad Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, Geomedium

Approach

  1. Hash node identifiers (with V vnodes each) onto a ring of size 2^32 or 2^64.
  2. Hash each data key onto the same ring.
  3. The owner of a key is the next vnode clockwise. Lookup: sorted ring + binary search → O(log V).
  4. For replication factor R, the next R distinct physical nodes (skipping vnodes belonging to nodes already chosen) hold replicas.
  5. Rack-aware variant: skip nodes in already-used racks to keep replicas across failure domains.
  6. Adding a node: assign V random tokens, transfer keys from neighbors' arcs.
  7. Removing a node: clockwise neighbor absorbs each vnode's arc; data moves to it.
  8. For hot keys, layer bounded-load: cap any node at C × average load; overflow goes to the next node.

Algorithm details

Ring representation: sorted array of tokens or a TreeMap; lookup via binary search / ceilingEntry.

Hash function: needs uniform distribution. MD5 is classic. MurmurHash3 / xxHash are faster.

Vnode tokens: random per physical node (Cassandra default), or pre-allocated for deterministic placement.

Replica walk: starting at primary, advance clockwise, take the first vnode whose physical node hasn't been used yet, continue until R replicas chosen.

Bounded-load (Google 2017): pick the closest node, but if it's already over 1+ε times average load, fall through to the next available.

Components

  • Ring data structure (sorted token list / TreeMap).
  • Token assignment policy (random, hashed-id, weighted, manual).
  • Replica placement strategy (simple-walk, rack-aware, datacenter-aware).
  • Bootstrap / decommission protocol to migrate keys.
  • Gossip / membership service to keep nodes' rings in sync.
  • Hot-key handling — bounded loads, key replication, or local in-process cache.

Trade-offs

Too few vnodes: ring is imbalanced; one node owns much more data than another.

Too many vnodes: memory overhead per node grows linearly; lookups slightly slower; failure recovery slower because one dead node has many tokens.

Consistent hashing solves placement skew. It does not solve workload skew — one hot key still saturates one node. You need additional mitigation for that (key replication, sharded counters, client-side cache).

Rendezvous (HRW) hashing has no ring, optimal balance, deterministic. Lookup is O(N) but for small N (a few hundred) that's not a problem and the code is much simpler.

Real-world systems

  • Memcached client libraries (libketama, dalli): consistent hashing for partitioning the cache fleet client-side.
  • Cassandra: virtual nodes (vnodes=256 default); rack-aware replica placement; gossip-based membership.
  • DynamoDB: consistent hashing partitions, with bounded-load to handle hot partitions.
  • Akamai: invented the technique for web caching; modern CDN routing builds on it.
  • Envoy / Maglev: bounded-load consistent hashing for service-mesh routing.
  • Discord: rendezvous hashing to map voice channels to media nodes.