Inside DynamoDB:
one write, many moving parts.

A checkout service can make several dependent database calls. Even when most requests are fast, one slow call can dominate the checkout’s response time. At scale, predictable latency matters alongside average latency. DynamoDB’s challenge is to deliver that predictability while many customers share machines and the service continually repairs failures, moves data, and deploys software.

The original Dynamo solved a highly available key-value storage problem, but teams still operated their own installations. SimpleDB offered a managed experience, yet table size and throughput constraints forced applications to divide data themselves. Indexing all attributes also complicated the predictability of writes. DynamoDB combined automatic partitioning and a managed service with a more constrained access interface.

The shared name is misleading: DynamoDB does not simply expose the original Dynamo’s architecture as a service. This paper describes replication groups with leaders and Multi-Paxos. Carrying over a leaderless mental model from the earlier Dynamo paper would give the wrong explanation of writes and strong reads.

A table contains items, and each item contains attributes. A primary key consists of a partition key, optionally combined with a sort key. DynamoDB hashes the partition key; that result and the sort key, when present, determine item placement. Two orders can share customer#42 as their partition key while order#824 and order#825 distinguish them through the sort key.

The table’s physical key space is divided into disjoint contiguous ranges called partitions. Each partition has a replication group distributed across availability zones. A storage node hosts many replicas belonging to different partitions and potentially different customers. A partition, a replica, and a physical node are therefore three different things.

• Request routers authenticate, authorize, perform admission control, and route requests.
• Metadata services map keys to partitions and replica membership.
• Storage nodes contain storage replicas with WALs and B-trees, and execute item operations.
• Autoadmin monitors health, replaces replicas, moves capacity, splits partitions, and executes control-plane requests.

That separation allows machines and replica placement to change while the application continues using the same table API. Item reads and writes go to storage; resource-management requests go to autoadmin. Transactions, global indexes, streams, global tables, and backups have additional supporting services whose full protocols are outside this paper’s scope.

Suppose an application changes an order from pending to paid. Each storage replica has a write-ahead log recording changes and a B-tree organizing key-value data for reads. The WAL makes recovery possible; the B-tree represents the data view. There is no single shared WAL box outside the replicas in the architecture described here.

1. Find the leader. After checking the caller and admitting the operation, the router resolves the key’s replication group. Writes must reach its elected leader.
2. Generate the log record. The leader creates a WAL record and sends it to peers. Replicas persist it in their own local write-ahead logs. Sending bytes over the network is not the same as persisting them.
3. Reach a quorum. The paper describes a normal three-replica group with a two-replica write quorum across different availability zones. In the lab, A and B persist first. C may still be slow.
4. Acknowledge success. The write is acknowledged once a quorum has persisted the record. Requiring all three would let the slowest replica dictate latency and availability.
5. Maintain the B-trees. Storage replicas apply committed changes and lagging replicas catch up. Persistence in the WAL and application to the B-tree are separate concepts; they need not happen simultaneously across replicas.

The animation deliberately separates these events so you can inspect them. It is not a cycle-accurate account of when each B-tree page changes relative to the response. In particular, local persistence and peer replication can overlap.

A successful write does not mean every replica instantly serves the same value. Suppose A and B have persisted the paid update, but C still serves pending. In this architecture, a strongly consistent read goes to the leader. An eventually consistent read can go to a storage follower and may return the older value while that follower catches up.

The lab’s two read scenarios begin after the same successful write. “Strong read” routes to the leader and returns paid. “Eventual read” chooses lagging C and returns pending. The difference is the consistency contract and permitted destination, not simply whether a cache happened to contain the item.

A log-only replica cannot serve either item read because it has no B-tree. Likewise, a follower’s ability to serve eventual reads does not authorize it to accept writes. Conditional writes and multi-item ACID transactions add further semantics; a simple read-followed-by-write animation should not be mistaken for a transaction protocol.

Multi-Paxos handles leader election and consensus. A leader periodically renews its lease. If another replica detects failure, it can initiate an election, but a replacement must wait for the old leader’s lease to expire before serving writes and strong reads. That wait protects consistency during an uncertain leadership transition.

A missed heartbeat is not conclusive evidence that the leader is dead. One follower may have a broken network path while other participants still reach the leader—a gray failure. The improved detector asks other replicas whether they can communicate with the leader. A healthy response can suppress a spurious election and its associated interruption.

Repair also has two speeds. Rebuilding a full storage replica requires copying both a B-tree and WAL, potentially taking minutes. To restore protection for recent writes sooner, the leader can add a log-only replica. Copying just recent WAL entries can take seconds. Such a replica contributes durable log storage, like a Paxos acceptor, while full storage repair continues.

The original provisioned model distributed a table’s throughput among its partitions. For the item sizes described in the paper, one RCU supports one strong read per second up to 4 KB, and one WCU supports one standard write per second up to 1 KB. Equal allocations worked well only when traffic was reasonably balanced.

One hot partition could exhaust its allowance while the table had plenty of unused capacity elsewhere. Splitting for storage size created throughput dilution: dividing a parent’s allocation between children could reduce the allowance of the busy child even though demand had not changed.

Bursting addressed temporary spikes by retaining unused capacity for up to 300 seconds in the system described. Partition allocation and burst token buckets operated alongside a node-level bucket. Bursts required physical headroom; writes also needed capacity on peer nodes, not just on the leader.

