Dynamo: Amazon’s Highly Available Key-value Store
August 1, 2023 · 425 words · 2 min · Distributed System Storage
An old paper by AWS, Dynamo has been in the market for a long time, and the architecture has likely evolved since the paper’s publication. Despite this, the paper was selected as one of the SIGMOD best papers of the year, and there are still many valuable lessons to learn.
Design
Dynamo is a NoSQL product that provides a key-value storage interface. It emphasizes high availability rather than consistency, which leads to differences in architectural design and technical choices compared to other systems.
Technical Details
Dynamo has many aspects that may be considered problematic from a technical perspective, such as the NWR (N-W-R) approach. However, given Dynamo’s long track record in production, these issues may have been resolved over time, though the paper is not explicit about this. For now, let’s discuss some of the aspects I found noteworthy:
Data Partitioning
Dynamo uses a consistent hashing algorithm. Traditional consistent hashing employs a hash ring to address the problem of extensive rehashing when nodes are added or removed, but it cannot avoid issues like data skew and performance imbalance caused by heterogeneous machines. In practice, Dynamo introduces virtual nodes into the hash ring, which elegantly solves these problems.
Data Write Challenges
Most storage systems ensure a certain level of consistency during writes, trading off lower write performance for reduced read complexity. However, Dynamo takes a different approach.
Dynamo’s design goal is to provide a highly available key-value store that ensures always writable operations while only guaranteeing eventual consistency. To achieve this, Dynamo pushes data conflict resolution to the read operation, ensuring that writes are never rejected.
There are two key issues to consider here:
-
Data Conflict Resolution: Concurrent reads and writes to the same key by multiple clients can easily lead to data conflicts. Since Dynamo only provides eventual consistency, data on different nodes in the Dynamo ring might be inconsistent.
- Dynamo uses vector clocks to keep track of data versions and merges them during reads to resolve conflicts.
-
Replica Data Gaps: Since Dynamo employs the NWR gossip protocol, it is theoretically possible that none of the nodes hold the complete data set, requiring synchronization between replicas.
- Dynamo uses an anti-entropy process to address this, employing Merkle Trees to efficiently detect inconsistencies between replicas and minimize the amount of data transferred.
The table in the paper clearly shows the aspects considered during Dynamo’s development and the corresponding technical choices. For more information, refer to the original paper.
References
Dynamo’s Implementation and Decentralization