The idea: the order is fixed by the timestamps
A database that runs transactions at the same time must give the same result as running them one by one in some order. Two-phase locking finds that order while the transactions run: whoever locks first goes first. Timestamp ordering (TO) picks the order in advance. Each transaction gets a timestamp when it begins, and the result must equal running the transactions in timestamp order. Nobody locks anything; the scheduler only checks that no read or write comes "too late" for that order.
The canvas shows three transactions T1, T2 and T3, the data items A, B and C with their timestamps, the timestamp check for the current operation, and the serial order the timestamps stand for.
Timestamps, read_TS and write_TS
When T begins it gets TS(T) from a counter (or a clock): 1, 2, 3, … A smaller timestamp means an older transaction, which comes earlier in the serial order. Each data item X keeps two numbers:
- read_TS(X): the largest timestamp of any transaction that has read X.
- write_TS(X): the timestamp of the transaction that wrote X last.
Both start at 0. They say which transactions have already "used" X, so the scheduler can tell whether a new operation fits the order.
The read rule and the write rule
Read. If TS(T) < write_TS(X), a younger transaction has already written X. In timestamp order T should have read the older value, but it is gone. T is too late and is aborted. Otherwise T reads X, and read_TS(X) becomes max(read_TS(X), TS(T)). Demo: late read aborts, restart with a new TS.
Write. If TS(T) < read_TS(X), a younger transaction has already read X. In timestamp order it should have seen T's value, so T's write cannot go in: T is aborted (Demo: late write after a younger read). If TS(T) < write_TS(X), a younger transaction has already written X: basic TO aborts T too (Demo: outdated write, basic TO aborts). Otherwise T writes X and write_TS(X) becomes TS(T).
When every operation arrives in timestamp order, nothing aborts (Demo: in timestamp order, both commit). Conflicting operations of committed transactions always run in timestamp order, so the schedule is conflict-serializable, with the timestamp order as its serial order.
The Thomas write rule
Look again at a write with TS(T) < write_TS(X) but TS(T) ≥ read_TS(X). Nobody younger has read X, and a younger write has already replaced it. In timestamp order, T's value would be written and then overwritten at once, without anyone reading it. So the write can simply be skipped, and T goes on. That is the Thomas write rule (R. H. Thomas, 1979). Choose it under Options, or run Demo: outdated write, Thomas write rule skips it: T1 commits and A keeps T2's value. The result is serializable in timestamp order, but it can be a schedule that is not conflict-serializable (it is view-serializable).
Abort and restart with a new timestamp
An aborted transaction's writes are undone, and it starts again with a new, larger timestamp. Its old timestamp was the problem: the younger operations are now in its past, so the second try usually succeeds. In Demo: late read aborts, restart with a new TS, T1 restarts as TS 3 and reads T2's committed value. A transaction that keeps losing can still be restarted again and again (starvation), but with ever larger timestamps it usually gets through.
Strict TO: wait for uncommitted writes
Basic TO lets T read a value written by a transaction that has not committed yet. If that writer then aborts, T has read a value that never existed and must be aborted too: a cascading abort. Strict TO prevents it. When a read or write of X passes its check but X holds another transaction's uncommitted write, T waits until that writer commits or aborts, then runs its check again. The page uses strict TO (Demo: strict TO waits for an uncommitted write).
Such a wait is always a younger transaction waiting for an older one: the writer's timestamp is write_TS(X), and T passed the check, so TS(T) is larger. Waits can never form a cycle, so TO has no deadlocks. The price is aborts: where 2PL would make a transaction wait, TO often aborts it instead. Demo: three transactions shows both: T2 is aborted by a late write to B, while T1 and T3 commit.
Timestamp ordering, 2PL and MVCC
| serial order fixed by | a conflict means | deadlock | |
|---|---|---|---|
| Two-phase locking | who locks first | wait for the lock | possible, needs detection |
| Timestamp ordering | the begin timestamps | abort the late transaction (or wait, strict TO) | none |
| MVCC (InnoDB) | locks for writes, snapshots for reads | writers wait for row locks; readers never wait | possible between writers |
MariaDB and MySQL do not use timestamp ordering. InnoDB uses row locks under strict two-phase locking for writes and locking reads, and MVCC for plain SELECT: a reader sees a snapshot (a read view) built from undo records and never waits for a writer. See Two-Phase Locking, MVCC and Isolation Levels, InnoDB Isolation and the InnoDB lock system. InnoDB's trx ids do play a role like timestamps, but only to decide which row versions a snapshot sees. Timestamps of a different kind order events across machines: see Lamport clocks. At the application level, a version column gives a similar "check, abort, retry" style: optimistic vs pessimistic locking.
What the page leaves out
Multiversion timestamp ordering (MVTO), where each write makes a new version and a late read is served an older version instead of aborting. Where timestamps come from in a real system (a clock, a counter, hybrid clocks across nodes). The page does not lower read_TS when a transaction aborts (keeping it too high is safe), keeps all items in memory, and does not show the undo of aborted writes step by step. Timestamp ordering on predicates and ranges (phantoms) is not modelled.
See where this page fits on the Databases & Storage mind map.