Key-value stores and their sweet spot

15 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

A key-value store offers the smallest useful database API: get(key), put(key, value), delete(key), sometimes with compare-and-set and expiry. The value is opaque bytes; the store never looks inside.
Giving up queries on anything but the key buys predictable latency, simple partitioning and easy replication, which is why key-value stores sit under caches, session stores, config systems and many larger databases.
The first engine question is hashed or ordered. A hash index answers point lookups in one step but cannot scan a range; an ordered index (B+ tree or LSM tree) supports prefix and range scans, which turns key design into schema design.
The second is where the data lives: in memory (Redis, Memcached), in an embedded engine on local disk (RocksDB, LMDB, bbolt, Bitcask), or in a distributed service (DynamoDB, etcd, FoundationDB) that adds partitioning, replication and a consistency model.
Everything you would otherwise get from a query planner (secondary lookups, aggregates, joins) becomes your job, done by writing extra keys.

How it works

The narrow contract

The API is a map from short byte-string keys to values from a counter to a few hundred kilobytes. Because the store never interprets the value, it can place any key on any machine by hashing it, replicate it blindly, and serve it at the same cost every time. This is the "finding things fast" problem shape in its purest form. It also shows up as a DNS resolver's cache, Git's content-addressed object database, and an LLM server's prefix cache keyed by a hash of the prompt tokens.

Hashed versus ordered

