Consistent Hashing hard
In a P2P network (like BitTorrent DHT) where nodes join/leave every second (High Churn), why is standard Consistent Hashing insufficient?
- A It is not technically insufficient; the ring model is the industry-standard for all peer-to-peer file sharing networks at any scale.
- B Consistent hashing requires excessive CPU resources to re-calculate the ring topology every time a new peer joins the localized swarm.
- C The overhead of data movement (rebalancing) exceeds available bandwidth; the system spends more time moving data than serving it.
- D Standard hash keys are typically too large to be efficiently processed by the low-power devices that comprise the majority of P2P swarms.
Answer: C. The overhead of data movement (rebalancing) exceeds available bandwidth; the system spends more time moving data than serving it.
Consistent Hashing is designed for clusters where nodes are semi-permanent. In high-churn P2P networks (BitTorrent), nodes leave every second. Moving gigabytes of data every time the topology changes would saturate the network. Instead, these systems use 'Distributed Hash Tables' (DHTs) like Kademlia, which prioritize efficient routing to data locations without forcing the physical migration of the data itself.
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?