← 博客

Dynamo

Dynamo

virtual nodes

  • compared to basic consistent hashing, each node is assigned to multiple points on the ring

  • advantages

    • If a node becomes unavailable, the load handled by this node is evenly dispersed across the remaining available nodes.
    • When a new node is added to the system, the new node accepts a roughly equivalent amount of load from each of the other available nodes.
    • The number of virtual nodes that a node is responsible for can be decided based on its capacity, accounting for heterogeneity in the physical infrastructure.

  • solved consistent hashing’s problems

    • the random position assignment of nodes on the ring can lead to non-uniform data and load distribution
    • the basic algorithm does not consider heterogeneity in the performance of nodes

replication

  • each object is replicated on N hosts
  • the coordinator server determines which virtual node the key belongs to
  • the coordinator then finds the next N−1 distinct host successors on the ring, skipping duplicate servers
  • these N servers are called the preference list

Data Versioning

  • Dynamo uses eventual consistency and allows stale reads, but ensures that write operations are not lost
  • each modification is treated as a new immutable version, and reconciliation may depend on the client side
    • check whether there is a causal relationship using vector clocks
    • if there is a causal relationship, newer versions subsume previous versions
    • if not, the client side handles the business logic for reconciliation

vector clocks

  • A vector clock is a list of (node, counter) pairs. Every version of every object has its own vector clock
  • For two versions of the same object, if one version’s counters are greater than or equal to the other version’s counters for all nodes, then that version is newer and the older one can be discarded.
  • If neither version dominates the other, the two versions are considered to be in conflict, and the client must merge them.
  • A get may return multiple conflicting versions of the same object, and the client merges them and writes back a reconciled version with put.
  • grow infinitely?
    • theoretically, under what situation would a vector clock keep growing? If many servers coordinate writes to the same object.
    • won’t happen a lot because a key is usually handled by a small set of nodes
    • practically, if network partitions happen and the servers within the preference list become unavailable, it will switch to other servers
    • solution: limit the maximum length of the vector clock

client call

  1. client -> load balancer -> node
  2. use a partition-aware client library that routes requests directly to the appropriate coordinator nodes
  • coordinator: the first node in the preference list
  • after receiving the client’s request, the coordinator forwards it to the replicas
  • read/write operations use the first N nodes in the preference list. If some of them are down, other healthy nodes are selected instead
  • R / N / W
    • N: number of replicas for a key
    • R: for a read operation, at least R nodes must return a response
    • W: for a write operation, at least W nodes must acknowledge the write
    • R + W > N: ensures that a read and a write will intersect at least one common replica
  • if the coordinator ends up gathering multiple versions of the data, it returns all the versions it deems to be causally unrelated.

Hinted Handoff

  • If some nodes in the preference list are unavailable during a write, Dynamo uses sloppy quorum and writes the replica to another healthy node.
  • The temporary node stores the replica together with a hint indicating which node should have stored the data originally.
  • The hinted replica is kept in a separate local store and checked periodically.
  • When the original node recovers, the temporary node sends the replica back to it.
  • After the handoff succeeds, the temporary node deletes the hinted replica so that the total number of replicas remains N.

Merkle tree

  • Dynamo uses Merkle tree to help anti-entropy process and detect inconsistency between replicas

  • leaf nodes are hashes of the values of individual keys

  • parent nodes are hashes of their children

  • the root hash represents the hash of the whole data range

  • synchronization process

    • first compare the root hash of two replicas
      • if the root hash is the same, it means the whole subtree data is the same
      • if the root hash is different, compare the hashes of the children nodes
    • continue this process until reaching the leaf nodes, then the system can find which keys are out of sync

  • advantage

    • only small amount of hash values need to be transferred
    • no need to compare the whole dataset
    • reduce network transfer and disk reads during synchronization