Dynamo is a highly available key-value storage
implementation for large-scale distributed systems. Dynamo relies on the
following properties to be effective:
- Primary key data storage for a simple read/write interface
- Consistent hashing for replication
- Object versioning for consistency
The use of primary key data storage cuts down on the
overhead of a relational database. Dynamo also implements Service Level
Agreements between services in order to maintain latency requirements. Latency
requirements are made to satisfy the 99.9th percentile rather than relying
on a mean or median requirement. Amazon also acknowledges a trade-off between availability
and consistency. In order to improve availability, eventual consistency is
maintained with optimistic replication. This brings up the issue of conflict
management which is handled in data reads in a “last write wins” or
system-specified policy. This reduces the number of writes that are rejected
because of network and node failures. Dynamo is essentially a “zero-hop” DHT in
which a node stores all necessary information to know how to contact nodes with
which it needs to communicate.
Dynamo exposes the functions get() and put() to the system
which are executed using a quorum-like procedure, requiring a number of
responses before propagating. Along with consistent hashing, Dynamo’s
partitioning system assigns each node a set of virtual nodes which determine
which set of data it is responsible for. These nodes then replicate the data
they are responsible for on a number of successor nodes to ensure failure
tolerance. Because of system failure, it is possible to have multiple versions
of the same data in the system simultaneously. Dynamo uses vector clocks to
determine versioning between these data replicas and perform conflict
resolution. Dynamo detects inconsistent data through Merkle trees in which a
tree traversal algorithm is implemented to determine if all keys are
up-to-date.
This contributes to Dynamo’s use as a scalable and highly
available distributed data storage mechanism.
I'm surprised they didn't devote more time to discussing the effects of lessened consistency in their data model. I get the strive for extremely high availability, but lower consistency means there could be repeat issues with popular items selling out while still informing customers that they are available (like what happened with the Xbox, iirc).
ReplyDeleteThey do discuss the collapsing of inconsistent data in 4.4, but they don't really elaborate on attempts to mitigate this factor, or the potential dissatisfaction of customers. And seeing as how the main motivation for this store is customer service, I was disappointed they didn't elaborate more.
Since Dynamo is adopted in the inner processes of Amazon, I think the network is much more reliable than the Internet. This is a design for data center, not DHT, and I think the designers made a right decision on the tradeoffs between performance and consistency.
DeleteI agree with Josiah about the importance of inconsistency. Although, in a distributed system, one of the properties out of CAP has to be sacrificed (a necessary evil), here it is consistency. But, considering the resources Amazon had at their hands, it was a real clever strategy as seen from their impressive successful requests.
ReplyDeleteBut, I am rather more surprised to see no security considerations are assumed or mentioned which limits the applicability of the system in today's environment with serious security issues.
I was also surprised at their confidence in assuming entirely friendly nodes. I guess the rationale is that if a node in the system has been compromised they have bigger problems than key availability.
ReplyDeleteWhy would we need to worry about security? Isn't the internet full of friendly people?
DeleteBut in all seriousness, iirc Dynamo is only used for Amazon's internal processes, therefore a prerequisite is to assume that all notes are "friendly." In that sense, in the case one has a safe environment, Dynamo would be great.
Although authors assumed that they don't consider any security issue, actually we can find some solution for hostile nodes from use of Merkle tree. As you know, a Merkle tree is a hash tree where leaves are hashes of the values of individual keys and all internal and root nodes in the tree are hashes of their respective children. It provides not only several advantages as mentioned in the paper, but also tree authentication. If the root's hash value of certain tree is different from what Dynamo expected, then that node might be investigated friendship as well as causality. With tree authentication, we may be able to implement authentication system to find and block hostile node.
ReplyDeleteThis seems like it's not very fault tolerant to me. The notion that a node is self-contained and doesn't communicate very often is nice, but in the event of multiple node failures, this could prove problematic. I could be (and probably am) wrong, but their fault tolerance mechanisms seem much less focused on restructuring the network as opposed to keeping redundant data backed up. I guess that's another tradeoff.
ReplyDelete