Guide

Distributed systems

Dynamo vector clocks

Dynamo tags each version with a vector clock, a list of counters per writer. If one clock dominates another, the newer version wins. If neither dominates, the writes were concurrent, and both are kept as siblings.

162 of 285 · 2 min read

When two clients write the same key through different nodes, the system needs to know whether one write saw the other. Dynamo answers that with a vector clock on each version. If one version saw the other, the newer one replaces it. If neither saw the other, both are kept for the application to merge.

Concept

Before you start. A vector clock is a list of (node, counter) pairs. Each node bumps its own counter when it writes. Dominates means every counter in one clock is at least as large as the other's, and at least one is larger. Clocks and ordering explains the idea in more depth.

The big idea

Each node keeps its own tally of the edits it has made. A version carries the tallies it has seen. If a new version carries every tally of the old one, it came after it. If two versions each have a tally the other lacks, they happened side by side.

The picture hides a limit. The clock says that two writes were concurrent. It does not say which one should win. That is still a decision for the application.

Walking through it

Two writes start from the same value, v1, written at node A.

put #1 at A:            clock [(A,1)]              value v1
put #2 at A:            clock [(A,2)]              value v2   (saw v1, overwrote it)
put #2' at B from v1:   clock [(A,1),(B,1)]        value v2'  (did not see #2)

Compare [(A,2)] with [(A,1),(B,1)]:
  A: 2 >= 1, but B: 0 < 1  -> not dominated
  A: 1 < 2                 -> not dominated the other way
  Neither dominates, so the writes are concurrent. Keep both as siblings.

The application then merges the siblings. For a cart, it takes the union of items and writes back one value whose clock covers both. Two siblings with clocks {A:3, B:1} and {A:2, B:2} merge into a clock of {A:3, B:2}, which dominates both.

Most systems would stop there and use last-write-wins. Dynamo lets the application choose.

Common mistakes

  • Using vector clocks as timestamps. They order events by causality. They do not tell you real time.
  • Always taking last-write-wins. That silently drops the sibling you did not keep.
  • Treating siblings as a bug. They are how the system keeps data it cannot safely order.

Check yourself

  1. Does [(A,2)] dominate [(A,1)]? Yes. Every counter is at least as large, and A is larger.
  2. Why are [(A,2)] and [(A,1),(B,1)] concurrent? Neither has every counter at least as large as the other. Each one has a tally the other lacks.

Key takeaways

  • A vector clock is a list of counters, one per writer.
  • A clock that dominates another means the newer version saw the older one.
  • Clocks that neither dominate are concurrent, and both versions are kept as siblings.
  • The application or a rule must choose how siblings merge.

Further learning

Next, see how the Dynamo design fits together as one case study, in the distributed key-value store.

For the general theory of logical clocks, see clocks and ordering.

Case study: distributed key-value store

Build a Dynamo-style store from first principles. Consistent hashing places the data, quorums set the consistency, vector clocks detect conflicts, and hints and Merkle trees repair failures.

Time, clocks and ordering

Why wall clocks lie across machines, how skew silently loses writes, and how Lamport clocks, vector clocks, hybrid logical clocks and TrueTime order events you can't time directly.

Conflict resolution and CRDTs

What to do when replicas accept concurrent writes. The options run from last-write-wins and siblings to CRDTs, operational transformation and the sync engines used by collaborative editors.