Vector Clocks and Conflict Detection in Distributed Databases

When two replicas accept writes to the same key independently, how do you know whether one write happened after the other or whether they conflict? Physical timestamps can’t be trusted across machines. Vector clocks answer the question exactly.

The idea

Each replica keeps a counter. A vector clock is a map from replica ID to counter, attached to each version of a value.

  • When replica A updates a value, it increments its own entry: {A:2, B:1} becomes {A:3, B:1}.
  • When a replica receives a version, it keeps the entry-wise maximum of the clocks.

Comparing versions

  • V1 happened before V2 if every entry of V1 is less than or equal to V2’s and at least one is smaller. Then V2 safely replaces V1.
  • If neither is less-or-equal to the other, they are concurrent: a real conflict.

Example: {A:3, B:1} and {A:2, B:2} are concurrent; A and B each updated without seeing the other’s change.

Resolving conflicts

  • Return both versions (“siblings”) to the client and let the application merge them, as Amazon’s original Dynamo did with shopping carts (union of items).
  • Use CRDTs whose merge is automatic (counters, sets, registers).
  • Fall back to last-writer-wins by timestamp, which is simple but silently loses data; Cassandra does this.

Practical issues

Clocks grow with the number of writers; systems use the coordinating server’s ID rather than the client’s, and prune old entries. Lamport timestamps are a single counter: they give a total order consistent with causality but can’t detect concurrency, which is the reason to use vector clocks.

Disclosure: I’m on the team behind Linkjob AI (https://www.linkjob.ai/), an AI assistant for technical interviews.

new edit created at 13 Nov 06:02 updated at 13 Nov 06:02 7 views what is this?