Consistent Hashing easy
What primary inefficiency in traditional 'Modulo Hashing' (key % N) does Consistent Hashing address?
- A The occurrence of hash collisions where two distinct keys unfortunately generate the same underlying hash value.
- B The massive data reshuffling (resharding) required whenever a node is added or removed, which invalidates existing caches.
- C The fundamental inability to utilize string-based keys; Modulo arithmetic strictly requires integer inputs for calculation.
- D The excessive CPU utilization and computational overhead consumed during the initial hashing calculation phase.
Answer: B. The massive data reshuffling (resharding) required whenever a node is added or removed, which invalidates existing caches.
In standard Modulo hashing (key % N), changing the number of nodes (N) changes the mapping result for almost every single key in the system. Consistent hashing addresses this by ensuring that adding or removing a node only affects a local slice of keys (~1/N), preserving the majority of existing cache placements and system stability.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- In a 'Smart Client' architecture (e.g., modern Cassandra drivers), how does the client find the right node?
- When a new node (Node X) joins the ring, where does it acquire its initial data from?
- Google's Maglev hashing algorithm (used in their Network Load Balancers) differs from standard Consistent Hashing rings. How does it generate the lookup table?
- Virtual Nodes improve balance but increase metadata size (Memory). How does 'Multi-Probe Consistent Hashing' achieve good balance without VNodes?
- In the Chord DHT protocol (a P2P consistent hashing implementation), naive lookups are O(N). How does Chord optimize this to O(log N)?
- Which of these systems is a famous user of Consistent Hashing?