Advanced8 min read

How DynamoDB storage internals work

DynamoDB finds your data in two steps: a hash on the picks a partition, and inside that partition a B-tree keeps items in order.

How does DynamoDB store data?

The partition key's hash picks the partition that owns the item. Each partition is a group of three replicas in three Availability Zones, and per the 2022 USENIX ATC paper each replica keeps the partition's items in a B-tree.

A write goes to the partition's leader and is acknowledged once two of the three replicas have it.

  • The partition key is hashed, not searched. The hash picks the partition (or, once a big collection splits, one of several). Per the paper, latency stays flat as the table grows.
  • Items sit in a B-tree in key order. Within one partition key, items are ordered by sort key (UTF-8 byte order for strings, numeric order for Number keys), which is why range reads (begins_with, between) are cheap.
  • Every write commits on a quorum before it acks. The leader replicates to its two peers and acknowledges once two of the three replicas have persisted the write.
  • This is why the access-pattern rules exist. Hash-then-tree is fast only when you read by key; without the key, DynamoDB has to read every partition.

Start with the data structure, not the API

Coming from SQL, you picture a table as rows on disk with a query planner picking indexes. DynamoDB has no planner. The storage layout is the contract: what's fast and what's a footgun both follow from two structures.

Picture a distributed map. The partition key's hash says which partition holds an item; inside that partition, a B-tree keeps the items that share a partition key together, ordered by sort key.

Query semantics, the 10 GB LSI limit and why a missing key forces a Scan all follow from that layout.

Hash the partition key to find the partition

When a request arrives, DynamoDB applies an internal hash function to the partition-key value.

AWS documents this much: "The output value from the hash function determines the partition in which the item will be stored." That partition is three replicas on three storage nodes, and each node hosts replicas of many partitions.

How the hash is mapped to a partition is internal.

The ATC '22 paper describes a cached partition map that routers look up, and reports that "latencies remain stable" as tables grow from megabytes to hundreds of terabytes. Request routing covers that lookup.

Without the partition key, DynamoDB has no partition to go to, so it reads every one. That's a Scan, and its cost grows with the table.

When the value you have isn't the partition key, add a global secondary index keyed on that attribute (update-table --global-secondary-index-updates, or the console's Indexes tab).

A Query on the index gets the fast path back. See GSI vs LSI.

PutItem / GetItemPK=DEVICE#a91Hash(PK)Partition that owns the hash(3 replicas)Replica's B-treeitems in SK orderItem

The request hashes to one partition, then descends that partition's B-tree to the item: two steps instead of a table walk.

Order items in a per-partition B-tree

Inside a partition, items aren't a heap. Each replica holds the partition's key range in a B-tree, and within one partition key the items sit in sort-key order.

The tree holds only that partition's items, not the whole table's. (The ATC '22 paper documents the B-tree; AWS's developer guide says only that items are kept "in sorted order by the sort key".)

This is why sort-key range reads are cheap. Take a fleet-telemetry table where each device's readings live under one partition key:

PKSK
PK = DEVICE#a91SK = READING#2026-06-23T08:00Z
PK = DEVICE#a91SK = READING#2026-06-23T08:05Z
PK = DEVICE#a91SK = READING#2026-06-23T08:10Z

Because the tree is sorted, "all readings between 08:00 and 09:00" is a seek to the start value plus a sequential walk, not a filter over every reading the device ever sent. You read only the matched range.

That ordering is also why a begins_with(SK, "READING#2026-06-23") query is fast while filtering on a non-key attribute is not: the tree can seek by SK and nothing else.

To compose those key conditions safely, build them in the DynamoDB Expression Builder rather than hand-concatenating strings:

KeyConditionExpression  PK = :pk AND begins_with(SK, :day)

To seek by another attribute, make it an index key. An LSI gives the same partition key an alternate sort key, but only at table creation and with a 10 GB cap per key.

A GSI can key on any attribute, can be added later, and is eventually consistent.

Replicate every write to three AZs

A partition isn't one machine. Each one is replicated across three replicas in three Availability Zones, the leader-based quorum design described in the 2022 USENIX ATC paper.

(The 2007 Amazon Dynamo paper is a naming ancestor, not this replication model; see From the Dynamo paper to DynamoDB.)

One replica is the leader for the partition. A write goes to the leader, which logs it and sends it to its two peers.

The leader acknowledges the write once two of the three replicas have persisted it, so durability across AZs is paid for before your PutItem returns.

Reads have a choice. A read goes to the leader and sees the latest committed write. An read can be served by any of the three replicas, which may lag the leader. AWS publishes no bound on that lag.

Eventually consistentStrongly consistent
Served byAny of the 3 replicasLeader only
Sees latest writeNot always (no published lag bound)Yes
Read costHalf: 0.5 read unit per 4 KBFull: 1 read unit per 4 KB
AvailabilityAny healthy replica can answerNeeds the leader to be reachable

A 2 KB item read strongly costs 1 read unit (an RCU on provisioned, a read request unit on on-demand); the same read eventually consistent costs 0.5.

Ask for the leader with ConsistentRead: true (tables and LSIs; a GSI rejects it). Price your hot paths in the pricing calculator.

GSIs are updated asynchronously and serve only eventually consistent reads, so a GSI read can be stale too. See GSIs are eventually consistent.

Read the rules off the structure

  • Always supply the partition key. Without it you read every partition. This is the core of Query vs Scan; add a GSI when the key you have is a different attribute.
  • Co-locate what you read together under one partition key, so one hash and one tree walk return the whole item collection. That's the foundation of single-table design.
  • Keep partitions bounded. A partition has fixed limits (physical partitions). With an LSI, request ReturnItemCollectionMetrics: SIZE on writes and alert below the 10 GB per-key cap; for a hot key, see hot partitions.

Next steps

Model your keys to match the structure with sort key strategies and single-table design, then assemble the actual expressions in the DynamoDB Expression Builder.

Try DynoTable to run these reads against your own tables and see which items a key condition pulls back.

By Dmitriy · Updated