Information Technology Reference
In-Depth Information
Multiversion Concurrency Control
An alternative to enforcing transaction isolation with locks is to enforce it with multi-
version concurrency control. In multiversion concurrency control each write of an object
x creates new version of x, the system keeps multiple versions of x, and the system
directs each read to a specific version of x. By keeping multiple versions of objects,
the system can allow transaction A to read a version of x that has been overwritten by
transaction B even if B needs to be serialized after A.
There are various multiversion concurrency control algorithms that ensure serializ-
ability. A simple one is multiversion timestamp ordering (MVTO), which processes con-
current transactions, enforces serializability, never blocks a transaction's reads or writes,
but which may cause a transaction to roll back if it detects that a read of a later transac-
tion (based on the serializable schedule MVTO is enforcing) was executed before—and
therefore did not observe—the write of an earlier transaction (in serialization order.)
MVTO assigns each transaction T a logical timestamp. Then, when T writes an
object x, MVTO creates a new version of x labeled with T's timestamp t T , and when T
reads an object y, MVTO returns the version of y, y v with the highest timestamp that
is at most T's timestamp; MVTO also makes note that y v was read by transaction t T .
Finally, when T attempts to commit, MVTO blocks the commit until all transactions with
smaller timestamps have comitted or aborted.
MVTO rolls back transaction rather than allowing it to commit in three situations. First,
If MVTO aborts any transaction, it removes the object versions written by that transac-
tion and rolls back any transactions that read those versions. Notice that a transaction
that reads a version must have a higher timestamp than the one that wrote it, so no
committed transactions need to be rolled back.
Second, if a transaction T writes an object that has already been read by a later
transaction T 0 that observed the version immediately prior to T's write, T MVTO rolls
back T. It does this because if T were to commit, T 0 's read must return T's write, but
that did not occur.
Third, if MVTO garbage collects old versions and transaction T reads an object for
which the last write by an earlier transaction has been garbage collected, then MVTO
rolls back T.
Additional details and alternative implementations of multiversion concurrency con-
trol for transactions are available in Concurrency Control and Recovery in Database
Systems by Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman (chapter 5).
Search WWH ::




Custom Search