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

1. 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.

2. Membership Changes

• Implement addNode/removeNode with minimal key movement.
• Handle wrap-around and token collisions.

3. 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.

4. Complexity

• Analyze time and space complexity for lookup, add, remove, and put/get with replication factor R.

5. 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.

6. 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.