Notes › DBMS
Concurrency Control, Schedules and Locking
A database runs many transactions at the same time for speed. Concurrency control makes sure the result is the same as if they had run one after another — the I (Isolation) in ACID.
What can go wrong
| Problem | What happens | Example |
|---|---|---|
| Lost update | two writes, one overwrites the other | T1 and T2 both read balance 100, add 50 and 20 → final 120 instead of 170 |
| Dirty read | read data another transaction hasn't committed | T2 reads T1's change, T1 rolls back |
| Non-repeatable read | the same row read twice gives different values | T2 updates the row between T1's two reads |
| Phantom read | the same query returns new rows | T2 inserts a row matching T1's WHERE |
Schedules
A schedule is the order in which operations (R = read, W = write) of several transactions run.
- Serial schedule: one transaction fully, then the next. Always correct, but no concurrency.
- Serializable schedule: concurrent, but its effect equals some serial schedule. This is the goal.
Conflicting operations
Two operations conflict if they are from different transactions, on the same data item, and at least one is a write:
| Pair | Conflict? |
|---|---|
| R(A) – R(A) | ❌ |
| R(A) – W(A) | ✅ |
| W(A) – R(A) | ✅ |
| W(A) – W(A) | ✅ |
Conflict serializability — the precedence graph test
- Make a node for each transaction.
- For each conflicting pair where Ti's operation comes before Tj's, draw an edge Ti → Tj.
- No cycle → conflict serializable. A topological order of the graph gives the equivalent serial order.
Example
S: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)
Conflicts: W1(A)→R2(A), W1(B)→R2(B) … all edges are T1 → T2. No cycle → serializable, equivalent to T1, T2.
S: R1(A) R2(A) W1(A) W2(A)
R1(A)→W2(A) gives T1→T2; R2(A)→W1(A) gives T2→T1 → cycle → not conflict serializable (this is the lost-update pattern).
View serializability is a weaker condition (same initial reads, same reads-from, same final writes). Every conflict-serializable schedule is view-serializable, not the reverse; a view-serializable but not conflict-serializable schedule always contains a blind write (write without reading first). Testing view serializability is NP-complete.
Recoverability
| Type | Rule | Why |
|---|---|---|
| Recoverable | if T2 reads from T1, T1 commits before T2 commits | otherwise T2 commits data that may be rolled back |
| Cascadeless | read only committed data | one abort doesn't force a chain of aborts (cascading rollback) |
| Strict | no read or write of an item until the last writer commits/aborts | simplest recovery |
| Strict ⊂ Cascadeless ⊂ Recoverable. |
Lock-based protocols
- Shared lock (S): for reading; many transactions can hold it together.
- Exclusive lock (X): for writing; only one holder, no one else can read.
| Held \ Requested | S | X |
|---|---|---|
| S | ✅ grant | ❌ wait |
| X | ❌ wait | ❌ wait |
Two-Phase Locking (2PL)
- Growing phase: may acquire locks, may not release any.
- Shrinking phase: may release locks, may not acquire any.
The moment of the last lock acquired is the lock point. 2PL guarantees conflict serializability (serial order = order of lock points), but not freedom from deadlock, and plain 2PL can still give cascading rollbacks.
| Variant | Extra rule | Gives |
|---|---|---|
| Basic 2PL | — | serializability |
| Strict 2PL | hold all X locks until commit | + cascadeless, strict schedules (used by most DBs) |
| Rigorous 2PL | hold all locks until commit | + serial order = commit order |
| Conservative 2PL | take all locks before starting | + no deadlock (hard in practice) |
Deadlocks in databases
T1 locks A and waits for B; T2 locks B and waits for A. DBs detect cycles in a wait-for graph and abort one transaction (the victim), or prevent deadlocks with timestamps:
| Scheme | Older Ti requests a lock held by younger Tj | Younger Ti requests a lock held by older Tj |
|---|---|---|
| Wait–Die | Ti waits | Ti dies (restarts with the same timestamp) |
| Wound–Wait | Ti wounds Tj (Tj aborts) | Ti waits |
| Both ensure older transactions are favoured, so no starvation. More: Deadlocks. |
Timestamp ordering
Each transaction gets a timestamp when it starts; operations must follow timestamp order. Each item keeps read_TS and write_TS.
- Ti reads X: if
TS(Ti) < write_TS(X)→ abort Ti (it would read a value from the future). - Ti writes X: if
TS(Ti) < read_TS(X)orTS(Ti) < write_TS(X)→ abort Ti. - Thomas write rule: if
TS(Ti) < write_TS(X)only, just ignore the outdated write. No locks → no deadlocks, but more restarts.
Optimistic concurrency & MVCC
- Optimistic (validation-based): read and compute freely, check for conflicts only at commit. Great when conflicts are rare. Web apps do this with a version column:
UPDATE … SET qty=?, version=version+1 WHERE id=? AND version=?— 0 rows updated means someone else changed it. - MVCC (multi-version concurrency control): writers create a new version; readers see a consistent snapshot — readers never block writers. Used by PostgreSQL, MySQL InnoDB, Oracle, MongoDB.
SQL isolation levels
| Level | Dirty read | Non-repeatable read | Phantom |
|---|---|---|---|
| Read Uncommitted | possible | possible | possible |
| Read Committed (PostgreSQL, Oracle default) | ❌ | possible | possible |
| Repeatable Read (MySQL InnoDB default) | ❌ | ❌ | possible* |
| Serializable | ❌ | ❌ | ❌ |
| *InnoDB's next-key locks prevent most phantoms in practice. |
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE; -- lock the row
UPDATE accounts SET balance = balance - 500 WHERE id = 1;
COMMIT;
Higher isolation = fewer anomalies but less concurrency.
Interview one-liners
- Conflict = same item, different transactions, at least one write.
- Acyclic precedence graph ⇔ conflict serializable.
- 2PL guarantees serializability but not deadlock freedom.
- Strict 2PL avoids cascading rollbacks.
- MVCC: readers don't block writers.
- Related: Indexing, B+ Trees and SQL vs NoSQL.