Key-Value Stores

Out of everything the marketplace asks its data, one question towers over the rest by sheer volume: "what's in user 8412's cart?" Ten thousand times a minute at lunch rush. Same shape every time — a known key in, one value out. No joins, no ranking, no cross-checking. And every time, your relational database dutifully parses the SQL, consults the planner, walks an index… to do what is conceptually a dictionary lookup.

The previous lesson showed you five gifts relational databases hand you for free. Here's the uncomfortable follow-up: for this question, you're not using any of them. You're just paying for them.

A key-value store is what you get when someone takes that observation completely seriously. It's the coat check of the database world: hand over your item, get a ticket; hand back the ticket, get your item — instantly, no questions asked. Literally no questions — ask the attendant for "all the black coats, size M" and watch the whole metaphor collapse: someone now has to walk every rack.

In this lesson: the simplest data model in existence, why subtraction is what buys planet-scale, the family's origin story (a shopping cart that was never allowed to fail), its two very different species, and the one failure mode every interviewer eventually asks about.

Scope: caching strategy — when to cache, eviction, invalidation — lives in Fundamentals' Caching section (Why Caching Wins onward); how a cluster rebalances when shards come and go is Consistent Hashing; Redis and DynamoDB each get a full internals deep-dive in Interview Mastery. This lesson is the family itself.

Here is the entire data model: a key (a string) maps to a value (bytes). And here is essentially the entire API:

That's it. No tables, no columns, no query language. The value is an opaque blob — the engine stores bytes and never parses them. It doesn't know your cart has items in it, doesn't know items have prices, can't check that quantities are positive. As the Stonebraker–Pavlo retrospective puts it: the DBMS "is unaware of its contents — it is up to the application to maintain the schema and parse the value."

