Timestamp Oracles and Global Transaction Order

A timestamp-based transaction system needs a total order on transactions, and it needs the order to be consistent with the order in which clients observe effects. A single-node database gets both from a counter incremented under a lock. A distributed system has neither the lock nor the counter, and every attempt to supply them is an attempt to reconcile two different things: the order the system assigns, and the order that actually happened.

Two properties that look like one

The first property is serialisability: the system’s output must be explainable by some serial order of the transactions. The assigned timestamps define that order, and as long as all nodes agree on the timestamps, the order is internally consistent.

The second property is real-time order, or external consistency: if transaction A committed before transaction B started, in real time, then B must be ordered after A. This is the property that makes a system’s behaviour intuitive, because a client that reads a value it just wrote must see it.

A timestamp oracle can give the first property cheaply. A single service handing out monotonically increasing numbers makes every transaction’s timestamp unique and comparable, and every node’s version checks are consistent. It does not automatically give the second property, because the oracle’s numbers are not tied to real time: a transaction that committed at oracle value 500 may have started after one that committed at 501, if the second one requested its timestamp earlier. Serialisability holds, external consistency does not.

Tying the order to real time requires the timestamps to reflect something about when things actually happened, which means involving physical clocks and the error bounds they carry.

The oracle’s shape and its availability cost

A timestamp oracle is a service that, on request, returns a value larger than any value it has previously returned, and guarantees that it will never return a smaller value later. The guarantee requires durability if the oracle can restart, because a restarted oracle that forgets its last value will hand out timestamps that are lower than ones already in use, which breaks monotonicity and silently corrupts version comparisons.

That durability requirement is the oracle’s weak point. Each request must either be persisted or be recoverable from a value that is persisted at a coarser granularity. Persisting every request makes the oracle a write bottleneck with the throughput of its log; persisting in blocks of values means a restart loses the current block and must skip ahead, which wastes timestamp space but preserves monotonicity.

The availability cost is the same as any centralised service: if the oracle is unreachable, no transaction can start, because no transaction can get a timestamp. That is a hard dependency on a single component, and the mitigation is replication, which turns the oracle into a consensus problem and gives it the latency of a majority round trip. At that point the timestamp is no longer cheap: every transaction pays a consensus round trip before it does any work.

Systems avoid the per-transaction cost by batching. A node requests a block of timestamps and hands them out locally, which makes timestamp acquisition a local operation for most transactions. The block boundary is the constraint: a node that has exhausted its block must request another, and during the request it cannot start transactions. Large blocks reduce the frequency of the stall but increase the number of timestamps wasted when a node restarts, and they widen the window in which a node’s timestamps are ahead of the oracle’s durable value, which matters for recovery.

Hybrid logical clocks

The hybrid logical clock is the design that gets most of real-time ordering without an oracle round trip per transaction. It combines a physical clock reading with a logical counter: the clock’s value is a pair of (physical time, counter), and the update rule ensures that the value is always greater than any value the node has previously seen, while staying close to physical time.

The rule is straightforward. On a local event, the node takes the maximum of its previous value and the current physical time; if the physical time is greater, the counter resets, otherwise the counter increments. On receiving a message carrying a timestamp, the node takes the maximum of its own value, the received value, and the physical time, and applies the same counter logic. The result is a clock that never goes backwards, tracks physical time when nothing unusual happens, and advances logically when messages arrive from a node whose clock is ahead.

The ordering guarantee that follows is causal: if event A happened before event B in the happens-before sense, A’s timestamp is less than B’s. That is stronger than a pure counter and weaker than real time. It gives external consistency for transactions that communicate, because the communication carries the timestamp and forces the receiver’s clock forward. It does not give it for transactions that are causally unrelated but ordered in real time by a client that observed one and then started the other without any message passing; that case needs the physical clock to be accurate, and the client’s observation is a message even if the system does not see it as one.

Where the physical clock bound enters

The remaining gap is closed by bounding clock uncertainty. If every node’s physical clock is within ε of true time, then a transaction that starts at true time t can safely be assigned a timestamp of at least t, and any commit that happened before t - ε is guaranteed to have a timestamp below t. The system can therefore wait out the uncertainty, or push timestamps forward, to ensure that a transaction never gets a timestamp below one it should have observed.

Spanner’s approach is the well-known instance: commit timestamps are chosen at or after the transaction’s start, and the commit waits until the timestamp is in the past according to the clock bound, so that any later transaction’s timestamp is guaranteed to be greater. The wait is the price of external consistency, and it is on the order of the clock uncertainty, a few milliseconds with a well-maintained clock infrastructure.

The failure mode is a clock that exceeds the assumed bound. A node whose clock jumps forward breaks the assumption that ε holds, and the system’s ordering guarantee becomes conditional on a property it cannot verify locally. The standard defences are to monitor the bound and to refuse to serve when it is exceeded, which trades availability for correctness in exactly the way the assumption requires. A node whose clock jumps backward is worse, because it may hand out a timestamp below one already used, and the only safe response is to stop the node and let its state be reconciled.

Ordering without a global timestamp

Not every system needs a total order. Some need only a per-key order, with the requirement that transactions touching the same key are ordered consistently. That is achievable with a per-key version counter and no global authority, at the cost of making cross-key transactions need a different mechanism.

The design question is whether the application’s invariants are per-key or cross-key. A per-key invariant, such as a counter that must not go below zero or a state machine that must not transition illegally, can be enforced by a per-key order, and the ordering infrastructure is then local to the key’s owner. A cross-key invariant needs a total order, and the total order needs one of the mechanisms above. Most large systems end up with a mixture: a per-key order for the common case and a slower total order for the transactions that span keys, which is why the cost of a cross-key transaction is often an order of magnitude above a single-key one.

What the order does not give

A total order on transactions is not the same as a serialisable schedule unless the system also enforces the isolation rules against that order. A timestamp assigned at the start of a transaction, with no validation at commit, gives a snapshot but not serialisability: two transactions with overlapping snapshots can both commit changes that violate an invariant, as discussed in serializable snapshot isolation across shards.

Enforcing serialisability against a timestamp order means validating at commit that no conflicting transaction with a lower timestamp committed in the interval, or taking locks that prevent such a commit. Timestamp ordering as a concurrency control method does the latter: a transaction that wants to write a version reads the version’s write timestamp and aborts if a younger transaction has already written it. That is a lock-free protocol with its own failure mode, which is that a long transaction is repeatedly aborted by younger ones and makes no progress.

The order also does not survive a partition without a decision about which side may assign timestamps. A minority side that keeps issuing timestamps from its local clock produces transactions ordered after ones it never saw, and when the partition heals, the merged history may not be consistent with any serial order. The rule that prevents this is the same as for commit: only the side with a majority may proceed, which means the timestamp authority is a consensus group and the partition’s minority is unavailable for writes. That is the same majority requirement that governs replicated commit decisions, applied to the clock rather than to the transaction’s outcome.

Reading the guarantee from the timestamp

Given a timestamp value, what can be concluded? If the timestamp comes from a logical clock, it says something about causal order and nothing about real time. If it comes from a physical clock with a bound, it says something about real time within the bound. If it comes from an oracle with no time component, it says only that the order is consistent.

Those three answers correspond to three different systems, and confusing them is the source of most incorrect reasoning about distributed transaction ordering. A system whose timestamps are oracle values cannot claim external consistency without an additional mechanism; a system whose timestamps are physical cannot claim unbounded correctness without a bound; a system whose timestamps are logical cannot claim either without a communication path that carries them. The timestamp’s provenance is the guarantee.