A hash store (Memcached, the Redis keyspace, Bitcask) maps each key to a slot. Lookups are O(1), but keys sit in no useful order, so "every key starting with user:42:" means scanning everything. An ordered store (RocksDB, LMDB, bbolt, etcd, FoundationDB, DynamoDB's sort key) keeps keys sorted, so a prefix or range is one seek followed by a sequential read. Ordered stores let you build structure into the key: order/2026-10-16/000187 makes "today's orders" a range scan, and FoundationDB's tuple layer encodes (tenant, table, id) into bytes that sort the way the tuple does (FoundationDB docs).

Key design is the schema

With no secondary indexes, every access pattern needs a key that answers it. To look a user up by email as well as by id, you write two keys, user/id/42 holding the record and user/email/ana@x.io holding 42, and you are now responsible for keeping them consistent. The Indexing lesson shows the database doing this for you; here you do it by hand, ideally in one transaction or with a repair job. Hot keys are the other half of key design: a key that receives a large share of traffic lands on one partition no matter how many you have (see Hot Keys).

Families of stores

In-memory stores trade durability for sub-millisecond latency (see Redis). Check the licence as well as the engine: Redis moved to source-available licences in 2024, the Linux Foundation forked Valkey from Redis 7.2.4 under BSD (Linux Foundation), and Redis 8 added AGPLv3 as an option (Redis). Embedded engines are libraries: RocksDB is an LSM tree (see LSM Trees), LMDB and bbolt are copy-on-write B+ trees read through mmap (bbolt README), and Bitcask is a log plus an in-memory hash table. Distributed stores partition and replicate the keyspace: DynamoDB with per-partition leaders, etcd with Raft over one small keyspace, Dynamo-style systems with leaderless quorums (see Design a Key-Value Store). Many richer databases are key-value stores underneath: CockroachDB and TiKV map SQL rows onto ordered keys.

Conditional writes

A plain put loses updates when two clients read, modify and write the same key. Every serious store therefore offers a compare-and-set: Redis WATCH with MULTI/EXEC or SET key value NX, DynamoDB's ConditionExpression, etcd transactions that compare a key's mod_revision. This is the contention problem shape, solved by optimistic concurrency on a single key.

Down the stack

Layer 1The contract

Per key, a store promises either linearizability (etcd, FoundationDB, DynamoDB strongly consistent reads: a read returns the latest acknowledged write) or eventual consistency (Dynamo-style stores, DynamoDB's default reads, Redis replicas: a read may return an older value for a while). Durability is a separate dial: Memcached promises none, Redis with appendfsync everysec, the default AOF policy, may lose about one second of writes on a crash (Redis docs), and etcd acknowledges only after a majority of members have the entry on disk. Limits are part of the contract: DynamoDB items are capped at 400 KB, etcd requests at 1.5 MiB with a 2 GiB default storage quota and a suggested maximum of 8 GiB (etcd docs), and Redis strings at 512 MB. Multi-key atomicity is never free: absent, limited to keys on one shard (Redis Cluster hash tags, cluster spec), or a transaction with a size cap (100 items and 4 MB in DynamoDB, AWS docs).

Layer 2The mechanism

Bitcask, Riak's original engine, is the simplest durable design. Every write appends a record to the active data file: CRC, timestamp, key size, value size, key, value; a delete appends a tombstone. An in-memory hash table, the keydir, maps each key to (file_id, value_sz, value_pos, tstamp) of its latest record, so a read is one hash lookup and one disk read (Bitcask paper). A background merge rewrites only live records into new files, plus a hint file of keys and positions so a restart rebuilds the keydir without reading values. On startup, a record whose CRC does not match is a torn write from a crash, and the tail after it is discarded.

LMDB and bbolt keep one file holding a B+ tree, updated copy-on-write: a write transaction writes changed pages to free space, then flips a meta page to the new root. Readers keep the old root and never block; there is one writer at a time, and old pages cannot be reused while a long read transaction still holds them, so a stuck reader makes the file grow. etcd stores every revision of every key in bbolt, keyed by revision number, with an in-memory B-tree from user keys to revisions, which is how it serves watches and historical reads (etcd docs).

Layer 3The machine

An in-memory hash lookup costs about 100 ns, mostly one or two cache misses. Over the network the same GET costs a datacenter round trip of 100 to 500 µs, which is why Redis clients pipeline: 100 commands share one round trip and one read/write syscall pair. An NVMe SSD serves a 4 KB random read in roughly 10 to 100 µs, so Bitcask's one read per get is fast while the keydir fits in RAM; at the key plus a few dozen bytes per entry, 500 million keys need tens of gigabytes.

Writes hit the log sequentially, and durability is decided by fsync: a millisecond or more on a consumer SSD, tens of microseconds on drives with power-loss protection. Stores batch many writes per fsync (group commit). LMDB maps its file with mmap, so a cold read is a page fault and its cache is the OS page cache.

Why it's built this way

Most hot data is fetched by an exact identifier, so a structure that answers only that question can be faster and simpler than a general query engine.
Random writes are slow and sequential appends are fast on every medium, so durable engines log first (Bitcask, LSM) or copy-on-write (LMDB) instead of updating in place.
Logs accumulate dead records, so engines merge or compact in the background, and must checksum records because a crash can tear the last write.
An opaque value with a hashable key can live anywhere, so partitioning and replication are mechanical; the price is that every other access path must be a key you maintain.

Diagram

flowchart LR
  P["put(k, v)"] --> L["Append record: crc, key, value"]
  L --> K["keydir: k to offset"]
  G["get(k)"] --> K
  K --> R["One read at offset"]
  D["delete(k)"] --> T["Append tombstone, drop from keydir"]
  M["merge"] --> N["New log: live records only"]
  N --> K
  C["Crash restart"] --> S["Scan log, stop at bad CRC"]
  S --> K

Worked example

A login service keeps 40 million active sessions. Each key is sess: plus a 32-character token (37 bytes) and each value is about 300 bytes of JSON. Traffic is 60,000 reads and 4,000 writes a second, with a 30-day sliding expiry.

In Redis, each key costs key and value plus roughly 50 to 80 bytes for the dictionary entry, object header and expiry, about 420 bytes. 40 million sessions need about 17 GB: three shards of about 6 GB leave room for replication buffers and snapshot forks, and 64,000 operations a second is light for three shards.

On a Bitcask-style disk store, the keydir holds 37 bytes of key plus about 40 bytes of overhead per entry, about 3 GB of RAM, and the values live on SSD: 40 million times 340 bytes is 14 GB of live data. With 4,000 writes a second and sessions updated on activity, the log grows by about 1.4 MB a second, around 117 GB a day, almost all of it garbage. Merging when dead bytes exceed 50% of a file keeps disk usage near 30 GB and costs a steady background read and write stream.

Sessions are a natural key-value fit. The trap arrives when someone asks for "all sessions for user 42" to log a user out everywhere. With only token keys, that is a full scan. The fix is a second key per user, user_sess:42, holding a set of tokens, updated in the same transaction as the session itself.

In the wild

Jepsen, 2020: etcd's key-value operations are safe, its locks are not. Under partitions, pauses, clock skew and membership changes, etcd 3.4.3's reads and writes were strict serializable. Its lock API did not give mutual exclusion: with 2-second lease TTLs and process pauses, lock-protected updates lost about 18% of acknowledged writes. The advice: use such locks for efficiency, and have the protected resource check a fencing token such as the key's revision (Jepsen).
Roblox, 2021: a 73-hour outage inside a key-value store. Every backend service, and monitoring, depended on one Consul cluster. A newly enabled streaming feature caused contention under heavy load, and Consul's BoltDB Raft log had a freelist of nearly a million page IDs (about 7.8 MB) that was rewritten on every append, slowing the leader. The fixes included a planned move to bbolt, cleaning obsolete keys, and separate Consul clusters (Roblox).
Cloudflare, 2025: a "coreless" KV with a central dependency. Workers KV served from edge caches but relied on a central source-of-truth store, part of which ran on a third-party cloud that had an outage. About 90% of KV requests failed for roughly 2.5 hours, taking Access logins, WARP and other products with it; Cloudflare is building tooling to re-enable namespaces progressively during storage incidents (Cloudflare).

Trade-offs

Option	Strengths	Weaknesses	Choose when
In-memory hash (Memcached, Redis)	Sub-millisecond, simple, rich types in Redis	RAM cost, weak durability by default	Caches, sessions, counters, rate limits
Log plus hash index (Bitcask)	One disk read per get, sequential writes, simple recovery	All keys must fit in RAM, no range scans	Many writes, point lookups, moderate key count
LSM tree (RocksDB)	High write throughput, ordered, compresses well	Read and write amplification, compaction tuning	Write-heavy embedded storage, engines under databases
Copy-on-write B+ tree (LMDB, bbolt)	Fast lock-free reads, crash-safe without a log	One writer, write amplification on random updates	Read-heavy embedded data, config and metadata
Distributed service (DynamoDB, etcd)	Replication, failover and scaling handled for you	Network latency, item and request limits, cost per request	Shared state across services and regions

Pitfalls in production

Scanning a hash keyspace. KEYS * in Redis is O(N) and blocks the single thread while it walks every key; Redis's own docs warn against it in application code (Redis docs). Use SCAN with a cursor, and better, keep an explicit index key for any set you need to enumerate.
Lost updates. Read, modify, write without a condition loses concurrent changes. Use compare-and-set, an atomic server-side operation (INCR, HINCRBY) or a version check.
Large values. A 5 MB value blocks a Redis shard for milliseconds on every read and inflates replication. Split large values into chunks or store them in object storage and keep a pointer.
Unbounded growth. Keys written without expiry accumulate until memory or disk runs out, and etcd stops accepting writes when it hits its storage quota. Set TTLs, compact old revisions, and alert on keyspace growth.
Hand-made indexes that drift. A secondary key written in a separate request will eventually disagree with the primary record. Write both atomically, or run a periodic repair that rebuilds the index from the source keys.

Leadership lens

Before approving a key-value store, ask for the list of access patterns and the key that serves each one; if any pattern needs a scan, the store is the wrong choice or the design needs an extra key.
Decide durability explicitly: "it's a cache" and "it holds the only copy of the sessions" lead to different persistence settings, replication and on-call expectations.
In managed stores, a hot key or an accidental scan shows up first as throttling and on the invoice; review key design with cost in mind.
Keep etcd and similar coordination stores for small, critical metadata, owned by the platform team, and push application data elsewhere.

Check yourself

Why can Bitcask serve any get with a single disk read, and what limits how much data it can hold?
Show answer
The in-memory keydir gives the exact file and offset of the latest value, so the read goes straight there. Every key must fit in RAM, so key count, not value size, sets the limit.
You need "all orders for customer 42 in the last week". What does each kind of store require?
Show answer
An ordered store can hold keys like cust/42/order/2026-10-16/... and answer with one prefix range scan. A hash store needs an extra key per customer listing order ids, maintained on every write.
Why must a log-structured store checksum every record?
Show answer
A crash can leave the last record partly written. Without a checksum, recovery would load garbage as a valid value; with one, it detects the torn record and discards the tail.
Two workers increment the same counter with get then put. What goes wrong and what are the fixes?
Show answer
Both read 10 and both write 11, losing an increment. Use an atomic server-side increment or a compare-and-set that retries when the value changed.

Sources and further study

Primary

Zhou et al., FoundationDB: A Distributed Unbundled Transactional Key Value Store (SIGMOD 2021): an ordered, strictly serializable key-value core with everything else built as layers on top.
Nishtala et al., Scaling Memcache at Facebook (NSDI 2013): leases, regional pools and commit-log invalidation around a plain in-memory key-value store.
Jepsen: etcd 3.4.3: what a linearizable key-value store does and does not guarantee once you build locks on it.

Systems docs

etcd: system limits: request size, storage quota and why the database should stay small.
bbolt README: copy-on-write B+ tree, one writer, mmap caching and the costs of long read transactions.
Redis cluster specification: 16,384 hash slots, hash tags and which multi-key operations a cluster allows.

Books

Database Internals, Alex Petrov, Ch 6 "B-Tree Variants" and Ch 7 "Log-Structured Storage": copy-on-write B-trees as in LMDB, and Bitcask-style unordered log storage.
System Design Interview, Volume 1, Alex Xu, Ch 6 "Design A Key-value Store": the distributed side, with partitioning, quorums and anti-entropy.

Other curricula

donnemartin/system-design-primer: describes a key-value store with the abstraction "hash table", noting that some keep keys sorted for range reads and that complexity moves to the application.
Azure Architecture Center: Understand data models: points out that most key-value stores overwrite the whole value on change and that value-based lookups need a redesign.
roadmap.sh: System Design: its "Key-Value Store" node is a one-paragraph definition naming Redis and DynamoDB for caching and sessions.

Watch

F2023 #07 - Hash Tables (CMU Database Group): the hashing schemes inside key-value engines, including how they resize and handle collisions.
RocksDB: A High Performance Embedded Key-Value Store for Flash Storage (Meta Developers): Dhruba Borthakur on why RocksDB was built and how it uses flash.
Amazon DynamoDB Under the Hood (AWS re:Invent 2018): request routing, partitions and replication in a distributed key-value service.

Free resources

Bitcask: A Log-Structured Hash Table for Fast Key/Value Data: the short paper behind this lesson's Practice, including the record format, keydir and hint files.
Dynamo: Amazon's Highly Available Key-value Store: the paper that defined leaderless, eventually consistent key-value stores.
RocksDB Overview: the architecture of the most widely embedded ordered key-value engine.
etcd: data model: revisions, MVCC and how etcd stores history on top of bbolt.
FoundationDB: data modeling: how to build tuples, indexes and richer models on an ordered key-value store.
Redis persistence: RDB snapshots, AOF and the durability each fsync policy gives.

Open in the interactive app: practice, quiz, mock interview →