NotesSystem
Dynamo
Also: Amazon Dynamo
Amazon's internal key-value store (2007), built to be "always writeable" for services like the shopping cart. Not the same system as the DynamoDB cloud service.
Design choices
- Leaderless Replication: each key is replicated to n nodes on a consistent-hash ring; no leader.
- Quorum: tunable (n, r, w), most commonly (3, 2, 2), targeting 99.9% of requests within 300 ms.
- Sloppy Quorum: writes go to the first n healthy nodes in the preference list, with hinted handoff.
- Version Vectors: vector clocks (truncated at about ten entries) detect concurrent versions; the application reconciles siblings.
- Anti-Entropy: Merkle trees to find and sync divergent key ranges.
Notable trade-offs
- Availability over consistency: the shopping cart never lost an add, but merged carts could bring back deleted items.
- Divergence was rare in practice: over 24 hours, 99.94% of cart requests saw exactly one version, with most concurrency caused by automated clients.