System Design- Chapter.4: Designing a Key-Value Store

Remember whenever we go to temple. We have to leave our shoes outside, sometimes we hand it to an attendant and they give us a token number (that’s our key). Now, when we want our shoes back, we show the token back, they fetch exactly our shoes (that’s our value). That’s a key-value store, a lookup system where every piece of data has a unique label attached to it.

In code terms: you put(“user_123”, userData) to save it, and get(“user_123”) to retrieve it. That’s literally the whole interface.

The Single server problem

The simplest version: store everything in one computer’s memory (like a giant dictionary/hashmap). Super fast, but what happens when you run out of scope? Or that one computer crashes? You lose everything. So we need to distribute the data across many machines.

Here’s a diagram of how a single server works vs. what breaks:

Fig 1. Single Server Vs Distributed Server

The CAP Theorem: the fundamental trade-off

Before you design anything distributed, you need to understand the most important rule in the field. Think of it like this:

Imagine their are 3 friends — Rishabh, Prince and Diwakar, all sharing a Google Doc. The CAP theorem says you can only guarantees 2 of these 3 promises at once:

• Consistency (C): Everyone always sees the same, latest version of the doc. No one reads stale data.
• Availability (A): The doc is always accessible, even if one friend’s internet goes down.
• Partition Tolerance (P): The system keeps working even if Prince and Diwakar can’t talk to Rishabh (a “Partition” = a network split).

In the real world, network splits always happen, a cable gets cut, a data center loses power. So you always need Partition Tolerance. The real choice is: when a split happens, do you stay Consistent or Available?

Fig 2. CAP Theorem — a distributed system can only guarantee 2 of the 3 properties simultaneously

CP Systems choose consistency and partition over availability. When a partition happens, they’d rather block or return an error than risk showing stale data. Example: A bank (CP) would rather lock your account and show an error than show you a wrong balance.

AP Systems choose availability and partition over consistency. During a partition, they keep responding but some nodes might return slightly stale data. Example: A social media feed (AP) would rather show you a post that’s slightly stale than go down entirely.

CA Systems choose consistency and availability over partition tolerance. These cannot exits in the real world because network partitions are unavoidable.

Data Partition with Consistent Hashing

With multiple servers, you need a rule for deciding which server stores which key. Suppose you have 5 server, which server stores which key? You can’t just do key % 5 (number of servers), because if you a 6th server, almost every key moves and that’s a disaster. Almost every key maps to a different server. You’d have to move nearly all your data every time you scale. That’s unacceptable.

Consistent Hashing solves this beautifully. You place your server at spots around the ring, then “throw” each key at the ring and it lands on the first server it encounters going clockwise. If you add or remove a server, only the keys near that server move. Everything else stays put.

Fig 3. Consistent hashing — keys are placed on a ring and assigned to the nearest server clockwise

Note: To know about Consistent Hashing in detail please refer to this blog: https://medium.com/@RobuRishabh/system-design-chapter-3-consistent-hashing-explained-aeef2f3ebf63

Consistency — Quorum: how many servers must agree?

Here’s a subtle but important problem. If data is copied to 3 servers, what happens when a write comes in? Do all 3 need to confirm before we say “success”? What about reads?

This is the Quorum system. You set three knobs:

• N = number of replicas
• W = how many servers must confirm a write before it’s “done”
• R = how many servers must responds to a read before we trust the result

The golden rule: if W + R > N, you get strong consistency (at least one server in the read set definitely has the latest write).

Fig 4. Three quorum configurations for N=3 replicas — trading off read/write speed vs. consistency

• W=3, R=1 (Optimise for reads): Every write hits all nodes. Reads are instant from any single node. Use when reads massively outnumber writes.
• W=1, R=3 (Optimise for writes): Writes confirm immediately. Reads must check all nodes. Use for write-heavy workloads like logging or event streams.
• W=2, R=2 (Strong consistency): W+R=4 > N=3. There’s always an overlapping node. No client ever sees stale data. The recommended default.

Resolving Conflicts — Vector Clocks

Imagine two doctors updating the same patient record from different hospital terminals, both offline due to a network outage. When the network comes back, both terminals try to sync. Each has a “last modified” time, but one terminal’s clock runs 3 seconds fast. Which version is actually newer? You simply cannot know.

Wall-clock time is unreliable in distributed systems because clocks drift, servers disagree, and network delays make ordering ambiguous. What you actually need to track is causality, did event A definitively happen before event B, or did they happen independently of each other? That’s exactly what vector clocks solve.

What is a vector clock?

Think of a vector clock like a travel journal that your data carries everywhere it goes. Every time a server writes to that data, it signs the journal with its name and how many times it has written, like a country stamping your passport on entry.

When two versions of the data need to be compared, you simply open their journals side by side. If every entry in journal A is less than or equal to the matching entry in journal B, then B is simply a newer version of A , no conflict, B wins. But if journal A shows a higher count for one server while journal B shows a higher count for a different server, it means both servers wrote independently without knowing about each other. That is a genuine conflict.

