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

High-Level Architecture

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.

Workshop note · added for the website’s common reading format

Walk through three failure moments in Key-Value Store: a request times out before its result is known; a dependency becomes slow rather than unavailable; and a process restarts after committing state but before acknowledging it.

For each case, name the authoritative record, define a safe retry, cap resource usage, and describe what the caller sees. Anti-entropy should help detect and contain the problem: Compare replica ranges and repair divergence in the background.

Tradeoffs & Design Decisions Summary

Failure Detection: Gossip Protocol

Node Join / Leave / Failure Handling

Adding a New Node

Handling Node Failure

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."