Time: Lamport clocks, vector clocks, TrueTime and HLC

What it is

Four mechanisms for ordering events in a distributed system, because wall-clock timestamps cannot order events across machines and the ways they fail are specific.

LAMPORT CLOCK    one integer per node. Gives a total order that
                 is CONSISTENT with causality: a -> b implies
                 L(a) < L(b). The converse does not hold.

VECTOR CLOCK     one integer per node, per node. Detects
                 concurrency exactly: a -> b iff V(a) < V(b),
                 and incomparable means genuinely concurrent.

TRUETIME         a physical clock API returning an INTERVAL
                 [earliest, latest] with a bounded error. Lets
                 you order by real time, if you wait out the
                 uncertainty.

HYBRID LOGICAL   physical time in the high bits, a logical
CLOCK (HLC)      counter in the low bits. Monotonic, close to
                 wall time, and consistent with causality
                 without special hardware.

Commonly confused with each other in a specific way: Lamport clocks give a total order and cannot detect concurrency; vector clocks detect concurrency and give only a partial order. Choosing between them is choosing which of those you need, and they are not interchangeable.

Also commonly confused: HLC is not TrueTime. TrueTime bounds clock error using GPS and atomic clocks and lets you wait it out. HLC makes no claim about error bounds; it guarantees monotonicity and causal consistency, which is a weaker but much cheaper property.

The problem it solves

Wall-clock timestamps are wrong in two independent ways, and both cause real bugs.

1. SKEW. Two machines' clocks differ. NTP typically keeps them
   within 1-10 ms in a datacenter and can be far worse.
   A write at 10:00:00.005 on node A and one at 10:00:00.002 on
   node B may have happened in the opposite order.

2. NON-MONOTONICITY. NTP corrects by STEPPING the clock, which
   can move it BACKWARDS. So on a single machine, a later event
   can carry an earlier timestamp.

The concrete failures:

LAST-WRITER-WINS with wall clocks
  A node whose clock is 200 ms fast wins EVERY conflict,
  permanently and silently. The "most recent" write is the one
  from the machine with the worst NTP configuration.

LEASE EXPIRY
  A lease granted for 10 s expires early or late depending on
  skew, and a backwards NTP step can make a held lease appear
  expired while its holder still believes it holds it.

LOG CORRELATION
  Merged logs from several services show a response before its
  request, which makes debugging incidents genuinely harder.

CERTIFICATE / TOKEN VALIDATION
  A machine whose clock is minutes off rejects valid tokens or
  accepts expired ones.

"Never order distributed events by wall clock" is the rule, and the mechanisms below are what you use instead.

Mechanics

Lamport clocks

class LamportClock:
    def __init__(self):
        self.t = 0

    def local_event(self) -> int:
        self.t += 1
        return self.t

    def send(self) -> int:
        self.t += 1
        return self.t

    def receive(self, msg_t: int) -> int:
        # Take the max, then advance. This is the whole algorithm.
        self.t = max(self.t, msg_t) + 1
        return self.t

GUARANTEE:      a -> b  implies  L(a) < L(b)
NOT GUARANTEED: L(a) < L(b)  implies  a -> b

So a smaller Lamport timestamp does NOT mean "happened before".
It might mean "concurrent, and this node's counter was lower".

Lamport clocks give a total order (break ties by node id) that never contradicts causality, which is exactly what you need for a replicated state machine: every replica applies operations in the same order, and that order is a plausible one.

They cannot detect concurrency, which is why they are useless for conflict detection.

Vector clocks

class VectorClock:
    def __init__(self, node_id: str):
        self.node = node_id
        self.v: dict[str, int] = {}

    def local_event(self):
        self.v[self.node] = self.v.get(self.node, 0) + 1

    def receive(self, other: dict[str, int]):
        # Element-wise max, then advance our own entry.
        for k, val in other.items():
            self.v[k] = max(self.v.get(k, 0), val)
        self.local_event()

