In DBMS-What is Timestamp based concurrency control algorithm? explain Multiversion technique using timestamp ordering

Timestamp based concurrency control algorithm

              

Timestamp : -  A monotonically increasing variable (integer) indicating the age of an operation or a transaction.  A larger timestamp value indicates a more recent event or operation.

Timestamp based algorithm uses timestamp to serialize the execution of concurrent transactions

     Basic Timestamp Ordering

 1.  Transaction T issues a write_item(X) operation:

1. If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger transaction has already read the data item so abort and roll-back T and reject the operation.
2. If the condition in part (a) does not exist, then execute write_item(X) of T and set write_TS(X) to TS(T).

2.  Transaction T issues a read_item(X) operation:

1. If write_TS(X) > TS(T), then an younger transaction has already written to the data item so abort and roll-back T and reject the operation.

If write_TS(X) £ TS(T), then execute read_item(X) of T and set read_TS(X) to the larger of TS(T) and the current read_TS(X

Strict Timestamp Ordering          

 1.  Transaction T issues a write_item(X) operation:

     a. If TS(T) > read_TS(X), then delay T until the transaction T’ that wrote or read X has terminated         (committed or aborted).

2.  Transaction T issues a read_item(X) operation:

a. If TS(T) > write_TS(X), then delay T until the transaction T’ that wrote or read X has terminated        (committed or aborted).

Thomas’s Write Rule

1.If read_TS(X) > TS(T) then abort and roll-back T and reject the operation.

2.If write_TS(X) > TS(T), then just ignore the write operation and continue execution.  This is because the most recent writes counts in case of two consecutive writes.

3.If the conditions given in 1 and 2 above do not occur, then execute write_item(X) of T and set write_TS(X) to TS(T).

Multiversion concurrency control techniques

Concept

This approach maintains a number of versions of a data item and allocates the right version to a read operation of a transaction.  Thus unlike other mechanisms a read operation in this mechanism is never rejected.

Side effect:  Significantly more storage (RAM and disk) is required to maintain multiple versions.  To check unlimited growth of versions, a garbage collection is run when some criteria is satisfied.

Multiversion technique based on timestamp ordering

This approach maintains a number of versions of a data item and allocates the right version to a read operation of a transaction.  Thus unlike other mechanisms a read operation in this mechanism is never rejected.

Side effects:  Significantly more storage (RAM and disk) is required to maintain multiple versions.  To check unlimited growth of versions, a garbage collection is run when some criteria is satisfied.

Explanation

Assume X1, X2, …, Xn are the version of a data item X created by a write operation of transactions.  With each Xi a read_TS (read timestamp) and a write_TS (write timestamp) are associated.

read_TS(Xi):  The read timestamp of Xi is the largest of all the timestamps of transactions that have successfully read version Xi.

write_TS(Xi):  The write timestamp of Xi that wrote the value of version Xi.

A new version of Xi is created only by a write operation.

To ensure serializability, the following two rules are used.

If transaction T issues write_item (X) and version i of X has the highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), and read _TS(Xi) > TS(T), then abort and roll-back T;  otherwise create a new version Xi and read_TS(X) = write_TS(Xj) = TS(T).

If transaction T issues read_item (X), find the version i of X that has the highest write_TS(Xi) of all versions of X that is also less than or equal to TS(T), then return the value of Xi to T, and set the value of read _TS(Xi) to the largest of TS(T) and the current read_TS(Xi).