The Architecture of Amazon’s DynamoDB and Why Its Performance Is So High

DynamoDB is a NoSQL database provided by Amazon Web Service (AWS). It can provide extremely high performance, more than 10 trillion requests per day with peaks greater than 20 million requests per second, and can support virtually any size with horizontal scaling. It is not uncommon for DynamoDB to serve over petabytes of data.

In this article, we will start with a brief introduction to the APIs of the DynamoDB. We will then look into the architecture of DynamoDB and explain in detail why DynamoDB can provide such high performance.

From a 10,000 feet view, DynamoDB is basically a key-value store. It can be thought as a hash-map backed by some persistent storage. Two most important operations supported by DynamoDB are Get and Put.

Unsurprisingly, the semantics of Get and Put operations are consistent with our understanding of hash-map or key-value store. For instance, we can use Put operation to persists a key-value pair to the DynamoDB and a subsequent Get operation will return the value we stored previously.

Put(“key”, “value”);

Get(“Key”) → Returns “value”

What differentiates DynamoDB is its extremely high performance. In the next sections, we will closely examine the architecture of DynamoDB and understand why DynamoDB is so scalable.

• Partitioning

To achieve horizontal scaling, DynamoDB assigns data to different partitions which are hosted by distinct machines. When there are more data, DynamoDB can create more partitions and use more machines to host those additional partitions. It works as following.

DynamoDB uses a cluster of machines and each machine is responsible for storing a portion of the data in its local disks. When a machine is added to the DynamoDB machine cluster, it is randomly assigned an integer value, which we call token in our article. In our example, we assume the DynamoDB has 3 machines. A is assigned a token of 100, B 2000 and C 10,000.

When we insert a key-value pair to the DynamoDB, the key is first hashed into an integer, I. The key-value pair is then stored on the machine that we will meet first if we start from I and walk clockwise around the ring. Therefore keys that are hashed to (1000, 2⁶⁴-1] and [0, 100] are stored on machine A. Machine B therefore stores keys whose hash values are between 100 and 2000. The rest are stored on machine C.

If we receive a lot of data whose hash values are between (10,000, 30,000], machine A will probably be overloaded. What we can do now is add another machine D and split the data stored on A between A and D. Given that data are mostly between (10,000, 30,000], we could assign the machine D a token of 15,000. The load is then more or less evenly spread between machine A and D.

When a range becomes hot, that is, we received a lot of data whose hash values fall inside the range, we could add more machines and assign those machine a token value within the range. With this change, the load and data are spread across more machine. If data are deleted and two consecutive ranges become cold, we can merge them. For example, if there is little data whose hash values are inside (100, 2000] and (2000, 10,000], we could remove machine B from the cluster and uses C to host those data.

There are at least two benefits with this design.

• First, there is basically no scaling limitations. We can always scale up the DynamoDB to store more data by adding more machines.
• Second, this enables incremental scalability. When we first bring up a DynamoDB, we don’t need to allocate a lot of machines. We can add more machines as we have more data. This can greatly save resources.

Note that different keys may be hashed to the same value. It is fine because the hash value only decides which machine hosts the data. We retrieve the value from that machine based on the key, not its hash value.

• Replication

If the data is only stored on one machine, it is not very reliable nor available. When the machine crashes or the disk is corrupted, the data is lost. When the machine is down, we can’t access the data. To resolve the issue, DynamoDB replicates the data N times. We will assume N=3 in our article, which is commonly used in AWS.

Each machine has complete knowledge of the tokens of all machines inside the cluster. For example, all machines know that A has a token value of 100.

When a machine receives a request to persist data, it will forward the request to other two machines that have the next two greater tokens. For instance, when machine A receives a request to store {“key”: “value”}, it will first find out which two machines have the next two greater tokens, and in our case, it is machine B and C. It then sends the request to persist the key-value pair to machine B and C.

Machine A considers the data persisted after it receives responses from both machine B and C. It then sends the response back to the client. However, this has an issue. Without replication, the request processing is slow only when machine A is slow. Now the processing is slow when any of the 3 machines is slow.

To resolve the issue, DynamoDB doesn’t require receiving responses from all N machines before returning to the client. It only requires W machines to write the data to the disk. W is normally set to 2 in AWS. In our case, machine A returns to the client when 2 of the following events have happened

• Write to disk inside A succeeds
• Received response from B
• Received response from C

Note that machine A could actually receive response from B and C before it completes writing to its local disk if its disk is overloaded.

This approach reduces write latency, it however introduces another issue. You may not be able to read the value you just wrote into the database! Imagine the case that machine A received response from B and C and returns to the client. However the write to its local disk actually fails. Then when client wants to get the value, A would return a wrong result since its local disk doesn’t have the recently updated data.

DynamoDB thus further requires machine A to get R copies of data and return the latest copy to the client. R+W should be greater than N and we can guarantee the user will always see the latest data. R is normally set to 2. In our case, machine A is required to get a copy of the data from at least one of the machine B and C and return the latest value to the client. Therefore the correct value will be returned.

With partitioning and replication, DynamoDB is therefore able to provide both scalable and reliable service!

If you are interested in the architecture of AuroraDB, another featured database from AWS, you can read it from my other blog [Click here].