Consistent Hashing Explained

Problem

A cache layer spreads keys across N servers with server = hash(key) % N. When a server is added or removed, nearly every key maps to a different server, the cache hit rate collapses to near zero, and the databases behind it get overwhelmed.

1. Explain why modular hashing remaps almost all keys on a membership change, and quantify it.
2. Describe consistent hashing, implement a ring with virtual nodes that supports adding and removing servers and looking up the server for a key, and show that adding one server to N moves only about 1/(N+1) of the keys.
3. Explain what virtual nodes fix, how many to use, and how you would handle heterogeneous server capacities and replication.

• Use a real hash function for the ring positions; a Python hash() is randomized per process and unsuitable for anything shared.
• Lookup must be O(log V) for V total virtual nodes, not a linear scan.

Examples

• 10 servers, modular hashing, add an 11th: a key with hash 57 was on server 7 (57 mod 10) and is now on server 2 (57 mod 11). Only keys whose hash is congruent to the same value modulo both 10 and 11 stay put, about 1 in 11. Roughly 91% of keys move.
• 10 servers on a consistent hash ring, add an 11th: the new server takes over the arcs immediately before its positions, about 1/11 of the ring. Roughly 9% of keys move, all of them to the new server; no key moves between two old servers.
• 3 servers with a single position each: one may own 60% of the ring by chance. With 150 virtual nodes per server, each owns 33% ± a few percent.

Hints

1. Under hash % N, what determines a key's server? What fraction of keys keep the same result when N becomes N + 1?
2. Instead of dividing keys among servers, place both keys and servers on the same circle and give each key to the next server clockwise. Which keys change owner when a server appears?
3. With one point per server the arcs are wildly uneven. What happens to the variance if each server has 100 points?