TOCC

Timestamp ordering (T/O) is an optimistic class of concurrency control protocols where the DBMS assumes that transaction conflicts are rare. DBMS instead uses timestamps to determine the serializability order of transactions. Timestamp could allocate using system lock, logical counter and hybrid.

For every database object X is tagged with timestamp of the last transaction that successfully did read/write. W-TS(X) and R-TS(X). If transaction tries to access an object “from the future”, then the DBMS aborts that transaction and restarts it.

In read operations, if $TS(T_i)$ < W-TS(X), the transaction will read a value that was already overwritten and this transaction will be rejected and abort, restart with same TS. If $TS(T_i)$ >= W-TS(X), it allows $TS(T_i)$ to read X and update R-TS(X). Depends on isolation levels, it can make a local copy of X to ensure repeatable reads for $T_i$.

In write operations, if $TS(T_i)$ < W-TS(X) or if $TS(T_i)$ < R-TS(X), it tries to write an obsolete value or the value needed is in the past. Transaction will be aborted and roll back. Else it could write X and update W-TS(X).

For Thomas Write Rule

If $TS(T_i)$ < R-TS(X), it will abort and restart. If $TS(T_i)$ < W-TS(X), ignore the write and allow transaction to continue. It make use of view serializability, deleting obsolete write operations from the transactions that issue them.

The basic timestamp ordering cannot have deadlocks because no transaction ever waits. But there is a possibility of starvation for long transactions if short transactions keep causing conflicts.

It also permits schedules that are not recoverable. A schedule is recoverable if transactions commit only after all transactions whose changes they read or commit. Otherwise, the DBMS cannot guarantee that transactions read data that will be restored after recovering from a crash.

Issues:

• High overhead from copying data to transaction’s workspace and from updating timestamps.
• Long running transactions can get starved: The likelihood that a transaction will read something from a newer transaction increases.
• Suffers from the timestamp allocation bottleneck on highly concurrent systems.