Consistent Hashing easy
Consistent Hashing conceptually maps both data keys and server nodes to:
- A A fixed-size Hash Map or Dictionary structure located within a centralized configuration management server.
- B A balanced Binary Search Tree that provides O(log N) lookup efficiency for all distributed key requests.
- C A virtual ring (continuum) of hash values typically ranging from 0 to a very large prime (e.g., 2^32 - 1).
- D A sequential flat-file database that is strictly synchronized across all child nodes using a consensus protocol.
Answer: C. A virtual ring (continuum) of hash values typically ranging from 0 to a very large prime (e.g., 2^32 - 1).
Consistent Hashing maps both nodes and keys onto the same circular range (the hash ring). This shared topology allows the system to define data 'ownership' based on proximity on the circle (for example, the first node found clockwise from a key's hash position), enabling decentralized and deterministic routing.
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?