Requirements and Design Goals
A key-value store is a non-relational database where each unique key maps to a value. Operations: put(key, value) and get(key). Values are treated as opaque objects — the store does not interpret or index them.
Design targets: key-value pair size under 10 KB; store big data (petabytes total); high availability (fast responses even during failures); high scalability (add/remove nodes automatically); tunable consistency (configurable trade-off between consistency and availability); low latency. These are the same properties offered by DynamoDB, Cassandra, and Redis.
CAP Theorem
CAP theorem states no distributed system can simultaneously guarantee all three properties: Consistency (every read receives the most recent write), Availability (every request receives a response — not necessarily the latest data), and Partition Tolerance (the system continues operating despite network splits between nodes).
Since network partitions are unavoidable in any distributed system, you must choose between C and A during a partition event:
CP systems sacrifice availability: if a partition occurs, the system blocks writes to partitioned nodes until consistency can be restored. Bank systems often choose CP — showing stale balances is worse than showing an error.
AP systems sacrifice consistency: partitioned nodes continue serving requests with potentially stale data. Once the partition heals, data syncs. Most web applications choose AP — returning slightly stale data is preferable to returning errors.
Data Partitioning with Consistent Hashing
To distribute key-value pairs across multiple servers, we need a partitioning scheme that evenly distributes load and minimizes reshuffling when servers join or leave.
Consistent hashing: arrange all servers on a virtual hash ring (a circular hash space from 0 to 2^160 - 1 for SHA-1). Each server is assigned a position on the ring based on its hash. To look up which server stores a key, hash the key and walk clockwise around the ring until you find the first server.
When a server is added, only the keys between the new server and its predecessor need to be redistributed — a fraction of total keys. When a server is removed, its keys move to the next server clockwise — again, a small fraction.
Virtual nodes: each physical server is represented by multiple positions (virtual nodes) on the ring. This smooths out the distribution — without virtual nodes, some servers might receive significantly more keys than others depending on where they land on the ring.
Data Replication
To achieve high availability and fault tolerance, each key-value pair is replicated to N servers (N is configurable, typically 3). After hashing a key to a ring position, the key is stored on the first N unique physical servers encountered moving clockwise.
Why unique physical servers? With virtual nodes, the first N ring positions might map to the same physical server. We skip duplicates so each replica lives on a distinct physical machine.
For geographic resilience, replicas should span multiple data centers. Even if an entire data center goes offline, other replicas in separate locations continue serving requests.
Consistency with Quorum
With N replicas, configuring read and write quorums determines the consistency-availability trade-off:
W (write quorum): a write is successful when W replicas acknowledge it. R (read quorum): a read succeeds when R replicas respond.
If W + R > N, strong consistency is guaranteed — there is always at least one overlap between the write set and read set, ensuring the reader sees the latest write.
Common configurations (N = 3): W = 1, R = N (fast write, strong read consistency); W = N, R = 1 (strong write consistency, fast read); W = 2, R = 2 (balanced — good consistency and decent availability). Systems like Cassandra let you configure W and R per-operation, supporting both strong consistency and eventual consistency from the same cluster.
Conflict Resolution with Vector Clocks
In an eventually consistent system, two clients can write to the same key on different replicas simultaneously, creating conflicting versions. Vector clocks track causality to detect and resolve conflicts.
A vector clock is a list of (server, version) pairs associated with a data item. When a client reads data and writes it back, the server increments its version counter in the vector clock. If two writes happen concurrently on different servers, the resulting vector clocks are "siblings" — neither dominates the other. The system must resolve the conflict, either automatically (last-write-wins based on timestamp, or merge functions for specific data types like CRDTs) or by surfacing the conflict to the client.
DynamoDB uses vector clocks. The downside: client-side conflict resolution logic is complex, and the vector clock list grows with each server that touches the data.
Failure Detection with Gossip Protocol
In a distributed system, you cannot trust a single node's claim that another node is down — network issues can make a healthy node appear unreachable from one vantage point. Marking a node down requires independent confirmation from multiple sources.
Gossip protocol provides decentralized failure detection: each node maintains a membership list with heartbeat counters for every known node. Periodically, each node increments its own heartbeat counter and sends its membership list to a random subset of peers. When a node receives a heartbeat update, it merges it with its local list and propagates fresh information. If a node's heartbeat counter has not been updated for longer than a threshold (e.g., 30 seconds), it is marked as potentially down. Once enough independent nodes confirm the stale heartbeat, the node is marked offline and gossip propagates this information cluster-wide.
Anti-Entropy with Merkle Trees
When a node goes offline and comes back, it may have missed writes. Anti-entropy protocols synchronize replicas by comparing data and transferring only the differences.
Comparing entire datasets is expensive. Merkle trees enable efficient difference detection: build a tree where each leaf node is the hash of a data block. Parent nodes are hashes of their children. To compare two replicas, compare their root hashes. If they match, the replicas are identical. If they differ, descend into the tree — compare left child hashes, then right — until you identify the exact data blocks that differ. Only those blocks need to be transferred.
The amount of data transferred for synchronization is proportional to the number of differences, not the total dataset size.
Write and Read Paths
Write path (based on Cassandra's LSM-tree architecture): (1) Write is appended to a commit log on disk (durability). (2) Data is written to an in-memory memtable. (3) When the memtable is full, it is flushed to disk as an SSTable (Sorted String Table) — an immutable, sorted file. (4) Periodic compaction merges SSTables, removing deleted keys and merging duplicate entries.
Read path: (1) Check the in-memory memtable first. (2) If not found, check a bloom filter — a probabilistic data structure that quickly rules out SSTables that definitely do not contain the key, avoiding unnecessary disk reads. (3) Read from the relevant SSTables on disk. (4) Return the value to the client.
This architecture gives fast writes (append-only, sequential disk I/O) at the cost of potentially slower reads (must check multiple SSTables).