Multi-version & Optimistic Concurrency Control Schemes

 Multiversion Schemes

In multi-version concurrency control schemes, each writes (Q) operation creates a new version of Q. When a transaction issues a read(Q) operation, the concurrency control

manager selects one of the versions of Q to be read. The concurrency-control scheme must ensure that the version to be read is selected in a manner that ensures serializability. It is also crucial, for performance reasons, that a transaction be able to determine easily and quickly which version of the data item should be read.

Multiversion Timestamp Ordering

The most common transaction ordering technique used by multiversion schemes is timestamping. With each transaction Ti in the system, we associate a unique static timestamp, denoted by TS(Ti). The database system assigns this timestamp before the transaction starts execution.

With each data item Q, a sequence of versions <Q1, Q2,... ., Qm> is associated. Each version Qk contains three data fields:

• Content is the value of version Qk.

• W-timestamp(Qk) is the timestamp of the transaction that created version Qk.

• R-timestamp(Qk) is the largest timestamp of any transaction that successfully read version Qk.

A transaction—say, Ti—creates a new version Qk of data item Q by issuing a write(Q) operation. The content field of the version holds the value written by Ti. The system initializes the W-timestamp and R-timestamp to TS(Ti). It updates the R-timestamp value of Qk whenever a transaction Tj reads the content of Qk, and R-timestamp(Qk) < TS(Tj ).

Multiversion Two-Phase Locking

The multiversion two-phase locking protocol attempts to combine the advantages of multiversion concurrency control with the advantages of two-phase locking. This protocol differentiates between read-only transactions and update transactions. 

Update transactions perform rigorous two-phase locking; that is, they hold all locks up to the end of the transaction. Thus, they can be serialized according to their commit order. Each version of a data item has a single timestamp. The timestamp in this case is not a real clock-based timestamp, but rather is a counter, which we will call the ts-counter, that is incremented during commit processing. 

Read-only transactions are assigned a timestamp by reading the current value of the ts-counter before they start execution; they follow the multiversion timestamp ordering protocol for performing reads. Thus, when a read-only transaction Ti issues a read(Q), the value returned is the contents of the version whose timestamp is the largest timestamp less than TS(Ti).