DynamoDB (2022 paper): predictable performance

01 · CONTEXT

A database that promises predictable latency

The 2022 paper describes Amazon DynamoDB, AWS's cloud NoSQL database service. The stated design goal is to complete all requests with single-digit millisecond latency, and the authors state that, for customers, consistent performance often matters more than median response time.

To give a sense of scale: during the 2021 Prime Day event, which lasted 66 hours, the cited peak reached 89.2 million requests per second, as cited by Marc Brooker.

The service is multi-tenant: it stores data from different customers on the same physical machines, and isolation between neighboring tables comes from resource reservations, tuned provisioning, and usage monitoring.

02 · ARCHITECTURE

Partitions, replicas, and routing

A table is split into partitions that meet throughput and storage needs. Each partition has replicas in different Availability Zones, and the replication group uses Multi-Paxos for leader election and consensus.

Only the leader replica serves writes and strongly consistent reads. A write is acknowledged when a quorum of peers persists the record to the local log. In front sit the routing service, which authenticates, authorizes, and routes each request, and the metadata service, from which routers obtain routes.

1. The application sends the request to the router, which is responsible for authenticating, authorizing, and routing each request.

2. The router queries the metadata service to obtain routing information.

3. A write goes to the leader, which sends the log record to the followers and acknowledges after a quorum persists it.

4. The autoadmin service monitors partition health and replaces replicas deemed unhealthy.

03 · THE PROBLEM

Admission control tied to the partition

DynamoDB uses admission control so that storage nodes do not become overloaded. In the original version, the customer declared the table's throughput in read and write capacity units, and each node did admission independently, based on the allocations of the partitions it hosted.

When a partition was split by size, the parent partition's throughput was divided equally among the children. The paper itself illustrates: assuming a maximum of 1000 WCUs per partition, a table created with 3200 WCUs becomes four partitions of 800; when raised to 6000 WCUs, the table goes to eight partitions of 750.

This uniform split assumes the application accesses keys uniformly. In practice two problems emerged: hot partitions, with constant traffic to a few items, and throughput dilution, common when partitions were split by size. The result was throttling, that is, reads and writes rejected even though the table's total throughput was sufficient.

04 · EVOLUTION

Successive answers to the same problem

The first answer was bursting: letting the application use the partition's idle capacity, on a best-effort basis, to absorb short spikes. Unused capacity was retained for up to 300 seconds. The second was adaptive capacity, created to better absorb workloads with access patterns heavily skewed across partitions.

Adaptive capacity was, according to the paper, best effort, but it eliminated more than 99.99% of the throttling caused by skewed access. The paper points out that partition capacity was coupled to admission control and concludes that it would be beneficial to remove admission control.

05 · GLOBAL ADMISSION

Tokens at the router, accounting at the GAC

Global admission control (GAC) builds on the same token bucket idea. The service centrally tracks the table's consumption in tokens, and each router keeps a local bucket to decide admission, replenishing tokens from the GAC at regular intervals. The GAC state is ephemeral: a server can be stopped and restarted with no impact on operation.

1. The request arrives at the router, which debits tokens.

2. When tokens run out, the router asks the GAC for more.

3. The GAC estimates the table's global consumption and distributes the tokens for the next interval.

4. Per-partition buckets were kept in addition to the global scheme, with limited capacity.

Other pieces complete the picture. There is proactive balancing of partitions across nodes by throughput and storage consumption, and automatic partition splitting based on consumed throughput, with a split point chosen from the observed key distribution. The paper says the system detects certain access patterns and avoids splitting the partition. For on-demand tables, the service instantly accommodates up to double the previous peak.

06 · PREDICTABILITY

The cache that hides work

Among the paper's lessons is to design for predictability, not for absolute efficiency. Caches improve performance, but should not hide the work that would be done without them, so that the system is always sized for the unexpected.

The example is the routers' route cache. The hit rate reached about 99.75%, but on a cold start every request would generate a metadata lookup. The answer was MemDS, a distributed in-memory datastore; in the new cache, a hit also triggers an asynchronous call to MemDS, and the fleet receives constant traffic regardless of the hit rate.