Clocks

Purpose

This note explains why you cannot rely on physical clocks to order events across machines, and how logical clocks and vector clocks recover a useful ordering from causality alone.

Physical clocks

Quartz clocks in commodity machines drift apart, on the order of 30 ppm, largely because oscillator frequency is temperature sensitive. More accurate clocks (atomic, GPS-disciplined) exist but are expensive, so at best a few machines in a datacenter have one.

The deeper problem is that clocks are never perfectly synchronized and message delay is unpredictable. Network latency has a lower bound but no useful upper bound, so a timestamp from another machine tells you less than it appears to.

A practical approach is NTP-style synchronization: query a set of time servers and combine the readings, for example by taking the minimum or an outlier-trimmed average. This gets you to roughly 50 microseconds of skew on a LAN.

Huygens pushed this much further. Its main techniques:

• Timestamp packets in the NIC to avoid OS scheduling noise
• Keep only evenly spaced probe packets in the sample, a heuristic for no queuing delay
• Estimate relative clock phase and drift between pairs of machines
• Feed pairwise estimates into a network-wide correction (the paper calls this network effect estimation)

Huygens achieves clock skew under about 50 ns 99% of the time. That sounds excellent, and it is fine when time is only a hint. It is still not good enough for correctness. At Google’s scale, a billion RPCs per second with a 1% chance of exceeding the 50 ns bound means about 10 million RPCs every second whose timestamps you cannot trust to that precision. Ordering by physical timestamp will be wrong often enough to matter.

Physical clocks cannot order events at scale

Even with state-of-the-art synchronization achieving ~50ns skew, at 1 billion RPCs/sec the 1% tail means ~10 million misordered events per second. Physical timestamps are useful hints but unsafe for correctness.

Virtual clocks

Since physical time cannot be trusted, the goal shifts. Design the system so the ordering of events that can run concurrently does not matter, and the ordering of events that must be sequential is enforced on every possible execution.

Virtual (logical) clocks are a framework for reasoning about event order with no assumptions about clock skew or message delay. They respect causality and rely only on local information.

Happens before

Event $a$ happens before event $b$ if any of these hold:

1. $a$ occurs earlier than $b$ in the same process
2. $a$ is the sending of a message and $b$ is the receipt of that message
3. $a$ happens before some $c$ and $c$ happens before $b$ (transitivity)

This relation is a partial order. The definition comes from Lamport’s 1978 paper.

Happens concurrently

Events $a$ and $b$ are concurrent if neither happens before the other. This is exactly the case where a correct system must not depend on their order.

Logical clock implementation

• Keep a local counter $T$, incremented on every local event.
• Include the current $T$ as a timestamp $T_m$ on every message sent.
• On receiving a message, set $T=\max (T,T_m)+1$.

This guarantees that if $a$ happens before $b$ then $T(a)<T(b)$. The converse fails: $T(a)<T(b)$ does not imply $a$ happened before $b$, since two concurrent events can get any pair of timestamps.

Logical clocks vs vector clocks

Logical clocks give you “if $a\to b$ then $T(a)<T(b)$” but not the reverse. Two concurrent events can have any timestamp ordering. Vector clocks give both directions: $T(a)<T(b)⟺a\to b$. This lets you detect concurrency, which logical clocks cannot.

sequenceDiagram
    participant P1 as Process 1
    participant P2 as Process 2
    participant P3 as Process 3

    Note over P1: T=1 (local event)
    P1->>P2: msg (T=1)
    Note over P2: T=max(0,1)+1=2
    Note over P2: T=3 (local event)
    P2->>P3: msg (T=3)
    Note over P3: T=max(0,3)+1=4
    P3->>P1: msg (T=4)
    Note over P1: T=max(1,4)+1=5
    Note over P1: T=6 (local event)
    P1->>P2: msg (T=6)
    Note over P2: T=max(3,6)+1=7

Vector clocks

Vector clocks strengthen this to a two-way correspondence: $T(a)<T(b)\leftrightarrow a$ happens before $b$, where a vector $T(a)$ is less than $T(b)$ when every entry of $T(a)$ is $\le$ the corresponding entry of $T(b)$ and at least one entry is strictly smaller. If neither vector is less than the other, the events are concurrent. This precise representation of causal relationships is what eventually consistent and causally consistent systems build on, and the same idea shows up in Git and in Amazon’s Dynamo.

The algorithm, for a system of $n$ nodes, keeps a vector C of length $n$ per node:

• On node i, increment C[i] on each local event
• When node i sends a message, it attaches its vector C_m
• On receipt of a message with vector C_m at node i:
  • increment C[i]
  • for each j != i, set C[j] = max(C[j], C_m[j])

sequenceDiagram
    participant N1 as Node 1
    participant N2 as Node 2
    participant N3 as Node 3

    Note over N1: [1,0,0]
    Note over N2: [0,0,0]
    Note over N3: [0,0,0]

    N1->>N2: msg with [1,0,0]
    Note over N2: [1,1,0]

    Note over N3: [0,0,1] (local)

    N2->>N3: msg with [1,1,0]
    Note over N3: [1,1,2]

    N3->>N1: msg with [1,1,2]
    Note over N1: [2,1,2]

    Note over N1,N3: Compare [2,1,2] and [1,1,0]:<br/>N1's event happened after N2's send
    Note over N1,N3: Compare [1,1,0] and [0,0,1]:<br/>Neither ≤ other → concurrent

public class VectorClock {
  private final int[] clock;
  private final int id;
 
  public VectorClock(int id, int n) {
    this.id = id;
    this.clock = new int[n];
  }
 
  // Call on every local event, including sends.
  public void tick() {
    clock[id]++;
  }
 
  // Call on receipt of a message carrying the sender's vector.
  public void receive(int[] senderClock) {
    clock[id]++;
    for (int j = 0; j < clock.length; j++)
      if (j != id)
        clock[j] = Math.max(clock[j], senderClock[j]);
  }
 
  // Returns true iff this clock's event happened before other's.
  public boolean happenedBefore(VectorClock other) {
    boolean strictlyLess = false;
    for (int j = 0; j < clock.length; j++) {
      if (clock[j] > other.clock[j]) return false;
      if (clock[j] < other.clock[j]) strictlyLess = true;
    }
    return strictlyLess;
  }
}

Two events are concurrent exactly when a.happenedBefore(b) and b.happenedBefore(a) are both false.

Related notes

• ordering distributed events
• consistent global state