Dynamo: Amazon’s Highly Available Key-value Store

Question 1

Problem: Partitioning
Technique: ___

Answer 1

Consistent hashing

Question 2

Technique: Consistent hashing
Advantage: ___

Answer 2

Incremental scalability

Question 3

Problem: High availability for writes
Technique: ___

Answer 3

Vector clocks with reconciliation during reads

Question 4

Technique: Vector clocks with reconciliation during reads
Advantage: ___

Answer 4

Version size is decoupled from update rate

Question 5

Problem: Handling temporary failures
Technique: ___

Answer 5

Sloppy Quorum and hinted handoff

Question 6

Technique: Sloppy Quorum and hinted handoff
Advantage: ___

Answer 6

Provides high availability and durability guarantees when some replicas are unavailable

Question 7

Problem: Recovering from permanent failures
Technique: ___

Answer 7

Anti-entropy using Merkle trees

Question 8

Technique: Anti-entropy using Merkle trees
Advantage: ___

Answer 8

Synchronizes divergent replicas in the background

Question 9

Problem: Membership failure and detection
Technique: ___

Answer 9

Gossip-based membership protocol and failure detection

Question 10

Technique: Gossip-based membership protocol and failure detection
Advantage: ___

Answer 10

Preserves symmetry and avoids using a central registry for node membership and availability information

Question 11

Incremental scalability

Answer 11

scale out one node at a time with minimal impact on system & operators

Question 12

Symmetry

Answer 12

each node has the same responsibilities as its peers

Question 13

Decentralization

Answer 13

an extension of symmetry, favouring peer-to-peer techniques over centralized control

Question 14

Design consideration: heterogeneity

Answer 14

work distribution must be proportional to the capabilities of individual servers

Question 15

Random position assignment in consistent hashing leads to ___

Answer 15

non-uniform data and load distribution

Question 16

Consistent hashing ignores ___

Answer 16

heterogeneity in the performance of individual nodes

Question 17

Dynamo addresses problems with consistent hashing by ___

Answer 17

assigning each physical node to multiple points in the ring using virtual nodes

Question 18

When a (virtual) node becomes unavailable:

Answer 18

the load handled by this node is evenly dispersed across the remaining available nodes

Question 19

When a new / newly available (virtual) node joins:

Answer 19

the new node accepts a roughly equivalent amount of load from each of the other available nodes

Question 20

Using virtual nodes takes advantage of heterogeneity by:

Answer 20

assigning a proportional amount of virtual nodes to the physical node based on its capacity

Question 21

Dynamo’s view of data versions

Answer 21

Dynamo treats each modification as a new and immutable version of the data

Question 22

syntactic reconciliation

Answer 22

system determines the authoritative version of the data (i.e. timestamps)

Question 23

semantic reconciliation

Answer 23

client collapses multiple branched versions of the data into one version

Question 24

vector clock

Answer 24

list of (node, counter) paris associated with every version of every object

Question 25

hinted handoff

Answer 25

data intended for node A is instead stored on node B, with a “hint” that its intended recipient is A, and can be stored on A once it recovers

Question 26

sloppy quorum

Answer 26

all read and write operations are performed on the first N healthy nodes from the preference list