Overview

Dynamo uses vector clocks to compare version histories causally rather than by physical timestamp. A descendant supersedes its ancestor, while incomparable clocks expose concurrent branches for application reconciliation; the merged write records a new successor. Hinted handoff, read repair, and Merkle-tree anti-entropy address different forms of replica divergence, but vector-clock truncation can reduce causal precision. In one reported 24-hour shopping-cart profile, 99.94% of reads saw one version, a workload-specific observation rather than a universal rate.

Learning outcomes

Vector clocks identify causal ancestry without treating physical time as proof that one update saw another.
Concurrent leaves stay visible to the application, which must choose or merge them according to data meaning.
The 99.94% single-version result describes one shopping-cart profile, while repair mechanisms still carry operational cost.

Keywords

Dynamovector clocksversioningconflictsrepaircausality

When Replicas Disagree: Versioning, Conflicts, and Repair

Dynamo's failure model can preserve more than one successful update, so the system needs a way to tell an obsolete copy from a genuinely concurrent one. This chapter follows a stored object's version lifecycle: causal updates extend one history, concurrent updates create branches, and application reconciliation writes a new version that collapses those branches. It also separates the recovery tools for temporary displacement, visible staleness, and longer-lived replica divergence.

From version history to a real conflict

Dynamo treats the result of a modification as a new version of the object. The important question is not simply which version has the larger timestamp. It is whether one version contains the history of the other. To record that relationship, Dynamo associates a vector clock with each version. A vector clock is a set of node-and-counter pairs: it records which coordinating nodes have advanced the object's history and how many updates each has contributed.

The comparison is causal rather than chronological. Suppose a first write creates a version with a clock such as [(A,1)]. A later write that has read that version can extend the history to [(A,2)]. The second version descends from the first, so the first is an ancestor that the system can eventually forget. If another node writes from an older or separate view, the resulting clock may contain information that the first branch does not contain, such as [(A,2),(B,1)] while another branch has advanced through a different node. Neither branch necessarily includes the other's update.

That distinction is what a plain “last write wins” rule cannot express. Physical time can say which request was recorded later, but it cannot prove that the later request saw the earlier one. A client may have been disconnected, a replica may have been unreachable, or two coordinators may have accepted updates concurrently. Dynamo uses the vector clock to preserve the difference between “this version supersedes what I saw” and “this version was created without knowledge of that other branch.”

Follow a single object through a short history. The first coordinator creates D1 with [(Sx,1)]; a later update handled by the same coordinator creates D2 with [(Sx,2)], so D2 supersedes D1. Now a different server handles an update based on a context that includes D2, producing a version whose clock extends the history with that server's counter. If another client had read D2 before a separate server saw the first branch and then wrote its own update, the resulting versions can each contain a different part of the history. When a read gathers those leaves, neither clock dominates the other. The system must keep both until the application writes a value whose context includes the branches it has considered.

This example shows why a causal clock is not a list of “the latest servers.” Its entries are evidence about the path by which the object changed.

Published by DeepMox

FAQ

What do vector clocks tell Dynamo about two versions?

Vector clocks tell Dynamo whether one version’s history contains another’s or whether the versions are causally unrelated. They preserve that distinction but do not decide which concurrent value is correct for the business.

Why can Dynamo return several versions instead of choosing one?

Dynamo returns several versions when their clocks are incomparable, preserving concurrent updates for application reconciliation instead of applying a generic last-write-wins rule. The application can merge or select according to the data’s meaning.

How often did the paper report divergent cart versions?

In the reported 24-hour shopping-cart profile, 99.94% of reads returned one version; 0.00057%, 0.00047%, and 0.00009% returned two, three, and four. These percentages describe that workload and were mainly attributed to concurrent writers.

Previous8 minDynamo Sloppy Quorum and Handoff

Next9 minDynamo Quorum, Latency, and Durability

Dynamo Vector Clocks and Conflicts

When Replicas Disagree: Versioning, Conflicts, and Repair

From version history to a real conflict

FAQ