Time, ordering and IDs

Two questions that sound like one

Almost every distributed design silently asks one of two questions. The first is what time is it?, wanted for expiry, rate limits, logs and "created at". The second is what happened before what?, wanted for conflict resolution, replication order and transactions. On one machine the answers coincide: read the clock, and the later number happened later. Across machines they separate, because each machine has its own clock, and no message can tell one machine what another's clock says right now. The replication chapter's dry run already showed the cost: a write that really came 20 ms later lost a last-write-wins comparison because its node's clock ran 80 ms slow. This chapter is about that failure and its four remedies: sturdier use of physical clocks, logical clocks, hybrid clocks, and clocks that publish an error bar. It ends with the practical problem that depends on all of them, generating identifiers.

Two clocks in every computer, for different jobs

Operating systems expose two kinds of clock, and mixing them up is a classic bug. On Linux the real-time clock (CLOCK_REALTIME) measures wall-clock time. It is settable, and the man page says it is affected by discontinuous jumps in the system time and by the incremental adjustments of NTP. The monotonic clock (CLOCK_MONOTONIC) is not settable and is not affected by discontinuous jumps, though it is still slewed (sped up or slowed down slightly) by NTP, and it does not count time while the system is suspended. Use the monotonic clock to measure a duration on one machine: a timeout, a latency, the age of a cache entry. Use the real-time clock only when you need a calendar time, and never assume two machines' real-time clocks can be compared exactly.

How wrong can a clock be?

Quartz oscillators drift. Google's Spanner paper applies a drift rate of 200 microseconds per second as its conservative worst-case bound for a server clock, which is not a small number:

NTP keeps drift in check by polling servers and slewing the clock, and it works well, but not perfectly. RFC 5905 (NTPv4) says that typical primary servers are precise within a few tens of microseconds, typical clients on fast LANs within a few hundred microseconds, and, with poll intervals up to 36 hours, within a few tens of milliseconds. A cloud provider's own time service narrows this: Amazon runs the Amazon Time Sync Service from satellite-connected and atomic reference clocks in each Region, and it offers ClockBound, a daemon and library that reports the instance's clock error so you can check whether a timestamp is in the past or future relative to your clock. Across a fleet you should still budget for tens of milliseconds of disagreement in the worst case, and for rare, much larger excursions when a time source fails or a VM is paused and resumed.

Leap seconds are a special hazard because UTC inserts an extra second and software must decide what the clock shows. The NTP protocol has a two-bit leap indicator warning that the last minute of the day will have 61 or 59 seconds. Google avoids the step by smearing: it spreads the extra second linearly over 24 hours, noon to noon UTC, so smeared time is just under 0.5 s behind UTC when the leap second begins and just under 0.5 s ahead when it ends, agreeing with UTC again at both ends of the window, with a frequency change of about 11.6 ppm (1 second in 86,400 is 11.57 parts per million). The consequence is that two machines can legally disagree by up to about half a second around a leap event if one smears and the other does not, which is why Amazon cautions against mixing smeared and non-smeared sources in one time client. The most recent leap second was at the end of 2016, and a 2022 resolution of the General Conference on Weights and Measures commits to abandoning them by or before 2035, as Amazon's documentation notes, but old data, old software and replayed history still carry the hazard.

Process pauses: the clock is right but the program is not looking

Even a perfect clock does not help if the program stops looking at it. A garbage-collection pause, a VM migration, a laptop lid or a page fault storm can freeze a process between "check that my lease is valid" and "act on it". When it resumes, the lease may have expired and another node may hold the lock, yet this process still believes it is the leader. The consensus chapter explains the cure, the fencing token, which moves the check to the resource. The lesson for time is the same: never base a safety property on "no more than X milliseconds can pass between these two lines".

Logical time: order without clocks

Lamport's 1978 paper begins from a different question. Instead of asking when an event happened, ask whether it could have influenced another. He defines happened-before: within one process, earlier events precede later ones; sending a message precedes receiving it; and the relation is transitive. Two events related by neither are concurrent. This is a partial order, not a timeline: it says only what could have caused what.

A Lamport clock is a counter per process that obeys the paper's Clock Condition: if event a happened before b, then C(a) < C(b). The rules are short: increment before each event; stamp every message with the counter; on receipt set the counter to the larger of its own and the message's, plus one. Breaking ties by process id turns the partial order into a total order that every node can compute alone. The catch is in the paper's own note: the converse does not hold. C(a) < C(b) does not mean a happened before b, so a Lamport clock cannot tell a cause from a coincidence.

A vector clock keeps one counter per process instead of one in total. Each process increments its own slot on every event and, on receipt, takes the element-wise maximum with the message's vector. Compare two vectors: if every slot of V1 is less than or equal to V2's, (and the two are not identical) then V1 happened before V2; if each is larger somewhere, the events are concurrent. That recovers exactly what the Lamport clock loses. The price is a vector the size of the number of writers. The Dynamo paper used vector clocks to detect conflicting versions of a key and returned both to the application, and it truncated the clock when it grew past a threshold (its example is 10 pairs), accepting that the ancestry check can blur.

Dry run: the six events in the figure

Hybrid logical clocks: timestamps that look like time and respect causes

Lamport and vector clocks cannot answer "what was the state at 14:00?", because their numbers are unrelated to the wall clock. Physical clocks answer that but can invert causes. The hybrid logical clock (HLC), proposed by Kulkarni and colleagues, keeps a pair (l, c): l is the largest physical time the node has seen, from its own clock or from any message, and c is a counter that breaks ties when l does not move. It fits in 64 bits, stays close to the physical clock, and is built to coexist with NTP. The paper's rules are:

