Timestamp-Based Protocols

Timestamp-Based Protocols

• Each transaction T_i  is issued a timestamp TS(T_i) when it enters the system.

•       Each transaction has a unique timestamp

•       Newer transactions have timestamps strictly greater than earlier ones

•       Timestamp could be based on a logical counter

§  Real time may not be unique

§  Can use (wall-clock time, logical counter) to ensure

• Timestamp-based protocols manage concurrent execution such that
        time-stamp order = serializability order
• Several alternative protocols based on timestamps

The timestamp ordering (TSO) protocol

• Maintains for each data Q two timestamp values:

•       W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q) successfully.

•       R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q) successfully.

• Imposes rules on read and write operations to ensure that

•       Any conflicting  operations are executed in timestamp order

Out of order operations cause transaction rollback

Suppose a transaction T_i issues a read(Q)

1.   If TS(T_i) < W-timestamp(Q), then T_i needs to read a value of Q  that

      was already overwritten.

• Hence, the read operation is rejected, and T_i  is rolled back.

2.   If TS(T_i) ³  W-timestamp(Q), then the read operation is executed, and

      R-timestamp(Q) is set to

                 max(R-timestamp(Q), TS(T_i)).

Suppose that transaction T_i issues write(Q).

1.   If TS(T_i) < R-timestamp(Q), then the value of Q that T_i is producing

      was needed previously, and the system assumed that that value

      would never be produced.

Ø  Hence, the write operation is rejected, and T_i is rolled back.

2.   If TS(T_i) < W-timestamp(Q), then T_i is attempting to write an

      obsolete value of Q.

Ø  Hence, this write operation is rejected, and T_i is rolled back.

3.   Otherwise, the  write operation is executed, and W-timestamp(Q) is

      set to TS(T_i).

 

n        Recoverable schedule — if a transaction T_j reads a data items previously written by a transaction T_i , the commit operation of T_i  appears before the commit operation of T_j.

The following schedule (Schedule 11) is not recoverable if T₉ commits immediately after the read

If T₈ should abort, T₉ would have read (and possibly shown to the user) an inconsistent database state.  Hence database must ensure that schedules are recoverable

Cascading rollback – a single transaction failure leads to a series of transaction rollbacks.  Consider the following schedule where none of the transactions has yet committed (so the schedule is recoverable)

n        If T₁₀ fails, T₁₁ and T₁₂ must also be rolled back.

n        Can lead to the undoing of a significant amount of work

n        Cascadeless schedules — cascading rollbacks cannot occur; for each pair of transactions T_i and T_j such that T_j  reads a data item previously written by T_i, the commit operation of T_i  appears before the read operation of T_j.

n        Every cascadeless schedule is also recoverable

n        It is desirable to restrict the schedules to those that are cascadeless

System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set.