Consistent Hashing hard
When a node recovers and rejoins the ring, it needs to sync missed data. Why use Merkle Trees instead of transferring the whole dataset?
- A Merkle Trees encrypt the dataset during transit to ensure that synchronization is cryptographically secure against packet sniffing.
- B Merkle Trees enable efficient comparison of massive datasets, allowing nodes to identify and transfer only the specific diffs.
- C Merkle Trees provide a pre-compressed representation of the data that is significantly smaller than the raw binary records.
- D Merkle Trees utilize a distributed locking mechanism to prevent write conflicts during the active data reconciliation phase.
Answer: B. Merkle Trees enable efficient comparison of massive datasets, allowing nodes to identify and transfer only the specific diffs.
Transmitting a 1TB shard just to check for a few missing records is wasteful. Merkle Trees (Hash Trees) allow nodes to compare root hashes first. If they differ, they compare children, effectively performing a binary search for the differences. This permits high-speed 'Anti-Entropy' repairs with minimal network usage.
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?