As we have seen above, a problem with 2PL is that it can lead to deadlocks. Reed's multiversion timestamp ordering scheme solves this problem by ordering transactions and aborting transactions that access data out of order. It also increases the concurrency in the system by never making an operation block (though it does abort transactions.)
2PL works because the lock status of items indicates the order in which transactions are currently accessing items, and locks are held long enough so that we can detect if serializablity is violated. Thus, if a transaction T2 tries to access an item T1 locked by another, then we know that T2 accesses the item after T1. As we saw earlier cyclic references in the transaction graph result in cylic locking.
Reed's scheme uses a more direct approach to determine the order in which items are accessed - timestamps. The basic idea is to assign transactions timestamps when they are started (which are used to order these transactions), keep with each data item information about the history of transactions that have accessed it so far and the kind of accesses they have made, and if two transactions access data items in an order that is inconsistent with their time stamps, then abort one of them.
Consider again the following schedule.
Assume T1 entered the system before T2. Then the system will try to serialize them in this order. When transaction T1 tries to read p2 written earlier by T2, it aborts one of them as they are out of the serialization order being enforced.
A possible implementation of this approach is to require each data item to remember the timestamps of the last transactions that wrote and read the item. If a transaction with an earlier timestamp than the write timestamp tries to read or write to this item, then it is aborted. Similarly, if a transaction with an earlier timestamp than the read timestamp tries to write to this item, then it is aborted. This implementation would allow the schedule of Figure 1 but not Figure 6.
Unfortunately, this scheme is too conservative in comparison to Reed's scheme. The problem with it is that it does not recognize that we can concurrently have transactions working with different versions of a data item that can be serialized.
Therefore, Reed's algorithm is more complicated.
As with the simpler scheme given above,
it assigns transactions timestamps when they are started,
which are used to order these transactions.
Moreover,
it associates each data item
with timestamped versions and associates each version with
readtimestamps.
A readtimestamp is associated with a data item whenever a transaction
reads the data item and is the same as the timestamp of the reading transaction.
A timestamped version is created whenever a transaction writes
a new value to the data item and has the timestamp of the writing transaction.
The following steps occur when a transaction accesses the database:
If the operation is a read,
then it is allowed,
and the version read is the one with the largest timestamp less
than the timestamp of the reading transaction.
The timestamp of the reading transaction is added to the item.
If the operation is a write,
then a new version of the data item is created with the timestamp
of the writing transaction as long as no transaction with a more recent
timestamp has read a version of the item with an older timestamp than
that of the writing transaction. If this check fails,
the writing transaction is aborted and restarted.
This approach will support the schedule shown in Figure 7 but not Figure 6. None of the schemes we have seen so far support the schedule of Figure 7. By making sure that T2 does not read the latest version of p, the scheme supports serializability. The problem with this scheme is the cost of keeping multiple versions and associated time stamps.
Perhaps even more interesting, it will allow the following schedule:
Here T2 writes the item after T3 writes it and T4 reads it, yet that is not a problem as no transaction after T2 has read a version with a time stamp earlier than T2. A scheme that kept a single time stamp with the object would not be able to allow this schedule.
Of course one problem with this scheme is that it tries only one serial order. Thus the following serializable schedule is not allowed:
