Concurrency control

Concurrency Control and Database Recovery 

Transaction Manager

It is a component of DBMS which is responsible for maintaining the acid properties of a transaction.

It has two sub components.

Concurrency Control Manager 

It is responsible for maintaining consistency and isolation property of a transaction.

Database Recovery Manager

It is responsible for maintaining atomicity and durability property of a transaction.

Concurrency control techniques 

To ensure that concurrent execution of transactions maintain consistency and isolation property various concurrency control techniques are used.

1. Lock based protocol 

2. Timestamp based protocol 

3. Validation based protocols

Lock based protocol 

Concept of locks 

Whenever a transaction needs to access a data item. It has to follow the following steps.

1. Request Lock on data item from concurrency control manager.

2. Access data item provided lock is granted by the concurrency control manager, otherwise wait.

3. Release Lock on data item.

Types of locks 

1. Read lock 

It is used for read access. It is also called shared lock. A transaction can share read lock with another transaction as read read never conflicts.

2. Write lock 

It is used for write access. It is also called exclusive lock. Write lock cannot be shared with another transaction.

Lock compatibility matrix

Lock Protocol

1. A transaction request a lock from concurrency control manager over data item.

2. If a data item is not previously locked then concurrency control manager grants lock to transaction.

3. If data item is previously locked by some other transaction then concurrency control manager will check lock compatibility before granting lock to the transaction.

4. If locks are compatible then concurrency control manager grants the lock to the transaction, otherwise the transaction waits.

5. The transaction after using data item unlocks the data item.

Note - Deadlock is necessary evil associated with locks.

Types of lock based protocol 

1. Two phase locking protocol

2. Strict two phase locking protocol 

3. Rigorous two phase locking protocol 

4. Two phase locking protocol with lock conversion.

Two phase locking Protocol 

In this a transaction performs locking and unlocking of data items in two phases growing and shrinking phase.

In growing phase a transaction can perform only locking activity whereas in shrinking phase a transaction can only unlock data items. The lock point is the point where a transaction has obtained its final lock.

Strict two phase locking Protocol 

In this transaction acquires locks in growing phase. In shrinking phase a transaction can unlock only shared locks whereas exclusive locks are released only when the transaction commits.

Rigorous two phase locking Protocol 

In this transaction acquires locks in growing phase.In this both shared and exclusive locks are held until a transaction commits.

Two phase locking protocol with lock conversion 

In this transaction performs locking and unlocking of data items in two phases.

In growing phase a transaction can perform locking and lock upgrade activity where as in shrinking phase a transaction can perform only unlocking and lock downgrade activity.

Note - Two phase locking protocol ensures conflict serializable schedule.

Timestamp based protocol

Concept of timestamp

With each transaction Ti a unique fixed timestamp is associated which is denoted by TS(Ti).

It is associated with the transaction when its execution is started. It can be implemented in two ways.

1. system clock 

2. logical counter which keeps on incrementing

Timestamp of data items 

With each data item two timestamps are associated.

1. Read timestamp

It is the maximum of the timestamps of the transactions that successfully executed read operation over the data item. It is denoted by RTS(q).

2. Write timestamp 

It is the timestamp of the last transaction that successfully executed write operation over the data item. It is denoted by WTS(q).

Example

Timestamp ordering protocol 

This protocol is used by concurrency control manager to ensure conflict serializable schedule. The protocol is as follows:

1. Suppose a transaction Ti issues read operation on data item q. 

If TS(Ti) < WTS(q) then read operation is rejected and Ti is rolled back. 

Otherwise read operation is executed and RTS(q) is set equal to Max{ TS(Ti),RTS(q)}

2. Suppose a transaction Ti issues write operation on data item q. 

If TS(Ti) < RTS(q) or   TS(Ti) < WTS(q) then write operation is rejected and Ti is rolled back. 

Otherwise write operation is executed and WTS(q) is set equal to TS(Ti).

3. A transaction which is rolled back is restarted with a new timestamp.
Example