Formally, vector clock looks like this: D([Sx, vx], [Sy, vy], [Sz, vz]...),where each entry is a [server, version_counter] pair.

The rule is simple: when server Si writes data, it increments its own counter vi. If Si hasn't written this data before, it adds a new entry [Si, 1].

Fig 5. Shows what the stamp looks like and how it grows with each write

Let’s understand it through a real-life analogy

Dr. Prince and Dr. Diwakar both pull up the same patient record, “Diagnosis: mild fever” on their tablets before a network outage. Cut off from each other, Prince updates the diagnosis to “viral infection” and Diwakar updates it to “bacterial infection”. When the network comes back, both tablets try to sync. Who wins? Neither edit came after the other, they happened at exactly the same time, on separate machines, with no knowledge of each other. This is a genuine conflict that “last write wins” cannot safely resolve in a medical context.

Vector clocks make this conflict visible and explicit, so the system never silently picks the wrong one. Let’s watch it play out step by step:

Fig 6. Full vector clock story play out

How to read the conflicts — the two comparison rules

Given any two versions with their clocks, there are only 2 possible outcomes:

1. Rule 1 — Ancestor (NO conflict): Version A is an ancestor of B if every counter in A is ≤ the corresponding counter in B. B simply happened after A. Use B, throw away A.
2. Rule 2 — Siblings (Conflict): A and B conflicts if A has a higher counter for at least one server, while B has a higher counter for at least one different server. Neither descended from the other, they forked.

Fig 7. How do you decide if one is newer, or if they conflict

The two downsides — and how the real systems handle them

Vector clocks are powerful but they come with two practical problems:

Fig 8. Summary of both problems

Failure Detection — The Gossip Protocol

How does the system know when a server has died? You can’t rely on one server to report another as dead (that reporter might itself be having issues). Instead, the system uses gossip protocol, just like how rumors spread in an office.

Each server regularly sends its “heartbeat” (a counter that keeps increasing) to a few random neighbors. Those neighbors pass it on. If a server’s heartbeat stops incrementing, the whole cluster eventually figures out it’s dead, without any central coordinator.

Fig 9. Gossip Protocol

Write & Read Paths — What actually happens inside a node?

When a write request lands on a node, it goes through three stages before it’s considered safely stored. The order matters, crash safety comes first.

Write: The data first goes to a commit log on disk (a crash-safe journal), then into an in-memory cache. When the cache fills up, it’s flushed to disk as an SSTable (a sorted file of key-value pairs).

Fig 10. Write Path

Read: The node first checks memory (fastest). If not there, it uses a Bloom filter, a clever probabilistic shortcut that quickly says “this key is definitely NOT in file X, don’t bother checking”, then fetches from the right SSTable on disk.

Fig 11. Read Path

Handling Temporary Failures — Sloppy Quorun & Hinted Handoff

In a strict quorum system, if a required node is down, the whole operation blocks. That kills availability. The fix is sloppy quorum. Instead of waiting for the exact nodes that should hold the data, the system just picks the first “W” healthy servers on the ring for writes and the first “R” healthy servers for reads, skipping offline ones entirely.

But what about the offline server’s data? That’e where hinted handoff comes in. Think of it like a neighbor collecting your mail while you’re on holiday. A server temporarily accepts writes meant for the down server, tags them with a note saying “this belongs to server S2”, and the moment S2 comes back online, the healthy server hands everything back.

Fig 12. Sloppy Quorum & Hinted Handoff

Handling Permanent Failures — Merkle Trees

Hinted handoff handles servers that comeback. But what if a server is gone for good, and gets replaced with a fresh empty machine? That new machine is missing months of data. How do you efficiently sync it with the other replicas without transferring every single key?

The answer is Merkle tree (also called a hash tree). The core idea: instead of comparing individual keys one by one, you build a tree of hashes. Comparing two trees starts at the root.

Fig 13. Build Merkle tree step by step

Now here is how two servers use their Merkle trees to find exactly which data differs without scanning every key:

Fig 14. Merkle tree comparision

The efficiency is dramatic. In real systems, a billion keys might be split into a million buckets, each holding about 1,000 keys. Comparing two replicas requires only comparing ~20 hash values to find the exact bucket that differs, then syncing just those ~1,000 keys. Not the entire billion.

Handling Data Center Outage

A single data center can fail entirely, power cut, network cable, natural disaster. If all your replicas live in one building, a single event wipes out everything.

The fix is straightforward: replicate across multiple geographically separate data centers, connected by high-speed private networks. When DC-West goes dark, clients are automatically routed to DC-East. No data is lost because both centers have full copies.

Fig 15. Data Center Replication

Putting it all together — the full architecture

Every node in the system is equal, there is no master, no single point of failure. Each node can act as a coordinator, store data, detect failures, and replicate to neighbours.

Fig 16. System Architecture

Acknowledgement — I learned the above concepts from book: [System Design Interview by Alex Xu], do read this book, if you want to understand in better way.

If you liked this breakdown of concepts please follow, subscribe and clap 👏