Consistent Hashing hard
Virtual Nodes improve balance but increase metadata size (Memory). How does 'Multi-Probe Consistent Hashing' achieve good balance without VNodes?
- A It utilizes a centralized high-speed load balancer that maintains a real-time health map of all physical nodes and their capacities.
- B It uses a hardware-based ASICs hash accelerator to process ring lookups in nanoseconds, eliminating the software overhead of metadata.
- C It hashes the key K times (probes) and selects the closest node, achieving statistical smoothness with only O(1) metadata per node.
- D It utilizes Jump Consistent Hash to map keys directly to physical indices, effectively eliminating the need for a shared ring topology.
Answer: C. It hashes the key K times (probes) and selects the closest node, achieving statistical smoothness with only O(1) metadata per node.
Virtual Nodes (VNodes) provide balance by replicating nodes on the ring, which consumes memory (O(Node * VNode)). Multi-Probe Hashing flips this: it maps the node only once (O(N) memory), but hashes the *key* multiple times. By picking the 'best' of the K locations for that key, you get the same statistical smoothing benefits as VNodes without the memory explosion.
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?
- 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?
- If you reside a cluster from 10 to 11 nodes using Modulo Hashing, what happens?