consistent.md
· 1.8 KiB · Markdown
Raw
# 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.*
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
- Map servers and keys onto the same ring of hash values (for example 0 to 2^32 - 1).
- A key belongs to the first server clockwise from its position.
- When a server joins, it takes keys only from its clockwise neighbour; when one leaves, its keys move to the next server.
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, which helps candidates during live interviews.