Labs

System lab · hard · 28 min

DynamoDB: Key-value store

A Dynamo-style store that keeps serving while machines fail.

Every other lab in this course uses a database. This one builds one. You'll design a distributed key-value store in the style of the original Dynamo paper from Amazon (2007), the design that inspired Cassandra, Riak and others. The goal is a store that keeps accepting writes while machines die, disks fail and networks split.

One note before you start. The managed DynamoDB service sold today has moved on from the 2007 design in several ways, for example using a leader per partition. This lab follows the classic Dynamo-style ideas, because they're the clearest way to learn how a leaderless store survives failure.

The brief

You're building the storage layer behind something like a shopping cart for a huge online shop. Teams across the company will store data in it by key. The shop's rule is simple: adding to cart must always work. A customer who can't add to cart during a sale is lost revenue, so the store should prefer saying "yes" to a write over being perfectly consistent.

In scope:

  • get(key) and put(key, value) on items up to 400 KB.
  • Spreading data across hundreds of machines.
  • Replication, and staying available when machines fail.
  • Repairing replicas that have drifted apart.
  • Adding and removing machines without downtime.

Out of scope: secondary indexes, range queries across keys, transactions across keys, a query language, backups and multi-region replication. Each could be its own lab.

Requirements

Functional

  • put(key, value) stores a value. get(key) returns it.
  • Keys are opaque byte strings. Values are blobs up to 400 KB.
  • If two writes to the same key conflict, the store must not silently lose one. It can return both versions and let the application merge them.

Non-functional

  • Always writable: a write succeeds as long as any few healthy nodes can be reached, even during failures.
  • Durable: an acknowledged write survives the loss of any single machine, and usually two.
  • Low latency: p99.9 under 10 ms for reads and writes within a data centre.
  • Incrementally scalable: add a machine, and data and load spread onto it automatically, moving as little as possible.
  • No single point of failure and no special nodes. Any node can take any request.
  • Eventually consistent by default, with a per-request option for stronger reads.

That "always writable" requirement is the root of nearly every decision below. It's a deliberate choice of availability over consistency during partitions. Module 13 covers consistency models and CAP.