Techniques Used in Dynamo Systems
| Problem | Technique | Advantage |
|---|---|---|
| dataset partitioning | Consistent Hashing | Incremental, possibly linear scalability in proportion to the number of collaborating nodes. |
| highly available writes | Vector Clock or Dotted-Version-Vector Sets, reconciliation during reads | Version size is decoupled from update rates. |
| handling temporary failures | Sloppy Quorum and Hinted Handoff | Provides high availability and durability guarantee when some of the replicas are not available. |
| recovering from permanent failures | anti-entropy using Merkle tree | Can be used to identify differences between replica owners and synchronize divergent replicas pro-actively. |
| membership and failure detection | gossip-based membership protocol and failure detection | Avoids having a centralized registry for storing membership and node liveness information, preserving symmetry. |
Consistent hashing: See memcached, they used the same hashing algorithm.
Vector Clock: see here for more information.
Sloppy Quorum and Hinted handoff:
In this method during writes if we find that the destination nodes are down we store a "hint" of the updated value on one of the alive nodes. Then when these down nodes come back up the "hints" are pushed to them thereby making the data consistent
anti-entropy using Merkle tree:
Each node maintains a separate Merkle tree for each key range (the set of keys covered by a virtual node) it hosts. This allows nodes to compare whether the keys within a key range are up-to-date. In this scheme, two nodes exchange the root of the Merkle tree corresponding to the key ranges that they host in common. Subsequently, using the tree traversal scheme described above the nodes determine if they have any differences and perform the appropriate synchronization action. The disadvantage with this scheme is that many key ranges change when a node joins or leaves the system thereby requiring the tree(s) to be recalculated
gossip-based membership protocol:
Read full article from Dynamo DB | miafish
No comments:
Post a Comment