Key-value stores - System Design Guide

Overview

A key-value store is the simplest database model: store a value under a key, and get it back by that key. There are no joins or complex queries, which makes key-value stores extremely fast and easy to scale horizontally by partitioning keys across nodes, typically with consistent hashing.

They power caches (Redis, Memcached), session stores, feature flags, shopping carts, and the storage layer of many larger systems. 'Design a distributed key-value store' is a classic interview question covering partitioning, replication, consistency, and failure handling.

Lockers at a train station

Each locker has a number (key) and holds a bag (value). You can put a bag in or take it out instantly if you know the number, but you cannot ask 'which lockers contain red bags?'.

When to use it

Access is always by a known key.
Very low latency and very high throughput.
Caching, sessions, counters, feature flags, carts.
As a building block inside larger systems.

Where it shows up in interviews

Design a key-value store

Recognize it when: build a distributed, highly available store.

Design DynamoDB
Design a distributed cache

Key-based lookups

Recognize it when: session, cart, profile by ID at massive scale.

Design a session service
Design a URL shortener's storage

Where it is used in real software

Amazon Dynamo

The 2007 Dynamo paper introduced consistent hashing with virtual nodes, sloppy quorums, hinted handoff, and vector clocks; it influenced Cassandra, Riak, and DynamoDB.

etcd

A strongly consistent key-value store using Raft; Kubernetes stores all cluster state in it.

RocksDB

An embedded key-value engine using LSM trees, used inside MySQL (MyRocks), Kafka Streams, and CockroachDB.

Key terms

get / put / delete: The core operations.
Partitioning: Spreading keys across nodes, often with consistent hashing.
Replication factor: How many nodes store each key (often 3).
Quorum: R + W > N reads and writes for consistency.
LSM tree: Write-optimized storage: memtable, sorted files, compaction.

Designing a distributed key-value store

1
API
get(key), put(key, value), delete(key); values up to a size limit.
2
Partition
Consistent hashing with virtual nodes spreads keys evenly.
3
Replicate
Store each key on N consecutive nodes on the ring.
4
Tune consistency
Choose R and W per request; R + W > N for strong reads.
5
Handle failures
Hinted handoff for temporary failures, anti-entropy (Merkle trees) to repair replicas.
6
Storage engine
LSM trees for fast writes, with bloom filters to speed up reads.

Key-value store trade-offs

Popular options

Store	Consistency	Persistence	Typical use
Redis	Primary-replica, async	Optional (RDB / AOF)	Cache, sessions, counters, queues
Memcached	None (no replication)	No	Simple cache
DynamoDB	Eventual or strong per read	Yes	Serverless app data at scale
etcd / ZooKeeper	Strong (consensus)	Yes	Config, coordination, leader election

NOWStore: Redis | Consistency: Primary-replica, async | Persistence: Optional (RDB / AOF) | Typical use: Cache, sessions, counters, queues

Pick by durability and consistency needs: a cache can lose data; coordination data cannot.

Implementation

1SET session:abc123 '{"userId":42}' EX 1800   # value with 30-minute TTL2GET session:abc1233INCR page:views:home                          # atomic counter4HSET cart:42 sku-1 2 sku-7 1                  # hash as a small document5HGETALL cart:426DEL cart:42

Complexity and performance

get / putO(1) average

Sub-millisecond in memory stores.

Redis throughput~100k+ ops/s per node

Single-threaded command execution.

Trade-offs

Simplicity vs query power

No secondary queries without extra indexes; you trade flexibility for speed and scale.

Memory vs disk

In-memory stores are fastest but limited and costly; disk-based stores hold far more data.

Variants and related techniques

Ordered key-value stores

Keys kept sorted (Bigtable, RocksDB) enable range scans by prefix.

Embedded stores

RocksDB and LevelDB run inside the application process.

Common mistakes

Huge values.
Fix: Keep values small (KBs); store large blobs in object storage and keep a pointer.
Hot keys.
Fix: Replicate or split hot keys; cache locally.
Treating a cache as durable storage.
Fix: Know the persistence guarantees of your store.

Interview questions

How would you design a distributed key-value store?

Partition keys with consistent hashing and virtual nodes, replicate each key to N nodes, use tunable quorums for consistency, detect failures with gossip, handle temporary failures with hinted handoff, repair with Merkle trees, and store data in an LSM-tree engine.

How do you resolve conflicting writes in an eventually consistent store?

Last-write-wins with timestamps (simple, may lose updates), vector clocks with application-level merge, or CRDTs that merge automatically.

Practice problems

Problem	Difficulty	What it trains
Implement an in-memory KV store with TTL	Easy	Expiry.
Design a distributed key-value store	Hard	Partitioning, replication, repair.