Consistent Hashing hard
Google's Maglev hashing algorithm (used in their Network Load Balancers) differs from standard Consistent Hashing rings. How does it generate the lookup table?
- A It utilize a cryptographic signature verification process to ensure that all incoming data packets have not been tampered with.
- B It constructs a large, fixed-size lookup table where backends fill slots based on their own random permutations to ensure balance.
- C It utilizes a distributed binary search tree that is strictly synchronized across all regional load balancers using the Raft protocol.
- D It relies on a centralized Zookeeper locking mechanism to prevent multiple backends from claiming the same hash range simultaneously.
Answer: B. It constructs a large, fixed-size lookup table where backends fill slots based on their own random permutations to ensure balance.
Maglev doesn't use a 'ring'. Instead, it generates a heavy lookup table (e.g., 65k entries). Each backend generates a preferred list of slots (a permutation). They take turns filling empty slots in the table. This 'Maglev Hashing' achieves much better load balance than standard rings and offers O(1) lookup speed (direct array access), which is critical for Google's networking layer.
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?
- 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?
- If you reside a cluster from 10 to 11 nodes using Modulo Hashing, what happens?