• Local or send event: set l to the larger of the old l and the physical time. If l did not change, increment c; otherwise reset c to 0.
• Receive event: set l to the largest of the old l, the message's l and the physical time. If l equals both the old l and the message's l, c is the larger of the two c values plus one; if it equals only the old l, increment c; if it equals only the message's l, take the message's c plus one; otherwise reset c to 0.

Compare timestamps as pairs, l first, then c. The effect is that a node whose clock is slow never produces a timestamp lower than something it has already heard about.

Dry run: the slow clock, when the later write is causally after

This is a variant of the replication chapter's scenario in which B has already received A's update before it writes, so B's write is causally later and its stamp is 9.980 (true time 10.060) instead of the concurrent 9.940.

HLC fixes a causally later write receiving an earlier stamp. It does not fix truly concurrent writes, as in the replication chapter, where B never saw A's write: one of the two still has to lose or be merged. CockroachDB is a real user. Its documentation describes each node's HLC as a physical part always close to local wall time plus a logical part for ties, and warns that clock skew beyond the configured maximum offset can violate single-key linearizability between causally dependent transactions (serializability at SERIALIZABLE isolation holds regardless). A node whose clock is out of sync with at least half of the others by 80% of the maximum offset shuts itself down, so a bad clock cannot silently corrupt the order.

TrueTime: a clock that reports its own error

Spanner takes the opposite route to logical clocks: make physical time trustworthy enough, and expose its uncertainty. TrueTime's TT.now() returns an interval, [earliest, latest], that is guaranteed to contain the true time. Half the width is the error bound ε, so the interval is 2ε wide. Google's time masters use GPS receivers and atomic clocks (it calls the atomic-clock masters "Armageddon masters"), and each machine's daemon polls several of them, rejects liars, and advertises a slowly growing uncertainty between polls. In the paper, ε is typically a sawtooth varying from about 1 to 7 ms over each 30-second poll interval, which is 4 ms most of the time. The arithmetic is visible: 30 s × 200 µs/s = 6 ms of drift allowance, which accounts for the sawtooth between 0 and 6 ms, and the remaining 1 ms is communication delay to the time masters.

The protocol follows. A read-write transaction picks a commit timestamp s no earlier than TT.now().latest, then the coordinator waits until TT.after(s) is true before applying the commit and replying. By then s is in the past on every machine, so any transaction that starts after the client hears "committed" gets a larger timestamp. That is Spanner's external consistency, the strict serializability described in the consistency models chapter. The expected wait is at least 2ε, and the paper says it is typically overlapped with the Paxos communication; in its one-replica experiments commit wait was about 5 ms and Paxos latency about 9 ms. It also explains why TrueTime matters for the engineering trade: Spanner pays with specialised time hardware; CockroachDB, running on ordinary NTP clocks, accepts a configured maximum offset and restarts reads that fall inside an uncertainty interval, and its documentation says that skew beyond the bound can break single-key linearizability between causally dependent transactions.

Generating IDs: uniqueness, order and no coordination

Every row, message and event needs an identifier, and generating one is a time-and-ordering problem in disguise: you want values that are unique without a round trip to a central allocator, roughly sortable by creation time so indexes stay cheap, and compact. No scheme gets all three for free.

Dry run: what the bit counts allow

The hazards, which are all clock hazards

• The clock goes backwards. A time-based ID generator that sees an earlier clock reading may reuse a timestamp and sequence, producing a duplicate. The archived Snowflake design refuses to generate IDs until the clock passes the last time it used. Do the same: stall, or fail loudly, never reuse.
• Two generators share a machine id. Snowflake-style schemes assume each worker id is unique. Assign ids from a coordination service with a lease, or from a fixed configuration, not from hostnames that can repeat.
• Order is approximate across machines. IDs from different machines are sorted only to within their clock skew. If two events must be ordered exactly, use a per-entity sequence or a log, not the timestamp inside an ID. This is the same limit as last-write-wins.
• IDs leak information. A sequence reveals volume, a time-based ID reveals creation time. Do not use either as a secret or an access token.
• Index locality. Random primary keys cause random page inserts in a B-tree, as the storage engines chapter describes; time-prefixed IDs append at the right-hand edge. Conversely, a monotonically increasing key makes all inserts hit one shard in a range-partitioned table, a hot-spot the sharding chapter covers.

Choosing

Recognizing it in an unseen problem

• Signals: "last write wins", "order of events", "timestamps", "unique ID", "expires at", "leader lease", "audit log". Each needs you to say whose clock and how wrong it can be.
• The naive design uses now() on each server for ordering. Ask yourself what happens when one server's clock is 80 ms slow, or steps back a second.
• Quantify the error budget. Drift of 200 µs a second is 6 ms per 30 seconds and 17 seconds a day without correction; NTP over the Internet gives tens of milliseconds; TrueTime gives 1 to 7 ms with special hardware. Pick a mechanism whose error is below the gap you need to resolve.
• Pick the weakest tool that works: a per-entity counter if one writer owns the entity, version vectors if you must detect concurrency, an HLC if you need time-like stamps, a consensus log or TrueTime only if you need a global order.
• For IDs state the layout and the failure mode: bits for time, worker and sequence, how worker ids are assigned, and what happens when the clock goes back.
• The pitfall to avoid: using timestamps for ordering and also for expiry without noticing they need different clocks, wall for the first and monotonic for the second.