Imagine you need to store hundreds of billions of small records - user sessions, feature flags, shopping cart state, configuration values - and retrieve any of them in under 5ms, 24/7, across data center failures. A single machine fails that requirement on day one. You need to split the data across dozens or hundreds of machines, keep multiple copies of each record in case machines die, and still give clients the illusion of a single coherent store.

Think of a distributed key-value store like a post office with thousands of branches. When you drop a letter (a PUT), the system must decide which branch handles your street address (consistent hashing), make photocopies and store them at nearby branches (replication), and ensure that when you ask “did my letter arrive?” at any branch counter (a GET), you get a truthful answer even if the original branch is temporarily closed. The moment you have three branches handling the same letter, you need rules for what happens when they disagree about whether the letter arrived at all.

The naive approach - round-robin sharding with key % N - breaks catastrophically when N changes. Add one node and every key remaps to a different machine. You trigger a full data migration, overload every machine simultaneously, and black out the system during the move. At 100 req/s and 10 nodes, this is annoying. At 100,000 req/s and 50 nodes it is a company-ending event.

At scale, the hardest part isn’t storage - it’s the geometry of distributed disagreement. When you write a value to three replicas and one replica is temporarily unreachable, do you wait for it (strong consistency, higher latency) or proceed without it (eventual consistency, risk of stale reads)? When the unreachable replica comes back with a conflicting version, whose write wins? We need to solve for partition-tolerant placement, tunable consistency, and convergent conflict resolution simultaneously.

Requirements and Constraints

Functional Requirements

• PUT(key, value) - store or update a value for a key
• GET(key) - retrieve the value for a key, or a not-found signal
• DELETE(key) - remove a key from the store
• Tunable consistency: ONE, QUORUM, ALL consistency levels per operation
• Automatic replication of each key to N replicas (configurable, default N=3)
• Transparent routing: any node in the cluster can receive any request and forward it appropriately
• TTL support: keys expire after a configured duration

Non-Functional Requirements

• Latency: GET at QUORUM consistency under 5ms p99; PUT under 10ms p99
• Throughput: 500,000 reads/second and 100,000 writes/second across the cluster
• Durability: survive loss of any single node with zero data loss; survive simultaneous loss of two nodes with no more than a brief availability gap
• Availability: 99.99% uptime (52 minutes downtime/year), tolerate single datacenter failure
• Storage: 10TB usable capacity across the cluster, keys up to 256 bytes, values up to 1MB
• Replication factor: default N=3, configurable per keyspace

Constraints and Assumptions

• Keys are arbitrary byte strings, not structured; no range scans required
• No cross-key transactions or multi-key atomicity
• Clients have access to a cluster membership list or DNS-based discovery
• Single region deployment in v1; multi-region is a future extension
• Clocks are not perfectly synchronized; we cannot rely on wall-clock ordering

High-Level Architecture

The system has five major components that interact along two distinct paths - the write path and the read path - plus a set of background maintenance processes that keep the cluster healthy without operator intervention.

The Client SDK embeds the cluster membership map and implements consistent hash lookups locally. This means clients can compute the correct coordinator node for any key without a central router, eliminating a single point of failure. The SDK refreshes membership from any live node via gossip.

The Coordinator Node receives the client request, looks up the preference list (the N nodes responsible for that key), fans out the write or read to those replicas in parallel, and waits for W (write) or R (read) acknowledgments before responding to the client. Any node in the cluster can act as coordinator for any request.

The Storage Nodes hold the actual data using an LSM-tree (Log-Structured Merge Tree) for write-optimized storage. Each physical node is responsible for many virtual nodes on the hash ring, which enables fine-grained load balancing.

The Gossip Protocol service runs continuously on every node, exchanging membership state with two random peers every second. This ensures every node has an eventually consistent view of which nodes are alive, which have failed, and which recently rejoined.

Anti-entropy repair, hinted handoff, and read repair are background processes that detect and fix divergence between replicas without operator intervention.