Design consistent hashing with a sorted map
Overview
This question evaluates understanding of consistent hashing, virtual nodes, sorted-map ring representation, replication and quorum strategies, membership changes and failure handling, complexity analysis, and testing considerations for distributed key-value or cache sharding systems.
Consistent Hashing with a Sorted Map (Virtual Nodes)
Context
You are building a client-side library to map arbitrary keys to backend nodes (cache/storage shards) that can be added or removed at runtime with minimal remapping. Represent the consistent hash ring with a sorted map (e.g., a TreeMap keyed by 64-bit hash tokens). Lookups should find the next node clockwise from a key's hash, with wrap-around to the beginning of the ring.
Requirements
- Hashing and Ring
- Choose a hash function; justify the choice.
- Use virtual nodes; specify how many per physical node and why. Support weights for heterogeneous node capacity.
- Represent the ring using a sorted map keyed by hash tokens.
- Membership Changes
- Implement addNode/removeNode with minimal key movement.
- Handle wrap-around and token collisions.
- APIs
- getNodeForKey(key) and getNNodesForKey(key, R) for replication.
- put(key, value) and get(key) that route to the selected node(s). You may simulate per-node storage in-process.
- Complexity
- Analyze time and space complexity for lookup, add, remove, and put/get with replication factor R.
- Reliability and Operations
- Discuss node failure detection and what happens when a node is down.
- Replication strategy, read/write quorum options, rebalancing, and capacity weighting.
- Testing
- Outline tests for correctness, distribution fairness, churn (add/remove), and failure scenarios.
Assume a single-process demo is fine. Use any language with a sorted map (e.g., TreeMap) and include code for the library and a brief example.
Solution
Login required