# Consistent Hashing Explained for System Design Interviews

When you shard a cache or database with `hash(key) mod N`, adding or removing one server remaps almost every key. **Consistent hashing** limits the damage to roughly 1/N of the keys.

## How it works

1. Map servers and keys onto the same ring of hash values (for example 0 to 2^32 - 1).
2. A key belongs to the first server clockwise from its position.
3. When a server joins, it takes keys only from its clockwise neighbour; when one leaves, its keys move to the next server.

```python
import bisect, hashlib

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.ring = sorted(
            (self._h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.keys = [h for h, _ in self.ring]

    @staticmethod
    def _h(s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def node_for(self, key):
        i = bisect.bisect(self.keys, self._h(key))
        if i == len(self.keys):
            i = 0          # wrap around the ring
        return self.ring[i][1]
```

## Virtual nodes

With only a few servers, the ring is uneven. Giving each server many virtual positions (the `vnodes` above) smooths the load, and lets bigger machines take more virtual nodes.

## Where it shows up

- Distributed caches (Memcached clients), Amazon Dynamo, Cassandra and Riak partitioning.
- Load balancers that need sticky routing.

## Interview talking points

- Replication: store each key on the next R distinct servers on the ring.
- Hot keys still overload one node; consistent hashing balances *keys*, not *traffic*.
- Alternatives: rendezvous (highest random weight) hashing, and jump consistent hash for numbered buckets.

---
*Disclosure: I work on [Linkjob AI's interview copilot](https://www.linkjob.ai/), which helps candidates during live interviews.*