11.6 Optimistic Techniques

In many environments, conflicts between transactions are relatively rare, and the extra processing required to apply locking schemes is unnecessary for most of the transactions. There is a class of techniques that reduces this overhead. Validation techniques, also called optimistic techniques, work under the assumption that conflict will normally not occur. They allow transactions to proceed as if there were no concurrency problems, but just before a transaction commits, a check is performed to determine whether a conflict has occurred. If there is a conflict, the transaction must be rolled back. Because the assumption is that conflict rarely occurs in this environment, rollback will be rare. The occasional rollback is the price to be paid for eliminating locks. These techniques allow more concurrency than traditional schemes because no locking is done.

In optimistic schemes, a transaction goes through two or three phases in order, depending on whether it is a read-only or an updating transaction:

1. A read phase that extends from the start of the transaction until just before it commits. During this phase, the transaction reads the values of all the data items it needs and stores them in local variables. If the transaction does any writes, they are done to a local copy of the data, not to the database itself.

2. A validation phase that follows the read phase. During this time, the transaction tests to determine whether there is any interference.

   1. For a read-only transaction, this consists of checking to see that there was no error caused by another transaction that was active when the data values were read. If no error occurred, the transaction is committed. If interference occurred, the transaction is aborted and restarted.

   2. For a transaction that does updates, validation consists of determining whether the current transaction will leave the database in a consistent state, with serializability maintained. If not, the transaction is aborted. If the update transaction passes the validation test, it goes on to a third phase.

3. A write phase that follows the successful validation phase for update transactions. During this phase, the updates made to the local copy are applied to the database itself.

The validation phase is accomplished by examining the reads and writes of transactions that may cause interference. Each transaction, T, is given three timestamps:

• Start(T), the starting time of the transaction

• Validation(T), the time when it ends its read phase and enters its validation phase

• Finish(T), the time it finishes, including its write phase, if any

To pass the validation test, we compare other transactions’ timestamps with Validation(T) and attempt to keep transactions in order. For any other transaction, S, one of the following must be true:

1. All transactions with earlier validation timestamps must have finished (including their writes) before the current transaction started. That means for any transaction S with Validation(S)<Validation(T), we must have Finish(S)<Start(T).

   or

2. If the current transaction starts before an earlier one finishes, that is, if Start(T)<Finish(S), then both of the following are true:

   1. The items written by the earlier transaction, S, are not the ones read by the current transaction, T.

   2. The earlier transaction, S, completes its write phase before the current transaction, T, enters its validation phase; that is, Finish(S)<Validation(T).

Rule 2(a) guarantees that the writes of the earlier transaction are not read by the current transaction, while rule 2(b) guarantees that the writes are done serially.

Although optimistic techniques are very efficient when there are few conflicts, they can result in rollback of individual transactions. Note that the rollback involves only a local copy of the data, so there are no cascading rollbacks because the writes have not actually reached the database. However, if the aborted transaction is a long one, valuable processing time will be lost, as the transaction must be restarted. If rollback occurs often, it is an indication that the optimistic method is a poor choice for concurrency control in the current application environment.