Design a Key Value Store

A key-value store has the simplest interface in all of databases (get, put, delete) but distributing it across machines surfaces every hard problem in distributed systems. Partitioning, replication, consistency, failure detection, conflict resolution. The simplicity of the API is deceptive. The complexity lives entirely in the infrastructure behind it.

Functional

• Get, put, and delete operations: The entire API is three operations. put(key, value) stores a key-value pair, get(key) retrieves the value, delete(key) removes it. Keys are strings or byte arrays, values are opaque blobs (the store does not interpret them). This simplicity is deliberate. It pushes all schema and query logic to the application layer.
• Data replication across multiple nodes: Every key-value pair is stored on multiple nodes (typically 3). If one node crashes, the other two still serve the data. Replication is not optional in a distributed KV store. Without it, a single node failure means permanent data loss for every key that node owned.
• Data partitioning across a cluster: No single node holds all the data. Keys are distributed across nodes so the system scales horizontally. Add more nodes to handle more data and more traffic. The partitioning scheme determines which node owns which keys.
• Persistence and durability: Data survives node restarts. Every write is appended to a write-ahead log (WAL) before being acknowledged. If a node crashes mid-write, the WAL replays on restart to recover the in-memory state.
• Optional TTL and expiration: Keys can have a time-to-live after which they are automatically expired and removed. Implementations vary: lazy deletion checks TTL on read, periodic sweeps scan for expired keys in the background, or compaction skips expired entries during SSTable merges.
• Optional compare-and-swap (CAS): Conditional updates where a value is written only if the current version matches what the client expects. This enables optimistic concurrency without distributed locks. The client reads a value with its version, modifies it, and writes back only if no other client changed it in between. If the CAS fails (another client wrote first), the client re-reads the current version and retries. This pattern is essential for counters, inventory levels, and any read-modify-write operation on shared data.

Capacity estimation derives the constraints that shape every architectural decision. How many nodes, how much replication overhead, whether disk or network is the bottleneck. Getting these numbers wrong means designing for the wrong problem.

Traffic

• Read throughput: 100K reads per second.
• Write throughput: 50K writes per second.
• Read-to-write ratio: 2:1. This is important. A 2:1 ratio is much more write-heavy than typical web applications (which are often 100:1). This tells us the storage engine must be optimized for writes.
• Average value size: 1 KB. Key size: 128 bytes.
• Raw write bandwidth: 50K writes/sec x 1 KB = 50 MB/s to a single replica.
• With replication factor 3: Every write goes to 3 replicas, so cluster-wide write throughput is 150K writes/sec, consuming approximately 150 MB/s of aggregate disk I/O. Modern NVMe SSDs handle 500+ MB/s sequential writes, so this is comfortably achievable.

Three operations cover the entire interface. But the optional parameters on each operation reveal the distributed complexity hiding beneath the simple API.

Core Operations

• put(key, value, options): Stores a key-value pair. Options include consistency_level (ONE, QUORUM, ALL), ttl (time-to-live in seconds), and if_not_exists (CAS semantics. Fails if key already exists). The coordinator hashes the key, identifies N replica nodes on the hash ring, sends the write to all N, and waits for W acknowledgments before returning success.
• get(key, options): Retrieves the value for a key. Options include consistency_level. With QUORUM, the coordinator reads from R replicas, compares versions, and returns the latest. With ONE, it reads from the nearest replica for minimum latency. If replicas disagree, the coordinator triggers read repair in the background.
• delete(key, options): Removes a key-value pair. Distributed deletes cannot simply erase data. If one replica deletes the key but another is temporarily down, the surviving replica would resurrect the key on the next read repair. Instead, delete writes a tombstone marker that propagates to all replicas. Compaction permanently removes tombstoned data after a grace period (typically 10 days).

Two problems must be solved simultaneously, where data lives across the cluster (partitioning) and how each node stores data locally (storage engine). Getting either wrong undermines the entire system.

Consistent Hashing

The naive approach to partitioning is key mod N. Hash the key and assign it to node hash(key) % N. This works perfectly for a fixed cluster size. But distributed systems do not stay fixed. Nodes fail, get replaced, and new nodes are added as data grows. With N=10, adding an 11th node changes the modulus from 10 to 11, remapping roughly 90% of all keys. At 1 TB of data, that means moving 900 GB across the network. An unacceptable disruption that takes hours and degrades performance for every client during the migration.

Three mechanisms explain 80% of how DynamoDB and Cassandra work: consistent hashing distributes data, replication copies it, and quorum parameters control the consistency-availability knob. Everything else in the architecture exists to keep these three working during failures.

Architecture Overview

Write and read flows are where quorum, replication, and consistency become concrete network call sequences. Understanding these step-by-step flows is essential for debugging distributed consistency issues.

Write Flow

The defining challenge of a distributed key-value store: two clients write the same key on different replicas simultaneously. How does the system detect the conflict and resolve it without losing data? This is where the design separates competent answers from great ones.

Conflict Resolution: The GATE Challenge

When a network partition occurs, do you reject writes (CP) or accept writes that may conflict (AP)? This single decision cascades through every layer of the design. Storage engine, conflict resolution, failure handling, and client library complexity.

CP vs AP

CP (Consistency + Partition Tolerance): During a partition, the minority side refuses reads and writes. HBase with ZooKeeper is the canonical example. The ZooKeeper quorum determines which side is the "real" cluster, and the minority side stops serving entirely until the partition heals. Advantage: clients never see stale or conflicting data. Disadvantage: the minority side is completely unavailable, and even brief network blips cause visible errors. For a key-value store serving user-facing traffic, where network partitions happen more often than you think (Google reports roughly 10 per day across their clusters), unavailability during every partition is unacceptable.

Failures are not exceptional events. With hundreds of nodes, something is always crashing, being deployed, or experiencing a network blip. The system must handle failures continuously and automatically, without human intervention.

Temporary Failure: Hinted Handoff

Three challenges extend the core design beyond a single-datacenter key-value store: geographic distribution for latency and disaster recovery, richer query patterns for broader application support, and operational automation to reduce human intervention. Each of these adds significant complexity but is necessary for production-grade systems serving global users.

Multi-DC Replication (XDCR)

Cross-datacenter replication extends availability across geographic regions. Each data center operates as an independent cluster with its own quorum. Writes are acknowledged locally with W ACKs from local replicas, then asynchronously forwarded to remote data centers. This keeps write latency low (local DC round-trip) while providing disaster recovery (entire DC failure does not lose data).