Amazon DynamoDB (Week 10, Monday, March 17, 2014)

Replicated data accepting independent writes

Source: Distributed systems for fun and profit, Chapter 5.

Suppose instead of a single database, we have several replicas storing values for the same key.

Two problems:

• When the system is completely connected (no network partitions), we have to propagate changes to all the replicas

• If we continue accepting updates to all replicas even when they are separated by network partitions, we have to reconcile conflicting values for the same key

If we’re willing to give up strong consistency, we can be

• Highly available, even in the presence of partitions

• Low latency

• Almost always “consistent enough”

Amazon’s DynamoDB is an example of such a system

Partial quorums

DynamoDB (and systems inspired by it) replace the notion of strict quorum with a partial quorum

• Assume we have N replicas of the data

• We synchronously write to W replicas on a write (1 <= W <= N)

  • If W < N, we gossip to make the remaining N-W replicas consistent

• We synchronously read from R replicas on a read (1 <= R <= N)

Describe these using the first two diagrams of Distributed Algorithms in NoSQL Databases

Demonstration

See the Berkeley PBS: Probabilistically Bounded Staleness (with interactive demonstration).