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.)
The basic idea in this scheme is to assign transactions timestamps when they are started, which are used to order these transactions. If two transactions access data items in an order that is inconsistent with their time stamps, then one of them is aborted.
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 remembered.
A possible implementation of this approach is to require each data item to remember the timestamp of the last transaction that wrote the item. If a transaction with an earlier timestamp tries to read or 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 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 T1 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.
