Lec 21: Case study: Dynamo

Paper published at last SOSP (Oct 2007)
Experience paper
Amazon's Dynamo

Dynamo: key/value store
  always writeable
  conflict resolution
  SLA: 300 msec
  interface
    put(key, context, object)
    get(key, context) -> object
    caller picks keys and objects
    ID = MD5(key)
  partitioning
    consistent hashing
  replication
    N nodes
    preference list
  versioning
    version vectors
      what are the ID of the writers?
      context includes version vector
      how large can the vectors gets?
  put & get
    sloppy quorum: 
      R nodes perform get
      W nodes perform put
      R+W > N
      N is healthy nodes in preference list
    hinted handoff
    usually both R + W < N because don't want to wait on the slowest
  permanent failures
    replicas synchronization through merkle trees
    ring membership: manual
      what risk does this avoid?
    add node: transfer keys
  experience
   transfer and synchronization is expensive, because of key scan
     --> independent schemes for partitioning and placement
     Q partitions, Q/S tokens per server, Q >> N, Q >> S*T
     tokens are randomly redistributed
     copy complete partitions
   background tasks