Adaptive capacity addressed sustained imbalance. When a partition throttled but the table remained within its budget, a control loop could boost that partition, with autoadmin moving it to a suitable node. The paper reports eliminating more than 99.99% of throttling caused by skewed access patterns through this mechanism.

It still reacted after throttling had occurred. Bursting was temporary and best effort. These limitations explain why the paper continues beyond adaptive capacity to a different admission architecture.

Global admission control (GAC) replaced the earlier adaptive-capacity mechanism described above. It tracks table-wide token consumption while each request router maintains a local token bucket. Routers periodically replenish tokens, on the order of seconds, and spend them locally to admit individual requests. GAC need not be a synchronous remote call for every item operation.

This loosens the coupling between the customer’s table budget and fixed per-partition allowances. Partition-level limits remain as defense in depth for shared storage nodes. “Global” refers to coordinating the table’s admission budget, not to cross-Region global-table replication.

Budget enforcement cannot create physical resources. Nodes monitor consumed throughput and data size; when overloaded, they propose replicas for autoadmin to move to suitable destinations that do not already host a replica of the same partition. Placement based on actual consumption improves utilization when tenants peak at different times.

A busy partition can also split for consumption. DynamoDB uses observed access distribution to choose a split point rather than blindly bisecting the key range. Splits take minutes in the paper’s account. A single hot item or a sequentially moving hot range may not benefit, so the system detects those patterns and avoids ineffective splits.

On-demand tables build on consumption tracking, placement, GAC, and splitting. The paper describes immediately accommodating up to twice a table’s previous traffic peak, with additional capacity allocated as demand rises further. This historical description is not a claim that every workload has unlimited instantaneous scalability.

Replication tolerates a lost machine, but replicas can also propagate bad bytes. Checksums in log entries, inter-node messages, and log files detect corruption at multiple boundaries. Checking each transfer helps identify errors introduced by processors, memory, disks, or intermediate transformations.

WAL files are periodically archived to S3. Before upload, agents check table and partition identity, checksums, and gaps in sequence numbers. A manifest describes the file and its boundaries. Archival agents run on all three replicas; if a file is already archived, an agent compares it against its local WAL rather than assuming the first uploaded copy is correct.

The scrub process compares live replicas with each other and with a replica reconstructed offline from archived log history. Those are different tests: current copies might agree with one another while still disagreeing with independently replayed history. Continuous verification detects failures that replication alone cannot rule out.

Backups and point-in-time restores also use archived logs. The system selects suitable partition snapshots, replays subsequent records up to the requested timestamp, and restores into a new table. This avoids doing backup reconstruction on the live request path and also provides recovery from application mistakes, such as an accidental deletion that was replicated perfectly.

The paper complements these runtime checks with TLA+ specifications and model checking of replication changes, along with failure injection and stress testing. Protocol reasoning, implementation testing, and verification of stored data address different sources of failure.

Originally, routers cached a table’s complete partition map. With approximately 99.75% cache hits, metadata storage normally saw only a tiny fraction of total traffic. But a new router started with an empty cache. Adding router capacity could unexpectedly overload metadata services and destabilize the system.

DynamoDB built MemDS, an in-memory distributed metadata store designed to handle the full incoming lookup rate. Its compressed Perkle structure combines Patricia-tree and Merkle-tree ideas and supports ordered lookups such as floor and ceiling. Routers retrieve the partition relevant to a key instead of downloading an entire large table’s map.

The surprising cache policy is that even hits trigger an asynchronous MemDS refresh. Backend load stays steadier as cache effectiveness changes. The cache still improves foreground latency, but it no longer hides nearly all metadata demand until a cold start exposes it at once.

Storage nodes remain authoritative for membership and push changes into MemDS. If metadata is stale, a contacted storage node can return newer membership when known or an error that prompts another lookup. A cached routing map does not override actual replica ownership.

Availability is measured from several perspectives: service and table metrics, observations from internal client applications, and canaries running in each availability zone against public endpoints. Internal health alone cannot reveal every failure customers experience on the path to the service.

Deployments are not atomic across a fleet. To change a protocol, DynamoDB first deploys software that can read both old and new formats, then enables writers of the new format. Upgrade and downgrade tests deliberately exercise rollback, because a failed upgrade may leave a state different from the original one.

Rollouts begin with small groups of nodes and expand while monitoring latency and errors, with automatic rollback on threshold violations. Planned leader handoffs can explicitly relinquish leadership, avoiding the lease-expiration wait associated with an unexpected failure.

Request routers also cache IAM and KMS results and refresh them asynchronously. The paper describes bounded continued use of cached results during dependency impairment. This helps established work continue; it does not mean bypassing authorization or making cold-cache requests immune to the outage. The principle is to preserve useful operation with information already available while honoring security constraints.

The evaluation uses YCSB workload A, with 50% reads and 50% updates, and workload B, with 95% reads and 5% updates. Both use uniformly distributed keys and 900-byte items against production DynamoDB in North Virginia. Total throughput increases from 100,000 to 1,000,000 operations per second.

Median and 99th-percentile latency profiles remain broadly stable across that increase. This supports the argument that aggregate scale need not increase individual operation latency. It does not establish identical behavior for a hot item, large payloads, transaction contention, or every client network path.

The mechanisms fit together because they solve different constraints. WAL quorums protect acknowledgements. B-trees serve data. Leases regulate leadership. Log replicas shorten repair exposure. GAC separates customer budgets from placement. Consumption-aware splits distribute suitable workloads. Metadata refreshes and cautious deployments make changing conditions less disruptive.