CSE Roadmap

Core tier · about 2 hours · 6 parts

Part 5 of 6 · 2 min read

What a key-value store gives up

The same narrow get-and-put model that makes partitioning easy also rules out secondary indexes, range scans across machines, and joins.

What a key-value store gives up

Think of that same cloakroom again. It is excellent at one job: returning a coat for its exact ticket number. It cannot answer "which coats are blue," since it never looked inside any of them, and no attendant maintains that list.

In plain words: the narrow get-and-put model is exactly what makes partitioning simple, but it also means a key-value store cannot natively search by a value's contents. Finding "every cart containing book 42" has no direct answer; the application would have to scan every cart itself. A key-value store also has no built-in concept of a join between two kinds of records. Any relationship between them has to be resolved in application code, by making a second lookup with a different key. Some key-value stores add secondary indexes as an extra feature, but this is not the core model, and it adds real implementation complexity.

A worked example. Finding the cart belonging to customer 501 is instant, since the customer ID is the key. Finding every cart that currently contains book 42, with no secondary index, has no efficient answer; every cart in the store would need to be fetched and checked individually.

The key lines. No SQL; the point is the absence of a query language capable of expressing "find by value," not a specific syntax.

Secondary index (absence, in a plain key-value store)

A secondary index lets a record be found by a field other than its primary key. A plain key-value store has no secondary index by default; it can only be looked up by the exact key used to store it, so searching by any other field requires either scanning every record, or an application-maintained second key-value mapping.

Example: a cloakroom unable to answer "which coats are blue," since nothing records that fact by coat, mirrors a plain key-value store's lack of a secondary index.

Remember this

A key-value store does exactly one thing well: get and put by an exact key. That narrowness is precisely what lets it partition across many machines and scale its throughput almost linearly. It gives up secondary indexes, cross-machine range scans, and joins in exchange. The next page covers graph databases, built for exactly the kind of connected data a key-value store handles worst.

Quick notes

  • A key-value store supports exactly two operations: put a value under a key, and get a value by that exact key.
  • An index, typically a hash map from key to location, turns a lookup from a full scan into a direct lookup.
  • Because every access names an exact key, a request can be routed to the one machine responsible for that key, which is why key-value data partitions easily.
  • A plain key-value store has no secondary index, no cross-machine range scan, and no joins; any of these must be built in application code if needed.
  • Some key-value stores are caching-only, accepting data loss on restart; others are durable, writing changes to disk or replicating them.