Concurrency Control in DBMS: Serializability and 2PL

A database serves hundreds of transactions at once. Running them strictly one after another would be correct but slow, because each spends most of its time waiting for disk, network or the user. Running them interleaved is fast, but some interleavings produce results no serial run could: lost money, wrong totals, phantom rows. Concurrency control decides which interleavings to allow. This note defines when a schedule is correct, works a precedence graph, lists the anomalies and the isolation levels that permit them, and covers the protocols that enforce correctness: two-phase locking, timestamp ordering and deadlock handling.

Schedules

A schedule is the order in which the operations of several transactions are executed, keeping each transaction's own order. Ri(X) and Wi(X) mean transaction Ti reads or writes item X.

• A serial schedule runs transactions one at a time: all of T1, then all of T2. Always correct, never concurrent.
• A concurrent (non-serial) schedule interleaves them.
• A schedule is serializable if it is equivalent to some serial schedule of the same transactions. Serializability is the definition of correctness for concurrent execution.

Conflict serializability

Two operations conflict if they belong to different transactions, access the same item, and at least one is a write:

A schedule is conflict serializable if swapping adjacent non-conflicting operations can turn it into a serial schedule. The test is the precedence graph: one node per transaction, and an edge Ti → Tj whenever an operation of Ti conflicts with a later operation of Tj. The schedule is conflict serializable if and only if the graph has no cycle, and any topological order of the graph is an equivalent serial order.

Worked example: a precedence graph

Schedule S1, with commits omitted:

Check every pair of operations on the same item from different transactions, in schedule order:

1. Scan the schedule for conflicts: two operations of different transactions on the same item, at least one a write. Each conflict adds an edge from the earlier operation's transaction to the later one's.
2. W1(A) at step 3 and R3(A) at step 4: same item A, a write then a read. Edge T1 → T3.
3. W2(B) at step 5 and R1(B) at step 6: same item B, a write then a read. Edge T2 → T1.
4. R2(B) at step 2 and W3(B) at step 7: same item B, a read then a write. Edge T2 → T3.
5. W2(B) at step 5 and W3(B) at step 7: same item B, both write. The edge T2 → T3 is already there; a second conflict adds nothing.
6. R1(B) at step 6 and W3(B) at step 7: same item B, a read then a write. The edge T1 → T3 is already there; a second conflict adds nothing.
7. The graph has 3 edges and no cycle, so S1 is conflict serializable. T2 has no incoming edge and goes first, then T1, then T3: the only topological order, and the equivalent serial schedule.

Five pairs conflict, giving the edges T2 → T1, T1 → T3 and T2 → T3. R1(A) with R3(A) and R2(B) with R1(B) are pairs of reads, so they add nothing. There is no cycle, so S1 is conflict serializable, equivalent to the serial order T2, T1, T3.

Now the schedule S2: R1(A), R2(A), W1(A), W2(A), where T1 debits ₹1,000 and T2 credits ₹500:

S2 is not conflict serializable. It is the lost update: both read the same balance, and T2's write wipes out T1's.

View serializability

Two schedules are view equivalent if every transaction reads the same values in both (same initial reads, same reads-from) and the same transaction makes the final write of each item. A schedule is view serializable if it is view equivalent to a serial one.

Every conflict-serializable schedule is view serializable, but not the reverse. S3: R1(A), W2(A), W1(A), W3(A) has edges T1 → T2 and T2 → T1, a cycle, so it is not conflict serializable. Yet it is view equivalent to T1, T2, T3: T1 reads the initial A in both, and T3 writes the final A in both. The difference comes from blind writes (W2 and W3 write A without reading it). Testing view serializability is NP-complete, which is why systems enforce conflict serializability.

Recoverable and cascadeless schedules

Serializability ignores aborts. Three stronger properties handle them:

Example of a non-recoverable schedule: W1(A), R2(A), commit T2, then T1 aborts. T2 has committed using a value that never officially existed, and durability forbids undoing it. Each class contains the next: every strict schedule is cascadeless, and every cascadeless schedule is recoverable.

Concurrency anomalies

Take account A with ₹5,000:

1. Dirty read: T2 reads 4000, written by T1 but not committed, and then T1 rolls back to 5000. T2 has acted on a value that never existed. READ COMMITTED and above prevent it.
2. Non-repeatable read: T1 reads A twice and gets 5000, then 4000, because T2 updated A and committed in between. Both values are committed; REPEATABLE READ prevents it.
3. Phantom read: T1 runs the same count twice and gets 2, then 3, because T2 inserted a matching row and committed. No row T1 read changed; only SERIALIZABLE prevents it in the standard.

Isolation levels

SQL defines four isolation levels by which of three phenomena they allow:

Defaults differ: MySQL's InnoDB uses REPEATABLE READ; PostgreSQL, Oracle and SQL Server use READ COMMITTED. Implementations go beyond the table. InnoDB's REPEATABLE READ reads from a snapshot taken at the first read and uses next-key locks for locking reads, so phantoms are prevented in most cases; PostgreSQL treats READ UNCOMMITTED as READ COMMITTED.

The lost update is not in the standard table. SERIALIZABLE prevents it. At REPEATABLE READ, PostgreSQL aborts the second writer with a serialization error, while InnoDB lets a read-then-write in application code lose an update. Avoid it with an atomic UPDATE accounts SET balance = balance - 1000, or by reading with SELECT … FOR UPDATE, which takes the write lock up front.

Most modern systems implement isolation with multi-version concurrency control (MVCC): a write creates a new version of a row, and each reader sees the versions committed as of its snapshot, so readers never block writers and writers never block readers. Writers still lock rows against each other.

Locks: shared and exclusive

