Ordering without clocks: Lamport timestamps and vector clocks in practice

Two services update the same user record within a few milliseconds of each other. The database resolves the conflict with last write wins, comparing timestamps taken from each service’s system clock.

The service with the clock running 8 milliseconds fast wins, regardless of which write actually happened second. A user’s email change is silently discarded because the machine that processed their password change had drifted forward.

No error is logged. The database did what it was configured to do. It just used a number that does not mean what everyone assumed it meant.

Counting events instead of measuring time

Lamport’s insight, from the 1978 paper on time and clocks in distributed systems, is that ordering does not require knowing when something happened. It requires knowing what could have influenced what.

Each node keeps a counter. Increment before every local event. Send the counter with every message. On receipt, set your counter to one more than the maximum of yours and the one you received.

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

    def local_event(self):
        self.counter += 1
        return self.counter

    def send(self):
        self.counter += 1
        return self.counter          # attach to the outgoing message

    def receive(self, incoming):
        # Adopt the sender's knowledge, then move past it.
        self.counter = max(self.counter, incoming) + 1
        return self.counter

That max is the whole trick. It means a node that receives a message can never afterwards produce a timestamp lower than the one it received, so any event caused by that message sorts after it.

sequenceDiagram
    participant A as Node A
    participant B as Node B

    Note over A: local event, counter 1
    A->>B: message, counter 2
    Note over B: counter was 0,<br/>becomes max(0,2)+1 = 3
    Note over B: local event, counter 4
    B->>A: message, counter 5
    Note over A: counter was 2,<br/>becomes max(2,5)+1 = 6

The guarantee is one directional and it is worth stating precisely. If A caused B, then timestamp(A) is less than timestamp(B). The converse does not hold: a smaller timestamp does not prove causality, because two nodes doing unrelated work produce comparable numbers that mean nothing.

Ties are broken with a node identifier, which gives a total order that every node agrees on. It is arbitrary but consistent, which is often exactly what you need for something like ordering entries in a replicated log.

What the single counter cannot tell you

The limitation matters most in the situation you built this for.

Two writes arrive with Lamport timestamps 7 and 9. Did the second one see the first, or did they happen independently on different nodes that never communicated?

The timestamps cannot answer that. Both cases produce the same numbers. So if you use them for conflict resolution you will resolve a genuine concurrent conflict by picking the higher number, which is the same arbitrary choice as last write wins, just with a counter instead of a clock. Better, because it is not affected by drift, and still arbitrary.

Detecting concurrency requires tracking what each node knew.

Vector clocks answer the concurrency question

A vector clock stores a counter per node. Increment your own entry on a local event, and on receipt take the element-wise maximum before incrementing your own.

class VectorClock:
    def __init__(self, node_id, nodes):
        self.node_id = node_id
        self.clock = {n: 0 for n in nodes}

    def local_event(self):
        self.clock[self.node_id] += 1
        return dict(self.clock)

    def receive(self, incoming):
        for node, value in incoming.items():
            self.clock[node] = max(self.clock.get(node, 0), value)
        self.clock[self.node_id] += 1
        return dict(self.clock)


def compare(a, b):
    a_le = all(a.get(n, 0) <= b.get(n, 0) for n in set(a) | set(b))
    b_le = all(b.get(n, 0) <= a.get(n, 0) for n in set(a) | set(b))
    if a_le and b_le:  return "equal"
    if a_le:           return "a happened before b"
    if b_le:           return "b happened before a"
    return "concurrent"          # the answer Lamport cannot give you

That last branch is the point. Neither vector dominating the other means the two events genuinely happened without knowledge of each other, which is a real conflict requiring a real decision rather than an arbitrary tiebreak.

A = {node1: 3, node2: 1}
B = {node1: 3, node2: 2}   -> A happened before B, no conflict

A = {node1: 4, node2: 1}
B = {node1: 3, node2: 2}   -> concurrent. Two valid values. Decide.

Riak exposed this directly by returning both siblings to the application and letting it merge them, which is honest and unpopular, because most applications do not want to think about it. Being asked to resolve a conflict is annoying and it is considerably better than having one resolved incorrectly and silently, which is what a wall clock gives you.

The cost, which is why people avoid it

A vector clock grows with the number of nodes that have ever written. In a system with a fixed small set of replicas that is fine. In one where every client is a node, it grows without bound, and pruning old entries risks incorrectly reporting concurrent events as ordered.

Dotted version vectors address this by tracking per-key rather than per-node history, which keeps the size proportional to actual concurrency rather than to cluster size. That is what modern Dynamo style systems use, and it is a meaningful improvement over the textbook version.

Hybrid logical clocks are the other direction: combine a physical timestamp with a logical counter, so timestamps stay close to wall clock time while preserving causality when the physical component is ambiguous. That gives you numbers a human can interpret and ordering a machine can trust, which is why CockroachDB and several others use them. It is the pragmatic middle ground between pretending the system clock is trustworthy and buying atomic clocks.

Where this shows up whether you chose it or not

Kafka offsets are a logical clock: monotonic per partition and meaningless across partitions, which is exactly why ordering guarantees stop at the partition boundary.

A database version column used for optimistic locking is a per-row Lamport clock, and the check that a write only succeeds if the version matches is a causality check.

Git commit graphs are vector clocks with better tooling. A merge conflict is the concurrent case, and Git’s decision to surface it rather than pick a winner is exactly the choice Riak made.

The reason I think this is worth understanding rather than delegating is that the failure mode of getting it wrong is silent. A wrong lock produces an error. A wrong ordering produces a database that is internally consistent, fully available, and holding the wrong value, with no signal anywhere that a decision was made badly.

Frequently Asked Questions

What is a Lamport timestamp?
A Lamport timestamp is an integer counter maintained by each node, incremented before every local event and included in every message sent. On receiving a message, a node sets its counter to one more than the maximum of its own value and the value received. This guarantees that if event A causally precedes event B then A has a smaller timestamp, which is enough to build a consistent total order across the system without relying on any physical clock.
What is the difference between Lamport timestamps and vector clocks?
A Lamport timestamp is a single integer and gives a one directional guarantee: causally related events are correctly ordered, but a smaller timestamp does not prove causality, so two unrelated events cannot be distinguished from related ones. A vector clock stores a counter per node, which allows direct comparison: if every element of one vector is less than or equal to the other it happened before, and if neither dominates the other the events were genuinely concurrent and represent a conflict.
Why not just use timestamps from the system clock to order distributed events?
Because clocks on different machines disagree by milliseconds or more, and NTP corrections can move a clock backwards, so an event that happened later can carry an earlier timestamp. Under last write wins conflict resolution that silently discards the newer value with no error. Logical clocks avoid the problem entirely by counting events rather than measuring time, so ordering depends only on message passing rather than on clock synchronisation.

Sources

[ RELATED_LOGS ]

TTFB: -- ms LOAD: -- s PAYLOAD: -- kb