Key-Value and Document Stores

A key-value store maps a unique key to a value and supports lookup, write, and delete by key. A document store is a key-value store whose values are structured documents (usually JSON or a binary encoding such as BSON) that the database can inspect, index, and partially update. Both families give up general joins and ad hoc querying in exchange for simple, predictable access paths that partition and scale horizontally.

Key-value stores

The core interface is get(key), put(key, value), and delete(key). The store treats the value as opaque bytes or as a small set of typed structures. Lookup by key is a single-partition operation, so latency and throughput scale with the number of partitions.

Two designs dominate.

In-memory stores (Redis, Memcached)

Data is held in RAM, giving sub-millisecond latency. Redis values can be strings, lists, hashes, sets, sorted sets, streams, and other types, each with type-specific operations executed on the server (for example ZADD and ZRANGE on a sorted set, INCR on a counter). Durability is optional and is provided by snapshots and an append-only log. Typical uses: caching, sessions, counters, rate limiting, leaderboards, and queues. See Redis and Memcached.

Durable, partitioned stores (DynamoDB, Riak, etcd)

DynamoDB is a managed store built on Dynamo-style ideas: partitioned by hash of the partition key, replicated across availability zones, with single-digit-millisecond reads and writes at any scale when access is well distributed. etcd is a small, strongly consistent key-value store based on Raft, used for configuration and coordination rather than bulk data.

DynamoDB data model

• A table holds items (rows). Items in a table need not share attributes beyond the key.
• The primary key is either a partition key alone, or a partition key plus a sort key. The partition key is hashed to choose the partition. Within a partition, items are stored ordered by sort key.
• Queries with a partition key and a sort key condition (=, <, between, begins_with) read one contiguous range from one partition.
• A local secondary index (LSI) offers an alternative sort key within the same partition key. A global secondary index (GSI) has its own partition and sort key, is updated asynchronously, and supports eventually consistent reads only.
• Reads are eventually consistent by default; a strongly consistent read can be requested on the base table.
• A Scan reads the whole table and is used for exceptional cases only.
• An item is limited to 400 KB, so large payloads are stored elsewhere (for example in object storage) with a reference in the item.
• An LSI must be defined when the table is created. A GSI can be added later. In the diagram below, a query for all orders with status = "shipped" uses the GSI, because the base table can be queried efficiently only by customer_id.

erDiagram
    ORDERS {
        string customer_id "partition key"
        string order_ts_id "sort key"
        string status
        number total
    }
    ORDERS_BY_STATUS_GSI {
        string status "GSI partition key"
        string order_ts_id "GSI sort key"
    }
    ORDERS ||--o{ ORDERS_BY_STATUS_GSI : "projects into"

Single-table design

Since there are no joins, items of different entity types that are read together are stored in one table with a shared partition key and distinguishing sort keys:

One query with PK = CUSTOMER#42 and SK begins_with ORDER# returns all the customer's orders in time order, from a single partition, in one request.

Document stores

MongoDB stores documents in collections. Documents in one collection may have different fields (schema-flexible), and a document can contain nested objects and arrays.

{
  "_id": "order-1001",
  "customer_id": 42,
  "status": "shipped",
  "items": [
    { "sku": "A-1", "qty": 2, "price": 9.5 },
    { "sku": "B-7", "qty": 1, "price": 30.0 }
  ],
  "shipping": { "city": "Oslo", "country": "NO" }
}

Characteristics:

• Locality. Data read together is stored together, so a read fetches the order and its items in one operation without a join.
• Rich queries. Queries can filter on any field, including nested and array fields, and use secondary indexes (single field, compound, multikey, text, geospatial).
• Partial updates. Individual fields can be updated in place with operators such as $set and $inc.
• Atomicity. Updates to a single document are atomic. Multi-document transactions exist in MongoDB but are costlier, and the document model encourages designs that avoid them.
• Size limits. A document has a maximum size (16 MB in MongoDB), so unbounded arrays inside a document are a design error.
• Scaling. MongoDB shards a collection by a shard key (hashed or ranged) and replicates each shard as a replica set with one primary. See sharding and partitioning and replication.

Access-pattern-driven design

Relational design starts from entities and normalizes them, then queries are written later. Key-value and document design starts from access patterns: the list of queries the application performs, with frequency and latency needs. The schema is shaped to answer each one from a single partition or a single document.

Process:

1. List the queries: "get order by ID", "list a customer's orders newest first", "list orders by status".
2. Choose the partition key that is present in the most frequent and latency-sensitive queries.
3. Choose sort keys so results arrive in the required order.
4. Add secondary indexes for the remaining queries, accepting their write cost.
5. Duplicate data where it removes a lookup (see data modeling and denormalization).

Changing access patterns later is expensive because the layout is tuned to the old ones. This is the main cost of the model.

Partition key design

A partition key must satisfy two goals that conflict in practice.

• High cardinality and even distribution, so no partition receives a disproportionate share of data or requests.
• Query alignment, so the common queries name the key.

Failure modes:

DynamoDB throttles requests to a partition that exceeds its per-partition throughput limit, so an uneven key shows up as throttling even when the table's total provisioned capacity is unused.

Comparison

For background on the wider decision, see SQL vs NoSQL.

When to use and when not to

Use a key-value or document store when:

• Access is dominated by lookups on a known key or by a small number of well-known queries.
• Data has a natural aggregate boundary (an order with its lines, a user profile) that is read and written as a unit.
• The workload needs horizontal scaling and low latency at high volume.
• The schema varies between records or changes frequently.

Avoid when:

• Queries are unpredictable or analytic, requiring joins and aggregations across entities.
• Many-to-many relationships are central and must be traversed in several directions.
• Strong multi-entity transactional guarantees are required on the hot path.

Interview questions

• Why must you know the access patterns before designing a DynamoDB table? The partition and sort keys determine the only efficient queries. Other lookups need a secondary index or a scan, and reshaping the key later means rewriting the data.
• When should you embed data in a document rather than reference it? Embed when the data is read with the parent, is bounded in size, and is owned by the parent. Reference when the data is large, unbounded, shared between parents, or updated independently.
• What is a hot partition and how is it avoided? A hot partition receives disproportionate requests because of a skewed key. Avoid it with a high-cardinality key, write sharding of hot keys, and caching hot reads.
• Why can a DynamoDB global secondary index return stale data? It is maintained asynchronously from the base table, so a read after a write can precede the index update. Only eventually consistent reads are offered on it.