A lock is a transaction's right to use an item. A shared lock (S) permits reading; an exclusive lock (X) permits reading and writing.

Locking alone does not give serializability: a transaction that unlocks A, then later locks B, can let another transaction see a mix of its old and new state. The protocol around the locks matters.

Two-phase locking

Under two-phase locking (2PL), each transaction has a growing phase, in which it may acquire locks but release none, then a shrinking phase, in which it may release locks but acquire none. The moment it acquires its last lock is its lock point. Every schedule 2PL allows is conflict serializable, in the order of the transactions' lock points.

1. Basic 2PL: T1 takes X(A) and X(B) as it needs them, and its lock point is X(B), its last acquisition. After the first unlock it may never lock again, which is what makes every 2PL schedule conflict serializable.
2. Strict 2PL holds its exclusive locks until commit, so no other transaction can read or overwrite T1's uncommitted writes. An abort then never forces anyone else to roll back.

2PL fixes the lost update, but it can deadlock, as when two transactions both read a balance under a shared lock and then both try to upgrade it to write:

1. T1 wants to read the balance, so it asks for a shared lock on A. Nobody holds A: granted.
2. T2 asks for S(A) too. Shared locks are compatible with each other, so both transactions now hold S(A) and both read the same balance.
3. T1 asks to upgrade to X(A) to write the new balance. X conflicts with T2's S, so T1 waits, and the wait-for graph gets the edge T1 → T2.
4. T2 asks to upgrade to X(A) as well, and must wait for T1's shared lock. T2 waits for T1 and T1 waits for T2: a cycle in the wait-for graph, which is a deadlock. Neither can ever proceed.
5. The DBMS finds the cycle and rolls back one victim, here T2. Its shared lock is released, T1's upgrade to X(A) is granted, and T2 restarts later. Taking X(A) at the first read, as SELECT … FOR UPDATE does, avoids this deadlock.

Timestamp ordering

The timestamp-ordering protocol uses no locks. Each transaction gets a timestamp when it starts (smaller means older), and conflicting operations must happen in timestamp order. Each item X keeps R-TS(X) and W-TS(X), the largest timestamps of transactions that read and wrote it.

A rolled-back transaction restarts with a new timestamp. The protocol guarantees conflict serializability and is deadlock-free, since nobody waits, but long transactions can starve, and schedules are recoverable only if commits are handled carefully. With the Thomas write rule it also accepts some view-serializable schedules such as S3.

Deadlock handling

A deadlock is a set of transactions each waiting for a lock held by another in the set. Systems handle it in three ways:

• Detection: keep a wait-for graph (Ti → Tj when Ti waits for a lock Tj holds); a cycle is a deadlock, and one victim is rolled back. InnoDB checks at once by default and rolls back the transaction it judges smallest, by rows changed.
• Timeout: give up after waiting too long (InnoDB's innodb_lock_wait_timeout, 50 seconds by default).
• Prevention with timestamps: wait-die and wound-wait, which let waits run in one direction only, so no cycle can form.

With T1 older (timestamp 5) and T2 younger (timestamp 10):

In both schemes the rolled-back transaction restarts with its original timestamp, so it eventually becomes the oldest and cannot starve. Wait-die can kill a young transaction repeatedly; wound-wait usually causes fewer rollbacks.

Common mistakes

• Drawing a precedence edge for two reads: only read-write, write-read and write-write pairs conflict.
• Drawing edges from the later operation to the earlier: the edge follows time.
• Saying 2PL prevents deadlocks: it guarantees serializability, and deadlocks remain possible.
• Saying serializable means "serial": the transactions still interleave.
• Assuming REPEATABLE READ prevents lost updates everywhere: InnoDB allows them for read-then-write.
• Confusing timestamp restarts: timestamp ordering restarts with a new timestamp; wait-die and wound-wait keep the old one.

Interview questions

What is the difference between conflict and view serializability? Conflict serializability requires reordering by swaps of non-conflicting operations and is tested with a precedence graph in polynomial time. View serializability only requires the same reads and final writes; it is a larger class, differing through blind writes, and testing it is NP-complete.

How do you check whether a schedule is conflict serializable? Build the precedence graph with an edge Ti → Tj for each conflicting pair where Ti's operation comes first. If there is no cycle, it is conflict serializable, and a topological sort gives the equivalent serial order.

Why does strict 2PL hold exclusive locks until commit? So that no other transaction can read or overwrite uncommitted data. That makes schedules strict, so an abort never forces other transactions to roll back.

Which anomalies does each isolation level prevent? READ COMMITTED prevents dirty reads, REPEATABLE READ also prevents non-repeatable reads, and SERIALIZABLE also prevents phantoms. READ UNCOMMITTED prevents none of the three.

How do databases detect deadlocks? They maintain a wait-for graph and look for cycles, either on every wait or periodically, then roll back a victim, usually the transaction cheapest to undo. Lock wait timeouts are a fallback.

What is MVCC and why is it used? Multi-version concurrency control keeps several committed versions of a row so each reader sees a consistent snapshot. Readers and writers do not block each other, which suits read-heavy workloads; InnoDB and PostgreSQL both use it.

What is a cascading rollback and how do you avoid it? When one transaction aborts, others that read its uncommitted writes must abort too, and so on. Cascadeless schedules, produced by strict 2PL, avoid it by letting transactions read only committed data.

Explain wait-die and wound-wait. Both give every transaction a timestamp. In wait-die, older transactions wait and younger ones requesting an older one's lock are rolled back; in wound-wait, older transactions pre-empt younger holders and younger ones wait.

Next, how a database finds rows quickly: Indexing and B+ Trees in DBMS. Isolation and transactions are examined in the SQL (Intermediate) skill test.