Amazon Dynamo Notes

• Primary key interface. You ask for a key, you get back the data.
  • Why does this enable the system to scale?
  • Why are relational databases mentioned as fundamentally non-scalable technology?
  • Complex queries and data management options.
• Technologies behind Dynamo
  • Consistent hashing XX
  • Vector clocks.
  • Object versioning
  • Quorum consistency
  • Decentralized replica synchronization.
  • Gossip based failure detection and membership protocol.
• Stateless vs stateful
• No operations span multiple data items and there is no relational schema.
• What's so bad about schema? Why not allow schema
  • Nothing bad in principle
  • It's about how you use it.
  • Invites complex operation spanning multiple items.
  • That invites indices
  • Then availability becomes difficult.
• Assumption
  • Dynamo used only for internal services
  • No longer true. Offered as a cloud service.
• Consistency and availability trade off. Can you provide an example of how this can happen? - One of the replicas is unavailable. You still want to let the client write to any available replica. If you had to wait until the replicas synchronize, you would deny availability.
• P2P Pastry and Chord. Log N routing. Show slides? Dynamo is a single-hop DHT, to avoid variability if routing from multiple nodes.
• Discuss consistent hashing. How does Dynamo deviate from it?
• Discuss how Dynamo maps keys to nodes. And where it replicates (N-1) successors. It deviates by skipping successors in the preference list to ensure that each key is replicated on distinct physical nodes.
• Discuss vector clocks, show slides. Vector clocks are used to determine whether two versions of an object have causal ordering or diverge. A vector clock is a collection if nice, counter pairs. One vector clock is associated with every version of every object.
• Replication of requests:
  • Scenario 1: the request is forwarded to the coordinator.
  • Scenario 2: the request is forwarded to one of the N nodes in the preference list using a load balancer. The node that receives it becomes the coordinator.
  • R+W=N.
  • The coordinator forwards requests to N replicas. Read is successful if at least R have replied. Write is successful if at least W have replied.
  • That's how replicas may become divergent.
• Walk through an example
  • We have three servers, X, Y and Z.
  • The key exists with version D1. The client reads it, then does a put. That creates a version D2.
  • Server X put: Sx, 1.
  • Server X put: Sx, 2.
  • Server Y put: has the version Sx, 1. The put arrives on Sx, 2. It knows that Sx, 1 can be discarded. New clock: Sx, 2, Sy, 1. (See how a vector can grow).
  • Server Z does a put: same situation as Y, so Sx, 2; Sz, 1.
  • Now these versions will be propagated to X when the client does another read.
  • A client does another get, X sees two causally unrelated versions, responds with both versions. The client does a put on a new version with a reconciled vector clock: Sx, 3; Sy, 1; Sz, 1.

Updated Tue March 10 2015, 15:55 by fedorova.