Consistent Hashing

A hashing scheme that maps keys and nodes onto a fixed ring so that adding or removing a node remaps only K/N keys rather than the whole keyspace.

Practical example

Cassandra assigns each physical node 100-256 vnodes on the ring and walks clockwise from a key's primary vnode to select N-1 additional replicas using NetworkTopologyStrategy, ensuring replicas span racks or availability zones.

The core mechanism places both nodes and keys onto a modulo-2^m ring via a hash function. A key is owned by the first node encountered walking clockwise from the key’s hash position. Naive modulo-N hashing (hash(key) % N) causes near-total remapping when N changes; consistent hashing constrains remapping to only the keys owned by the immediate successor of the node being added or removed, giving the theoretical O(K/N) movement bound cited in the original Karger et al. paper (used to underpin Akamai’s CDN routing and later Dynamo/Cassandra).

In practice, a single point per physical node produces severe load skew because random hash placement doesn’t guarantee uniform arc lengths on the ring — some nodes end up owning disproportionately large key ranges. The standard mitigation is virtual nodes (vnodes): each physical node is assigned many (often 100-256) points on the ring. This smooths load distribution via the law of large numbers and, critically, decouples data ownership from physical topology, enabling heterogeneous hardware to be weighted by assigning proportionally more vnodes to more capable machines.

Hot ranges: vnodes reduce but do not eliminate skew for non-uniform key access patterns (e.g., celebrity keys); this is an orthogonal problem requiring request-level load balancing or key salting.
Replica placement: systems like Cassandra walk the ring clockwise from a key’s primary vnode to select N-1 additional replicas, but naive walking can co-locate replicas on the same physical node if vnodes aren’t rack/AZ aware — requiring topology-aware placement strategies (e.g., NetworkTopologyStrategy).
Rebalancing cost: even with the O(K/N) bound, physically moving data still saturates network and disk I/O during scale-out events; production systems throttle bootstrap/decommission streaming rates to avoid impacting foreground latency.

An important architectural variant is Rendezvous Hashing (highest random weight), which avoids the ring data structure entirely by computing hash(key, node_i) for every node and selecting the maximum — trading O(N) lookup cost for perfectly uniform distribution without needing vnodes, and it’s frequently preferred in cache-sharding and CDN request-routing layers (e.g., Google’s Maglev) where lookup cost is amortized and skew must be near-zero. The choice between ring-based consistent hashing and rendezvous hashing is ultimately a tradeoff between O(log N) lookup with vnode-management overhead versus O(N) computation with none.