Timestamp protocols

Timestamp protocols in database management system (DBMS)

1. DBMS PRESENTATION ON TIMESTAMP PROTOCOLS BY: PRASHANT PRIYADARSHI (110103135) PRASHANT SAINI (110103134) RONIT RAJ (110103160) PRIYANKA KUMARI(110103139)

2. INTRODUCTION A timestamp is a unique identifier used in DBMS to identify a transaction. Typically, timestamp values are assigned in the order in which the transactions are submitted to the system, so a timestamp can be thought of as the  transaction start time. We will refer to the timestamp of transaction T as TS(T). Concurrency control techniques based on timestamp ordering do not use locks; hence,  deadlocks cannot occur.

3. GENERATION OF TIMESTAMPS Timestamps can be generated in several ways. One possibility is to use a counter that is incremented each time its value is assigned to a transaction. The transaction timestamps are numbered 1, 2, 3, . . . in this scheme. A computer counter has a finite maximum value, so the system must periodically reset the counter to zero when no transactions are executing for some short period of time. Another way to implement timestamps is to use the current date/time value of the system clock and ensure that no two timestamp values are generated during the same tick of the clock.

4. TIMESTAMP ORDERING A schedule in which the transactions participate is then serializable, and the equivalent serial schedule has the transactions in order of their timestamp values. This is called  timestamp ordering (TO). Notice how this differs from 2PL, where a schedule is serializable by being equivalent to  some  serial schedule allowed by the locking protocols. In timestamp ordering, however, the schedule is equivalent to the  particular serial order  corresponding to the order of the transaction timestamps.  The algorithm must ensure that, for each item accessed by  conflicting operations  in the schedule, the order in which the item is accessed does not violate the serializability order. To do this, the algorithm associates with each database item  X  two timestamp ( TS ) values:-

5. 1.  Read_TS( X ):  The  read timestamp  of item  X;  this is the largest timestamp among all the timestamps of transactions that have successfully read item  X —that is, read _TS( X ) = TS(T), where T is the youngest  transaction that has read  X  successfully.   2.  Write_TS ( X ) :  The  write timestamp  of item  X;  this is the largest of all the timestamps of transactions that have successfully written item  X —that is, write_ TS( X ) = TS(T), where T is the  youngest  transaction that has written  X  successfully.  

6. BASIC TIMESTAMP ORDERING Whenever some transaction T tries to issue a read_item ( X ) or a write_item ( X ) operation, the  basic TO  algorithm compares the timestamp of T with read_TS ( X ) and write_TS ( X ) to ensure that the timestamp order of transaction execution is not violated. The concurrency control algorithm must check whether conflicting operations violate the timestamp ordering in the following two cases: 1. Transaction T issues a  write_item ( X )  operation:   a. If read_TS ( X ) > TS(T) or if write_TS ( X ) > TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with a timestamp greater than TS(T)—and hence after   T in the timestamp ordering—has already read or written the value of item  X  before T had a chance to write  X , thus violating the timestamp ordering.   b. If the condition in part (a) does not occur, then execute the write_item ( X ) operation of T and set write_TS ( X ) to TS(T).

7. 2. Transaction T issues a  read_item ( X )  operation:   a. If write_TS ( X ) > TS(T), then abort and roll back T and reject the operation. This should be done because some younger transaction with timestamp greater than TS(T)—and hence  after  T in the timestamp ordering—has already written the value of item  X  before T had a chance to read  X .   b. If write_TS ( X ) <= TS(T), then execute the read_item ( X ) operation of T and set read_TS ( X ) to the  larger  of TS(T) and the current read_TS ( X ).  

8. STRICT TIMESTAMP ORDERING A variation of basic TO called  strict TO  ensures that the schedules are both  strict  (for easy recoverability) and (conflict) serializable. In this variation, a transaction T that issues a read_item ( X ) or write_item ( X ) such that TS(T) > write_TS ( X ) has its read or write operation  delayed  until the transaction T that  wrote  the value of  X  (hence TS(T) = write_TS ( X )) has committed or aborted. To implement this algorithm, it is necessary to simulate the locking of an item  X  that has been written by transaction T until T is either committed or aborted. This algorithm does not cause deadlock, since T waits for T only if TS(T) > TS(T).  

