1 Strict 2PL in practice
Imagine a colouring book that the whole class wants to use. To stop two kids scribbling on the same page at once, there's one rule: before you touch a page, you grab its little token, and nobody else can touch that page until you hand the token back. If you want to look at a page, lots of kids can share a "looking" token at once — but if you want to draw, you need the page all to yourself. And the strict version of the rule says: you must hold on to every token until you're completely finished and the teacher has marked your work done. That way nobody ever sees your half-finished scribbles.
Let's recall the problem from Session 12. When two transactions run at the same time and touch the same data, you can get nasty bugs: dirty reads (reading someone's uncommitted change), lost updates (two writes clobbering each other), and more. To prevent these, the database uses locks — little "do not disturb" signs placed on data so transactions take turns.
Recap: what is Two-Phase Locking (2PL)?
Two-Phase Locking (2PL) is the classic rule for using locks safely. Every transaction's lock activity is split into exactly two phases:
The single rule: once you release any lock, you may never acquire another one. This simple discipline is what guarantees serializability — the schedule behaves as if the transactions ran one-after-another, even though they actually interleaved.
Plain 2PL lets you release a lock during the shrinking phase while you're still running. If another transaction grabs that data and you later abort, the other transaction read data that never officially existed — and now it must abort too. This domino effect is called a cascading abort, and it's both slow and painful to recover from.
Strict 2PL — the fix used in real systems
Strict 2PL adds one extra rule to 2PL: hold every exclusive (write) lock until the transaction commits or aborts. You don't release write locks early — they all drop at the very end, atomically, at commit time. (The even stricter variant, Rigorous 2PL, holds all locks — both read and write — until the end; most textbook discussions and most real lock-based engines effectively use this.)
By holding write locks until commit, no other transaction can ever see your uncommitted changes. If you abort, nobody depended on you, so nobody has to cascade-abort. Strict 2PL buys you serializability and a clean, cascade-free recovery — which is exactly why nearly every lock-based database uses it.
Shared vs exclusive locks
Not all locks are equal. A reader doesn't conflict with another reader — two transactions can safely read the same row at the same time. They only conflict with writers. So databases use two lock modes:
- Shared lock (S) — a "read" lock. Many transactions can hold an S-lock on the same item simultaneously. ("I'm reading; you can read too.")
- Exclusive lock (X) — a "write" lock. Only one transaction can hold it, and no one else can hold any lock on that item meanwhile. ("I'm writing; everybody back off.")
The lock compatibility table
The lock manager consults this tiny table every time a transaction asks for a lock. "Yes" means the request is granted immediately; "No" means the requester must wait until the holder releases.
| Requested ↓ / Held → | None | Shared (S) | Exclusive (X) |
|---|---|---|---|
| Shared (S) | ✅ Yes | ✅ Yes | ❌ No (wait) |
| Exclusive (X) | ✅ Yes | ❌ No (wait) | ❌ No (wait) |
Read it as a friendly rule of thumb: reads share, writes don't. S–S is the only pair that gets along.
Two transactions on a bank table. T1 transfers ₹100 from account A to B.
T2 just wants to read A's balance. Under strict 2PL the timeline looks like:
-- T1: transfer 100 from A to B T2: read A's balance T1: X-lock(A) -- T1 grabs exclusive lock on A T1: read(A) -> 500 T1: write(A = 400) T2: S-lock(A) ............... ⏸ BLOCKED (X held by T1) T1: X-lock(B) T1: read(B) -> 200 T1: write(B = 300) T1: COMMIT -- ALL locks (A and B) released here, atomically T2: S-lock(A) ............... ▶ granted now T2: read(A) -> 400 -- sees the committed value, never 500-mid-transfer T2: COMMIT
Notice T2's read was blocked the entire time T1 held the X-lock, and was only released after T1 committed. So T2 can never see the in-between state where ₹100 has left A but not yet arrived at B. The money is never seen as missing. That's strict 2PL protecting the ACID Isolation and Consistency we met in Session 12.
Strict 2PL = 2PL + "hold write locks until commit." It gives you serializable execution and cascade-free aborts. The cost? Readers and writers block each other — a writer freezes out every reader of that row until it commits. Remember that pain point; MVCC (Topic 3) is largely a reaction to it.
2 Deadlocks & how to handle them
Picture two kids in a narrow hallway. Aria is holding the red crayon and reaching for the blue one. Ben is holding the blue crayon and reaching for the red one. Neither will let go first, so they stand there frozen forever, each waiting for the other. That frozen-forever situation is called a deadlock. The grown-up has to step in, take a crayon from one kid, and tell them "you have to start over." Annoying — but better than standing frozen all day.
Strict 2PL keeps data correct, but it introduces a new danger. Because transactions wait for locks, two of them can end up waiting on each other in a circle. Nobody can proceed, nobody will give up — a deadlock.
How a lock cycle forms
-- T1 wants to update A then B; T2 wants to update B then A T1: X-lock(A) ✅ granted T2: X-lock(B) ✅ granted T1: X-lock(B) ⏸ waits for T2 to release B T2: X-lock(A) ⏸ waits for T1 to release A -- T1 waits for T2, T2 waits for T1 -> frozen forever (DEADLOCK)
The database detects this using a wait-for graph: draw an arrow
Ti → Tj whenever transaction Ti is waiting for a lock
held by Tj. A cycle in this graph means a deadlock.
Three strategies for handling deadlocks
There are three broad approaches. Real systems pick one (often detection).
| Strategy | How it works | Trade-off |
|---|---|---|
| Detection (wait-for graph) | Let deadlocks happen, but periodically scan the wait-for graph for cycles. When one is found, pick a victim and abort it. | No restriction on locking order; but you pay the cost of running the detector and of the work the victim wasted. Used by PostgreSQL, MySQL/InnoDB. |
| Prevention (timestamp schemes) | Never let a deadlock form in the first place, by deciding up front who is allowed to wait, based on transaction age. Two schemes: wait-die and wound-wait. | Some transactions get aborted even when no real deadlock would have happened — but you never need a detector. |
| Timeouts | If a transaction waits longer than some limit, just assume it's deadlocked and abort it. | Dead simple to implement, but crude: a slow-but-fine transaction can be killed needlessly, and picking the timeout is guesswork. |
Prevention in detail: wait-die vs wound-wait
Both give every transaction a timestamp when it starts — older transactions
have smaller timestamps. When transaction Ti wants a lock held by
Tj, the rule decides who lives:
| Scheme | If requester (Ti) is OLDER than holder (Tj) | If requester (Ti) is YOUNGER than holder (Tj) |
|---|---|---|
| Wait-die (non-preemptive) | Ti waits for Tj. | Ti dies (aborts & restarts later) — a young transaction never makes an old one wait. |
| Wound-wait (preemptive) | Ti wounds Tj (forces Tj to abort) and takes the lock. | Ti waits for Tj. |
The key shared idea: both schemes only ever let waiting go in one direction by age, so a cycle (which needs waiting going both ways) can never form. A nice property is that the oldest transaction never gets aborted, so it always eventually finishes — no transaction starves forever.
Wait-die: the requester either waits (if old) or dies (if young). Wound-wait: the requester either wounds the other (if old) or waits (if young). In both, "old transactions get priority." Older = closer to finishing = worth protecting.
Resolving a deadlock: victim selection
Whether you detect a cycle or prevent one, the resolution is the same: abort one transaction (the victim), roll it back so its locks release, and restart it later. The system tries to pick a cheap victim — typically the one that has done the least work, holds the fewest locks, or has made the fewest changes — to minimise wasted effort.
If the victim-picker always chooses the same unlucky transaction, that transaction might be aborted again and again and never finish — this is starvation. Good systems guard against it, e.g. by giving a transaction higher priority each time it's restarted, or (as in wait-die/wound-wait) by never aborting the oldest transaction.
A deadlock is a cycle of transactions each waiting for a lock the next one holds. You can detect it (wait-for graph + abort a victim), prevent it (wait-die / wound-wait using timestamps), or use blunt timeouts. Every resolution costs you an aborted transaction — so concurrency is never free.
3 MVCC — multi-version concurrency control
Imagine a notebook where, instead of erasing the old answer when you change something, you cross it out lightly and write the new version on the next line — keeping every old version too. Now if a friend started reading the page a moment ago, they can keep reading their version in peace, even while you scribble a new one. Nobody has to wait for anybody. Readers read their own snapshot; writers add new versions. That's the whole trick of MVCC: keep many versions, so readers never block writers and writers never block readers.
Recall the pain point from Topic 1: under strict 2PL, a writer holding an X-lock freezes out every reader of that row until commit. In a read-heavy system (most systems!) that's a serious bottleneck. MVCC (Multi-Version Concurrency Control) attacks exactly this.
Instead of overwriting a row in place (which forces locking), each write creates a new version of the row and leaves the old one alive. A reading transaction is handed a consistent snapshot — the set of row versions that were committed at the moment it started. So readers don't block writers, and writers don't block readers. The only real conflict left is writer-vs-writer on the same row.
Snapshots — everyone gets a consistent photo
When a transaction begins (or, depending on isolation level, when each statement begins), MVCC conceptually takes a snapshot: a frozen view of the database as of that instant. Every read it does sees that same consistent picture, no matter how many other transactions commit changes meanwhile. This is how MVCC delivers snapshot isolation — reads are stable and repeatable without holding any read locks at all.
How PostgreSQL implements MVCC
PostgreSQL is the textbook real-world example. Every row version (PostgreSQL calls a row version a tuple) carries two hidden system columns:
- xmin — the ID of the transaction that created this row version (its "born at" stamp).
- xmax — the ID of the transaction that deleted or replaced this row version (its "died at" stamp). If the row is still live, xmax is empty/zero.
Every transaction has a monotonically increasing XID (transaction ID). A row
version is visible to your transaction roughly when: its xmin is a
transaction that committed before your snapshot, AND its xmax is either
empty or belongs to a transaction that had not committed as of your snapshot. That visibility check
is what makes your snapshot consistent.
Start with one row, Alice, balance 500, created by transaction 100:
-- Initial tuple (one physical row version) xmin=100 xmax=0 (name=Alice, balance=500) <- live -- Transaction 105 runs: UPDATE accounts SET balance=600 WHERE name='Alice'; -- Postgres does NOT overwrite. It marks the old row dead and inserts a new version: xmin=100 xmax=105 (name=Alice, balance=500) <- old version, now dead to new readers xmin=105 xmax=0 (name=Alice, balance=600) <- new version
Now suppose another transaction T_old started before 105 committed.
Its snapshot says "105 hasn't committed." So when it reads Alice, the visibility rule rejects the new
version (xmin=105, not yet committed to me) and shows it the old version — balance 500.
Meanwhile a transaction that starts after 105 commits sees balance 600. Two
readers, two correct answers, zero locks, zero blocking. A DELETE
works the same way: it just sets xmax on the current version, leaving the row
physically present but invisible to new snapshots.
MVCC removes read/write blocking, but two transactions updating the same row still conflict —
one must wait or, at higher isolation levels, get a "could not serialize" error and retry. PostgreSQL
handles writes with row-level locks only against other writers, plus a check on
xmax. So writes are serialized per row; reads are completely free.
The catch: garbage collection & VACUUM
If every update leaves an old version lying around, the table just keeps growing with dead tuples — called bloat. Eventually no live transaction can still see those old versions, so they're pure garbage that wastes disk and slows scans. PostgreSQL reclaims them with a background process called VACUUM (and its automatic form, autovacuum), which finds dead tuples no snapshot needs anymore and frees their space for reuse.
VACUUM can only remove a dead version if no running transaction might still need it. So a single very long-running transaction can pin millions of old versions in place, causing bloat to balloon across the whole database. This is why "don't leave transactions open for hours" is a real-world golden rule in MVCC systems.
MVCC keeps multiple versions of each row so reads see a consistent snapshot without locking. In
PostgreSQL, xmin/xmax stamps plus transaction IDs decide
visibility; updates write new versions, deletes mark old ones dead, and VACUUM later cleans up. The
payoff is huge read concurrency; the price is extra storage and the housekeeping of garbage collection.
xmin/xmax
columns and per-transaction IDs that drive a visibility check; updates create new versions, deletes
stamp old ones dead, and VACUUM/autovacuum garbage-collects the versions no snapshot needs.
4 2PL vs MVCC — the trade-offs
Two ways to share one library book. Way 1 (locking): only one person holds the book at a time; everyone else stands in line and waits. Simple and tidy, but the line gets long. Way 2 (MVCC): the librarian photocopies the book so everybody reads their own copy and nobody waits — but now there are copies everywhere that someone has to tidy up later. Neither way is "wrong"; they just trade waiting for extra copies.
We've now seen both major families of concurrency control. Let's lay them side by side — this is exactly the comparison your written assignment asks for.
| Aspect | Strict 2PL (lock-based) | MVCC (version-based) |
|---|---|---|
| Core mechanism | Locks; transactions take turns on each item. | Multiple versions + snapshots; readers see a frozen view. |
| Readers vs writers | Block each other. A writer freezes out all readers of that row. | Never block each other. Readers use old versions, writers add new ones. |
| Writers vs writers | Block (X-lock conflict). | Still block / may abort on the same row. |
| Read overhead | Must acquire & release S-locks. | No read locks — just a visibility check. |
| Storage cost | Low — data stored once. | Higher — old versions linger until garbage-collected. |
| Extra housekeeping | Lock manager, deadlock detection. | Version visibility checks + VACUUM / GC. |
| Main failure mode | Deadlocks & long lock waits. | Table bloat; write-write conflicts → retries. |
| Best for | Write-heavy, contention-light workloads. | Read-heavy workloads (the common case). |
A reporting query scans the orders table for 30 seconds while a busy
checkout flow keeps inserting and updating orders.
- Under strict 2PL: the long report holds S-locks (or the writers hold X-locks), so either the report blocks the checkouts or the checkouts block the report. Throughput tanks; you might even hit lock-wait timeouts.
- Under MVCC: the report reads a 30-second-old consistent snapshot and never touches a lock, while checkouts merrily create new versions. Both run full speed. The only cost is some dead versions for VACUUM to mop up afterward.
This is the everyday scenario that makes MVCC win — and it's why your assignment should conclude that for typical, read-dominated applications MVCC usually delivers far better concurrency.
Why most modern databases use MVCC
Real-world workloads are overwhelmingly read-heavy, and the single worst thing you can do to a database's responsiveness is make reads wait. MVCC's promise — "readers never block writers" — maps perfectly onto that reality. That's why it's the default in PostgreSQL, Oracle, MySQL's InnoDB engine, SQL Server (snapshot isolation), and most in-memory databases. Pure strict 2PL still shows up where write contention dominates or where the implementation must stay simple, and many systems actually combine the two — MVCC for reads, locks for the write paths.
The 2017 VLDB paper "An Empirical Evaluation of In-Memory MVCC" (Wu et al.) tested many MVCC design choices on modern hardware. Its headline finding: there's no single "best" MVCC scheme — the right version-storage, garbage-collection, and conflict-detection choices all depend on the workload. The takeaway for us: MVCC is a family of designs, and tuning garbage collection in particular matters enormously for performance.
2PL trades throughput for simplicity and low storage; MVCC trades storage and housekeeping for far better read concurrency. Because most apps read far more than they write, MVCC (often blended with locking on the write path) is the dominant choice in modern databases.
★ Putting it all together
You just learned how a database lets a crowd of transactions share data without corrupting it. Here's the one-paragraph story that connects all four topics:
To keep concurrent transactions correct, the classic approach is locking: strict 2PL takes shared locks for reads and exclusive locks for writes, and holds write locks until commit so there are no cascading aborts. But locks make transactions wait, and waiting can form a cycle — a deadlock — which the system handles by detection (wait-for graph), prevention (wait-die / wound-wait), or timeouts, always resolving it by aborting a victim. To dodge the read/write blocking that locking causes, modern systems use MVCC: each write makes a new version, readers see a consistent snapshot (in PostgreSQL via hidden xmin/xmax stamps), and VACUUM later garbage-collects dead versions. Because most workloads are read-heavy, MVCC usually wins — which is why it's the default in nearly every modern database. Next session we'll see what happens when the whole thing crashes: logging & recovery.
Quick self-check
What extra rule does strict 2PL add on top of plain 2PL, and what does it buy you?
It holds all exclusive (write) locks until the transaction commits or aborts, instead of releasing them during the shrinking phase. This prevents other transactions from reading uncommitted data, which eliminates cascading aborts.
In the lock compatibility table, which pair of lock requests is compatible?
Only Shared–Shared (two readers). Any combination involving an Exclusive lock conflicts, so the requester must wait.
How does a database detect a deadlock, and how does it resolve one?
It builds a wait-for graph (an arrow from each waiting transaction to the one holding the lock it wants) and looks for a cycle. A cycle means a deadlock. It resolves it by choosing a victim transaction, aborting and rolling it back so its locks release, then restarting it later.
In wound-wait, what happens when an OLDER transaction requests a lock held by a younger one?
The older transaction "wounds" the younger one — it forces the younger transaction to abort and takes the lock. (If the requester were younger, it would instead wait.)
In PostgreSQL MVCC, what do xmin and xmax record, and what happens on an UPDATE?
xmin is the transaction ID that created the row version; xmax is the transaction ID that deleted/replaced it (empty if still live). An UPDATE does not overwrite in place — it stamps xmax on the old version (marking it dead) and inserts a brand-new version with a fresh xmin.
Why does MVCC need VACUUM, and why are long-running transactions dangerous for it?
Old row versions pile up as dead tuples (bloat); VACUUM reclaims those no live snapshot needs. A long-running transaction keeps an old snapshot alive, so VACUUM can't remove versions it might still need — letting bloat grow across the whole database.
Why do most modern databases prefer MVCC over pure strict 2PL?
Most workloads are read-heavy, and MVCC's defining property is that readers never block writers and writers never block readers. That delivers much higher read concurrency than locking, at the acceptable cost of extra storage and garbage collection.
📚 References & Further Reading
Class material
- 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
- DBMS Session 13 — Concurrency — the class handout that accompanies this session.
Papers, docs & deep dives
- PostgreSQL Documentation — Concurrency Control (MVCC) — the official, authoritative explanation of snapshots, visibility, and isolation levels behind Topic 3.
- Wu et al., "An Empirical Evaluation of In-Memory MVCC" (VLDB 2017) — measures the real trade-offs between MVCC design choices; the research backing for Topic 4.
- CMU 15-445 Database Systems — Concurrency Control & MVCC lectures — Andy Pavlo's free, superb lectures covering 2PL, deadlocks, and MVCC in depth.
- PostgreSQL Documentation — Routine Vacuuming — exactly how garbage collection and autovacuum reclaim dead tuples (the VACUUM part of Topic 3).
- CMU 15-445 — Two-Phase Locking lecture notes — a clean written treatment of 2PL, strict 2PL, and deadlock handling for Topics 1 and 2.