def compare(a: dict, b: dict) -> str:
    a_gt = any(a.get(k, 0) > b.get(k, 0) for k in a | b)
    b_gt = any(b.get(k, 0) > a.get(k, 0) for k in a | b)
    if a_gt and b_gt: return "CONCURRENT"     # a genuine conflict
    if a_gt:          return "A_AFTER_B"
    if b_gt:          return "B_AFTER_A"
    return "EQUAL"

GUARANTEE: a -> b  iff  V(a) < V(b) element-wise
           Incomparable  iff  genuinely concurrent.

That "iff" is the whole value: vector clocks DETECT conflicts
exactly, where Lamport clocks cannot.

The cost is size, and it is the practical limit. One entry per node that has ever written. For a fixed set of replicas, that is small and bounded. For a vector keyed by client, it grows without bound, which is the well-known operational problem, and it is why Dynamo-style systems version by node or region rather than by client.

Riak's approach: cap the vector size and prune the oldest
entries, accepting occasional false-concurrency (a spurious
sibling) in exchange for bounded metadata.

Dynamo's approach: one entry per storage node, not per client.
Bounded by replica count.

TrueTime

Spanner's mechanism, and the one that needs hardware.

TT.now() returns an INTERVAL, not an instant:
    [earliest, latest]   with  latest - earliest = 2ε

ε is the clock uncertainty, bounded by GPS receivers and atomic
clocks in every datacenter, with a documented distribution
historically averaging a few milliseconds and bounded around 7 ms.

The API's three calls:
  TT.now()          -> [earliest, latest]
  TT.after(t)       -> true if t has definitely passed
  TT.before(t)      -> true if t definitely has not

The commit-wait protocol is the interesting part:

To commit a transaction at timestamp s:
  1. choose s = TT.now().latest
  2. do the work
  3. WAIT until TT.after(s) is true, so wait out 2ε
  4. only then release locks and acknowledge

The wait guarantees that when the transaction is visible, s is
definitely in the past for EVERY node, so a later transaction
anywhere in the world gets a larger timestamp.

That wait is why Spanner can offer external consistency (strict serializability) globally, and it costs roughly $2\epsilon$ per commit, which historically has been single-digit milliseconds. You are literally paying for clock uncertainty in latency.

Which is the trade to state: TrueTime buys globally-ordered transactions in exchange for specialised hardware in every datacenter and a commit wait proportional to clock uncertainty. Tighter clocks are directly faster transactions, which is an unusual and memorable property.

Hybrid logical clocks

The mechanism to reach for when you do not have atomic clocks, which is everyone.

@dataclass(order=True)
class HLC:
    physical: int   # milliseconds
    logical: int    # tiebreaker within the same millisecond
    node: str       # total-order tiebreaker

    @staticmethod
    def local(last: "HLC", node: str) -> "HLC":
        wall = now_ms()
        if wall > last.physical:
            return HLC(wall, 0, node)
        # The physical clock did NOT advance, or went BACKWARDS
        # after an NTP step. Advance the logical counter instead.
        # This is what makes the clock monotonic despite NTP.
        return HLC(last.physical, last.logical + 1, node)

    @staticmethod
    def receive(last: "HLC", msg: "HLC", node: str) -> "HLC":
        wall = now_ms()
        p = max(last.physical, msg.physical, wall)
        if p == last.physical == msg.physical:
            l = max(last.logical, msg.logical) + 1
        elif p == last.physical:
            l = last.logical + 1
        elif p == msg.physical:
            l = msg.logical + 1
        else:
            l = 0
        return HLC(p, l, node)

Three properties, and each one matters:

MONOTONIC          never goes backwards, even across an NTP step.
CAUSAL             a -> b implies HLC(a) < HLC(b), like Lamport.
CLOSE TO WALL TIME the physical component stays within the clock
                   skew bound of real time, so timestamps are
                   human-interpretable and comparable to logs.