9. THOMAS WRITE RULE A modification of the basic TO algorithm, known as  Thomas’s write rule, does not enforce conflict serializability; but it rejects fewer write operations, by modifying the checks for the write_item ( X ) operation as follows: 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 do not execute the write operation but continue processing. This is because some transaction with timestamp greater than TS(T)—and hence after T in the timestamp ordering—has already written the value of  X . Hence, we must ignore the write_item ( X ) operation of T because it is already outdated and obsolete. Notice that any conflict arising from this situation would be detected by case (1).   3. If neither the condition in part (1) nor the condition in part (2) occurs, then execute the write_item ( X ) operation of T and set write_TS ( X ) to TS(T).    

10. Correctness of Timestamp-Ordering The timestamp-ordering protocol guarantees serializability since all the arcs in the precedence graph are of the form: Thus, there will be no cycles in the precedence graph Timestamp protocol ensures freedom from deadlock as no transaction ever waits. But the schedule may not be cascade-free, and may not even be recoverable. transaction with smaller timestamp transaction with larger timestamp

11. Recoverability and Cascade Freedom Problem with timestamp-ordering protocol: Suppose T i aborts, but T j has read a data item written by T i Then T j must abort; if T j had been allowed to commit earlier, the schedule is not recoverable. Further, any transaction that has read a data item written by T j must abort This can lead to cascading rollback --- that is, a chain of rollbacks Solution: A transaction is structured such that its writes are all performed at the end of its processing All writes of a transaction form an atomic action; no transaction may execute while a transaction is being written A transaction that aborts is restarted with a new timestamp

12. Multiversion Timestamp Ordering Each data item Q has a sequence of versions Q 1 < Q 2 ,...., < Q m . Each version Q k contains three data fields: Content -- the value of version Q k . W-timestamp ( Q k ) -- timestamp of the transaction that created (wrote) version Q k R-timestamp ( Q k ) -- largest timestamp of a transaction that successfully read version Q k when a transaction T i creates a new version Q k of Q , Q k 's W-timestamp and R-timestamp are initialized to TS( T i ). R-timestamp of Q k is updated whenever a transaction T j reads Q k , and TS( T j ) > R-timestamp( Q k ).

13. Multiversion Timestamp Ordering (Cont) The multiversion timestamp scheme presented next ensures serializability . Suppose that transaction T i issues a read ( Q ) or write ( Q ) operation. Let Q k denote the version of Q whose write timestamp is the largest write timestamp less than or equal to TS( T i ). If transaction T i does a read ( Q ), then the value returned is the content of version Q k . If transaction T i does a write ( Q ), and if TS( T i ) < R -timestamp( Q k ), then transaction T i is aborted and rolled back. Otherwise , if TS( T i ) = W -timestamp( Q k ), the contents of Q k are overwritten, otherwise a new version of Q is created. Reads always succeed; a write by T i is rejected if some other transaction T j that (in the serialization order defined by the timestamp values) should read T i 's write, has already read a version created by a transaction older than T i .

14. T 1 t1 T 2 t2 T 3 t3 T 4 t4 T 5 t5 read 2 ( Y )->Y0 read 1 ( X )->X0 read 3 ( Y )->Y0 write 4 ( Y ) write 5 ( Z ) read 6 ( Z )->Z1 read 7 ( Y )->Y0 abort read 8 ( X )->X0 write 9 ( Z ) abort write( Y ) write( Z ) Example Use of the Protocol A partial schedule for several data items for transactions T 1 , T 2 , T 3 , T 4 , T 5 , with timestamps t1 < t2 < t3 < t4 < t5 Version 0 Version 1 C R W C R W X X0 1 :t5 Y Y0 2 :t2 Y1 4 :t3 Z Z0 Z1 6 :t5 5 :t3 Still have cascading rollback

15. THANK YOU