A user changes their email address in a mobile app, notices a typo, and fixes it a fraction of a second later. The two requests land on different servers. Server A handles the first update and stamps it 10:00:00.100. Server B handles the correction, but B’s clock happens to run 300 milliseconds slow, so it stamps the correction 09:59:59.900. The database keeps the value with the latest timestamp. The typo wins. The user’s correction, which really happened later, is silently discarded.
Nothing here is a bug in the usual sense. Each server faithfully recorded its own time. The problem is the assumption that timestamps from different machines can be compared to decide order.
Why physical clocks cannot be trusted for ordering
Every computer keeps time with a quartz oscillator, and every oscillator drifts at a slightly different rate depending on manufacturing and temperature. Protocols such as NTP periodically correct clocks against reference servers, but the correction is only as good as the network. Over the internet, a few milliseconds of disagreement is normal and much more is possible during network trouble or misconfiguration. Within a well-run data centre it can be far smaller, but never zero.
Worse, clocks do not only drift; they jump. When NTP finds a clock running fast it may step it backwards, so a later event on the same machine can get an earlier timestamp. Virtual machines paused and resumed by the hypervisor can see sudden leaps. Leap seconds have historically caused odd behaviour in some systems. So even on a single machine, wall-clock time can go backwards.
Two practical rules follow. To measure a duration, such as a request’s latency or a timeout, use a monotonic clock (System.nanoTime in Java, performance.now in browsers, time.monotonic in Python), which never goes backwards but has no meaning across machines. And to decide which of two events on different machines came first, do not rely on wall-clock timestamps unless you know the bound on clock error and design around it.
Ordering by causality: Lamport timestamps
In 1978 Leslie Lamport published a paper titled “Time, Clocks, and the Ordering of Events in a Distributed System”. Its key observation is that we usually do not need to know exactly when events happened. We need to know whether one event could have influenced another. Event X happened before event Y if they occurred in sequence on the same process, or if X was sending a message and Y was receiving it, or through a chain of such steps.
A Lamport clock is just a counter on each process, following three rules.
- Before each local event, increment the counter.
- When sending a message, include the current counter value.
- When receiving a message, set the counter to the larger of its own value and the received value, then add one.
Walk through it. Process A does two local events, reaching counter 2, and sends a message stamped 2 to process B. B’s counter is 0. On receipt, B sets its counter to max(0, 2) + 1 = 3. Any event B does afterwards will have a number larger than 3, so it is ordered after everything A did before sending. Causality is preserved, regardless of what either machine’s clock says.
The guarantee runs one way only. If X happened before Y, then X’s Lamport timestamp is smaller. But a smaller timestamp does not prove X happened before Y; the two might be unrelated events on different processes that never communicated. To get a total order everyone agrees on, ties are broken by process id. That total order is consistent with causality, which is enough for many purposes, such as ordering operations in a replicated log.
Detecting concurrency: vector clocks
Sometimes you need to know when two events are genuinely concurrent, meaning neither could have known about the other. That is exactly when a conflict may need resolving rather than one write silently overwriting another. Vector clocks provide this.
Each process keeps a vector with one counter per process. A process increments its own entry on each event, sends its whole vector with messages, and on receipt takes the element-wise maximum before incrementing its own entry. Comparing two vectors then tells you everything. If every entry of V1 is less than or equal to the corresponding entry of V2, V1 happened before V2. If V1 is larger in some entries and V2 in others, the events are concurrent.
Example with three replicas A, B and C. A writes a shopping cart, giving [1,0,0]. That syncs to B, which adds an item: [1,1,0]. Meanwhile C, which also received A’s version, removes an item: [1,0,1]. Compare [1,1,0] with [1,0,1]: B’s is larger in the second position, C’s in the third. They are concurrent. The system knows not to pick one blindly; it can keep both versions and merge them, or ask the application to decide. Amazon’s Dynamo paper described this approach for shopping carts, and Riak used variants of it.
The price is size. A vector has one entry per participant, which becomes unwieldy with many clients or replicas, and systems use various techniques to prune or bound it.
Middle grounds used in real databases
Hybrid logical clocks combine a physical timestamp with a logical counter. They stay close to real time, so they are readable and useful for queries like “as of 10 AM”, while still guaranteeing that causally related events are ordered correctly even when clocks disagree. CockroachDB is a well-known user.
Bounded uncertainty is the approach taken by Google’s Spanner. Its TrueTime API returns not a single time but an interval guaranteed to contain the true time, backed by GPS receivers and atomic clocks in Google’s data centres. Before making a commit visible, Spanner waits out the uncertainty, so timestamps can be trusted to reflect real order. The trick works because the uncertainty is kept small; with ordinary NTP-level uncertainty, the waits would be too long.
For everyday application design the lesson is narrower and very practical. Last-write-wins based on server timestamps is fine for data where losing an occasional concurrent update is harmless, such as a “last seen” field. For anything where a lost update matters, use a version number that the database increments, a conditional update, or a single authority that assigns order, rather than asking several clocks to agree.
Written by the RP Strativa Team. Timestamps, clock offsets and replica examples are illustrative.
Leave a Reply