1 of 9

Dynamo: Amazon’s Highly Available Key-value Store

​

​

2 of 9

Contributions / Questions

      • Main contributions of the paper
    • ​
      • Questions you want to discuss
    • ​
      • Rating

​

​

​

​

​

​

​

​

​

​

​

​

​

3 of 9

Overview

  • Primary key interface rather than relational DB
    • Distributed Hash Table (DHT)
  • Sacrifice consistency for availability
  • Commodity hardware infrastructure
  • Key design principles
    • Always writable
    • Incremental scalability
    • Symmetry
    • Decentralization
    • Heterogeneity

4 of 9

Architecture

5 of 9

Partitioning and Replication

​

  • Consistent hashing
  • Virtual nodes
  • A key is assigned to a coordinator and replicated at N-1 successors
    • Preference list

6 of 9

Versioning

  • Client specifies version it is updating
  • Client reconciles divergent versions during a read operation

7 of 9

get/put

  • Requests go through a coordinator who reads from/writes to R/W nodes from the preference list
  • Sloppy quorum
    • Read/write to first N healthy nodes
    • Provide a hint for where data is supposed to be stored and it will be moved there when node recovers

8 of 9

Membership

  • Nodes added/removed manually
  • Gossip protocol used to propagate membership info
    • Nodes all sync with seeds
  • A new node identifies its key range and transfers appropriate data

9 of 9

Results