DynamoDB Internals #1: How does it store data?

In my current team, we use DynamoDB a lot. This weekend, i felt the curiosity to know more about it. It is classified as a Key-Value store, but is it something more than that? I have recently gone through this paper:

Amazon DynamoDB: A scalable, predictably performant, and fully managed NoSQL database service

… and there are a ton of learnings here. I’d like to distill these learnings via a series of articles. This is the first one which deals with how EXACTLY does DynamoDB store it’s data, manage it, and scale it.

---

Architecture: The Schema

To understand how it stores the data, and what happens around it, we first need to understand the schema. More importantly, its Primary key.

The schema of the primary key is specified at the table creation time. The primary key schema contains a partition key or a partition and sort key

This key goes through a hash function, whose output decides which partition the corresponding data is stored in. DynamoDB is heavily intertwined with rest of AWS infrastructure, so much so that each partition is replicated to 3 AZs to achieve maximum fault tolerance (hence their 5 9’s of availability).

The following architecture diagram illustrates how a request to DynamoDB comes in and and how the data is replicated across multiple AZs.

Fine, the key decided where the data gets stored, but what exactly is a partition?

A DynamoDB table is divided into multiple partitions to handle the throughput and storage requirements of the table. Each partition of the table hosts a disjoint and contiguous part of the table’s key-range.

So, a partition is a table-level construct which exists to physically store a portion of the table's data and to isolate and manage its throughput and storage independently, enabling DynamoDB to scale horizontally and distribute load across multiple storage nodes.

---

What happens when a partition begins filling up?

In DynamoDB, each partition is an internal unit that holds a slice of your table’s data and handles a portion of your table’s traffic. To maintain predictable performance, each partition is subject to fixed limits for both storage and throughput.

Understanding these limits is essential because when a partition crosses either the storage or throughput limit, DynamoDB automatically splits it to continue scaling horizontally.

There is no hard upper limit on how many partitions a DynamoDB table can have: It creates new partitions dynamically based on:

• When any partition grows beyond 10 GB, it is split.

• In provisioned mode: Every 1,000 WCUs or 3,000 RCUs provisioned creates 1 new partition.

• In on-demand mode, AWS automatically scales partitions based on actual traffic.

Here, 1 RCU represents the ability to read one strongly consistent item (up to 4KB) or two eventually consistent items (up to 4KB) per second. 1 WCU represents the ability to write one item (up to 1KB) per second.

Once the partition is split, The key space is divided, and new partitions are assigned subranges of the hash space. The original partition is no longer used for new writes but might still hold old data. Its also important to know that we can’t merge two partitions back together after splitting as it has its own risks. While going through the paper, I got the sense that AWS is more focused on availability and fault tolerance than any other metric.

---

Multi tenancy in DynamoDB

The partitions hosted on a single storage node could be wholly unrelated and belong to different tables. Hosting replicas from multiple tables on a storage node, where each table could be from a different customer and have varied traffic patterns involves defining an allocation scheme that decides which replicas can safely co-exist without violating critical properties such as availability, predictable performance, security, and elasticity.

So, what happens when one partition starts hogging resources?

Colocation was a straightforward problem with provisioned throughput tables. Colocation was more manageable in the provisioned mode because of static partitions. Static partitions made the allocation scheme reasonably simple. Allocation to a node involved finding storage nodes that could accommodate a partition based on its allocated capacity.

Partitions were never allowed to take more traffic than their allocated capacity and, hence there were no noisy neighbors. All partitions on a storage node did not utilize their total capacity at a given instance. Bursting when trying to react to the changing workload meant that the storage node might go above its prescribed capacity and thus made the colocation of tenants a more complex challenge.

DynamoDB implemented a system to proactively balance the partitions allocated across the storage nodes based on throughput consumption and storage to mitigate availability risks caused by tightly packed replicas. Each storage node independently monitors the overall throughput and data size of all its hosted replicas.

… but as you guessed, this is just for provisioned throughput. What happens in on-demand mode?

DynamoDB provisions the on-demand tables based on the consumed capacity by collecting the signal of reads and writes and instantly accommodates up to double the previous peak traffic on the table. If an application needs more than double the previous peak on table, DynamoDB automatically allocates more capacity as the traffic volume increases to ensure that the workload does not experience throttling. On-demand scales a table by splitting partitions for consumption. The split decision algorithm is based on traffic.

The ability to balance based on consumed capacity effectively means partitions of on-demand tables can be placed intelligently so as to not run into node level limits.

---

… and that is how data is stored in DynamoDB. Of course, there are a lot of other concepts to be discussed. We broached upon how partitions are replicated across AZs, but did you know that each of the replicas has a “leader replica” which behaves differently? We’ll discuss all that and more in the next article of this series.