Failure Handling in Dynamo

A core part of Amazon's Dynamo design is the strategy for handling both temporary and permanent node failures. It achieves this primarily through hinted handoff for short-term outages and replica synchronization using Merkle trees for long-term data consistency.

Detailed explanations of some of these concepts can be found in the previous posts of this series on Data Replication and Data Partitioning

To understand failure handling, you first need to understand Dynamo's data replication strategy. Data is replicated across N nodes. When a client wants to write or read data, it requires a certain number of nodes, or a quorum, to respond successfully.

• N: The total number of nodes a piece of data is replicated to.

• W: The write quorum, or the minimum number of nodes that must acknowledge a write for it to be considered successful.

• R: The read quorum, or the minimum number of nodes that must respond to a read request.

For high availability, Dynamo often uses a configuration where R + W <= N. This "sloppy quorum" means the read and write sets don't necessarily have to overlap, which is key to how it handles failures. The list of N nodes responsible for a particular key is called the preference list.

A temporary failure occurs when a node is briefly unavailable due to a network partition, a crash, or a reboot. Dynamo must remain writable even if some nodes in a key's preference list are down. This is where hinted handoff comes in.

1. Write Request: A client sends a write request for a key. The coordinating node identifies the preference list for that key. Let's say the preference list is [Node A, Node B, Node C] and W=2.

2. Node Failure: The coordinator attempts to write to all three nodes but discovers that Node C is temporarily unreachable.

3. Handoff: Instead of failing the write (since it can still meet W=2 with A and B), the coordinator looks for another healthy node on the ring (let's call it Node D). This Node D is not in the original preference list.

4. Hinted Write: The coordinator sends the data to Node D with a "hint" in the metadata. This hint explicitly states that the data actually belongs to Node C. Node D stores this data in a separate, local database.

5. Successful Write: The write is considered successful once W nodes (in this case, Node A, Node B) have responded. The hinted replica on Node D does not count towards the W quorum. This ensures that the write is durable enough according to the configured consistency level.

6. Recovery: When Node C comes back online, Node D (or any node that has a hint for C) detects this via the gossip protocol. Node D then delivers the data it was holding to Node C. Once the transfer is complete, Node D can delete the hinted data.

The primary benefit of hinted handoff is that it maintains write availability and data durability during transient failures. If a client had to wait for all N nodes to be up, the system's availability would be drastically lower.

Permanent failures (or long-term temporary ones) lead to a problem called replica entropy, where replicas become inconsistent over time. A node that was down for an extended period will have stale data. Constantly comparing entire datasets between nodes to find differences would be computationally expensive and consume massive network bandwidth.

Dynamo solves this with an anti-entropy protocol that uses Merkle trees.

A Merkle tree (or hash tree) is a tree in which every leaf node is the hash of an individual key-value pair, and every non-leaf node is the hash of its children. The top node is the root hash.

1. Tree Construction: Each node in Dynamo builds a separate Merkle tree for every key range it is responsible for.

2. Efficient Comparison: To check for inconsistencies between two nodes holding the same key range, they don't need to exchange all the data. Instead, they just exchange the root hash of their respective Merkle trees for that range.

3. Drill-Down Synchronization:

   • If the root hashes of the two trees match, the nodes are in sync. No data transfer is needed.

   • If the root hashes differ, it means an inconsistency exists somewhere in that key range. The nodes then exchange the hashes of the children of the root.

   • They compare these children hashes and recursively traverse down the tree, only exploring the branches where the hashes do not match.

4. Pinpointing Differences: This process continues until they reach the leaf nodes with differing hashes. At this point, they have identified the exact keys that are out of sync.

5. Data Repair: The nodes can then synchronize only those specific keys, drastically minimizing the amount of data transferred for repair.

By using Merkle trees, Dynamo can detect and repair inconsistencies efficiently and quickly without requiring a full data scan, making replica synchronization a scalable background process.

Hinted handoff and Merkle trees are supported by other crucial design choices in Dynamo.

Dynamo nodes need to know the state of other nodes in the cluster (e.g., which nodes are up/down, what data ranges they are responsible for). They share this membership information using a gossip protocol.

• Each node periodically communicates its state and the state of other nodes it knows about to a random peer.

• This information propagates through the cluster in an epidemic-like fashion.

• This decentralized approach is vital for the hinted handoff mechanism, as it allows nodes to quickly detect when a failed node has recovered and is ready to receive the data it missed.

During failures and concurrent writes, conflicting versions of the same data object can arise. Dynamo uses vector clocks to track the causal history of an object.

• A vector clock is essentially a list of (node, counter) pairs associated with a piece of data.

• When a client reads an object, it gets its vector clock. When it writes it back, it includes the clock.

• If the system can determine that one version is a direct ancestor of another, it can automatically resolve the conflict.

• If two versions have diverged (e.g., written to different nodes during a network partition), Dynamo keeps both versions and presents them to the client, pushing the conflict resolution logic (the "merge") to the application layer. This design choice prioritizes write availability over a single, consistent state.