Entire website open-sourced at: https://github.com/grokit/website_grokit_ca/. Feel free to make pull requests if you find mistakes!
Dynamo is a key-value NoSQL database service that is designed for high availability and elastic scalability at the cost of lenient consistency. It offers an alternative to relational databases who are constrained by their requirement to support ACID properties which do not scale well horizontally.
The paper goes over a number of concepts that are useful to generic large-scale distributed systems. It is interesting even if you are not interested in using Dynamo because it explains a lot of distributed computing recurring themes.
Link to paper: http://dl.acm.org/citation.cfm?id=1294281, full pdf.
Keywords: key-value stores, large scale distributed systems.
Higher throughput for read/writes than relational database.
This is mainly due to using “eventual consistency” where a write returns before its data has been replicated to all N copies, allows to return from a read even if the queried node does not have the most recent copy of the data. This is a tradeoff for more availability at the cost of consistency.
Information is replicated on N servers in M datecenters, N and M being tunable.
Can use nodes of heterogeneous capabilities (will only handle the load it can, allows multiple hardware generations in the same cloud).
Elastic and distributed by default. You can add/remove nodes to the system without affecting the unchanged nodes or system's availability. There is no theoretical limit to the number of nodes you can have -- the system can scale practically infinitely.
Only supports get() and set(key, metadata, data) operations (as opposed to complex queries in relational databases).
Requires that client implements merge logic because of the lax consistency requirements.
Possible to read stale data, no concept of transaction.
Duplication logic of key-values-pairs using Merkle trees is tricky and can have awful performance on node join/leave a node set that share a key if not finely tuned. Getting this right is not a simple matter.
In a network of N nodes that want to know each other state, a naive approach is for all nodes to broadcast its status to all node for all status changes. However, as the number of nodes grows, this approach does not scale.
A gossip approach uses statistical propagation; for example, every second, every node selects another node randomly and sends its state. There are thorough mathematical underpinnings to consider (see ), but intuitively this generates a finite amount of traffic as N increases (N communications every second, instead of N square for the previous algorithm). Also intuitively, if the rate of change is slow enough, all nodes end-up with up-to date information on all nodes. Of course, this is another case of eventual consistency as it can take a lot of time for information to propagate to other nodes.
It was not clear to me at first the difference between Dynamo and Amazon S3. Dynamo is for storing/retrieving small objects at very high throughput rates whereas Amazon S3 is used for huge objects that are not queried very frequently.
How to structure data for a service when relational queries are not available. Dynamo does support relational and non-relational DB for storage, when it uses SQL does it offer queries? Aren't SQL queries fundamentally incompatible with the consistent-hashing-node-partition used in Dynamo?