HLC is the right default for most systems: it gives you Lamport's causal ordering and monotonicity, plus timestamps you can actually read, in 64 or 96 bits, with no hardware. CockroachDB, YugabyteDB and MongoDB all use it.

What it does not give you: bounded error. HLC cannot tell you that a timestamp is definitely in the past everywhere, so it cannot support Spanner's commit-wait protocol. CockroachDB works around this with an uncertainty interval: a read encountering a value within its uncertainty window restarts the transaction with a higher timestamp, which is correct and costs occasional retries where Spanner would have waited instead.

Choosing

Need a total order for a replicated state machine?
    -> LAMPORT (or the Raft log, which is a Lamport clock
       with a leader).

Need to DETECT concurrent writes for conflict resolution?
    -> VECTOR CLOCK, versioned per node or region, never per
       client.

Need globally ordered transactions with real-time guarantees,
and can you deploy GPS and atomic clocks?
    -> TRUETIME. Otherwise no.

Need monotonic, causally-consistent, human-readable timestamps
on commodity hardware?
    -> HLC. This is the answer for almost everything.

A worked example: fixing last-writer-wins

Symptom: in a 5-region key-value store, one region wins
conflicts far more often than chance. Investigation shows its
NTP source is a stratum-3 server that is consistently 180 ms
fast.

WITH WALL CLOCKS
  Every conflicting write from that region wins, permanently
  and silently, because its timestamp is always higher. Users
  in other regions lose edits for no reason anyone can see, and
  the bug is invisible in every metric.

WITH HLC
  The physical component is still 180 ms fast, so that region
  still tends to win *ties in real time*. But:
    - The clock is MONOTONIC, so an NTP correction cannot make
      a later write lose to an earlier one on the same node.
    - Causality is respected: if region B's write was caused by
      reading region A's write, B's HLC is strictly greater
      regardless of skew.
  The systematic bias is reduced to the skew, and the causal
  violations are eliminated entirely.

WITH VECTOR CLOCKS
  The concurrent writes are DETECTED as concurrent rather than
  silently ordered. The system returns both siblings and the
  application decides, which is the honest answer: they really
  were concurrent and no timestamp can say which "should" win.

THE ACTUAL FIX, in order
  1. Fix the NTP configuration. This is not optional and it is
     cheap; the rest is defence in depth.
  2. Switch to HLC so a backwards step cannot reorder writes.
  3. For data where a lost write is unacceptable, use vector
     clocks and surface the conflict rather than hiding it, or
     use a CRDT so there is no conflict to resolve.

The lesson: no clock mechanism makes last-writer-wins safe. HLC removes the causality violations and the non-monotonicity; it does not stop a concurrent write from being discarded. If losing a write is unacceptable, the answer is conflict detection or a CRDT, not a better clock.

Production evidence

Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (CACM 1978) is the foundational paper, and it is where the happened-before relation is defined. It is short and worth reading in full.

Fidge (1988) and Mattern (1989) independently introduced vector clocks, and the exact characterisation of concurrency (incomparable iff concurrent) is theirs.

Corbett et al., "Spanner: Google's Globally-Distributed Database" (OSDI 2012) documents TrueTime, the GPS and atomic clock deployment, the reported $\epsilon$ distribution, and the commit-wait protocol. Its key claim, that tighter clock bounds directly reduce transaction latency, is the memorable one.

Kulkarni et al., "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" (2014) defines HLC, and CockroachDB, YugabyteDB and MongoDB's use of it is the production evidence.

Amazon Time Sync Service with microsecond accuracy and Facebook's published NTP infrastructure work both reflect that clock accuracy is now treated as infrastructure rather than as a given, which has narrowed the gap between commodity clocks and TrueTime.

Riak's vector clock pruning and Dynamo's node-level versioning are the production answers to unbounded vector growth, and Riak's documented experience of client-keyed vectors growing without bound is the cautionary case.

The debate

