Scale a NoSQL Key–Value Store to One Million QPS

Scenario

LinkedIn maintains critical user context, service state, and real-time counter data across distributed microservices. You are tasked with designing a distributed NoSQL key-value store capable of handling high-throughput, low-latency lookups and updates at scale.

Requirements

Functional Requirements

• get(key): Retrieve the value associated with the specified key.
• put(key, value): Insert or update the value for the given key.
• delete(key): Remove the key-value pair.

Non-Functional Requirements

• High Throughput: Support 1,000,000 queries per second (QPS) at peak.
• Low Latency: p99 latency under 5 ms for reads and under 10 ms for writes.
• High Availability: 99.999% uptime; tolerate individual node and rack failures.
• Tunable Consistency: Support trade-offs between eventual consistency and strong consistency depending on client requirements.
• Durability: Data must not be lost once a write is acknowledged.

Scale & Capacity Assumptions

• Total Dataset: 50,000,000 key-value pairs.
• Key Size: Average 64 bytes.
• Value Size: Average 1 KB.
• Traffic Split: 800,000 reads/sec (80%) and 200,000 writes/sec (20%).

What Your Design Should Cover

1. Capacity Planning: Compute the memory, storage, and network bandwidth requirements for the cluster.
2. Data Partitioning & Routing: How keys are distributed across nodes, how hot partitions are avoided, and how clients locate keys.
3. Replication & Consistency: How data is replicated across nodes, node failure handling, and quorum models (R + W > N).
4. Storage Engine: Internal storage architecture on individual nodes (e.g., in-memory hash map vs. LSM-tree vs. B-Tree) to meet latency and durability targets.
5. Trade-offs: Address the trade-offs between network bandwidth, consistency models, and operational complexity.