Back to course home
0% completed
Summary: Dynamo
Summary
- Dynamo is a highly available key-value store developed by Amazon for their internal use.
- Dynamo shows how business requirements can drive system designs. Amazon has chosen to sacrifice strong consistency for higher availability based on their business requirements.
- Dynamo was designed with the understanding that system/hardware failures can and do occur.
- Dynamo is a peer-to-peer distributed system, i.e., it does not have any leader or follower nodes. All nodes are equal and have the same set of roles and responsibilities. This also means that there is no single point of failure.
- Dynamo uses the Consistent Hashing algorithm to distribute the data among nodes in the cluster automatically.
- Data is replicated across nodes for fault tolerance and redundancy. Dynamo replicates writes to a sloppy quorum of other nodes in the system instead of a strict majority quorum.
- For anti-entropy and to resolve conflicts, Dynamo uses Merkle trees.
- Different storage engines can be plugged into Dynamo's local storage.
- Dynamo uses the gossip protocol for inter-node communication.
- Dynamo makes the system "always writeable" by using hinted handoff.
- Dynamo's design philosophy is to ALWAYS allow writes. To support this, Dynamo allows concurrent writes. Writes can be performed by different servers concurrently, resulting in multiple versions of an object. Dynamo attempts to track and reconcile these changes using vector clocks. When Dynamo cannot reconcile an object's state from its vector clocks, it sends it to the client application for reconciliation (the thought being that the clients have more semantic information on the object and may be able to reconcile it).
- Dynamo is able to successfully pull together several distributed techniques such as consistent hashing, p2p, gossip, vector clocks, and quorum, and combine them into a complex system.
- Amazon built Dynamo for internal use only, so no security related issues were considered.
The following table presents a summary of the list of techniques Dynamo uses and their respective advantages:
<table class="tg" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; border-spacing: 0px; border-color: black; --tw-border-opacity:1; margin: 2em auto; table-layout: fixed; width: 800px; color: rgb(61, 61, 78); font-family: "Droid Serif", Georgia, serif; font-size: 18px;"> <tbody style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Problem</td> <td class="tg-1yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Technique</td> <td class="tg-1yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Advantage</td> </tr> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Partitioning</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Consistent Hashing</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Incremental Scalability</td> </tr> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">High availability for writes</td> <td class="tg-yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Vector clocks with reconciliation during reads</td> <td class="tg-yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Version size is decoupled from update rates.</td> </tr> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Handling temporary failures</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Sloppy Quorum and Hinted Handoff</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Provides high availability and durability guarantee when some of the replicas are not available</td> </tr> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Recovering from permanent failures</td> <td class="tg-yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Anti-entropy using Merkle trees</td> <td class="tg-yw4l" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(103, 171, 159); vertical-align: top;">Synchronizes divergent replicas on the background</td> </tr> <tr style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent;"> <td class="tg-1rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; font-weight: bold; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Membership and failure detection</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Gossip-based membership protocol and failure detection</td> <td class="tg-rmb8" style="--tw-shadow:0 0 transparent; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 transparent; --tw-ring-shadow:0 0 transparent; padding: 10px 5px; border-width: 1px; border-style: solid; border-color: black; --tw-border-opacity:1; word-break: normal; hyphens: auto; font-family: Arial, sans-serif; font-size: 17px; overflow: hidden; color: black; background-color: rgb(197, 214, 196); vertical-align: top;">Preserves symmetry and avoid centralized monitoring</td> </tr> </tbody> </table>System design patterns
Here is a summary of system design patterns used in Dynamo:
-
Consistent Hashing: Dynamo uses Consistent Hashing to distribute its data across nodes.
-
Quorum: To ensure data consistency, each Dynamo write operation can be configured to be successful only if the data has been written to at least a quorum of replica nodes.
-
Gossip protocol: Dynamo uses gossip protocol that allows each node to keep track of state information about the other nodes in the cluster.
-
Hinted Handoff: Dynamo nodes use Hinted Handoff to remember the write operation for failing nodes.
-
Read Repair: Dynamo uses 'Read Repair' to push the latest version of the data to nodes with the older versions.
-
Vector clocks: To reconcile concurrent updates on an object Dynamo uses Vector clocks.
-
Merkle trees: For anti-entropy and to resolve conflicts in the background, Dynamo uses Merkle trees.
References and further reading
Mark as Completed