Timestamp ordering

Why it exists

Locking decides the order of conflicting operations as the transactions run: whoever gets the lock first goes first, and a transaction that cannot get a lock waits, so deadlocks can arise. Timestamp ordering decides the order in advance. Each transaction is given a number when it starts; the protocol makes sure that every pair of conflicting operations is executed in the order of these numbers, as if the transactions had run one after another in order of their numbers. An operation that arrives too late is not made to wait: its transaction is rolled back and restarted with a new number. Nobody ever waits, so there are no deadlocks.

Prerequisites

You need conflicts, precedence graphs and conflict serializability (schedules and serializability). The comparison with locking uses two-phase locking, and the part on recoverability uses recoverable and strict schedules.

Precise definitions

Timestamp. Each transaction $T$ receives a unique timestamp $TS(T)$ when it starts, from a clock or a counter, increasing with time. A smaller timestamp means an older transaction.

Item timestamps. For every item $X$ the system keeps

• $R\text{-}TS(X)$: the largest timestamp of any transaction that has successfully read $X$;
• $W\text{-}TS(X)$: the largest timestamp of any transaction that has successfully written $X$.

Both start at 0.

The rules (basic timestamp ordering) for an operation of $T$ on $X$:

• $T$ reads $X$. If $TS(T) < W\text{-}TS(X)$, a younger transaction has already overwritten $X$, so $T$ would read a value from its future: abort $T$. Otherwise execute the read and set $R\text{-}TS(X) = \max(R\text{-}TS(X), TS(T))$.
• $T$ writes $X$. If $TS(T) < R\text{-}TS(X)$, a younger transaction has already read $X$ and would have needed this value: abort $T$. If $TS(T) < W\text{-}TS(X)$, a younger transaction has already written $X$: abort $T$. Otherwise execute the write and set $W\text{-}TS(X) = TS(T)$.

An aborted transaction is rolled back and restarted with a new, larger timestamp. The rule can be said in one sentence: an operation is rejected exactly when a younger transaction has already made a conflicting access to the item.

Thomas write rule. In the second write case ($TS(T) < W\text{-}TS(X)$, but $TS(T) \ge R\text{-}TS(X)$) the write is ignored instead of aborting $T$: the value would be overwritten at once by the younger writer and nobody has read it.

Strict timestamp ordering. A read or write that passes the test but would read or overwrite a value written by a transaction that has not committed is delayed until that transaction commits or aborts.

Deadlock prevention with timestamps (for locking). Two schemes use timestamps as priorities when a lock request conflicts with a lock held by another transaction:

• Wait-die (non-preemptive): if the requester is older than the holder, it waits; if it is younger, it dies (is rolled back).
• Wound-wait (preemptive): if the requester is older, it wounds the holder (the holder is rolled back and the requester takes the lock); if it is younger, it waits.

In both, a rolled-back transaction restarts with its original timestamp.

How it works

The rules on every pair of conflicting operations

Two transactions: $T_1$ older, $T_2$ younger. A read and a read never conflict. When the older transaction acts first, everything is fine: the order of the operations agrees with the order of the timestamps. When the younger acts first and the older follows with a conflicting operation, the older one is rejected, because it arrives too late. The single exception in the last row is the Thomas write rule, which skips the late write instead of aborting.

A schedule run through the protocol

Read the table column by column: $R\text{-}TS$ and $W\text{-}TS$ grow only when an operation is accepted. $w_1(B)$ is rejected because $T_2$ (younger) has read $B$; $r_2(A)$ is rejected because $T_3$ (younger) has written $A$. The aborted transactions' remaining operations disappear from the schedule; they will run again after the restart with new timestamps. The accepted operations $r_1(A)$, $r_2(B)$, $w_2(C)$ and $w_3(A)$ followed the timestamp order.

Why it is serializable and deadlock free

Every accepted pair of conflicting operations is in timestamp order, so every edge of the precedence graph goes from a smaller to a larger timestamp. A cycle would need an edge going back, so the graph is acyclic: the schedule is conflict serializable, equivalent to the serial schedule in timestamp order. The checks confirm the converse as well: a schedule passes without abort exactly when each conflicting pair is in timestamp order. No operation ever waits, so no deadlock can occur. The price is restarts: a transaction can be aborted again and again (starvation is possible), and the work done before the abort is lost.

Restarts get new timestamps

$T_1$ is aborted at step 3 because $T_2$ (younger) has read $B$. It restarts with the timestamp 3, larger than all existing ones, which means it is now the youngest transaction. Its new read of $A$ passes the test but would read a value written by the uncommitted $T_2$, so it waits (this run uses the strict variant, explained below); after $T_2$ commits it goes through. The final order of the committed work is $T_2$ then $T_1$: the order of their final timestamps, 2 and 3.

The Thomas write rule

