Design Distributed Key-Value Store

Design a distributed key-value store like Redis or Dynamo. Support high availability, consistency, and scalability.

Note: This is LinkedIn's most frequently asked system design question. Focus can vary between low-level implementation (append-only files, memtable, WAL) and high-level distributed systems (sharding, replication).

Requirements:

• Basic CRUD operations (get, put, delete)
• High availability with replication
• Horizontal scalability via sharding
• Configurable consistency levels (eventual vs strong)
• Handle billions of keys

Key Components:

• Storage Engine (LSM tree, memtable, SSTable)
• Sharding/Partitioning (consistent hashing)
• Replication (leader-follower, multi-leader)
• Consistency Protocol (vector clocks, read/write quorum)
• Failure Detection (gossip protocol)

Discussion Points:

• Write-ahead logging (WAL) for durability
• Compaction strategies
• Read repair and anti-entropy
• Handling network partitions
• CAP theorem tradeoffs

Low-Level Variant (asked at LinkedIn): Design a KV store engine on an append-only file system (single machine). Discuss memtable, WAL, file pointers, compaction, and how to handle deletes.