Vector Clocks

How distributed systems tell whether one event caused another or happened independently, without trusting wall clocks: Lamport clocks, vector clocks, version vectors, and the alternatives databases chose.

Overview

In one process, the order of events is obvious: one line of code runs after another. Across machines it is not. Each machine has its own clock, clocks drift apart, and a message can take a millisecond or a second to arrive. Two writes stamped 10:00:00.120 and 10:00:00.118 on different machines tell you almost nothing about which came first, or whether either one knew about the other.

What systems usually need is not the exact time but causality: could event a have influenced event b? Leslie Lamport defined this in 1978 as the happens-before relation, and showed how simple counters, Lamport clocks, respect it. Colin Fidge (1988) and Friedemann Mattern (1988 workshop, published 1989) independently described vector clocks, which capture it exactly: comparing two vector timestamps tells you whether one event happened before the other or whether they are concurrent.

That last answer matters in replicated databases. If two writes to the same key are concurrent, neither one should silently replace the other; the system has a conflict to keep or merge. Amazon's 2007 Dynamo paper used vector clocks for exactly this, and Riak still does, in a refined form.

What you will be able to do

  • Define happens-before and concurrency, and explain why wall-clock timestamps cannot decide them.
  • Apply the Lamport clock and vector clock rules, and compare two vector timestamps.
  • Explain how version vectors detect conflicting writes in a Dynamo-style store, and what siblings are.
  • Describe the costs (size, siblings, false conflicts) and the fixes: dotted version vectors and truncation.
  • Choose between vector clocks, last-write-wins, hybrid logical clocks and CRDTs for a given design.

Key concepts

  • Happens-before
  • Concurrent events
  • Lamport clocks
  • Vector clocks
  • Version vectors
  • Siblings
  • Dotted version vectors
  • Clock truncation
  • Last-write-wins
  • Hybrid logical clocks

Interview questions

  • How do vector clocks decide whether two events are ordered or concurrent?
  • What is the difference between Lamport clocks and vector clocks?
  • How does a Dynamo-style database use version vectors to handle conflicting writes?
  • What are siblings, and how do dotted version vectors reduce them?
  • Why did Cassandra choose last-write-wins instead of vector clocks?
  • What is a hybrid logical clock, and when would you use it instead of a vector clock?
  • How do you keep vector clocks from growing without limit?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio