Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 79 ยท Concurrency Control

Timestamp-Based Protocols

Learn timestamp-ordering concurrency control: read and write timestamps, the accept or abort rules, the Thomas write rule and starvation, with a live simulator.

Two-phase locking keeps transactions serializable by making them wait for each other. Timestamp ordering (TO) takes the opposite approach: nobody waits. Each transaction gets a timestamp when it starts, and the system makes sure that the outcome is equivalent to running the transactions serially in timestamp order. If an operation would break that order, the transaction that issued it is aborted and restarted with a new timestamp.

The result is a protocol with no locks and therefore no deadlocks, at the price of aborts. It is a good way to see concurrency control as a pure ordering problem, and its ideas live on in multi-version systems, which you will meet in MVCC and Optimistic Concurrency Control.

Order by age, not by waiting

Timestamp Assigned at start. Smaller means older.
Equivalent serial order Older transactions act as if they ran first.
Too late? Abort A late operation kills its own transaction.

No locks, so no deadlock.

1 / 2

Timestamps and the idea

A timestamp TS(T) is a unique number given to transaction T when it begins. It can be the system clock or, more safely, a counter that increases by one for every new transaction. The rule is: if TS(T1) < TS(T2), the database must behave as if T1 ran completely before T2.

To enforce it, every data item Q carries two numbers:

  • R-TS(Q), the largest timestamp of any transaction that successfully read Q.
  • W-TS(Q), the largest timestamp of any transaction that successfully wrote Q.

Both start at 0. They record "who has already touched this item, and how young were they?". An operation is allowed only when no younger transaction has already done something that the operation should have come before.

The basic timestamp-ordering rules

Suppose transaction T with timestamp TS(T) wants to read or write item Q.

Read(Q).

  1. If TS(T) < W-TS(Q), a younger transaction has already overwritten the value that T should have seen. T is too late, so the read is rejected and T is aborted.
  2. Otherwise the read executes and R-TS(Q) becomes max(R-TS(Q), TS(T)).

Write(Q).

  1. If TS(T) < R-TS(Q), a younger transaction has already read Q and would have needed to see T's value. The write is rejected and T is aborted.
  2. If TS(T) < W-TS(Q), a younger transaction has already written Q. In the basic protocol the write is rejected and T is aborted.
  3. Otherwise the write executes and W-TS(Q) becomes TS(T).

A rolled-back transaction restarts with a new, larger timestamp. That is why the protocol never needs a "wait" state: it either lets the operation go through now or sends the transaction back to the start.

The next TryIt is a small simulator of exactly these rules. Each step is (transaction, operation, item). Transactions T1, T2, T3 get timestamps 1, 2, 3. Once a transaction aborts, its later steps are skipped. The simulator only tracks timestamps, not values, so you can concentrate on the accept/reject decisions.

Python Timestamp ordering simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the four runs side by side. In schedule A, T1 is the oldest, but T2 (younger) has already read X and T3 has already written it, so T1 can no longer write X without contradicting the timestamp order. In schedule C, T1 tries to read a value that a younger transaction has already replaced, so it is aborted too.

The Thomas write rule

Look at schedule B. T2 wrote X, and then the older T1 tries to write X. In timestamp order T1 comes first, so its value would be overwritten by T2 right away. Could anyone have seen T1's value? A transaction younger than T2 would see T2's value instead. A reader in between would have raised R-TS(X) above TS(T1), and the write check would already have aborted T1. So the write is obsolete: it has no readers and is immediately overwritten.

The Thomas write rule says: when R-TS(Q) <= TS(T) < W-TS(Q), do not abort T; simply ignore the write and carry on. This accepts some schedules that are view serializable but not conflict serializable (the extra ones always contain blind writes, that is, writes with no earlier read of the same item). The run above shows the difference: the basic rule aborts T1, the Thomas rule lets it continue and just drops one of its writes.

The rules for reads and for the TS(T) < R-TS(Q) case of writes are unchanged. Only the "obsolete write" case is relaxed.

What timestamp ordering guarantees

  • Conflict serializability. Every conflicting pair of accepted operations runs in timestamp order, so the precedence graph only has edges from older to younger transactions. It cannot contain a cycle.
  • Deadlock freedom. Transactions never wait, so there is no wait-for graph to worry about (Deadlocks).
  • Not recoverable by itself. In the version above, a transaction can read a value written by one that later aborts, and then it must abort too (a cascading abort), or it may even commit first. Real implementations add a rule such as "do not let a transaction commit until all transactions whose writes it read have committed", or they buffer all writes until commit (the strict variant).

Starvation

Aborting and restarting looks harmless, but it has one nasty failure mode. A long transaction touches many items. Whenever a short transaction that started after it writes an item the long one has not read yet, the long one fails its read check, restarts with a new timestamp and begins again. If short transactions keep arriving, the long transaction can restart indefinitely. This is starvation: work is happening, but this transaction never finishes.

Keeping the old timestamp does not cure it (an older timestamp makes reads of freshly written items fail even more often). The usual remedies are practical: after a few restarts, run the starving transaction with exclusive access for a moment (delay newly arriving writers), or switch it to a locking protocol.

Python A long transaction that keeps restarting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first three attempts die at item B, each time because a younger transaction got there first. Only when the system holds the short writers back does the long transaction get through. Production systems implement this idea in many forms: priorities, retry limits that escalate to locks, or admission control.

Timestamp ordering versus locking

Two-phase locking Timestamp ordering
Serial order Order of lock points (decided as it runs) Fixed in advance by start time
On conflict Wait for the lock Abort the younger or too-late transaction
Deadlocks Possible, must detect or prevent Impossible
Wasted work Rare (only deadlock victims) Frequent when conflicts are common
Best when Conflicts are common Conflicts are rare, mostly reads
Extra state Lock table Two timestamps on every item

Neither wins everywhere. Under low contention timestamp ordering is cheap, because almost every check passes. Under high contention the aborts pile up and locking is usually better. This trade-off, "assume conflicts are rare and pay when you are wrong", is the heart of optimistic concurrency control.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A transaction with TS = 5 wants to read item Q, and W-TS(Q) = 8. What does the basic timestamp-ordering protocol do?

    The younger transaction (TS 8) already overwrote Q. Transaction 5 should have come first, so its read is rejected and it is aborted and restarted with a new timestamp.
  2. 2. When does the Thomas write rule let a write be skipped instead of aborting?

    No younger transaction read Q, and a younger one has already written it, so the older write would be overwritten before anyone could see it. Ignoring it is safe.
  3. 3. Why can timestamp ordering never deadlock?

    Deadlock needs a cycle of transactions waiting for one another. Timestamp ordering has no waiting, so no cycles can form.
  4. 4. A long transaction restarts again and again because short transactions keep writing items before it reads them. What is this called?

    No transaction waits, so it is not a deadlock. The long transaction is simply beaten every time, which is starvation; systems fix it with retry limits, priorities or temporary exclusive access.

Summary

  • Timestamp ordering fixes the serial order at start time: older timestamp means earlier in the equivalent serial schedule.
  • Every item stores R-TS and W-TS; reads fail if TS(T) < W-TS(Q), writes fail if TS(T) < R-TS(Q) or (basic rule) TS(T) < W-TS(Q).
  • The Thomas write rule ignores obsolete writes instead of aborting, accepting some view-serializable schedules.
  • The protocol is conflict serializable and deadlock free, but needs extra rules for recoverability and can starve long transactions unless the system intervenes.
  • It shines when conflicts are rare; locking tends to win when they are frequent.

Next: MVCC and Optimistic Concurrency Control.