← Create New Paste

Consistent Hashing Explained for System Design Interviews

3 views
If a system design interviewer asks you to design a distributed cache, a sharded key-value store, or a load balancer that keeps users on the same server, consistent hashing is almost certainly part of the answer they are hoping for. It is worth understanding well enough to explain from first principles, not just name-drop. The problem with naive sharding The obvious way to spread keys across N servers is server = hash(key) % N. It works until N changes. Add one server and almost every key maps to a different server: with 10 servers going to 11, roughly 90 percent of keys move. For a cache, that means a near-total miss storm hitting your database at the worst possible moment. For a data store, it means a huge, expensive rebalance. The ring Consistent hashing maps both keys and servers onto the same circular hash space, say 0 to 2^32 - 1. Each server is placed at hash(server_id). To find a key's owner, hash the key and walk clockwise around the ring until you hit the first server. When a server is added, it only takes over the keys between itself and its predecessor. When a server is removed, only its keys move, to the next server clockwise. On average only K/N keys move, instead of nearly all of them. import bisect, hashlib def h(s): return int(hashlib.md5(s.encode()).hexdigest(), 16) class Ring: def __init__(self, nodes, vnodes=100): self.ring = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes)) self.keys = [k for k, _ in self.ring] def owner(self, key): i = bisect.bisect(self.keys, h(key)) % len(self.keys) return self.ring[i][1] Virtual nodes With only a few real servers on the ring, the gaps between them are uneven, so some servers get far more keys than others. The fix is virtual nodes: each physical server is placed at many points (say 100 to 200) on the ring. This smooths the distribution and also lets you give a more powerful machine more virtual nodes to take a bigger share. When a server fails, its load is spread across many others instead of dumped on one neighbor. Replication For durability, store each key on the first R distinct physical servers clockwise from its position. This is how Dynamo-style systems such as Cassandra and Riak place replicas. Mention that you skip virtual nodes belonging to a server you already picked, so replicas land on different machines, ideally in different racks or zones. Trade-offs to bring up - Lookups are O(log V) with a sorted array and binary search, where V is the number of virtual nodes. That is fast enough for nearly any use. - Hot keys are not fixed by consistent hashing. A single celebrity key still lands on one server; you need replication of hot keys, request coalescing, or a local cache in front. - Alternatives exist: rendezvous (highest random weight) hashing gives similar minimal-movement properties with a simpler implementation, and jump consistent hash is very fast when servers are numbered sequentially. How to present it Start with modulo sharding and show what breaks when N changes. Introduce the ring, draw it, then add virtual nodes when the interviewer asks about balance. Finish with replication and hot-key handling. That sequence shows you understand why the technique exists, which is what interviewers grade. Explaining a design clearly while someone keeps adding constraints is hard. Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, so you can keep your system design answers organized as the conversation moves.
Created Nov 15, 2026 11:30 Expires Nov 15, 2027 11:30