Flat/nested transactions; optimistic CC

Flat and nested transactions

• Flat transaction: a single-level transaction that issues its requests one after another on one or more objects. If any step fails, the whole transaction aborts and everything is undone. Example: a bank transfer withdraw(A, 100); deposit(B, 100). Its drawback is that it cannot commit part of its work and has no internal concurrency.
• Nested transaction: a transaction made of sub-transactions in a tree. The top-level transaction contains child transactions, which may contain their own children. Sub-transactions at the same level can run concurrently, and a sub-transaction can abort without aborting its parent; the parent may retry or choose another action. Example: a book trip transaction with sub-transactions book flight, book hotel, book taxi. If the taxi booking fails, the parent can try another company.

Rules of nested transactions:

• A sub-transaction commits only provisionally; its result becomes permanent only when all its ancestors commit up to the top level.
• If a parent aborts, all its sub-transactions abort, even those that provisionally committed.
• A child sees the parent's changes, but the parent does not see the child's until the child commits.

Optimistic concurrency control in distributed transactions

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.

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.

In distributed transactions: each server validates its own part of the transaction during the first (voting) phase of two-phase commit. If any server finds a conflict, it votes No, and the transaction is aborted everywhere. If each server validates one transaction at a time, commitment deadlock can arise (server X is validating T and waits for U, while server Y is validating U and waits for T); parallel validation avoids this. The servers must also agree on one serial order, for example by a global validation step after the local ones, or by giving each transaction a globally unique number at the start of validation.