# Consistent hashing

> Place nodes and keys on a ring so adding a node moves about 1/N of the keys, not all of them.

Concept · Replication & partitioning · https://levelcode.org/concepts/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.

> **Interactive: Modulo versus consistent hashing.** Remove a node under modulo hashing and most keys move; on the ring only the removed node's keys move. Turn on virtual nodes to even out the shares. Try it: https://levelcode.org/labs/load-balancer

## 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](https://levelcode.org/concepts/sharding).
- **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.