Timestamp-based concurrency control

In computer science, in the field of databases, timestamp-based concurrency control is a non-lock concurrency control method, used in relational databases to safely handle transactions, using timestamps.

Operation

Assumptions

* Every timestamp value is unique and accurately represents an instant in time. No two timestamps can be the same. A higher-valued timestamp occurs later in time than a lower-valued timestamp.

Formal

Each transaction can be assigned a timestamp at startup, so we can ensure that if an action A_i of a transaction T_i conflicts with action A_j of a transaction T_j, action A_i occurs before action A_j if TS(transaction T_i) < TS(transaction T_j), where TS("x") means the timestamp of "x". If an action violates the order, the transaction is aborted and restarted.

Every database object O is given a read timestamp RTS(O) and a write timestamp WTS(O).

If a transaction T wants to read O, and TS(T) < WTS(O), the order of the read with respect to the most recent write on O would violate the timestamp order between transaction and writer. So, T is aborted and restarted with a new, larger timestamp. If a transaction T wants to read O, and TS(T) > WTS(O), T reads O, RTS(O) is set to max [RTS(O), TS(T)] .

If a transaction T wants to write O, if TS(T) < RTS(O), the write action would conflict with the read action of O and T is aborted and restarted.

If a transaction T wants to write O, if TS(T) < WTS(O), we use the Thomas Write Rule and ignore this write to O and continue.

Otherwise, T writes to O, and WTS(O) is set to TS(T).

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,
* but the transaction started "before" the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is cancelled and must be restarted.
* and the transaction started "after" the object's write timestamp, it means that it is "safe" to read the object. In this case, if the transaction timestamp is after the object's read timestamp, the read timestamp is set to the transaction timestamp.

If a transaction wants to write to an object,
* but the transaction started "before" the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid, so the transaction is aborted and must be restarted.
* and the transaction started "before" the object's write timestamp it means that something has changed the object since we started our transaction. In this case we use the Thomas Write Rule and simply skip our write operation and continue as normal; the transaction does not have to be aborted/restarted.
* otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.

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, 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.

ee also

* Multiversion concurrency control