Consistent Hashing

The problem with modulo hashing

The naive way to spread keys across N servers is server = hash(key) mod N. It distributes evenly, but the moment N changes almost every key moves: going from 4 to 5 servers remaps roughly 80 percent of keys. For a cache fleet this is catastrophic, since a routine scale-up instantly invalidates most of the cache, the hit rate collapses, and the full read load lands on the database at once, a self-inflicted thundering herd.

The requirement, then: a mapping from keys to nodes where membership changes move only the keys that must move. Adding one node to N should relocate about 1/N of keys (about K/N of K keys) and nothing else. Consistent hashing, introduced in a 1997 MIT paper and commercialized by Akamai for CDN routing, achieves exactly this.

This matters for any stateful fleet: cache clusters (Memcached client libraries used consistent hashing early on), partitioned databases, and load balancers that want the same client or session to keep landing on the same backend.

The hash ring

Picture the output range of a hash function, say 0 to 2^32 - 1, bent into a circle. Each node is hashed (by name or IP) to one or more positions on this ring. To place a key, hash it to a point on the ring and walk clockwise to the first node you meet; that node owns the key. Each node therefore owns the arc between its predecessor and itself.

Membership changes are now local. When a node is removed, only the keys on its arc move, to its clockwise successor; every other key stays put. When a node is added, it takes over part of exactly one existing node's arc. With K keys and N nodes, each change moves about K/N keys, the theoretical minimum.

Lookups need a sorted structure of node positions, so routing is a binary search, O(log N), typically done in the client library (Memcached's ketama), in a coordinator, or via gossip-shared ring state as in Cassandra.

Virtual nodes

With one position per node, the ring is badly balanced: random placement gives some nodes arcs several times larger than others, and when a node dies its entire load dumps onto a single successor. Heterogeneous hardware makes it worse, since a box with twice the RAM cannot be given twice the keys.

Virtual nodes (vnodes) fix all three issues. Each physical node is hashed to many ring positions, commonly 100 to 1,000; Cassandra historically defaulted to 256 tokens per node, later reduced to 16 with a smarter allocation algorithm. With many vnodes per machine, arc sizes average out (variance falls roughly with the square root of the vnode count), a failed node's load scatters across many successors instead of one, and a beefier machine simply gets proportionally more vnodes.

The costs are modest: a larger ring table to store and search, and in replicated databases more distinct ranges per node, which increases the bookkeeping for repairs and streaming. This is why Cassandra tuned its default down once its allocator improved.

Where it is used, and alternatives

Amazon's Dynamo paper made consistent hashing with vnodes the backbone of its partitioning, and Cassandra and Riak inherited the design: the ring determines both the primary owner of a key and its replicas (the next R-1 distinct physical nodes clockwise). DynamoDB descends from this lineage. Akamai used consistent hashing to route URLs to CDN edge caches so that cache contents survive server churn. Discord uses it to assign guilds to server processes, and Envoy and HAProxy offer ring-hash load balancing for session affinity.

Know the notable alternatives. Rendezvous (highest random weight) hashing scores every node for a key via hash(key, node) and picks the maximum; it needs no ring, gives excellent balance, and is O(N) per lookup, fine for small N. Google's Maglev hashing builds a lookup table for near-perfect balance with minimal disruption, built for software load balancers. Jump consistent hash is a tiny, fast algorithm ideal when nodes are numbered and only added or removed at the end.

Also be ready to contrast with the explicit-mapping approach: systems like Redis Cluster (16,384 hash slots assigned to nodes) and Vitess keep a slot or shard map instead of a pure ring. Explicit maps allow deliberate, operator-controlled rebalancing at the cost of maintaining that metadata, effectively trading algorithmic simplicity for placement control.

Tradeoffs