Consistent hashing

With node = hash(key) mod N, changing N remaps almost every key: going from 4 to 5 nodes moves about 80% of them. For a cache that means a near-total miss storm; for a database, moving most of the data at once.

#The ring

Consistent hashing maps both nodes and keys onto the same circular hash space (a ring). Each key belongs to the first node found walking clockwise from the key's position.

• Adding a node takes over only the keys between it and its predecessor; nothing else moves.
• Removing a node hands its keys to the next node clockwise.
• On average, a change moves about 1/N of the keys — the minimum possible, since the new node must get its share from somewhere.

#Virtual nodes

With only a few points on the ring, shares are uneven: one node might own 50% of the ring by chance. Placing each physical node at many positions (virtual nodes, often 100–256 each) evens out the shares, and when a node leaves, its load spreads across many nodes rather than landing on one neighbour. Giving bigger machines more virtual nodes weights them accordingly.

#Where it's used

• Distributed caches and client-side sharding (Memcached clients, NGINX hash … consistent).
• Dynamo-style databases (Cassandra, Riak) to place partitions and replicas: a key's replicas are the next N distinct nodes on the ring.
• Load balancers that need request affinity to keep caches warm.

#Alternatives

• A fixed number of partitions (Redis Cluster's 16,384 slots, Kafka partitions) mapped to nodes by a table: simpler, and rebalancing moves whole partitions. See range vs hash partitioning.
• Rendezvous (highest-random-weight) hashing: each key goes to the node with the highest hash(key, node); also moves only 1/N of keys and needs no ring.

The DevSecOps roadmap's load-balancing lesson works through a ring step by step.