Consistent Hashing hard
In the Chord DHT protocol (a P2P consistent hashing implementation), naive lookups are O(N). How does Chord optimize this to O(log N)?
- A It relies on a centralized hierarchy of index servers that maintain the full global topology of the decentralized network.
- B It uses a blind 'Flooding' (Broadcast) mechanism where requests are forwarded to every connected peer until the data is found.
- C It caches every single key-to-node mapping locally on every participant node to ensure O(1) direct routing at the cost of memory.
- D It utilizes 'Finger Tables' where each node knows neighbors at distances of 2^i, allowing O(log N) jumps around the virtual ring.
Answer: D. It utilizes 'Finger Tables' where each node knows neighbors at distances of 2^i, allowing O(log N) jumps around the virtual ring.
In a pure P2P network like Chord, no one knows the whole ring. Naive routing (passing to the next guy) is O(N). Finger Tables allow a node to jump 1/2 the ring, then 1/4, etc. This logarithmic routing is beautiful: you only need to know O(log N) other nodes to find any data in the entire network efficiently.
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?
- 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?