Consistent Hashing and Distribution

Sharding is easy until the cluster changes size. Naive shard = hash(key) % N distributes perfectly across N shards and then catastrophically on the day you add a shard: every key whose modulo changes — about (N−1)/N of them — moves to a different node, and the whole dataset gets shuffled across the network at once. Consistent hashing exists to make rebalancing cheap: when a node joins or leaves, only ~1/N of the keys move.

The hash ring

Both nodes and keys are hashed onto the same conceptual circle of 2^32 positions:

ring.insert(hash(node_id))          # node positions
ring.insert(hash(key))              # key positions
 
lookup(key):                        # the whole algorithm
  pos = hash(key)
  n = ring.first_clockwise(pos)     # O(log N) with a sorted structure
  return n

A key belongs to the first node clockwise from its hash. When node X leaves, only the keys in the arc between X and its predecessor re-home to X's successor — statistically 1/N of the keyspace, and the successor briefly carries 2/N of the data. When a node joins, it claims the arc between itself and its predecessor, receiving that neighbor's 1/N share. That's the property everyone quotes: the rebalance cost is O(1/N) of the data instead of O(N).

The math is simple arc arithmetic: each node owns an arc whose expected length is 1/N of the circle. Removal doubles one neighbor's arc — briefly 2/N — while leaving every other node's load untouched. This is why consistent hashing feels like magic in sharded caches and key-value stores: adding a node for capacity doesn't require a full rebalancing pass.

The load imbalance problem

A plain ring is unbalanced in practice. With few nodes, the hash function's randomness leaves some arcs 30-50% larger than average — the famous Cassandra load skew without virtual nodes. And removal temporarily doubles one node's load, which at 80% utilization is a saturation incident, not a routine rebalance.

Virtual nodes fix the variance by making many small bets instead of one big one: each physical node claims V positions on the ring (Cassandra's default is 256), and the ring holds N×V entries. By the law of large numbers, each physical node's total arc length converges to 1/N, with variance shrinking as the square root of N×V. Rebalancing gets smoother too: when a node leaves, its 256 arcs spread across 256 different successors instead of piling onto one neighbor. The cost is memory and lookup time — the ring holds tens of thousands of entries, and a binary search over it is still O(log(N×V)): microseconds.

Rendezvous hashing: the no-ring alternative

Rendezvous (highest random weight, HRW) hashing asks a different question. Instead of finding the node clockwise from the key, it computes, for every node, hash(key, node) and picks the maximum:

lookup(key):
  best, best_weight = null, -inf
  for node in nodes:
    w = hash(key, node)             # deterministic, well-mixed
    if w > best_weight: best, best_weight = node, w
  return best

It has the same minimal-rebalance property — when a node leaves, only keys that chose it as the maximum move, again ~1/N — with two practical differences. First, the max-of-N statistic gives measurably better load balance than a plain ring: worst-case load is within a small constant factor of optimal, with no vnode configuration to tune. Second, lookups are O(N) hash computations per key instead of O(log N) structure lookups — irrelevant at N=10, wasteful at N=1,000. Rendezvous is right for small, frequently-changing memberships (client-side shard selection, cache affinity in a fleet of tens); the ring with vnodes wins for large clusters where per-lookup cost matters.

Real deployments

• Cassandra / Dynamo-style stores: vnodes on the ring, membership by gossip.
• Memcached client libraries (libketama): ring with 160 vnodes per server.
• Load balancers (nginx, HAProxy): consistent hashing by client IP or user ID for stickiness without per-client state.
• Kafka: partition-to-consumer assignment is related but distinct — the partition count is static precisely because consistent hashing cannot make repartitioning free.

What consistent hashing does not give you

It minimizes data movement, not everything else. The 1/N keys that do move still need transfer, queries that used to hit the old owner miss, and per-node indexes and caches rebuild. If the cluster grows continuously, 1/N per change still compounds into steady background migration — which is exactly why sharded stores batch topology changes and let repairs run in the background. The promise worth remembering: most of your data stays put when the fleet changes, and that property is worth paying for in lookup complexity.