Dynamo (storage system)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Dynamo is the name given to a set of techniques that when taken together can form a highly available key-value structured storage system[1] or a distributed data store.[2] It has properties of both databases and distributed hash tables (DHTs). Amazon DynamoDB derives its name from Dynamo, but is not at all related in any other way. Dynamo has a multi-master design requiring the client to resolve version conflicts whereas DynamoDB has a single master design.

Principles of Dynamo Systems[edit]

  • Incremental scalability: Dynamo should be able to scale out one storage host (henceforth, referred to as “node”) at a time, with minimal impact on both operators of the system and the system itself.
  • Symmetry: Every node in Dynamo should have the same set of responsibilities as its peers; there should be no distinguished node or nodes that take special roles or extra set of responsibilities. In our experience, symmetry simplifies the process of system provisioning and maintenance.
  • Decentralization: An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control. In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
  • Heterogeneity: The system needs to be able to exploit heterogeneity in the infrastructure it runs on. e.g. the work distribution must be proportional to the capabilities of the individual servers. This is essential in adding new nodes with higher capacity without having to upgrade all hosts at once.

Techniques Used in Dynamo Systems[edit]

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.

Implementations[edit]

See also[edit]

References[edit]

  1. ^ Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007
  2. ^ Decandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, W. (2007). "Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles - SOSP '07". p. 205. doi:10.1145/1294261.1294281. ISBN 9781595935915.  |chapter= ignored (help) edit

Further reading[edit]