Note - timestamp ordering protocol ensure that conflicting operations are executed in a serialised manner.

Validation based protocol (optimistic protocol)

Concurrency control can slow down the execution of transaction in optimistic scenario most transactions are of read nature. In such situations concurrency control can degrade system performance.

In such cases validation based protocols are used. In validation based protocols checks are imposed on a transaction at the end of execution. 
In this we define three phases of transaction.

1. Read Phase

 In this phase the transaction reads data items from database and stores them in memory variables.

2. Validation Phase 

In this phase various validation tests are performed to determine whether the changes made to the memory variables can be applied to the database or not without causing any consistency problem.

3. Write phase

Only those transactions which successfully passes validation phase moves to the write phase. In this phase all the changes made to the local variables are permanently applied to the database.

Validation test 

For performing validation test three different timestamps are attached to a transaction.

1.start(ti)

It is the time when transaction Ti started its execution.

2. validation(Ti)

It is the timestamp when transaction Ti finished its read phase and started its validation phase.

3. finish(Ti) 

It is the timestamp when transaction Ti finished its write phase.

The validation test for transaction Tj is performed as follows:

For all the transactions Ti such that validation(Ti) is less than validation(Tj) one of the following two conditions must hold-

1. finish(Ti) is less then start(Tj) or 

2. start(Tj) is less than finish(Ti) is less than validation(Tj) and read set of Tj is disjoint with write set of Ti.

The transaction which passes validation test moves to the write phase, whereas the transaction which fails validation test is rolled back and restarted.

Example

Deadlock 

A system is said to be in deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set.

for example, T1 is waiting for T2, T2 is waiting T3 and so on ... TN is waiting T1.

Example

In deadlock state execution goes down to zero level and system enters infinite wait state.

Deadlock Handling

1. Deadlock Prevention

2. Deadlock Detection and Recovery

Deadlock prevention

 In this we ensure that deadlock cannot occur in the first place. There are two different schemes under it-

1. Wait die non preemptive scheme and

2. Wound wait preemptive scheme

Wait Die

When a transaction Ti requests a data item held by Tj, Ti is allowed to wait only if it is older otherwise it is rolled back and restarted with a new timestamp.

Example

Wound wait

When a transaction Ti requests a data item held by Tj, Ti is allowed to wait only if it is younger otherwise it snatches data item from Tj and Tj is rolled back and restarted with the same timestamp.

Example

In wait die we may have starvation of transaction whereas wound wait is free from transaction starvation.

A transaction said to be starved if it fails to execute for an infinite long period.

Note - Deadlock prevention approach reduces system performance and resource utilisation.

Deadlock detection and recovery 

In this the system maintains information about the current allocation of data items to various transactions. The system also maintains information about outstanding data item requests. 

The system applies deadlock detection algorithm to determine whether the system has entered a deadlock state or not. When the system detects presence of deadlock then recovery from deadlock is performed.

Deadlock detection using wait for graph

A wait for graph consists of vertices representing transactions and edges Ti to Tj representing Ti waits for Tj.

A cycle in the wait for graph represents a deadlock state. No cycle in wait for graph means no deadlock.

Example

Recovery from deadlock 

The simplest way of recovering from deadlock is to break the wait cycle. This can be done by killing one or more transactions involved in the deadlock. 

The following actions can be taken to recover from deadlock.

1. Selection of victim. 
The following factors need to be considered for selection of victim-

a. how much a transaction has been executed and how much it remains 

b. the number of transactions involved with the rollback of victim.

c. the transaction with the lowest cost

d. how many data items are consumed by the transaction

e. priority of the transaction

f. number of previous rollback transaction has already suffered.

2.Rollback of victim transaction

Once we have selected a victim transaction. We must determine how far  this transaction should be rolled back. We have two options for rollback.

a. total rollback 

In this transaction is completely aborted and restarted 

b. Partial rollback

In this transaction is rolled back only upto that point which is necessary to break deadlock.

Note - Deadlock detection and recovery guards the system against deadlock without compromising system performance.