Design a horizontally scalable distributed key-value store. The system must store opaque values keyed by a string key and support get, put, and delete operations on a single key. The system should scale across many commodity nodes, remain available when individual nodes fail, and redistribute data smoothly as nodes are added or removed. The design should focus on data partitioning (sharding), replication, rebalancing, and failure handling.

Constraints & Assumptions:

• Billions of keys; values range from a few bytes up to a few megabytes.
• Core operations are single-key get, put, and delete; range scans are out of scope.
• Target low single-digit-millisecond p99 latency for single-key operations and high availability (99.9%+).
• The system runs on many commodity nodes spread across racks; multi-datacenter is an extension.
• The workload is read-heavy but with a meaningful write rate; data must be durable.

Clarifying Questions to Ask:

• What consistency model is required: strong consistency, or eventual consistency with read-your-writes? How much staleness is tolerable?
• What is the value-size distribution, and are accesses strictly point lookups or do we need range queries?
• What durability and replication guarantees are required? Single datacenter or multi-DC?
• What are the throughput and latency targets, and the read/write ratio?
• Do we need multi-key atomic operations or transactions, or is single-key atomicity enough?

Design Focus Areas:

1. Partitioning: How to map billions of keys across many nodes, minimizing data movement during node additions/removals, and how clients locate the responsible node.
2. Replication and Consistency: How to replicate data for durability and availability, maintain replica consistency, and resolve concurrent writes.
3. Rebalancing and Failure Handling: How the cluster heals itself when nodes are added, removed, or fail (transient and permanent failures).