Advanced7 min read

From the Dynamo Paper to DynamoDB

The 2007 paper "Dynamo: Amazon's Highly Available Key-value Store" described a store Amazon teams ran for themselves. DynamoDB is the managed service AWS built later under a similar name.

Is DynamoDB based on the Dynamo paper?

Only loosely. The 2022 USENIX ATC paper that describes today's service says DynamoDB "shared most of the name of the previous Dynamo system but little of its architecture." It still hashes your .

The ring, sloppy quorums, vector clocks and gossip are gone.

  • The paper optimized for writes that never fail. Its job was to accept a shopping-cart write during a failure, even if a later read returned a stale or conflicting version.
  • DynamoDB kept the hashing and replaced the machinery. Partitions own contiguous key ranges, each one is a three-replica group with an elected leader, and a write needs two of the three.
  • You no longer tune the knobs. N, R and W from the paper became one per-read choice: ConsistentRead true or false.
  • The lineage is context, not a cause. It helps you read the design, but AWS's own docs explain Scan cost and GSI lag.

What the paper was solving

Amazon's shopping cart could not go down. The 2007 paper describes an "always writeable" store: accept the write, reconcile disagreements later.

A database that refused writes under load, or blocked on a failed replica, was what it was built to avoid.

To work without a single master, Dynamo had to answer two questions on its own: where does a key live, and how many copies must agree before a read or write counts?

Consistent hashing: where a key lived in Dynamo

The paper placed every node at a random position on a hash ring. A key's position is the hash of the key; the next node clockwise owns it, and the following N-1 nodes hold replicas.

Adding or removing a node only moves its neighbors' keys. That's consistent hashing.

DynamoDB kept the first step, hashing the key, and replaced the ring. Per the ATC '22 paper, each partition "hosts a disjoint and contiguous part of the table's key-range", and DynamoDB splits partitions as they grow or run hot.

How partition keys work walks through placement; physical partitions covers splits.

The hashing is why key choice still matters. Pick a low-cardinality partition key, say STATUS with two values, and every item with the same value shares one item collection. That's the footgun.

The way out is a high-cardinality partition key, such as a user or tenant id. Keep the low-cardinality value as a GSI sort key, or in a composite key such as ACTIVE#customer123. Hot partitions covers sharding a key that has to stay hot.

Quorum: how many copies had to agree

The paper's second knob was a quorum. With N replicas, a write succeeds once W of them ack, and a read consults R of them. The paper says R + W > N "yields a quorum-like system": with strict membership, every read overlaps the newest write.

Dynamo then relaxed that. Its "sloppy" quorum used the first N healthy nodes, so a write meant for a down node went to a stand-in and was handed back later (hinted handoff).

Conflicting versions were tagged with vector clocks and reconciled by the application on read.

What DynamoDB kept and what it changed

DynamoDB kept the goal of predictable performance at scale and the hashing of the key. The ATC '22 paper describes the rest as new machinery.

Concern2007 Dynamo paperDynamoDB today (ATC '22 paper, AWS docs)
Key placementConsistent hashing ringHash of the partition key (plus the sort key once a collection splits) → the partition owning that key range
ReplicationN nodes, you choose3 replicas across AZs in a Multi-Paxos group with one leader
Consistency knobsR, W quorum tuningWrites need 2 of 3 replicas; ConsistentRead per read
Conflict resolutionVector clocks, app-side merge on readNone in-Region (writes go through the leader); across Regions, last-writer-wins in MREC global tables, rejected in MRSC
MembershipGossip protocol between peersFully managed; invisible to you
Multi-key opsNone, pure key-valueQuery, GSIs, transactions

In a multi-Region strong consistency (MRSC) global table, a concurrent write to an item being modified in another Region fails with ReplicatedWriteConflictException, and you retry it. (AWS, How global tables work.)

The paper's API was two calls: get(key) and put(key, value). DynamoDB offers a key-value model like the paper's and adds a sort key, indexes and queries.

A Query reads one item collection in sort-key order; a Scan reads every partition of the table.

How a write travels, then and now

The flow below contrasts the paper's quorum write with DynamoDB's leader-based one. In the paper your code tuned the numbers and merged conflicts; in DynamoDB, AWS owns both and you choose only ConsistentRead per read.

Paper: ring, you tune N,R,WDynamoDB: managedput(key, value)Hash the keyWhich system?Write to W of N nodesReconcile via vector clocks onreadLeader logs the writeAck once 2 of 3 AZ replicaspersist it

Where the paper still helps you read DynamoDB

The eventually consistent default rhymes with the paper's "reconcile later" bargain. Read that as an analogy; AWS's own sources give the actual reasons.

Per the ATC '22 paper, any replica can serve an eventually consistent read, and AWS says GSIs are updated "asynchronously, using an eventually consistent model".

So a fresh item can be missing from a GSI for a moment. See GSI vs LSI for when that lag matters.

You buy back strong consistency two ways. Use ConsistentRead: true on a base-table read (it goes to the leader replica), or guard a write with a ConditionExpression so it only lands if the item's current state matches.

Sketch one in the DynamoDB expression builder: attribute_not_exists(PK) makes a PutItem insert-only, the closest modern stand-in for the paper's conflict detection.

The trade DynamoDB made instead

The paper never said no to a write. DynamoDB can: a partition without a healthy write quorum refuses writes, and after a leader failure the new leader waits a couple of seconds for the old lease to expire before it accepts any (ATC '22).

The AWS SDKs retry these failed requests with backoff (error handling), but the default budget (3 attempts in standard retry mode) can run out before a new leader takes over. On write paths that must ride out a failover, raise the SDK's maximum attempts. For a whole-Region outage, use global tables.

In return you get one current version per item in a Region and no merge code.

Model your keys for single-collection Querys, as in single-table design, and keep Scan for exports and one-off jobs. Storage internals covers the leader and its replicas; request routing covers the router in front of them.

Try DynoTable to browse your tables and their GSIs, then run JOINs across tables and GROUP BY over your own data in the SQL Workbench.

By Dmitriy · Updated