Key-Value Store

A key-value store must support point lookups by primary key in constant time, range queries within a partition, and horizontal scaling by adding partitions as data grows. DynamoDB extends the basic model with transactions, streams, and global replication.

DynamoDB handles trillions of requests per day across all AWS customers. For a single large table, these are representative numbers. The key insight: scale is achieved by adding partitions, not by making individual nodes faster.

DynamoDB's API is intentionally narrow -- no arbitrary SQL, no joins, no aggregations. Every operation targets a specific partition key, which guarantees the router can send the request to exactly one partition in O(1). This constraint is what enables single-digit ms latency at any scale. The exception is Scan, which touches every partition and should never be used on the hot path.

Three layers: request router (stateless fleet, caches partition map), partition map (consistent hash ring mapping key ranges to virtual nodes to physical storage nodes), storage nodes (leader + 2 replicas each running an LSM tree engine). The request router is the only component the client talks to -- it abstracts the entire distributed system behind a simple API.

A separate control plane runs alongside: the auto-admin service monitors throughput and triggers partition split/merge operations; the global table replicator reads from DynamoDB Streams and writes to remote regions; CloudWatch collects per-partition metrics for adaptive capacity decisions.

(a) Request Routing. The client SDK sends a request to a stateless request router (a fleet of lightweight proxies behind a load balancer). The router computes hash(partition_key) -- typically MD5 or a similar uniform hash -- and looks up the consistent hash ring to find the virtual node (vnode) that owns that key range. Each physical storage node owns multiple vnodes (typically 100-200), which ensures even distribution even when node counts change. The router maps the vnode to a physical node's address and forwards the request.

The router caches the partition map in memory for fast lookups. If the map is stale (partition was split, moved, or a new leader was elected), the storage node returns a MOVED-like redirect containing the new owner's address. The router updates its local cache and retries the request transparently -- the client never sees the redirect. This is similar to Redis Cluster's MOVED/ASK protocol.

(b) LSM Storage Engine. Every write goes to two places simultaneously: an append-only Write-Ahead Log (WAL) on disk for durability, and an in-memory sorted buffer called the memtable (typically a red-black tree or skip list). When the memtable reaches a size threshold (~64 MB), it is flushed as an immutable SSTable (Sorted String Table) to disk. Background compaction merges multiple SSTables to reclaim space and reduce read amplification. Each SSTable has a Bloom filter -- a probabilistic data structure that tells you "definitely not here" in O(1), avoiding unnecessary disk reads.

-- Write path (simplified):
1. Append to WAL (sequential disk write, ~0.1 ms)
2. Insert into memtable (in-memory, ~0.01 ms)
3. Ack to client (total: ~0.1 ms)
-- Background:
4. When memtable full -> flush to SSTable on disk
5. Compaction merges SSTables (leveled or size-tiered)

-- Read path (simplified):
1. Check memtable (in-memory, ~0.01 ms)
2. If not found, check each SSTable level:
   a. Query Bloom filter -> "definitely not here" (skip) or "maybe here"
   b. If maybe here, binary search SSTable index -> read data block
3. Return first match (newest version wins)
-- Bloom filter: ~10 bits per key, < 1% false positive rate
-- Typical read touches 1-2 SSTables thanks to Bloom filters

(c) Replication. Each partition has a leader and 2 followers, each in a different Availability Zone. All writes are directed to the leader, which writes locally and then replicates to both followers. A write is acknowledged when 2 of 3 nodes (quorum) confirm -- this ensures durability even if one entire AZ fails. The math: W=2, R=2, N=3. Since W+R > N (4 > 3), any read quorum overlaps with the write quorum, guaranteeing the latest value is always seen by strong reads.

Strong-consistency reads are served by the leader only -- guaranteed to return the most recent write. Eventually-consistent reads (the default, 50% cheaper in RCU) can be served by any replica. Replication lag is typically under 100 ms but can spike during leader elections or network partitions.

(d) Auto-Scaling. The auto-admin service monitors per-partition throughput via CloudWatch metrics. When a partition exceeds its throughput limit, it is split into two partitions (key range bisected). Cold partitions below a threshold are merged. Adaptive capacity goes further: if partition A uses only 200 of its 1000 WCU, and partition B is throttled at 1000 WCU, the system borrows 800 WCU from A and gives it to B -- no user action needed.

(e) DynamoDB Streams (CDC). Every write to the base table produces a time-ordered stream record containing the old and new item images. Stream records are organized by partition and retained for 24 hours. Consumers (Lambda, Kinesis Data Streams) process records in order per partition key. This enables: materialized view updates, cross-region replication for global tables, event-driven architectures, and real-time analytics pipelines -- all without polling the table.

