Consistent Hashing

When adding a node to a cluster, move only 1/N of the keys instead of rebalancing everything.

Problem

Naively, distributing K keys over N nodes with hash(key) % N is correct but disastrous on rescaling: adding a node (N → N+1) changes almost every key's placement; ~ K(N/N+1) data must move. For a 100 GB cache on 10 nodes, adding an 11th node moves ~91 GB — unacceptable.

Forces

• Node add/remove must be near-instant (autoscaling, failure).
• Key distribution must stay uniform as the cluster grows.
• Hot keys unbalance the ring.
• A client must compute the target without a centralised coordinator.

Solution

Place nodes and keys on a virtual hash ring (space [0, 2⁶⁴)). A key is served by the first node encountered going clockwise. Adding a node invalidates only keys between it and the previous node — ~ K/N on average. To avoid imbalances from small clusters, each physical node is represented by v virtual nodes (typically 100-200) spread randomly on the ring. Variants: Jump consistent hash (Google, 2014) for simple spaces, Rendezvous hashing (Highest Random Weight).

Structure

Ring [0 .. 2^64):

    Node A vNode1  ──┐
                     │
    key X ──► hashed │
                     ▼  (closest clockwise)
                  Node A vNode1 serves it
                     │
    Node B vNode1 ───┘
       :
    Node C vNode1
       :
    A vNode2, B vNode2, C vNode2 ... (interleaved)

Add Node D: only ~K/4 keys move (those falling between D's vNodes and their successors).

EDI implementation

A multi-tenant EDI hub uses consistent hashing to distribute partners across a worker pool: hash(partnerId) → worker. When adding a worker, only ~1/N of partners migrate, with no full cache rebuild of their state. Kafka uses consistent hashing for partitioning when adding partitions to a topic (with sticky partitioner). For EDI CDNs (exotic case: caching PRICAT catalogues), Akamai and Cloudflare have used it for 20 years.

Anti-patterns

• No virtual nodes — unbalanced distribution on small clusters (3-5 nodes).
• Biased hash function — concentration on a few nodes (use MurmurHash, xxHash, SHA).
• Cluster with different capacities without weighting — a small node absorbs as much as a big one.
• Modifying the number of virtual nodes after production — massive reorganisation.
• Unmanaged hot keys — a premium tenant taking 80% of traffic saturates its node.

Related patterns

• Sharding — typical use of consistent hashing for placement.
• Competing Consumers — alternative when affinity is not required.
• Rate Limiter — can be sharded via consistent hashing by tenant.
• Partition Tolerance — discusses governing CAP trade-offs.

Sources

• Karger D., Lehman E., Leighton T., Panigrahy R., Levine M., Lewin D. — Consistent Hashing and Random Trees, STOC 1997. dl.acm.org/doi/10.1145/258533.258660
• DeCandia G. et al. — Dynamo: Amazon's Highly Available Key-Value Store, SOSP 2007. allthingsdistributed.com — Dynamo paper
• Kleppmann M. — Designing Data-Intensive Applications, O'Reilly 2017, ch. 6 "Partitioning".