Design a Key-Value Store

Consistent Hashing with Virtual Nodes

• Why: Distributes data evenly across nodes; adding/removing nodes only affects neighboring keys
• How:
  • Hash ring with 2^128 positions (MD5/SHA-256 of key)
  • Each physical node owns multiple virtual nodes (150-200 vnodes)
  • Key is placed on the ring → walk clockwise to find the first node → that's the coordinator
  • Next N-1 distinct physical nodes clockwise are the replicas
• Why Virtual Nodes: Without vnodes, data distribution is uneven. Vnodes ensure uniform distribution and smooth rebalancing when nodes join/leave

Storage Engine — LSM Tree (Log-Structured Merge Tree)

Why LSM over B-Tree: Optimized for write-heavy workloads (sequential disk writes)

Write Path

1. Write to WAL (Write-Ahead Log) — append-only file, fsynced on every write for durability
   • Format per entry: | CRC (4B) | Timestamp (8B) | Key_Len (4B) | Val_Len (4B) | Key | Value |
   • On crash: replay WAL entries to reconstruct the MemTable (no data loss)
   • Truncated after MemTable successfully flushes to SSTable
2. Write to MemTable — in-memory sorted skip list (O(log n) insert/lookup)
3. When MemTable reaches threshold (~64 MB) → freeze current MemTable (still readable), create a new empty MemTable for new writes → flush frozen MemTable to disk as an immutable SSTable
4. Background compaction merges SSTables to reduce read amplification

Read Path

1. Check MemTable (most recent data, in-memory, fastest)
2. Check Bloom Filter for each SSTable (probabilistic: "definitely not here" or "maybe here" — eliminates ~99% of unnecessary disk reads)
3. If Bloom filter says "maybe" → check SSTable's sparse index → locate data block → read and decompress
4. Check SSTables from newest to oldest (Level 0 first, then Level 1, etc.)
5. Return first match found

SSTable Internal Structure

• Data blocks: Sorted key-value pairs, compressed (LZ4/Snappy)
• Sparse index: Every Nth key → block offset (binary search to find the right block)
• Bloom filter: Per-SSTable, ~1% false positive rate with 10 bits per entry
• Footer: Metadata, compression codec, format version, checksum

SSTable Levels

• Level 0: Freshly flushed from MemTable — key ranges MAY overlap (multiple SSTables can contain the same key)
• Level 1+: Compacted — key ranges are non-overlapping within a level (each key exists in at most one SSTable per level)
• Each level is ~10× the size of the previous level

Compaction Strategies

• Size-Tiered Compaction (STCS): Merge similarly-sized SSTables when count exceeds threshold. Good for write-heavy workloads. Trade-off: high space amplification (up to 2× during compaction)
• Leveled Compaction (LCS): Promote SSTables from Level N to Level N+1, re-splitting to maintain non-overlapping ranges. Good for read-heavy workloads. Trade-off: high write amplification (rewrites entire level on merge)

Replication

• Replication Factor (N): Configurable, default 3
• Replication Strategy:
  • Coordinator writes to N replicas
  • Quorum-based: W + R > N ensures consistency
    • W=2, R=2, N=3 → strong consistency
    • W=1, R=1 → eventual consistency (fast)
    • W=3, R=1 → write-heavy consistency

Gossip Protocol (Failure Detection + Membership)

• Why: Decentralized — no single point of failure (unlike Raft/Paxos leader)
• How: Every node periodically (every 1 second) picks a random node and exchanges membership state
• Failure detection: Uses Phi Accrual Failure Detector — calculates a suspicion level (phi) based on heartbeat intervals. Declares node dead when phi exceeds threshold (e.g., 8)
• Information propagated: Node liveness, token ranges, load metrics
• Convergence: With N nodes, information reaches all nodes in O(log N) gossip rounds (~10 rounds for 1000 nodes)

Hinted Handoff (Temporary Failure Handling)

• When: A write's designated replica is DOWN but the write must still succeed (AP system)
• How:
  1. Coordinator detects that replica B is unreachable
  2. Instead of failing the write, coordinator writes B's copy to substitute node D
  3. D stores the data with a hint: {target: B, key: K, value: V, timestamp: T}
  4. When B recovers (detected via gossip heartbeat resuming), D forwards all hinted data to B
  5. D deletes the hints after B acknowledges receipt
• Hint TTL: 3 hours — if B doesn't recover within this window, hints are dropped. Full repair via Merkle trees is then needed to restore consistency.
• Sloppy quorum interaction: During partitions, writes can go to ANY W available nodes (not necessarily the "correct" replicas). This is what makes the system AP — always writable.

Anti-Entropy Repair (Merkle Trees)

• Purpose: Detect and repair data inconsistencies between replicas that hinted handoff couldn't fix (e.g., node was down longer than hint TTL)
• How:
  1. Each node maintains a Merkle tree per key range it owns
  2. Leaf node = hash(key + value) for each key-value pair
  3. Parent node = hash(left_child + right_child)
  4. Periodically (e.g., every hour), two replica nodes compare their Merkle tree root hashes
  5. If roots match → replicas are identical, done
  6. If roots differ → recursively walk down the tree comparing children until divergent leaf nodes are found
  7. Only the divergent keys are synchronized between replicas
• Efficiency: For 1 million keys, a Merkle tree has ~20 levels. If only 10 keys differ, you compare ~200 hashes (not 1 million) — O(log N × diff_count) bandwidth.
• Rebuild: Merkle tree is rebuilt after compaction (SSTables changed)

Conflict Resolution

• When: Two clients write to the same key concurrently (or during a network partition)
• Option 1 — Vector Clocks (Amazon Dynamo):
  • Each version carries a vector clock: {node_A: 3, node_B: 1}
  • On read, compare vector clocks: if one dominates (all entries ≥), take the dominant one
  • If neither dominates (concurrent) → conflict → return BOTH versions to the client → client merges (application-aware resolution, e.g., union of shopping cart items)
  • Problem: Vector clock size grows with number of writers — mitigate by truncating oldest entries when clock exceeds N entries
• Option 2 — Last-Write-Wins (Cassandra):
  • Compare timestamps → highest wins → other version silently discarded
  • Simpler but can lose data — concurrent writes, one is dropped
  • Use Hybrid Logical Clocks (HLC) instead of wall clock to avoid clock skew issues (HLC = max(wall_clock, last_HLC) + 1)

Coordinator Node

• Role: The node that receives the client request (determined by consistent hashing of the key)
• Write coordination:
  1. Append to local WAL (fsync for durability — survives crashes)
  2. Write to local MemTable (in-memory, fast)
  3. Forward write to N-1 replica nodes in parallel
  4. Wait for W total acknowledgments (including own)
  5. Return success to client
  6. If a replica is DOWN: Coordinator uses Hinted Handoff — writes the data to a substitute node with a hint. When the target recovers, the substitute forwards the hinted data.
• Read coordination:
  1. Send read request to all N replica nodes in parallel
  2. Wait for R responses
  3. Return the value with the highest timestamp (or latest vector clock) to the client
  4. Read Repair: If the R responses contain different versions, the coordinator sends the latest version to the stale replicas in the background — eventually converges all replicas
  5. Per-node read flow:
     • a. Check MemTable (newest data, in-memory)
     • b. Check Bloom Filter for each SSTable — if BF says "definitely not here," skip that SSTable entirely (saves disk I/O)
     • c. If BF says "maybe" → read SSTable's sparse index → find the data block offset → read and decompress the data block
     • d. Return the first match found (newest SSTable first)