Timestamp-based concurrency control

In computer science, a timestamp-based concurrency control algorithm is a non-lock concurrency control method. It is used in some databases to safely handle transactions, using timestamps.

Operation

Assumptions

Generating a Timestamp

A number of different ways have been used to generate timestamp

Formal

Each transaction (T_i) is an ordered list of actions (A_{ix}). Before the transaction performs its first action (A_{i1}), it is marked with the current timestamp, or any other strictly totally ordered sequence: TS(T_i) = NOW(). Every transaction is also given an initially empty set of transactions upon which it depends, DEP(T_i) = [], and an initially empty set of old objects which it updated, OLD(T_i) = [].

Each object (O_j) in the database is given two timestamp fields which are not used other than for concurrency control: RTS(O_j) is the time at which the value of object was last used by a transaction, WTS(O_j) is the time at which the value of the object was last updated by a transaction.

For all T_i:

For each action A_{ix}:
If A_{ix} wishes to use the value of O_j:
If WTS(O_j) > TS(T_i) then abort (a more recent thread has overwritten the value),
Otherwise update the set of dependencies DEP(T_i).\mathrm{add}(WTS(O_j)) and set RTS(O_j) = \max(RTS(O_j), TS(T_i));
If A_{ix} wishes to update the value of O_j:
If RTS(O_j) > TS(T_i) then abort (a more recent thread is already relying on the old value),
If WTS(O_j) > TS(T_i) then skip (the Thomas Write Rule),
Otherwise store the previous values, OLD(T_i).\mathrm{add}(O_j, WTS(O_j)), set WTS(O_j) = TS(T_i), and update the value of O_j.
While there is a transaction in DEP(T_i) that has not ended: wait
If there is a transaction in DEP(T_i) that aborted then abort
Otherwise: commit.

To abort:

For each (\mathrm{old}O_j, \mathrm{old}WTS(O_j)) in OLD(T_i)
If WTS(O_j) equals TS(T_i) then restore O_j = \mathrm{old}O_j and WTS(O_j) = \mathrm{old}WTS(O_j)

Informal

Whenever a transaction starts, it is given a timestamp. This is so we can tell which order that the transactions are supposed to be applied in. So given two transactions that affect the same object, the transaction that has the earlier timestamp is meant to be applied before the other one. However, if the wrong transaction is actually presented first, it is aborted and must be restarted.

Every object in the database has a read timestamp, which is updated whenever the object's data is read, and a write timestamp, which is updated whenever the object's data is changed.

If a transaction wants to read an object,

If a transaction wants to write to an object,

Recoverability

For an explanation of the terms recoverable (RC), avoids cascading aborts (ACA) and strict (ST) see Schedule (computer science).

Note that timestamp ordering in its basic form does not produce recoverable histories. Consider for example the following history with transactions T_1 and T_2:

W_1(x)\;R_2(x)\;W_2(y)\;C_2\;R_1(z)\;C_1

This could be produced by a TO scheduler, but is not recoverable, as T_2 commits even though having read from an uncomitted transaction. To make sure the it produces recoverable histories, a scheduler can keep a list of other transactions each transaction has read from, and not let a transaction commit before this list consisted of only committed transactions. To avoid cascading aborts, the scheduler could tag data written by uncommitted transactions as dirty, and never let a read operation commence on such a data item before it was untagged. To get a strict history, the scheduler should not allow any operations on dirty items.

Implementation Issues

Timestamp Resolution

This is the minimum time elapsed between two adjacent timestamps. If the resolution of the timestamp is too large (coarse), the possibility of two or more timestamps being equal is increased and thus enabling some transactions to commit out of correct order. For example, assuming that we have a system that can create one hundred unique timestamps per second, and given two events that occur 2 milliseconds apart, they will probably be given the same timestamp even though they actually occurred at different times.

Timestamp Locking

Even though this technique is a non-locking one, in as much as the Object is not locked from concurrent access for the duration of a transaction, the act of recording each timestamp against the Object requires an extremely short duration lock on the Object or its proxy.

See also