The case for logical clocks (Lamport, vector): they are correct without any assumption about physical time, so they cannot be broken by NTP misconfiguration, VM migration or a clock step. Correctness that does not depend on operations is worth a lot.

The case for TrueTime: it gives external consistency, meaning the order matches real time, which is what humans actually expect and what makes reasoning about a global database tractable. The cost is hardware and a few milliseconds per commit.

The case for HLC: almost all of TrueTime's practical benefit (monotonic, causal, human-readable timestamps) with none of the hardware, on any machine.

The case for wall clocks: simple, universal, and adequate when nothing depends on cross-machine ordering.

My position: HLC as the default, vector clocks where conflicts must be detected rather than resolved, and never wall clocks for anything ordering-sensitive.

HLC is the default because it costs nothing (64 to 96 bits and a few lines) and removes the two failure modes that actually bite: a backwards NTP step reordering writes on one machine, and causality violations where an effect gets a lower timestamp than its cause. Those are real bugs, they are silent, and HLC eliminates them without special hardware.

The distinction I would insist on is that no clock makes last-writer-wins safe. HLC removes the pathologies; it does not stop a genuinely concurrent write from being discarded, because that is what LWW means. If a lost write is unacceptable, the answer is vector clocks surfacing the conflict or a CRDT that has no conflict to resolve, and reaching for a better clock is solving the wrong problem.

On TrueTime, the position I would take is that it is a legitimate engineering trade and it is not available to most people. Its interesting property is that clock accuracy converts directly into transaction latency, which is unusual and is worth naming. And the gap has narrowed: cloud providers now offer microsecond-accurate time as a service, which makes bounded-uncertainty designs more plausible outside Google than they were in 2012.

On vector clocks, the one thing I would get right is versioning per node or region, never per client, because client-keyed vectors grow without bound and that is a documented production failure rather than a theoretical concern. Riak's pruning, which accepts occasional false concurrency in exchange for bounded size, is the pragmatic version.

And the operational point I would make before any of the algorithms: fix NTP first. A region 180 milliseconds fast winning every conflict is an operations problem, and the clock mechanisms are defence in depth rather than a substitute for correct time configuration.

Follow-up Q&A

"Why can't you just use timestamps?" Two independent failures. Skew, where two machines disagree by anywhere from a millisecond to much worse, so the "later" write may have happened first. And non-monotonicity, because NTP corrects by stepping the clock, which can move it backwards, so even on one machine a later event can carry an earlier timestamp. The concrete consequence with last-writer-wins is that the node with the worst NTP configuration wins every conflict, permanently and invisibly.

"Lamport or vector clocks?" They answer different questions. Lamport gives a total order consistent with causality, so it is what you want for a replicated state machine where every replica must apply operations in the same order. It cannot detect concurrency: a lower timestamp does not mean happened-before. Vector clocks detect concurrency exactly, which is what conflict resolution needs, and give only a partial order. So: Lamport for ordering, vector for detection, and they are not interchangeable.

"What is the practical limit on vector clocks?" Size. One entry per node that has ever written, which is fine for a fixed replica set and unbounded if you version per client. That is a documented production failure, not a theoretical one, which is why Dynamo versions by storage node and Riak caps the vector and prunes the oldest entries, accepting occasional spurious siblings in exchange for bounded metadata.

"What does TrueTime actually give you?" A bounded uncertainty interval rather than an instant, backed by GPS receivers and atomic clocks. That lets Spanner commit at a timestamp and then wait out the uncertainty before releasing locks, so when a transaction becomes visible its timestamp is definitely in the past everywhere and any later transaction anywhere gets a higher one. That is what makes global external consistency possible, and it costs about two epsilon per commit, historically single-digit milliseconds. The memorable property is that tighter clocks directly mean faster transactions.

