Design a Distributed Key-Value Store

Requirements

A key-value store maps a key to a value: put("cart:42", {...}) and get("cart:42"). Amazon's Dynamo paper (2007) described one built for the shopping cart, where a customer must always be able to add an item, even during failures. Cassandra, Riak and Voldemort follow the same ideas. Amazon DynamoDB, the managed service, is a different system that shares the name.

Functional:

• put(key, value) and get(key). Values are opaque blobs, up to about 1 MB.
• Keys spread over many machines, with no single master.

Non-functional:

• Highly available for writes: accept a write even when some nodes are down or unreachable.
• Scalable: add nodes and capacity grows roughly linearly.
• Low latency: single-digit milliseconds at the median.
• Eventually consistent by default, with tunable strength. Eventual means that if writes stop, all replicas converge to the same value.