Coming from the relational lesson, this should feel like walking out of a bank vault into an empty room. Every gift is handed back: no joins (nothing relates keys to each other), no constraints (the engine can't see inside values to check anything), no secondary access (you cannot ask "which carts contain dish 99?" — only "what's the value for this key"), no general multi-key transactions. Even the schema didn't disappear — it moved into your code, twice: your application parses the value's format, and your key naming convention (user:8412:cart, session:ab3f, flag:checkout-v2) is your schema now, enforced by nothing but team discipline.

Why would anyone accept this deal? Because the blindness isn't a missing feature. It's the entire product.

Follow the consequences of "every operation touches exactly one key," and the architecture falls out by itself.

If no operation ever spans two keys, then no two keys ever need to be on the same machine. So: hash the key, use the number to pick a machine, done. fnv1a("user:8412:cart") % 4 → shard 1. The "router" is one arithmetic expression — no coordinator to consult, no directory to look up, no planner to run. And a hash table sitting in RAM answers in about a hundred nanoseconds — you know from The Memory Hierarchy exactly why that number is unbeatable.

Now scale it. Need double the capacity? Add machines; keys spread across more shards; throughput grows linearly, because the shards never talk to each other. There's no clever engineering in the hot path to admire, and that's precisely the point — nothing coordinates, so nothing bottlenecks. Compare that with scaling the relational box, which you saw takes real engineering (Figma's proxy, Notion's 480 shards). Here, scale-out is the default posture, not a project.

This family has a founding document: Amazon's Dynamo paper (2007). Amazon had noticed that most of their services — carts, sessions, best-seller lists, preferences — "only need primary-key access to a data store," and that forcing those through a relational engine "would lead to inefficiencies and limit scale and availability." One requirement drove everything: the shopping cart must always accept writes. A customer mid-checkout during a datacenter failure still adds items; anything less costs real money. So they built a store around primary-key access and always-on writes, published the design, and accidentally founded a dynasty — Cassandra, Riak, and eventually DynamoDB all descend from that paper. (What Dynamo gave up to stay always-writable — and what "eventual" really means — is the whole drama of Replication & Consistency, one section ahead.)

"Key-value store" covers two kinds of systems that share an API and almost nothing else. Confusing them is the most common KV mistake in design interviews, so let's split them cleanly.

The RAM species — Memcached, Redis, and their fleets — lives entirely in memory and answers in microseconds. It expects to sit in front of a system of record, absorbing reads that would otherwise crush it. At Netflix, the EVCache tier serves about 400 million operations per second across 22,000 server instances holding roughly 2 trillion items (14.3 PB) — nearly every screen you see on Netflix is assembled from lookups like these. The deal: staggering speed, and if a node dies, you lost a cache — inconvenient, not catastrophic.

The durable species — DynamoDB and the Dynamo lineage — is a replicated, multi-node system of record. It answered 151 million requests per second at single-digit milliseconds during Prime Day 2025, and it wasn't caching anything: carts and orders live there. Same three-verb API, completely different promise — your write survives machine failures.

Redis deserves one extra sentence, because "Redis is just a cache" undersells the most-loved KV store on Earth (and the #5 most-used database overall). Redis is really a data-structures server: sorted sets that make leaderboards one command, streams that act as append-only logs, hashes, counters, pub/sub. But note the honest edge: with asynchronous replication and relaxed persistence settings, a bare Redis can lose acknowledged writes in a crash window — a fine trade for sessions and leaderboards, a terrible one for a ledger. If it must survive anything, use the durable species (or the relational lesson's family). Internals — the single-threaded event loop and why it's still that fast — wait in the Redis deep-dive.

Below is a KV cluster with a real hash router — the shard math is live FNV-1a, not an animation — next to a relational box with the previous lesson's gifts intact.

Do three things. First, edit the key — change 8412 to 8413 — and watch it re-route; that jump is the entire routing layer of a planet-scale cluster. Second, fire all six questions and read both sides' verdicts: GET is sublime, and then watch what "no secondary index," "no ORDER BY," and "no multi-key transaction" cost on foreign question shapes. Third, set 8 shards and fire the HOT KEY storm — then remember the number you see: one shard melting, seven idle.

The widget just showed you the family's signature failure, and it's worth naming carefully because it defies the intuition "more nodes = more capacity."

Hashing spreads keys evenly. It does not spread traffic. When one key goes viral — a celebrity's like counter, the homepage product, a config flag every request reads — every one of those million requests hashes to the same value, and lands on the same node. As one Redis engineering writeup puts it: "even if the cluster has 100 nodes, one key still maps to one node." That node saturates (Redis processes commands on a single thread — an increment storm simply outruns it) while its 99 neighbors sit idle. On DynamoDB the same shape appears as a table that throttles at a fraction of its provisioned capacity — the console shows errors, the graphs flatline, and the culprit is one overworked partition key.

The escape hatches all share one idea — make the hot thing plural. Split the key (post:123:likes:0 through :9, each on a different shard; sum on read). Cache the ultra-hot value locally in the application for a second. Or let the platform do it — DynamoDB's split-for-heat automatically divides a hot partition's key range. The deep treatment (including hot shards that aren't single keys) is Resharding & Hot Shards.

And one honest note from the widget: the hot row hurt the SQL box too. Concentrated traffic is a traffic-shape problem, not a family problem — the difference is that KV clusters are usually the ones big enough to meet it.

The decision, stated the way you'd defend it in a review.

Reach for a KV store when the access pattern is genuinely key-shaped at volume. Sessions (Stateful vs Stateless taught you why they get externalized — the store they're externalized to is this family), carts, feature flags, rate-limit counters, presence, and the classic cache-in-front-of-the-database. These workloads ask the one question this family answers better than anything on the map — and they're exactly what Dynamo was built for.

Don't reach for it when the questions vary. The moment you need "orders by restaurant," "top dishes by revenue," or "order and stock move together," you're either scanning every shard, hand-maintaining reverse indexes in application code, or reinventing transactions — badly. The 2024 Stonebraker–Pavlo retrospective is blunt about where that road ends: with no secondary indexes, applications "must implement joins... in the application," and "a RDBMS may be a better choice, even for simple applications, because they offer a path forward if the application's complexity increases." That's the same evidence-based rule from One Size Fits None, pointed at this family.

And calibrate the speed claim. A Postgres point lookup is a millisecond or two; at moderate scale, "we needed microseconds" is usually "we wanted microseconds." The KV store earns its slot when the key-shaped question comes at a volume — or with an availability requirement — the default can't meet. The full six-question checklist is SQL vs NoSQL: The Decision Rubric.

You're introducing a KV tier to the marketplace. Six candidate workloads landed on your desk. For each: in or out — and if in, design the key. Commit before scrolling.

1. Logged-in session state (who's logged in, device, expiry).
2. The cart.
3. Per-user API rate-limit counters (100 requests/minute).
4. "Show me every order from restaurant 7 last month."
5. The checkout-v2 feature flag, read by every request.
6. The payments ledger.

Answers. (1) In — session:<token>, TTL = expiry; the textbook case. (2) In — user:8412:cart; exactly Dynamo's founding workload — use the durable species if an empty cart costs money, the RAM species if the DB behind it holds truth. (3) In — ratelimit:user:8412:2026-07-12T14:31, TTL 60s; counters by key are a KV superpower (you met this design in Rate Limiting). (4) Out — that's secondary access; it needs an index on restaurant_id, which means the relational store (or hand-built reverse indexes you'll regret). (5) In, carefully — flag:checkout-v2 is the textbook hot key: every request reads it. Cache it in-process for a few seconds, or you've built the melting shard from the widget. (6) Out, emphatically — a ledger needs multi-row transactions and audit-grade durability: the relational lesson's whole job.

Notice what you just did in answers 1–5: you wrote the schema. It's just spelled in colons now.

• "KV stores are just caches." DynamoDB held Amazon's carts and orders at 151M requests/second on Prime Day — as the system of record. The family has two species: the RAM tier that may forget, and the durable tier that must not. Know which one you're talking about.
• "Redis is just a cache." It's a data-structures server — sorted sets, streams, counters, pub/sub — powering leaderboards and queues, not just lookups. The honest caveat cuts the other way: bare Redis's replication and persistence windows mean acknowledged writes can vanish in a crash — so it's also not a ledger.
• "KV is always faster than SQL." At the key-shaped question: yes, and it stays fast at any scale. At every other question: it's the slowest engine you can buy, because you are the query planner now. And a relational point lookup is ~1 ms — at moderate scale the difference is often academic (the 2024 retrospective: modern RDBMSs "can generally equal or beat" KV stores).
• "KV means no schema." Third lesson in a row, same truth: the schema moved — into your value-parsing code and your key naming conventions. user:8412:cart is a schema; it's just enforced by code review instead of the engine.
• "100 nodes = 100× capacity." For a million different keys, roughly. For one viral key: one node, always — hashing spreads keys, not traffic. The fix is making the hot thing plural (key-splitting), not adding node 101.
• "KV stores can't do transactions." Nuance: single-key operations are atomic everywhere; DynamoDB added multi-item transactions and Redis has MULTI — real but narrow and priced. Notice the pattern from One Size Fits None: every family slowly grows the features it swore it didn't need. Identities, not walls.

• The model is a dictionary with three verbs — GET/SET/DELETE by key — and the value is an opaque blob the engine never parses. That blindness is the product, not a gap.
• Because no operation spans keys, routing is just hash(key) % shards — no coordination anywhere in the hot path — so capacity scales linearly by adding machines. Subtraction is the architecture.
• Born at Amazon (Dynamo, 2007) because carts had to accept writes through any failure and most services only asked by primary key. Lineage: Cassandra, Riak, DynamoDB.
• Two species, one API: RAM-tier cache-speed (Memcached/Redis — Netflix's EVCache: 400M ops/s, ~2T items) and durable systems of record (DynamoDB: 151M req/s, single-digit ms, Prime Day 2025). Losing a cache is inconvenient; the durable species must never lose your cart.
• The signature failure: hashing spreads keys, not traffic — one viral key lives on one node no matter the cluster size. Fix by making the hot thing plural (key-splitting, local caching, split-for-heat).
• Choose it when access is truly key-shaped at volume (sessions, carts, flags, counters, cache tiers); walk away the moment questions vary — secondary access and multi-key transactions are the relational lesson's turf, and Postgres point lookups are already ~1 ms.
• Next: keep the key, but let the engine finally see inside the value — that single change creates an entire family: Document Databases.