Two-version locking; optimistic CC

Two-version locking

Two-version locking is a concurrency control method that allows one transaction to write tentative versions of an object while others read the last committed version. Each object can have two versions: a committed version and a tentative version (written by an uncommitted transaction).

Locks have three modes: read, write and commit.

• A read lock is allowed even if another transaction holds a write lock (it reads the committed version), but not if a commit lock is held.
• A write lock is allowed only if no other write lock is held (only one tentative version can exist); it can coexist with read locks.
• Before commit, a transaction converts its write locks to commit locks. This must wait until all read locks on the object are released (readers of the old version finish), and then the tentative version becomes the committed version.

This gives more concurrency than simple locking (readers are not blocked by writers) but commit can be delayed, and deadlock is still possible.

Optimistic concurrency control

Optimistic concurrency control (Kung and Robinson) assumes conflicts are rare, so transactions proceed without locks and are checked for conflicts only when they want to commit. A transaction goes through three phases.

1. Working phase: it reads and writes tentative copies of objects (private versions). Reads see the last committed values; no locks are taken. The system records the read set and write set.
2. Validation phase: when the client requests commit, the server checks for conflicts with other transactions that overlapped in time. If validation fails, the transaction is aborted (or conflict resolution is used).
3. Update phase: if validation succeeds, tentative versions are made permanent (written to permanent storage) and the transaction commits.

Validation (backward validation): transaction Tv is checked against earlier overlapping transactions Ti that committed before Tv started validation. Rules:

• If Ti writes an object that Tv reads (Ti's write set ∩ Tv's read set ≠ ∅), validation fails, because Tv read stale data.
• Otherwise Tv passes validation. (Writes are applied in commit order, so write-write conflicts cannot occur.)

Forward validation checks Tv's write set against the read sets of still-active transactions; it allows a choice of aborting Tv or the others.

In a distributed system, each server validates its own part of the transaction during the first phase of two-phase commit, and all servers must validate in the same global order to avoid commitment deadlock and inconsistent serial orders.

Advantages

• No locking, so no deadlock and no lock overhead.
• High concurrency when conflicts are rare; with forward validation, read-only transactions always pass validation.
• Abort is cheap because nothing was written permanently.

Disadvantages

• Under heavy conflicts many transactions abort and restart; starvation is possible.
• Wasted work for aborted transactions.