Clocks and ordering

The problem: which edit came first?

Snip's team plan lets several people edit a link's note. Ana in Berlin and Ben in New York both open the note "Spring campaign" and change it within the same second: Ana to "Spring campaign, EU only", Ben to "Spring campaign, ends 31 May". Each region accepts its edit and replicates it to the other.

Which one wins? Comparing wall-clock timestamps picks whichever server's clock happened to read later, which 05.06 Clocks, skew and ordering IDs showed can be wrong by milliseconds or more. But the deeper problem is that neither edit came first. Ana didn't see Ben's edit and Ben didn't see Ana's. They're concurrent, and the honest answer is "both"; the system should notice that, rather than silently drop one.

Happened-before

Leslie Lamport's 1978 paper gave the vocabulary. Event A happened before event B if:

• they're on the same process and A came first, or
• A is sending a message and B is receiving it, or
• there's a chain of those from A to B.

If neither happened before the other, they're concurrent: no information could have passed from one to the other. Lamport stressed that this is only a partial order, and that problems often arise because people aren't fully aware of that. Ana's and Ben's edits are concurrent.

Lamport clocks: a consistent order

A Lamport clock is a counter on each node, with two rules from the paper: increment it between events, and when a message arrives, set your counter higher than both your own value and the timestamp the message carries.

export class LamportClock {
  time = 0;
  tick() {
    return ++this.time; // a local event, or sending a message
  }
  receive(remote: number) {
    this.time = Math.max(this.time, remote) + 1;
    return this.time;
  }
}

This guarantees: if A happened before B, then A's timestamp is smaller than B's. Break ties by node ID, and you get a total order that every node agrees on, which respects causality. It's what lets replicas apply operations in the same order.

What it can't do is the reverse. If A's timestamp is smaller, A may have happened before B, or they may be concurrent. A Lamport clock can't tell you that two edits conflicted.

Vector clocks: spotting concurrency

A vector clock keeps one counter per node. Each node increments its own entry on a change, and a merge takes the maximum of each entry. Comparing two vectors gives one of four answers:

type VC = Record<string, number>;

export const vcTick = (vc: VC, node: string): VC => ({ ...vc, [node]: (vc[node] ?? 0) + 1 });

export const vcMerge = (a: VC, b: VC, node: string): VC => {
  const out: VC = { ...a };
  for (const [n, c] of Object.entries(b)) out[n] = Math.max(out[n] ?? 0, c);
  return vcTick(out, node);
};

/** "before", "after", "equal" or "concurrent". */
export function vcCompare(a: VC, b: VC) {
  let less = false;
  let more = false;
  for (const n of new Set([...Object.keys(a), ...Object.keys(b)])) {
    if ((a[n] ?? 0) < (b[n] ?? 0)) less = true;
    if ((a[n] ?? 0) > (b[n] ?? 0)) more = true;
  }
  return less && more ? "concurrent" : less ? "before" : more ? "after" : "equal";
}

Run on the note: the original version is {eu: 1}; Ana's edit becomes {eu: 2} and Ben's {eu: 1, us: 1}. Comparing the original with Ana's gives before; Ana's with Ben's gives concurrent; and a version that merges both gives after either. So the store can keep both versions (often called siblings) and let the app or a person resolve them, here by showing Ana and Ben a conflict, or by merging the two notes.

The cost is size: one entry per node that has written the key. Systems trim old entries or use refinements such as dotted version vectors, which Riak recommends over plain vector clocks.

Hybrid logical clocks: logical, but close to real time

Logical clocks order events but have nothing to do with real time, so you can't ask "what was the value at 14:00?". Wall clocks relate to real time but don't respect causality. A hybrid logical clock (HLC) combines them: it follows the physical clock when it can and adds a logical counter when events happen faster than the clock ticks or arrive "from the future". The 2014 paper that introduced it shows the value stays close to NTP time and fits in a 64-bit timestamp, while still capturing causality like a Lamport clock.

CockroachDB uses HLC timestamps for transactions. It also relies on a configured maximum clock offset: reads treat values within that window as uncertain and may restart, and a node whose clock drifts beyond the limit shuts itself down rather than risk violating consistency.

What to use when

Recap

Interview questions