(f) Global Tables. Multi-region active-active replication. Each region has a full replica of the table. Writes in any region are asynchronously replicated to all other regions via DynamoDB Streams, typically within 1 second. Last-writer-wins conflict resolution using timestamps. Enables low-latency reads in any region and disaster recovery with RPO near zero.

-- Consistent hash ring example:
-- 256 virtual nodes on a ring [0, 2^128)
-- hash("user_123") = 0x4A3F... -> falls between vnode 47 and vnode 48
-- vnode 48 owned by storage_node_7 (leader)
-- Router forwards PutItem to storage_node_7
-- If node_7 was split, it returns MOVED -> storage_node_12
-- Router updates cache, retries to node_12 transparently

-- Bloom filter per SSTable:
-- Insert: hash item key with k hash functions, set k bits
-- Lookup: check k bits. If ANY bit = 0 -> key NOT in this SSTable (skip)
-- If all bits = 1 -> key MIGHT be here (read the SSTable)
-- False positive rate ~1% with 10 bits/key, 7 hash functions
-- Saves ~99% of unnecessary SSTable reads

Most DynamoDB performance problems come from three mistakes: bad partition key design, using the wrong access pattern, or treating it like a relational database.

Every design decision in a key-value store is a tradeoff between latency, throughput, cost, and consistency. Here are the key choices and when each side wins.

• Provisioned vs on-demand capacity. Provisioned: cheaper at steady load, requires capacity planning. On-demand: 6x more expensive per request, but zero planning -- scales instantly. Use provisioned for predictable workloads, on-demand for spiky or new tables.
• Strong vs eventual consistency reads. Strong reads always go to the leader -- guaranteed latest, but higher latency and 2x RCU cost. Eventual reads can hit any replica -- lower latency, half the cost, but might return stale data (typically < 1 second behind). Default to eventual; use strong only when correctness requires it.
• Single-table vs multi-table design. Single-table: all entity types in one table using overloaded sort keys (e.g., pk=USER#123, sk=ORDER#456). Enables efficient queries across entity types in one call. Multi-table: simpler schema, easier to reason about, but requires joins at the application layer. Single-table wins for read-heavy access patterns; multi-table wins for simplicity.
• LSM tree (write-optimized) vs B-tree (read-optimized). LSM: writes are sequential (append WAL + memtable), ~10x faster writes, but reads may check multiple SSTables (read amplification). B-tree: reads are O(log N) from a single structure, but writes require random I/O to update in-place. DynamoDB chose LSM because key-value workloads are often write-heavy and sequential I/O is dramatically faster on SSDs.
• Partition key design: composite vs simple. Simple PK (just partition key): each item is unique by PK alone. Composite PK (partition key + sort key): enables Query operations over a range of sort keys within one partition. Use composite when you need to model 1-to-many relationships (e.g., user orders: pk=USER#123, sk=ORDER#timestamp).

DynamoDB is designed to degrade gracefully -- throttle rather than crash, redirect rather than error. But every distributed system has failure modes that the client must handle.

In a system design interview, the key-value store question tests your understanding of distributed systems fundamentals. Focus on these points to demonstrate depth.

1. Start with consistent hashing. "hash(partition_key) maps to a virtual node on a consistent hash ring. Adding/removing nodes only remaps 1/N of keys." This is the foundation.
2. Name the LSM tree explicitly. "Writes append to WAL + memtable, flush to SSTables, background compaction merges them. Bloom filters avoid unnecessary reads." Shows you understand the storage engine, not just the API.
3. Quorum math: W + R > N. "3 replicas, write quorum of 2, read quorum of 2. W+R=4 > 3, so any read sees the latest write. For eventual consistency, R=1 is enough."
4. Partition key design is the interview. High cardinality, uniform distribution, matches the access pattern. Bad PK = hot partition = system down. Give a concrete example: user_id good, date bad.
5. Mention adaptive capacity. This is the detail that shows you have gone beyond textbook knowledge. "DynamoDB borrows unused capacity from cold partitions to hot ones -- no manual intervention."
6. Contrast with the original Dynamo paper. "Dynamo used vector clocks and sloppy quorums for AP. DynamoDB uses a single leader per partition for CP within a region, which is a simpler model. Global tables add eventual consistency across regions."
7. Discuss single-table design. "Overload the sort key to store multiple entity types in one table. PK=USER#123 SK=PROFILE for metadata, SK=ORDER#2024-01-15 for orders. One Query returns all data for a user. This is the DynamoDB-native pattern."

Key-value store design shares foundational concepts -- consistent hashing, replication, sharding -- with many other distributed systems. Studying these reinforces the same patterns.

The evolution from a single-node hash table to a globally distributed managed service mirrors the history of distributed systems research -- each step added a capability and introduced new complexity.