Timestamp Based Protocol in DBMS

Introduction

The most commonly used concurrency protocol is the timestamp-based protocol. This protocol uses either system time or logical encounter as a time-stamp.

Lock-based protocols manage the order between the conflicting pairs among transactions at the time of execution, whereas timestamp-based protocols start working as soon as a transaction is created.  

Every transaction has a time-stamp associated with it, and the age of the transaction determines the ordering. A transaction created at 0002 clock time would be older than all other transactions after it. For example, any transaction ‘y’ entering the system at 0004 is two seconds younger, and the priority would be given to the older one. 

How does a Timestamp Ordering Protocol Work?

Time-stamp is a unique identifier created by the DBMS to identify a transaction. —Each transaction is issued a time-stamp when it enters the system. If an old transaction Ti has time-stamp TS(Ti), a new transaction Tj is assigned time-stamp TS(Tj) such that TS(Ti) < TS(Tj).

In time-stamp order, the schedule is equivalent to the particular serial order corresponding to the order of the transaction time-stamps, unlike the lock-based technique where the schedule is made serial schedule based on locks.

The time-stamp ordering protocol ensures serializability among transactions in their conflicting read and writes operations. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the time-stamp values of the transactions.

• The time-stamp of transaction Ti is denoted as TS(Ti)
   
• Read time-stamp of data item X is denoted by R - time-stamp (X)
   
• Write time-stamp of data-item X is denoted by W - time-stamp (X)
   
• Time-stamp ordering protocol works as follows” If a transaction Ti issues a read(X) operation”
   
• If a TS(T) < W-timestamp(X). Operation rejected
   
• If TS(Ti) >= W-timestamp(X). Operation executed
   
• All data-item time stamps are updated.
   
• If a transaction Ti issues a write(X) operation
   
• If TS(Ti) < R-timestamp(X). Operation rejected
   
• If TS(Ti) < W-timestamp(X). Operation rejected and Ti rolled back. Otherwise, the operation is executed

Basic Time-stamp Ordering

The basic time-stamp ordering protocol (BASIC T/O) allows reads and writes on database objects without using locks. Instead, every database object X is tagged with a time-stamp of the last transaction that successfully performed a read (denoted as R-TS(X)) or write (denoted as W-TS(X)) on that object.
The DBMS then checks these time-stamps for every operation. If a transaction tries to access an object in a way that violates the time-stamp order, the transaction is aborted and restarted. The underlying assumption is that violations will be rare, and thus these restarts will also be rare. 

Read Operations

For read operations, if TS(Ti) < W-TS(X), this violates the time-stamp order of Ti with regard to the previous writer of X. Thus, Ti is aborted and restarted with a new time-stamp. 

Otherwise, the read is valid, and Ti is allowed to read X. The DBMS then updates R-TS(X) to be the max of R-TS(X) and TS(Ti). It also has to make a local copy of X to ensure repeatable reads for Ti.

Write Operations

For write operations, if TS(Ti) < R-TS(X) or TS(Ti) < W-TS(X), Ti must be restarted. Otherwise, the DBMS allows Ti to write X and updates W-TS(X). Again, it needs to make a local copy of X to ensure repeatable reads for Ti.

Thomas Write Rule

An optimization for writes is if TS(Ti) < W-TS(X), the DBMS can instead ignore the write and allow the transaction to continue instead of aborting and restarting it. This is called the Thomas Write Rule.

Note that this violates the time-stamp Ti's order of Ti. However, this is okay because no other transaction will ever read Ti’s write to object X. The Basic T/O protocol generates a conflict serializable schedule if it does not use Thomas Write Rule.

It cannot have deadlocks because no transaction ever waits. However, starvation for long transactions is possible 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 commit. 

Otherwise, the DBMS cannot guarantee that transactions read data that will be restored after recovering from a crash.

Potential Issues: 

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

Strict Time-stamp Ordering

Timestamp-based concurrency control uses time stamps for synchronization instead of locks. From the outside, the transactions seem to be executed sequentially according to their starting time.

In other words, the scheduler generates serializable schedules equal to the serial execution of the transactions ordered by their starting time.

These time-stamps are used to guarantee the Time-stamp Ordering (TO) rule: if two operations pi(x) and qj (x) are in conflict, i.e., they access the same tuple x and at least one operation is a write operation, then the operation of the transaction with the lower time-stamp is always executed first. 

Thereby, the resulting schedule is equal to the serial execution of the transactions ordered by their time-stamp, and, as a consequence, it is serializable.

Time-stamp Ordering is called Strict Time-stamp Ordering (STO). STO does not only provide recoverable schedules but also strict schedules. That means no uncommitted changes of a running transaction are overwritten or read by another transaction. The use of a dirty bit prevents this.

Each transaction marks tuples with uncommitted changes by setting the dirty bit, and other transactions accessing such a tuple have to wait until the dirty bit is unset, which happens when the previous transaction commits or aborts.

Advantages 

• The time-stamp ordering protocol ensures conflict serializability. This is because conflicting operations are processed in time-stamp order.
   
• The timestamp-based protocol ensures freedom from deadlock since no transaction ever waits.

Disadvantages 

• There is the possibility of starvation of long transactions. This may be due to a sequence of conflicting short transactions causing repeated restarting of the long transaction. One can avoid this by finding a transaction that restarts repeatedly, and conflicting transactions need to be temporarily blocked to enable the transaction to finish. 
   
• The timestamp-based protocol may produce a schedule that is not recoverable. But one can make timestamp-based schedules recoverable.

Also read, File System vs DBMS