- Amazon’s Dynamo Key-Value store has emerged as a popular architecture for building Internet scale datastores.
4 April 2014: One of the key characteristics of Dynamo is the use of consistent hashing for horizontal scaling and reliability. Consistent hashing maps/partitions the keys over a single Distributed Hash Table (DHT) ring without requiring any centralised coordination. Dynamo’s pioneering architecture has been used as a blueprint in many other Key Value stores that followed up, e.g. Cassandra, Voldemort, Riak to name just a few.
Dynamo was originally designed to fulfill the very strict set requirements of the Amazon’s shopping cart. Current Key- Value stores, however, have relaxed and generalised the requirements in order to build data management systems that are more flexible, more generic and that can accommodate a wider range of applications and use cases. Some of the improvements proposed by Dynamo- inspired stores are the concepts of buckets as different partitioners. However, as of today, Key-Value stores still work under the constraint that one partitioner, or DHT- ring, has to apply to all data, or keys.
We propose to extend the Dynamo architecture by allowing more flexibility on how Dynamo maps/partitions keys. First, we propose an architecture where multiple concurrent DHT rings can exist, typically one per bucket. This improves the flexibility of how the datastore nodes are utilised, decouples the control plane from the data plane and allows for many domain specific optimizations. Second, we advocate for a hybrid mode where partitioners can use state to map keys to nodes. This allows for fine-grained control on how keys are mapped and allows for complex optimisations.
