Key-Value Store

Problem Statement & Requirements

Functional Requirements

• put(key, value) — store a key-value pair
• get(key) → value — retrieve the value for a given key
• delete(key) — remove a key-value pair
• Support variable-size values (1 byte to 1 MB)
• Keys are strings (up to 256 bytes)
• Automatic data expiration (TTL support)

Non-Functional Requirements

• High availability — always writable, even during network partitions (AP system)
• Low latency — single-digit millisecond reads and writes (p99 < 10 ms)
• Scalability — horizontally scale to petabytes across thousands of nodes
• Durability — no data loss once acknowledged
• Tunable consistency — allow clients to choose between strong and eventual consistency per request
• Fault tolerance — handle node failures, network partitions, and datacenter outages

Out of Scope

• Range queries / secondary indexes (that's a full database)
• Transactions across multiple keys
• Complex data types (lists, sets, sorted sets — that's Redis)
• SQL query interface

Scale Estimations

Traffic & Storage

Node Sizing

Network

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

Data Model & API

Wire Protocol

Internal Data Format (On Disk)

Storage Engine

LSM-Tree (Log-Structured Merge Tree) — Write-Optimized

Bloom Filters — Avoiding Unnecessary Disk Reads

B-Tree vs LSM-Tree Tradeoff

Our choice: LSM-Tree — write-heavy workload, sequential disk I/O, good for SSDs.

CAP Theorem & Design Philosophy

Our choice: AP with tunable consistency

• Default to availability + partition tolerance
• Allow clients to request stronger consistency when needed (quorum reads)
• This is the Dynamo model — write always succeeds, conflicts resolved on read

Core Component: Consistent Hashing

The Problem with Naive Hashing

Consistent Hashing Solution

Virtual Nodes (vnodes) — Solving Uneven Distribution

How Many Virtual Nodes?

Tradeoff: More vnodes = better distribution but more metadata to maintain and transfer during rebalancing.

Tunable Consistency (Quorum)

The N, W, R Parameters

Common Configurations

Sloppy Quorum & Hinted Handoff

Detailed Flow Diagrams

Write Flow

Read Flow

Read Repair

Compaction Strategies

Data Partitioning & Replication

Partition Assignment

Replication Strategy

Conflict Resolution

When multiple replicas accept concurrent writes to the same key (during a partition or with W < N), conflicts arise.

Vector Clocks

Conflict Resolution Strategies

Anti-Entropy: Merkle Trees

For replicas that haven't served reads recently, stale data can go undetected. Merkle trees solve this.

Suppose two replicas accept different values for the same key during a partition. A later read must either resolve the conflict according to a declared rule or return enough version information for the application to resolve it. Now delete that key: the deletion needs a durable marker so an older replica cannot resurrect the value during repair.

Tradeoffs & Design Decisions Summary

Failure Detection: Gossip Protocol

Node Join / Leave / Failure Handling

Adding a New Node

Handling Node Failure

High-Level Architecture

Production Architecture

Comparison with Real Systems

Interview Tips

1. Start with CAP — "Before diving into the design, let me clarify the consistency model. For a KV store, we usually want AP with tunable consistency." This frames the entire design.

2. Consistent hashing is the centerpiece — Draw the ring, explain vnodes, show why naive modulo hashing fails. This is the core algorithmic insight.

3. Walk through a write + read flow — Show how data flows through WAL → MemTable → SSTable, and how quorum reads work. This demonstrates you understand the full data path.

4. Discuss vector clocks carefully — Use a concrete example with two concurrent writes. Show how conflicts are detected and how the client resolves them.

5. Mention Merkle trees for anti-entropy — This shows you think about long-term consistency, not just the happy path. "How does a replica that was down for 2 hours catch up?"

6. Don't forget the storage engine — LSM-Tree with bloom filters is the standard answer. Explain write amplification as a tradeoff.

7. Gossip protocol for membership — Shows you understand decentralized failure detection. Mention the convergence time (O(log N) rounds).

8. Name real systems — "This is essentially the Dynamo paper architecture" or "Cassandra uses a similar approach but with LWW instead of vector clocks." Shows you've read the literature.

9. Tombstones for deletes — A subtle but important point. "You can't just delete from one replica — the other replicas will think the key still exists and resurrect it."