Consistent Hashing hard
What is 'Ketama' hashing?
- A A specialized cryptographic hash.
- B A load balancing proxy.
- C The standard implementation of Consistent Hashing (Ring + VNodes) used by the original Memcached client (libketama).
- D A database written in C.
Answer: C. The standard implementation of Consistent Hashing (Ring + VNodes) used by the original Memcached client (libketama).
Ketama (specifically libketama) was the first major implementation of Consistent Hashing for the web. It codified the pattern of treating the hash space as a 0-2^32 continuum and hashing nodes onto it multiple times (VNodes). Most modern implementations of sharding for caching are children of the Ketama approach.
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?