medium general · part of Practice Questions · Senior SWE Roadmap · topic form: Consistent Hashing
Requirements to clarify
- Functional: map keys to nodes such that adding/removing a node remaps as few keys as possible; distribute load evenly.
- Non-functional: this is a component/primitive design question — the “requirements” are really about the properties the algorithm must have: minimal remapping, even distribution, low implementation complexity.
Core components
This is the design itself — see Consistent Hashing for concept details.
- Hash ring: map both node identifiers and keys onto a fixed circular hash space (e.g., 0 to 2³²-1) using a hash function.
- Key ownership rule: a key belongs to the first node encountered walking clockwise from the key’s position on the ring.
- Virtual nodes: represent each physical node as many points on the ring (e.g., 100-200 virtual nodes per physical node) to smooth out load distribution — without this, a small number of real nodes can land unevenly and create hot spots.
- Node add/remove: only the keys between the new/removed node and its neighbor need to move — implement and be ready to trace through a concrete example with numbers.
Key tradeoffs
- More virtual nodes per physical node = better load balance but more metadata/lookup overhead — a tuning knob worth mentioning explicitly.