Concurrency control
Many transactions run at once. Concurrency control lets them overlap for speed while producing results equivalent to some serial order.
Schedules and serialisability
A schedule is an interleaving of the operations of concurrent transactions. A serial schedule runs transactions one at a time. A schedule is serialisable if its effect equals that of some serial schedule. Serialisability is the gold standard of correctness: users can reason as if transactions never overlapped.
Conflicts
Two operations conflict if they belong to different transactions, access the same item, and at least one is a write: read-write, write-read, or write-write. Conflict serialisability checks whether conflicting operations can be ordered consistently: draw a precedence graph with an edge from T1 to T2 when an operation of T1 conflicts with and precedes one of T2; the schedule is conflict serialisable exactly when the graph has no cycle.
Anomalies
Weak control allows anomalies. A dirty read sees another transaction's uncommitted data, which might be rolled back. A non-repeatable read sees a row change between two reads in the same transaction. A phantom read sees new rows appear that match a repeated query. A lost update occurs when two transactions read, modify, and write the same value, and one overwrites the other.
Two-phase locking
Two-phase locking (2PL) guarantees conflict serialisability. Transactions acquire shared locks to read and exclusive locks to write; in the growing phase they acquire locks, and once they release any lock, in the shrinking phase, they may acquire no more. Strict 2PL holds exclusive locks until commit, preventing others from reading uncommitted data and simplifying recovery.
Lock granularity
Locks can cover rows, pages, or whole tables. Fine-grained row locks allow more concurrency but cost more to manage; coarse locks are cheap but block more. Intention locks on tables signal that a transaction holds row locks inside, letting the system check table-level requests quickly. Some systems escalate many row locks into a table lock automatically.
Optimistic and timestamp methods
Optimistic concurrency control lets transactions run without locks, then validates at commit that nothing they read has changed; if it has, the transaction aborts and retries. This suits low-contention workloads. Timestamp ordering assigns each transaction a timestamp and ensures conflicting operations execute in timestamp order, aborting transactions that would violate it.
Application-level patterns
Applications can prevent lost updates with SELECT ... FOR UPDATE, which locks rows read for later modification, or with atomic statements such as UPDATE stock SET qty = qty - 1 WHERE id = 5 AND qty > 0, which read and write in one step. Web applications often use optimistic version columns: UPDATE ... WHERE id = 7 AND version = 3, failing if someone else changed the row first.
Worked example
T1 reads balance 100, T2 reads balance 100, T1 writes 100 + 50 = 150, T2 writes 100 - 30 = 70, both commit. The final balance is 70, and T1's deposit is lost: a lost update. The precedence graph has T1 to T2 (T1's read before T2's write) and T2 to T1 (T2's read before T1's write): a cycle, so the schedule is not serialisable. Under 2PL, T2 would wait for T1's exclusive lock, giving 120.
Key takeaways
A schedule interleaves transactions; serialisable schedules match some serial order. Conflicting operations touch the same item from different transactions with at least one write; acyclic precedence graphs mean conflict serialisability. Anomalies include dirty reads, non-repeatable reads, phantoms, and lost updates. Two-phase locking, with shared and exclusive locks and growing then shrinking phases, guarantees serialisability; strict 2PL holds write locks until commit. Lock granularity trades concurrency for overhead. Optimistic and timestamp methods avoid locks but may abort. FOR UPDATE, atomic updates, and version columns prevent lost updates in applications.
Flashcard
Interleaving of concurrent operations
Check your understanding
Under two-phase locking, what is a transaction forbidden to do after it releases its first lock?