The schedule has the conflicts $r_1(A) \to w_2(A)$ and $w_2(A) \to w_1(A)$, a cycle, so it is not conflict serializable. The basic protocol aborts $T_1$ at $w_1(A)$. With the Thomas rule, $w_1(A)$ is skipped: $T_2$ has already written $A$, nobody has read $T_1$'s value, and $T_3$'s later write will overwrite everything anyway. The outcome (the values read, the final database) equals that of the serial execution $T_1\ T_2\ T_3$, so the schedule is view serializable. The check ran this on symbolic values for every schedule the rule accepts and found no difference from the serial execution in timestamp order. So the Thomas rule accepts more schedules than conflict serializability allows, but stays view serializable.

Not recoverable: the dirty read

The basic protocol only looks at timestamps. $T_2$ reads the value of $A$ that $T_1$ wrote and has not committed, and commits. Then $T_1$ is aborted at $w_1(B)$ (because $T_2$ has read $B$). $T_2$ has committed a result computed from a value that never officially existed: the schedule is not recoverable (a transaction committed before the one it read from). The usual repair is the strict variant:

Now the reader waits. $T_2$'s read of $A$ is delayed until $T_1$ commits; $T_1$ is not aborted because $T_2$ has not yet read $B$. The resulting schedule is strict. A wait only ever points to an older transaction (a transaction waits for the writer of a value, and a writer that passed the test has a smaller timestamp), so even strict timestamp ordering has no deadlock.

Timestamps used against deadlocks in locking

When locks are used, a conflicting request makes the requester wait, and cycles of waiting are deadlocks. Wait-die and wound-wait use the timestamps to forbid such cycles:

Both schemes make every wait go in one direction of age: in wait-die only an older transaction waits for a younger one; in wound-wait only a younger waits for an older. A cycle would need a wait in the other direction somewhere, so no deadlock is possible (the check confirmed that the waits-for graph never had a cycle, also when a lock passed to a new holder while others were waiting). The same two transactions without any prevention end in a deadlock:

and with the two schemes:

In wait-die the younger $T_2$ dies at step 4 when it asks for $A$ held by older $T_1$, and again at step 6 (it retries at once here; a real system delays the restart). In wound-wait the older $T_1$ wounds the younger holder $T_2$ at step 3. Because a restarted transaction keeps its original timestamp, the oldest transaction is never rolled back in either scheme, so every transaction eventually becomes the oldest and finishes: there is no starvation. (This is different from timestamp ordering, where a restart takes a new, larger timestamp.)

Timestamp ordering against two-phase locking

For small sets of transactions, every interleaving was generated. Both protocols produce only conflict serializable schedules, but neither produces everything the other does. The first row has a schedule accepted by timestamp ordering that locking cannot produce ($T_1$ must keep its exclusive lock on $B$ until its last read of $B$, so $T_2$'s read cannot come in between). The second row has a schedule that locking produces and timestamp ordering rejects ($T_1$ started first, so it is older, but $T_2$ read $C$ before $T_1$ wrote it: the serial order is $T_2$ then $T_1$, against the timestamps). Locking puts the order in the order of lock points, timestamp ordering in the order of start times.

Multiversion timestamp ordering (quoted)

If every write creates a new version of the item, labelled with the writer's timestamp, a read never has to be rejected: it is given the version with the largest write timestamp not larger than the reader's timestamp. A write is rejected only if a younger transaction has already read the version the write would follow. This increases concurrency, at the cost of storing versions. It is described in the textbooks and is not computed here.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Timestamp ordering and two-phase locking both guarantee serializability, by different means: ordering decided at the start against ordering decided by the lock points. Their difference in recoverability is a typical exam topic. The wait-die and wound-wait schemes prevent the circular wait of deadlock by breaking its symmetry with an age.

PYQs

Consider the following two statements about database
transaction schedules:

I. Strict two-phase locking protocol generates conflict
serializable schedules that are also recoverable.

II. Timestamp-ordering concurrency control protocol with
Thomas write rule can generate view serializable schedules
that are not conflict serializable.

Which of the above statements is/are TRUE?

In a database system, unique timestamps are assigned to
each transaction using Lamport 's logical clock. Let
TS(T1) and TS(T2) be the timestamps of transactions T1
and T2 respectively. Besides, T1 holds a lock on the
resource R and T2 has requested a conflicting lock on
the same resource R. The following algorithm is used to
prevent deadlocks in the database system assuming that
a killed transaction is restarted with the same timestamp.

if TS(T2) < TS(T1) then

T1 is killed

else T2 waits.

Assume any transaction that is not killed terminates
eventually. Which of the following is TURE about the
database system that uses the above algorithm to prevent
deadlocks?

Which of the following concurrency control protocols
ensure both conflict serializability and freedom from
deadlock?

I. 2-phase locking

II. Time-stamp ordering

Self-check

Revision card

References