Multiversion Schemes
n Multiversion schemes keep old versions of data item to increase concurrency.
l Multiversion Timestamp Ordering
l Multiversion Two-Phase Locking
n Each successful write results in the creation of a new version of the data item written.
n Use timestamps to label versions.
n When a read(Q) operation is issued, select an appropriate version of Q based on the
timestamp of the transaction, and return the value of the selected version.
n reads never have to wait as an appropriate version is returned immediately.
Multiversion Timestamp Ordering
n Each data item Q has a sequence of versions <Q1, Q2,...., Qm>. Each version Qk contains three
data fields:
l Content -- the value of version Qk.
l W-timestamp(Qk) -- timestamp of the transaction that created (wrote) version Qk
l R-timestamp(Qk) -- largest timestamp of a transaction that successfully read version
Qk
n When a transaction Ti creates a new version Qk of Q, Qk's W-timestamp and R-timestamp are
initialized to TS(Ti).
n R-timestamp of Qk is updated whenever a transaction Tj reads Qk, and TS(Tj) > R-
timestamp(Qk).
n Suppose that transaction Ti issues a read(Q) or write(Q) operation. Let Qk denote the
version of Q whose write timestamp is the largest write timestamp less than or equal to
TS(Ti).
l If transaction Ti issues a read(Q), then the value returned is the content of
version Qk.
l If transaction Ti issues a write(Q)
n if TS(Ti) < R-timestamp(Qk), then transaction Ti is rolled back.
n if TS(Ti) = W-timestamp(Qk), the contents of Qk are overwritten
n else a new version of Q is created.
n Observe that
l Reads always succeed
l A write by Ti is rejected if some other transaction Tj that (in the serialization order
defined by the timestamp values) should read
Ti's write, has already read a version created by a transaction older than Ti.
n Protocol guarantees serializability
Multiversion Two-Phase Locking
n Differentiates between read-only transactions and update transactions
n Update transactions acquire read and write locks, and hold all locks up to the end of the
transaction. That is, update transactions follow rigorous two-phase locking.
l Each successful write results in the creation of a new version of the data item
written.
l Each version of a data item has a single timestamp whose value is obtained from a
counter ts-counter that is incremented during commit processing.
n Read-only transactions are assigned a timestamp by reading the current value of ts-counter
before they start execution; they follow the multiversion timestamp-ordering protocol for
performing reads.
n When an update transaction wants to read a data item:
l it obtains a shared lock on it, and reads the latest version.
n When it wants to write an item
l it obtains X lock on; it then creates a new version of the item and sets this version's
timestamp to .
n When update transaction Ti completes, commit processing occurs:
l Ti sets timestamp on the versions it has created to ts-counter + 1
l Ti increments ts-counter by 1
n Read-only transactions that start after Ti increments ts-counter will see the values updated
by Ti.
n Read-only transactions that start before Ti increments the
ts-counter will see the value before the updates by Ti.
n Only serializable schedules are produced.
