I enjoy reviewing classic industry papers periodically. The DynamoDB paper is fascinating, approachable, and deepens insights on almost every read. Finally, its a good reminder that good programs accomodate different concerns to optimize for others.

DynamoDB was built for handling amazon.com’s shared shopping cart problem. Most Amazon customers have a single household account, and any household member should be able to add items to a shared shopping cart at different times on their devices.

While relational databases (with sharded servers and replica sets) can be used to solve this problem, scalability, availability, and cost concerns motivated the Amazon engineering team to come up with a simpler solution that is more pertinent to their problem.

The engineering team at Amazon came up with several simplifications:

  1. Storage and query of data uses primary keys (as opposed to relations)
  2. Dynamo DB server side is more simpler, and requires clients to do more than relational database clients. For example, in Dynamo DB clients have to:
    1. Deal with different versions of the same data
    2. Deal with potentially stale data and or phantom data
  3. Dynamo DB does not provide granular security over the data it stores. Clients have full access to the data contained in the database.

Dynamo DB API is quite simple and straightforward:


func get(key string) (err error, value []byte)

// the context provides additional client metadata
// for tuning consistency (explained below)
func put(c context, key string, value []byte) (err error)

DynamoDB architecture is deliberately kept extensible and dynamic: a bunch of potentially heterogenous servers working together.

Storage nodes in Dynamo DB use consistent hashing algorithm and form a distributed hash table (DHT) to store data keys across this logical ring. A client calls into an arbitrary storage node, which acts as a coordinator to either get or put data keys. To ensure a good distribution of keys, each server is represented as a set of virtual nodes (with the number of virtual nodes based on overall server capacity). When storage nodes fail or are added to the ring, there is asynchronous rebalancing of data across the logical ring.

Dynamo DB nodes gossip among themselves to ensure valid membership to the ring. A seed file containing other nodes is maintained by each node, along with the time when that node heart beat to it.

Data availability is improved by replicating keys asynchronously across the ring to N servers clockwise. For durability, keys are replicated on physical servers.

Data versioning using vector clock metadata (a tuple consisting of server-id and a monotonically increasing counter), that allows for conflict resolution when values branch out due to either asynchronous replication or server unavailability (when network partitions or other failures occur). In case of the classic double descendant value issue, the client is sent back both values, and then client is expected to merge and resolve the conflict.

Dynamo DB additionally provides tunable consistency levers to clients (similar to the sql ISOLATION LEVEL clause in relational databases). Clients specify the server to read data from R servers or write data to W servers for a given key.