Consistent Hashing easy
What is reliable property for a hash function (like MurmurHash) used in this context?
- A Complete cryptographic irreversibility to ensure that stored keys can never be decrypted by an external attacker.
- B High execution speed and uniform distribution to ensure that keys are spread evenly across the entire ring range.
- C Absolute collision avoidance to guarantee that no two distinct inputs can ever produce the same hash output.
- D Strictly variable output lengths that can be adjusted based on the current available memory of the target node.
Answer: B. High execution speed and uniform distribution to ensure that keys are spread evenly across the entire ring range.
For distributed partitioning, uniform distribution (the 'Avalanche Effect') is more important than cryptographic security. We need a function that is fast (as it's computed on every request) and ensures that similar keys hash to very different positions to prevent data 'clustering' or hot spots on individual servers.
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?