"What is HLC and why is it the default?" Physical time in the high bits and a logical counter in the low bits. When the physical clock does not advance, or steps backwards after an NTP correction, you advance the logical counter instead, which makes the clock monotonic. It gives Lamport's causal ordering plus timestamps that stay close to wall time, so they are human-readable and comparable to logs, in 64 to 96 bits with no special hardware. That is why CockroachDB, YugabyteDB and MongoDB all use it.

"What can't HLC do?" Bound the error. It cannot tell you a timestamp is definitely in the past everywhere, so it cannot support Spanner's commit wait. CockroachDB handles that with an uncertainty interval instead: a read that encounters a value inside its uncertainty window restarts the transaction at a higher timestamp. Correct, and it trades occasional retries for the wait that Spanner pays unconditionally.

"Does HLC make last-writer-wins safe?" No, and this is the important distinction. HLC removes the pathologies: a backwards NTP step can no longer reorder writes on one node, and an effect can no longer get a lower timestamp than its cause. It does not stop a genuinely concurrent write from being discarded, because discarding one is what last-writer-wins means. If a lost write is unacceptable, the answer is vector clocks surfacing the conflict or a CRDT with no conflict to resolve, and a better clock is solving the wrong problem.

"One region wins every conflict. Walk through the fix." First, check NTP, because the likely cause is that region's clock running fast, and that is an operations fix that is cheap and comes before anything else. Then switch to HLC so a correction cannot reorder writes and so causal relationships are respected regardless of skew. Then, for data where losing a write matters, either vector clocks so the concurrency is surfaced and the application decides, or a CRDT so there is nothing to decide. The clock work is defence in depth; the NTP fix is the actual bug.

Common misconceptions

"Lamport clocks tell you what happened first." A lower Lamport timestamp does not mean happened-before. It gives a consistent total order, not causality detection.

"HLC is TrueTime without hardware." HLC gives monotonicity and causal consistency, not bounded error, so it cannot support commit-wait.

"NTP keeps clocks in sync." It keeps them close and it corrects by stepping, which can move a clock backwards. Monotonicity is not something NTP provides.

"Vector clocks resolve conflicts." They detect them. Resolution is an application-level decision, which is why Dynamo returns siblings.

"A better clock fixes last-writer-wins." It removes the pathologies. Discarding a concurrent write is the definition of LWW, not a bug in the clock.

Interview delivery note

Lead with why wall clocks fail, because the two failure modes are distinct and naming both shows precision: "Wall clocks fail in two independent ways. Skew, so two machines disagree and the later-timestamped write may have happened first. And non-monotonicity, because NTP corrects by stepping, so even on one machine a later event can carry an earlier timestamp. With last-writer-wins that means the node with the worst NTP config wins every conflict, permanently and invisibly."

Separate Lamport from vector by what they answer: "Lamport gives a total order consistent with causality, which is what a replicated state machine needs. It cannot detect concurrency: a lower timestamp doesn't mean happened-before. Vector clocks detect concurrency exactly, which is what conflict resolution needs, and only give a partial order. They're not interchangeable."

Give HLC as the default with its mechanism: "For almost everything I'd use hybrid logical clocks: physical time in the high bits, a logical counter in the low bits, and when the physical clock doesn't advance or steps backwards you advance the counter instead. That's monotonic, causally consistent, and still close enough to wall time to read in a log. Sixty-four bits, no special hardware, which is why CockroachDB and MongoDB use it."

The TrueTime line worth saying, because the property is unusual: "TrueTime returns an interval rather than an instant, and Spanner commits by waiting out the uncertainty before releasing locks, so its timestamp is definitely past everywhere. Which means clock accuracy converts directly into transaction latency: tighter clocks are literally faster commits."

And the distinction that shows you know what the mechanism is for: "but no clock makes last-writer-wins safe. HLC removes the pathologies and it doesn't stop a concurrent write being discarded, because that's what LWW means. If a lost write is unacceptable, you need vector clocks surfacing the conflict or a CRDT, and reaching for a better clock is solving the wrong problem."

The Staff & Team Lead Interview Reference