linkjobai revised this gist . Go to revision
1 file changed, 47 insertions
consistent.md(file created)
| @@ -0,0 +1,47 @@ | |||
| 1 | + | # Consistent Hashing Explained for System Design Interviews | |
| 2 | + | ||
| 3 | + | 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. | |
| 4 | + | ||
| 5 | + | ## How it works | |
| 6 | + | ||
| 7 | + | 1. Map servers and keys onto the same ring of hash values (for example 0 to 2^32 - 1). | |
| 8 | + | 2. A key belongs to the first server clockwise from its position. | |
| 9 | + | 3. When a server joins, it takes keys only from its clockwise neighbour; when one leaves, its keys move to the next server. | |
| 10 | + | ||
| 11 | + | ```python | |
| 12 | + | import bisect, hashlib | |
| 13 | + | ||
| 14 | + | class Ring: | |
| 15 | + | def __init__(self, nodes, vnodes=100): | |
| 16 | + | self.ring = sorted( | |
| 17 | + | (self._h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes)) | |
| 18 | + | self.keys = [h for h, _ in self.ring] | |
| 19 | + | ||
| 20 | + | @staticmethod | |
| 21 | + | def _h(s): | |
| 22 | + | return int(hashlib.md5(s.encode()).hexdigest(), 16) | |
| 23 | + | ||
| 24 | + | def node_for(self, key): | |
| 25 | + | i = bisect.bisect(self.keys, self._h(key)) | |
| 26 | + | if i == len(self.keys): | |
| 27 | + | i = 0 # wrap around the ring | |
| 28 | + | return self.ring[i][1] | |
| 29 | + | ``` | |
| 30 | + | ||
| 31 | + | ## Virtual nodes | |
| 32 | + | ||
| 33 | + | 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. | |
| 34 | + | ||
| 35 | + | ## Where it shows up | |
| 36 | + | ||
| 37 | + | - Distributed caches (Memcached clients), Amazon Dynamo, Cassandra and Riak partitioning. | |
| 38 | + | - Load balancers that need sticky routing. | |
| 39 | + | ||
| 40 | + | ## Interview talking points | |
| 41 | + | ||
| 42 | + | - Replication: store each key on the next R distinct servers on the ring. | |
| 43 | + | - Hot keys still overload one node; consistent hashing balances *keys*, not *traffic*. | |
| 44 | + | - Alternatives: rendezvous (highest random weight) hashing, and jump consistent hash for numbered buckets. | |
| 45 | + | ||
| 46 | + | --- | |
| 47 | + | *Disclosure: I work on [Linkjob AI's interview copilot](https://www.linkjob.ai/), which helps candidates during live interviews.* | |
Newer
Older