Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Timestamp ordering

Why was decreeing the order up front abandoned in its pure form, and where did it come back?

Decree the order instead of discovering it

Give each transaction a timestamp at its start, and enforce that every conflicting pair executes in timestamp order. Each item carries a read timestamp and a write timestamp (the largest timestamps of transactions that read and wrote it).

  • A read by T if TS(T) < write-TS(X), because T would be reading a value from its own future.
  • A write by T aborts if TS(T) < read-TS(X), because someone in the future has already seen the old value.

The Thomas Write Rule

One special case is theoretically interesting. If TS(T) < write-TS(X) on a write, the write is simply obsolete: a newer write has already replaced it. It can be discarded instead of aborted. This is the . It is the one place where production systems knowingly accept that is view-serializable but not conflict-serializable. That is small evidence that the stricter criterion is a concession to tractability, not a statement about correctness.

Why it is never implemented as described

Two timestamps per item means metadata proportional to the size of the whole database, including cold data nobody touches. and pay metadata proportional to concurrent activity (about L transactions), and L is small. That one asymmetry killed the scheme in its pure form.

Then it came back everywhere, in a version where the timestamps live on versions that already exist for other reasons:

  • 's visibility check is .
  • Percolator and Spanner, and every "if-version-matches" conditional write on an object store, are per-item write-timestamp checks.

The mechanism survived by attaching itself to metadata that someone else was already paying for.

Note also that timestamp ordering does not escape blocking entirely: a transaction that reads a value written by an uncommitted transaction must wait for that transaction's fate, or recoverability is lost. dependencies bring waiting back through the back door.

Timestamp ordering pays metadata per item rather than per active transaction, which is why it only survives where the versions already exist.