The idea: do the work first, check at the end
Locking assumes that transactions will get in each other's way, so it makes them wait before they touch data. Optimistic concurrency control (OCC) assumes conflicts are rare. A transaction runs without any lock, and only at the end does the system check whether it got in someone's way. If it did, it is aborted and runs again. This page shows the classic form of OCC by Kung and Robinson (1981), where each transaction goes through three phases.
- Read phase. The transaction reads items from the database and does its work. Every write goes to its own local copy (a private workspace), not to the database.
- Validation phase. When it wants to commit, it is checked against the other transactions. If the check passes, it gets a transaction number TN.
- Write phase. It copies its local writes into the database and is done.
The canvas shows three transactions T1, T2 and T3, each with its phase, its read and write sets and its local copies. Below them are the database (committed values only), the validation box with one line per check, and the validation order, which is the serial order the result is equal to. The clock t ticks once per statement.
Read sets, write sets and local copies
During the read phase the system records two sets for each transaction T:
- RS(T), the read set: the items T read from the database.
- WS(T), the write set: the items T wrote (in its local copy).
Because writes stay local, nobody else can see them, and no one can read a value that may still be thrown away. An aborted transaction leaves nothing behind in the database: there is nothing to undo and no cascading abort. If T reads an item it already wrote, it reads its own local copy, and the read set does not change.
Validation: the three conditions
The TN order is the serial order: the result must be the same as running the transactions one by one in TN order. So when Ti validates, it is checked against every transaction Tj that got its TN earlier (backward validation). For each such Tj, one of three conditions must hold:
| condition | when | check |
|---|---|---|
| (1) | Tj finished its write phase before Ti started | nothing: Ti read only values that already include Tj's writes |
| (2) | Tj finished its write phase after Ti started, before Ti validates | WS(Tj) ∩ RS(Ti) = ∅ |
| (3) | Tj is still in its write phase when Ti validates | WS(Tj) ∩ RS(Ti) = ∅ and WS(Tj) ∩ WS(Ti) = ∅ |
Condition 2 says: Ti must not have read anything Tj wrote. Ti may have read the old value, from before Tj's write phase, while the serial order says Tj comes first and Ti should have seen the new one. If the sets are disjoint, the order makes no difference to Ti. In Demo: low contention, different items, T2 is checked by condition 2: WS(T1) ∩ RS(T2) = {A} ∩ {B} = ∅, so T2 passes with TN 2.
Condition 3 adds a second check because the write phases overlap. Even if Ti read nothing Tj writes, both may write the same item, and Ti's value could reach the database before Tj's and then be overwritten by the older Tj. That is the wrong order. Demo: overlapping write phases, no common item passes both checks, and T2 even finishes its write phase before T1. Demo: overlapping write phases, same item fails: WS(T1) ∩ RS(T2) = ∅, but WS(T1) ∩ WS(T2) = {A}.
Only the read set counts for condition 2. In Demo: blind writes after a finished write phase, T1 and T2 both write A without reading it. T1 finishes first, and T2 passes because RS(T2) = ∅: in the serial order T1, T2, the value of T2 is last, and that is what the database holds.
Abort and restart
When a check fails, Ti is aborted. Its local copies are simply dropped. Then it starts again with a new start time and empty sets. Usually the transaction it lost to has finished by then, so on the second try that one falls under condition 1. In Demo: stale read, abort and restart, both T1 and T2 read A = initial and write A. T1 validates first and writes A. T2's check fails at t = 9: WS(T1) ∩ RS(T2) = {A} ∩ {A} = {A}. T2 restarts at t = 10, reads T1's value of A, and passes with TN 2 because T1 finished at t = 8, before T2 started. Without the check, T2 would have overwritten T1's update with a value computed from a stale read: a lost update.
The work done in the failed run is lost. The page counts it as wasted ops: the reads and writes of every aborted run. A transaction that keeps losing can be aborted again and again (starvation). Real systems give up after some tries, or let it run with locks the next time.
Low and high contention
OCC is cheap when transactions rarely touch the same items: no lock table, no waiting and no deadlocks. It gets expensive when many transactions update the same item. In Demo: high contention, three on one item, T1, T2 and T3 all read and write A. T1 validates first; T2 and T3 then fail and must redo their work: 2 aborts and 4 wasted operations, 5 validations for 3 commits.
| two-phase locking | validation-based OCC | |
|---|---|---|
| a conflict is found | when the second transaction touches the item | at the end, during validation |
| a conflict costs | a wait (or a deadlock and a rollback) | an abort and a full redo |
| low contention | works, but pays for locks it did not need | best: no locks, no waits, no aborts |
| high contention | queues the transactions; each work is done once | many aborts and much wasted work |
| undo on abort | yes, writes were in the database | no, writes were only local |
The high-contention schedule is hard for locking too: under two-phase locking, T1, T2 and T3 each hold a shared lock on A and each wants to upgrade it to an exclusive lock, which is a deadlock. Timestamp ordering checks each read and write as it happens instead of at the end: see Timestamp Ordering. To test a schedule for conflict-serializability directly, see Conflict Serializability.
What MariaDB does
MariaDB does not use validation-based OCC. InnoDB takes row locks for writes and locking reads (strict two-phase locking), and gives plain SELECT a consistent snapshot through MVCC: see Two-Phase Locking, MVCC and Isolation Levels and InnoDB Isolation. There are no read sets and no validation phase in the engine.
An application can still work optimistically on top of MariaDB, with a version column. It reads the row and its version without a lock, does its work, and then writes only if the version has not changed:
SELECT stock, version FROM items WHERE id = 1; -- 10, 3 (no lock) -- work ... UPDATE items SET stock = 9, version = version + 1 WHERE id = 1 AND version = 3; SELECT ROW_COUNT(); -- 1: done; 0: someone else won, retry
The UPDATE is the validation and the write phase in one statement: InnoDB locks the row while it checks version = 3, so two clients cannot both pass. The read set is just that one row. If the update matched 0 rows, the client starts again from the SELECT. Optimistic vs Pessimistic Locking animates this next to SELECT … FOR UPDATE.
See also recoverable, cascadeless and strict schedules for what goes wrong when one transaction reads another's uncommitted data.
What the page leaves out
Forward validation (checking the validating transaction against the ones still in their read phase, instead of the ones that finished). How the validation step itself is protected: Kung and Robinson put validation and the write phase in one critical section for serial validation, and the page lets the validation step be atomic and keeps the write phase separate so that condition 3 can be seen. Read sets of ranges and predicates (phantoms). Starvation control and backoff. Modern in-memory OCC engines (such as Silo and Hekaton) that validate with per-record version numbers. MariaDB has none of these in InnoDB; the version column above is the only optimistic scheme it supports, and it lives in the application.