Validation (Optimistic) Concurrency Control Techniques
In all the concurrency control techniques we have discussed so far, a certain degree of checking is done before a database operation can be executed. For example, in locking, a check is done to determine whether the item being accessed is locked. In timestamp ordering, the transaction timestamp is checked against the read and write timestamps of the item. Such checking represents overhead during transaction execution, with the effect of slowing down the transactions.
In optimistic concurrency control techniques, also known as validation or certification techniques, no checking is done while the transaction is executing. Several theoretical concurrency control methods are based on the validation technique. We will describe only one scheme here. In this scheme, updates in the trans-action are not applied directly to the database items until the transaction reaches its end. During transaction execution, all updates are applied to local copies of the data items that are kept for the transaction.6 At the end of transaction execution, a validation phase checks whether any of the transaction’s updates violate serializability. Certain information needed by the validation phase must be kept by the system. If serializability is not violated, the transaction is committed and the database is updated from the local copies; otherwise, the transaction is aborted and then restarted later.
There are three phases for this concurrency control protocol:
Read phase. A transaction can read values of committed data items from the database. However, updates are applied only to local copies (versions) of the data items kept in the transaction workspace.
Validation phase. Checking is performed to ensure that serializability will not be violated if the transaction updates are applied to the database.
Write phase. If the validation phase is successful, the transaction updates are applied to the database; otherwise, the updates are discarded and the trans-action is restarted.
The idea behind optimistic concurrency control is to do all the checks at once; hence, transaction execution proceeds with a minimum of overhead until the validation phase is reached. If there is little interference among transactions, most will be validated successfully. However, if there is much interference, many transactions that execute to completion will have their results discarded and must be restarted later. Under these circumstances, optimistic techniques do not work well. The techniques are called optimistic because they assume that little interference will occur and hence that there is no need to do checking during transaction execution.
The optimistic protocol we describe uses transaction timestamps and also requires that the write_sets and read_sets of the transactions be kept by the system. Additionally, start and end times for some of the three phases need to be kept for each transaction. Recall that the write_set of a transaction is the set of items it writes, and the read_set is the set of items it reads. In the validation phase for transaction Ti, the protocol checks that Ti does not interfere with any committed transactions or with any other transactions currently in their validation phase. The validation phase for Ti checks that, for each such transaction Tj that is either committed or is in its validation phase, one of the following conditions holds:
Transaction Tj completes its write phase before Ti starts its read phase.
Ti starts its write phase after Tj completes its write phase, and the read_set of Ti has no items in common with the write_set of Tj.
Both the read_set and write_set of Ti have no items in common with the write_set of Tj, and Tj completes its read phase before Ti completes its read phase.
When validating transaction Ti, the first condition is checked first for each transaction Tj, since (1) is the simplest condition to check. Only if condition 1 is false is condition 2 checked, and only if (2) is false is condition 3—the most complex to evaluate—checked. If any one of these three conditions holds, there is no interference and Ti is validated successfully. If none of these three conditions holds, the validation of transaction Ti fails and it is aborted and restarted later because interference may have occurred.