Dynamo: Amazon's Highly Available Key-Value Store

Dynamo was developed in Amazon to provide a highly available, scalable distributed data store for applications that need high reliability.  Usually, traditional dbmses are used as data stores, but Amazon determined that most applications only need simple key value access.  Dbmses have a lot of extra querying capabilities and also favor consistency over availability and scalability.  Dynamo provides an "always on" experience because the shortest unavailability could still have significant financial impact.  It is always writable, with conflict resolution during reads, and not writes.  At the base, Dynamo uses consistent hashing with virtual nodes.  Data is replicated to the first hashed node, and then the N-1 next available successors.  Each update creates a new version of the data for vector clocks, and for conflict resolution on the read.  The application developers can configure an instance with varying number of N, read quorum and write quorum, in order to achieve different levels of consistency and availability.  Hinted handoff protocol is used for nodes receive updates for data it is not responsible for, by trying to send the updates back to the original nodes.  Experiences show that the 99.9 percentile is around 200 ms, but there is a lot of variability.  Buffering helps reduce the variability, at the cost of durability.  Experiments also show that inconsistencies do not happen very frequently.

The future will have to rely more on distributing data across many different datacenters.  Datacenters are becoming more prevalent, and will be the "computers" of the future.  How will the Dynamo model map to many geo-diverse datacenters?  It will still be important for low, predictable latencies, but they will be more difficult to achieve when replicas could be all over the world.  Highly scalable and distributed data stores will have to be able to run across many datacenters.  Most likely, they will still be asynchronously replicated to remote sites to preserve latencies, but new techniques will be developed to provide consistency for applications which need it.  Also, Dynamo is only a key value store.  Future datastores will need to provide more rich APIs in order to support other use cases, such as analytics.