Concurrency Control: Schedules and Serializability

Account 7 holds 100. Transaction A wants to debit 20, transaction B wants to debit 30. Each does the obvious thing: read the balance, subtract, write the result. The engine runs them interleaved.

Final balance: 70. Correct balance: 50. Nothing failed, nothing was rejected, no lock was requested. A's write was simply overwritten by a value computed from a stale read. This is the lost update, and every concurrency control mechanism exists to make this schedule either impossible or detectable.

A schedule is the global order in which the operations of concurrent transactions actually executed. A serial schedule runs each transaction to completion before the next starts; serial schedules are correct by definition, whatever the transactions do. Two operations conflict when they come from different transactions, touch the same item, and at least one is a write: read–write, write–read and write–write pairs. Read–read pairs never conflict.

Swapping two adjacent non-conflicting operations cannot change any result, since neither could observe the other. A schedule is conflict-serializable if a sequence of such swaps turns it into a serial schedule. The test is mechanical: draw a node per transaction and an edge Ti → Tj for every conflict where Ti's operation came first. If the graph is acyclic, a topological order of it is a serial schedule the interleaving is equivalent to. If it has a cycle, no serial order matches. In the schedule above, B's read precedes A's write (B → A) and A's write precedes B's write (A → B): a cycle of length two.

Every anomaly in the practical lesson is a particular shape of conflicting schedule. Seeing them as schedules explains why they need different mechanisms: some are visible on a single item, and some only exist at the level of predicates or of pairs of items.

Prevent the conflict from forming. Before reading, take a shared lock on the item; before writing, an exclusive one; a conflicting request waits. Two-phase locking (2PL) adds the rule that makes this correct: a transaction acquires all its locks before it releases any (a growing phase, then a shrinking phase). Under 2PL every admitted schedule is conflict-serializable, because the point where a transaction holds its maximum set of locks orders it with respect to every transaction it conflicts with. Strict 2PL holds locks until commit, which additionally rules out dirty reads and cascading aborts, and is what real engines do.

In the lost-update schedule, A's read would take a shared lock; B's read a second shared lock; A's write would need to upgrade to exclusive and would wait for B; B's write would wait for A — a deadlock, which is detected and broken. The anomaly turns into an abort, which is the correct outcome. Locking is exact, and it pays in waiting and deadlocks; The Lock Manager shows the structure that grants the locks and Deadlock Detection: The Waits-For Graph the one that breaks the cycles.

Optimistic concurrency control (Kung and Robinson, 1981) assumes conflicts are rare. A transaction runs in three phases: *read* — execute freely against the database, buffering writes privately and recording the read set; *validate* — at commit, check that no transaction that committed since this one started wrote anything in its read set; *write* — install the buffered writes. Fail validation and the transaction restarts. No waiting ever, no deadlocks ever; the cost is wasted work under contention.

Multi-version concurrency control takes the reader side of that idea and makes it structural: never overwrite, keep every version, and give each transaction a snapshot that selects the versions it may see. Readers need no locks and no validation, because the versions they read cannot change. Writers still conflict, and engines handle that either with row locks (a write waits for a concurrent writer of the same row and then re-checks, or aborts) or with validation at commit. The result is a hybrid: pessimistic for write–write conflicts, optimistic for everything else. MVCC Internals: Version Chains and Snapshots derives the version chain and the visibility rule.

A workload is typically nine reads for every write. Giving reads the multi-version path removes them from the lock manager entirely: no lock table entries, no waiting, no deadlock participation. Writes are rarer and benefit from the exactness of locks — a row lock held to commit means a write–write conflict resolves in a definite order and the loser sees the winner's result rather than restarting blindly. Full serializability, which needs read–write conflicts tracked too, is the rare requirement, so it gets a separate mechanism that only those transactions pay for.

PostgreSQL: snapshot reads, row locks for writers, SSI dependency tracking at SERIALIZABLE. InnoDB: snapshot (read view) reads, next-key locks for writers and locking reads, SELECTs promoted to locking reads at SERIALIZABLE. Oracle: snapshot reads, row locks, and a SERIALIZABLE that is really snapshot isolation. The names of the levels are the same; the mechanisms — and therefore the anomalies that slip through — are not, which is the subject of Isolation Levels: The Mechanism Behind Each.