DynamoDB is Amazon's availability-centric key-value storage. It provides a simple interface with put&get methods. Dynamo achieves full availability and partition-tolerance, sacrificing consistency in favor of eventual consistency. This design choice is a requirement for some Amazon services. One example is an online cart, where adding an item to cart should not be lost in any case. To achieve fault-tolerance, DynamoDB stores each key on N servers. For each key, there is a preference list, which consists of M>N nodes. Preference list is constructed with consistent hashing: each node selects several numbers on a ring (tokens), then each key is hashed into the position in a ring, and preference list is constructed with next M tokens. To achieve eventual consistency, the sloppy quorum is used. There are two parameters: R and W, R+W>N, for the put request to succeed, at least W confirmations are required, for get - at least R. Servers used for the operation are determined as top-N healthy servers from preference list. In a presence of network partitioning, different branches of data would exist. To mitigate this issue, each request is marked with vector timestamp. Vector timestamp consists of autoincrementing ids, one id per server. When one update is lower than the other on all components, those updates are considered casually-ordered. In the case of causal uncertainty, some application-specific merge has to be performed. The configuration information in a system is propagated through gossip. Gossip is a technique when each node maintains a list of known nodes in a system, and repetitively sends this list to all of the nodes. Gossip is also used for updating vector components across the system.
Authors highlight two scenarios where DynamoDB performed especially well:
- A business logic specific merging of diverged branches of data.
- Adjusting "reads vs writes" and "performance vs durability" tradeoffs.
Now, I'd like to review the improvements to DynamoDB since 2007 and look at some alternatives. Although DynamoDB is a managed proprietary service, there are some similar open-source systems. One example is Cassandra - another highly available service. While Dynamo treats a value as a blob of bytes, Cassandra assumes that each value consists of predefined columns[1].
Other aspects of Cassandra implementation are similar to Dynamo. It also uses consistent hashing for partitioning and gossip for membership control. Cassandra uses the same manual control over adding and deleting nodes to the system[1]. The paragraph about this in both whitepapers match exactly, with replacements "Amazon"->"Facebook" and "Dynamo"->"Cassandra". Both solutions lacked ACID transactions at the beginning, but in November 2018, DynamoDB has implemented transactions support[3].
One other notable open source database to compare with is MongoDB. MongoDB is also a NoSQL solution but has a full document store functionality. This allows performing aggregations over the data, building secondary indices, multi-document transactions[4]. Although, Amazon also implemented DocumentAPI for DynamoDB in 2014. One drawback of MongoDB is poorer scalability: it uses master-slave replication[4], and the maximum number of instances in a replica set is 50.
[1] https://db-engines.com/en/system/Amazon+DynamoDB%3BCassandra
[2] https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf
[3] https://aws.amazon.com/blogs/aws/new-amazon-dynamodb-transactions/
[4] https://db-engines.com/en/system/Amazon+DynamoDB%3BMongoDB
[5] https://aws.amazon.com/blogs/developer/introducing-dynamodb-document-api-part-1/
- High availability, always writable
- Sacrice consistency and use eventual consistency
- Target at SLA with 99.9% requests
- Application- specific merge