1. Introduction

A Key-Value Store is the simplest yet one of the most powerful distributed data systems. It provides a dictionary-like interface where any piece of data is stored as a value indexed by a unique key. Despite its simplicity, building a key-value store that scales to millions of operations per second with strong durability and availability guarantees is a profoundly complex distributed systems challenge.

Consider Amazon DynamoDB, which serves tens of millions of requests per second for applications like Amazon.com's shopping cart, Prime Video session management, and Alexa voice data. Or consider Redis, which powers caching for virtually every major tech company. These systems started as simple key-value concepts but evolved into sophisticated distributed storage engines.

The Problem

Application developers need a data store that provides:

• Low Latency: Sub-millisecond access to individual records for real-time applications.
• High Throughput: Millions of reads and writes per second for popular applications.
• Horizontal Scalability: Scale from gigabytes to petabytes of data without re-architecture.
• Durability: Data survives node failures, power outages, and hardware degradation.
• Availability: Continuous operation even when individual nodes fail.

Relational databases provide strong consistency and complex querying but struggle at massive scale for simple key-value access patterns. The key-value store strips away relational complexity to deliver maximum performance for the simplest and most common data access pattern.

Business Motivation

• Session Storage: User session data for web applications (billions of sessions).
• User Profiles: Profile data for social networks (billions of users).
• Shopping Carts: E-commerce cart data requiring high availability.
• Real-Time Analytics: Counters, leaderboards, rate limiters.
• Configuration Management: Distributed configuration with fast lookups.
• Caching Layer: In front of databases to reduce latency and load.

Real-World Examples

• Amazon DynamoDB: Fully managed KV store. 89.2 trillion requests/day at peak. Powers Amazon.com, Alexa, Lambda.
• Redis: In-memory KV store. 100K+ operations/sec per instance. Used by Twitter, GitHub, Stack Overflow.
• Cassandra: Wide-column store with KV semantics. Netflix, Instagram, Apple use it for petabyte-scale data.
• Riak: Distributed KV store designed for high availability. Used by Yahoo, LinkedIn.
• etcd: Distributed KV store for configuration and service discovery. Backbone of Kubernetes.
• FoundationDB: Apple's distributed KV store. Used by Apple Cloud, Snowflake.

Evolution of Key-Value Stores

1. Single-Node Hash Tables (1970s): In-memory hash maps. Fast but no persistence, no distribution.
2. Berkeley DB (1990s): Embedded key-value store with persistence. Single-node only.
3. Dynamo Paper (2007): Amazon's landmark paper on distributed KV store. Introduced consistent hashing, vector clocks, gossip protocol.
4. NoSQL Movement (2009+): Redis, Riak, Voldemort. Open-source distributed KV stores.
5. Managed Services (2012+): DynamoDB, Azure Cosmos DB, Google Firestore. Cloud-native, fully managed.
6. NewSQL/HTAP (2020+): TiKV, FoundationDB. KV stores with stronger consistency and transactions.

2. Real Interview Context

Designing a key-value store is one of the most fundamental system design questions. It tests core distributed systems concepts in a manageable scope.

Companies That Ask This Question

Skills Being Evaluated

• Data Partitioning: How to distribute data across nodes. Consistent hashing, range partitioning.
• Replication: How to replicate data for durability and availability. Leader-follower, quorum.
• Consistency: Tunable consistency levels. Strong vs. eventual consistency trade-offs.
• Conflict Resolution: What happens when concurrent writes conflict. Vector clocks, CRDTs, last-write-wins.
• Failure Handling: Gossip protocol, failure detection, hinted handoff, anti-entropy.
• Storage Engine: How data is stored on disk. LSM-tree vs. B-tree trade-offs.

Common Mistakes

1. Skip Partitioning: Designing a single-node store without discussing how to shard data.
2. Ignore Replication: Not discussing how data survives node failures.
3. Over-Engineer: Building a full SQL engine when only simple KV operations are needed.
4. Forget Conflict Resolution: Not discussing concurrent writes to the same key.
5. Ignore CAP Trade-offs: Not explicitly choosing between consistency and availability.

3. Functional Requirements

Core Operations (FR-01 to FR-10)

1. FR-01: Support put(key, value) — insert or update a key-value pair. Key is a string up to 256 bytes. Value is a binary blob up to 1 MB.
2. FR-02: Support get(key) — retrieve the value associated with a key. Return error if key does not exist.
3. FR-03: Support delete(key) — remove a key-value pair. Deletion is idempotent (deleting non-existent key is a no-op).
4. FR-04: Support getMany(keys[]) — batch get for multiple keys in a single request.
5. FR-05: Support putMany(kvpairs[]) — batch put for multiple key-value pairs atomically.
6. FR-06: Support conditional writes — put only if the current version matches expected version (optimistic concurrency).
7. FR-07: Support TTL (Time-To-Live) — keys automatically expire after a configurable duration.
8. FR-08: Support key prefix scanning — iterate over keys with a given prefix.
9. FR-09: Support range queries — retrieve all keys within a given range [start, end].
10. FR-10: Support atomic counters — increment/decrement a value atomically.

Data Management (FR-11 to FR-20)

11. FR-11: Support configurable consistency levels per request (ONE, QUORUM, ALL).
12. FR-12: Support data replication across multiple nodes for durability.
13. FR-13: Support partition-aware routing — client sends request to the node owning the partition.
14. FR-14: Support automatic partition rebalancing when nodes join or leave the cluster.
15. FR-15: Support data compression for values to reduce storage footprint.
16. FR-16: Support metadata (creation time, last modified, version) for each key-value pair.
17. FR-17: Support namespace/tenant isolation — different tenants cannot access each other's data.
18. FR-18: Support data backup and restore operations.
19. FR-19: Support monitoring and metrics for all operations (latency, throughput, errors).
20. FR-20: Support graceful shutdown — drain connections and flush data before stopping.

Advanced Features (FR-21 to FR-30)

21. FR-21: Support transactions — atomic read-modify-write operations on multiple keys.
22. FR-22: Support change data capture (CDC) — notify downstream systems of data changes.
23. FR-23: Support secondary indexes — query by non-key fields.
24. FR-24: Support data compaction to reclaim storage from deleted and overwritten entries.
25. FR-25: Support rate limiting per client to prevent abuse.
26. FR-26: Support audit logging for all write operations.
27. FR-27: Support encryption at rest and in transit.
28. FR-28: Support cross-datacenter replication for geo-distributed deployments.
29. FR-29: Support online schema migration — change value format without downtime.
30. FR-30: Support debug commands — inspect cluster state, partition ownership, node health.

4. Non-Functional Requirements

5. Requirement Prioritization

Must Have

• get, put, delete operations
• Data partitioning across nodes
• Replication for durability
• Consistent hashing for routing
• Failure detection and recovery
• Tunable consistency levels
• Automatic partition rebalancing

Should Have

• Conditional writes (optimistic concurrency)
• Batch operations (getMany, putMany)
• TTL support
• Conflict resolution (vector clocks or LWW)
• Gossip protocol for membership
• Hinted handoff for temporary failures

Nice to Have

• Atomic transactions across keys
• Secondary indexes
• Change data capture
• Cross-datacenter replication
• Range queries and prefix scans

Out of Scope

• Complex query language (JOINs, aggregations)
• Full-text search
• Graph traversal
• Multi-model support

6. Capacity Estimation

Assumptions

Storage Calculations

Throughput Calculations

Node Sizing

Consistent Hashing Ring

Infrastructure Summary