M4

Transactions Motivation

A transaction groups related database operations into one all-or-nothing unit.

One Buy click is one transaction: three steps, all or none

One fan's Buy click is a single transaction: check the seat is open, charge the card, record the sale, bundled so either all three commit or none do, never a charge without a seat and never the same seat to two fans. Multiply by the on-sale crush, every fan racing for the same seats, and you have the problem this module solves.

Taylor Swift’s Eras Tour on sale

Ticketmaster reported 3.5 million registrations and 3.5 billion system requests, four times its prior traffic peak. Sales were delayed and fans encountered errors. The transaction guarantees are simple: no seat sold twice and no charge without a seat. Keeping those guarantees while staying responsive under load is the problem this module addresses.

Heavy demand tests availability and correctness

Ticketmaster reported 3.5 million registrations and 3.5 billion system requests, four times its prior traffic peak. Sales were delayed and fans encountered errors. The transaction guarantees are simple: no seat sold twice and no charge without a seat. Keeping those guarantees while staying responsive under load is the problem this module addresses.

Large workloads need deliberate engineering

Visa reports capacity above 65,000 transaction messages per second. During Prime Day 2022, Amazon DynamoDB peaked at 105.2 million requests per second with single-digit millisecond responses. Ticketmaster reported four times its previous traffic peak. These are different workloads and metrics, but all require deliberate engineering for concurrency and availability.

More writes, the same correctness guarantees

Figure: More writes, the same correctness guarantees

Three illustrative workload tiers. Classic retail systems such as Walmart in the 1990s and 2000s illustrate about ten thousand writes per second. Cloud services such as Gmail and Roblox in the 2010s and 2020s illustrate millions of writes per second. Agent workloads from 2025 onward motivate a target of tens of millions of writes per second with NVMe and distributed compute. These rates are illustrative tiers, not measured throughput attributed to the named services.

Three generations, 2 rows. Row 1 is concurrency, transactions per second: about thousands a second, about 10 million a second, then millions of AI agents a second. The figure marks each step from one generation to the next as times 10 to the fourth, about 10,000 times. Row 2 is the data structure underneath. Not in the table: the periods are Classic 1990s to 2000s (banks, Oracle), Modern 2000s to 2020s (Gmail, Roblox), and Future 2030s on (AI agents, serverless). The hardware is Classic HDD (hard disk drive) with 1 to 4 cores and 1 GB, Modern SSD (solid-state drive) with 128+ cores and 1 TB, and Future NVMe (the fastest flash storage) with 10K+ cores and 1 PB.
Classic	Modern	Future
~1,000s / sec	~10M / sec	millions of agents / sec
B-Trees	LSM Trees	Learned indexes

Classic retail systems such as Walmart, cloud services such as Gmail and Roblox, and agent workloads from 2025 onward illustrate increasing write demand: about 10,000 writes per second, millions, and a target of tens of millions. These are illustrative scale tiers, not measured rates for the named services. Hardware progresses from disks and a few cores to SSDs and many cores, then NVMe with distributed compute; every tier still needs correct transactions.

M4

ACID Properties

ACID defines four guarantees for a transaction.

Alice’s ticket purchase: commit or rollback

Alice’s purchase checks inventory, requests card authorization, and records the sale. The database commits its pending changes together or rolls them back on failure. A declined authorization leaves no confirmed sale or completed charge. Coordination with the external payment network is application logic; a database rollback alone cannot reverse an external charge.

ACID: four guarantees, four examples

Each card separates a guarantee from its ticket-purchase example: a declined card rolls back cleanly (atomicity), seats and revenue move as one (consistency), Alice locks the last seat so Bob waits (isolation), and a confirmed ticket survives a crash (durability).

Interest must not see a half-finished transfer

T1 moves $100 from Alice to Bob; T2 adds 6% interest to both accounts. Read each schedule downward, with a separate lane for each transaction. Without isolation, T1 credits Bob before debiting Alice, so T2 sees $400 and adds $24 of interest; T1 then finishes, leaving $324 (red), including $6 in excess interest. With isolation, T2 waits for T1 to commit and sees the settled $300, adding the correct $18 and leaving $318 (green).

M4

How ACID Protects a Stripe Payment

One payment updates several records that must agree.

One transaction commits four internal payment writes

After card authorization, the database records the payment, writes two balancing ledger rows, updates the merchant balance, and queues a webhook. One transaction commits those four internal writes together.

Four ACID properties prevent four payment failures

Four failures map to four guarantees: atomicity prevents partial internal writes, consistency keeps the ledger balanced, isolation prevents concurrent payments from losing a balance update, and durability preserves a confirmed payment after a crash.

M4

Sample Code: Running Transactions

Use BEGIN and COMMIT to group statements into one transaction.

BEGIN, COMMIT, ROLLBACK

The three keywords frame one block. BEGIN opens the transaction; your statements run inside as one logical operation; COMMIT makes every change since BEGIN permanent, or ROLLBACK undoes them all as if nothing happened. Rolling a transaction back is also called aborting it, the term the rest of this module uses (in Postgres, ABORT is the same command). Outside a block, each statement autocommits as its own one-statement transaction.

Buy tickets

BEGIN TRANSACTION;

SELECT available_tickets
FROM Concerts
WHERE concert_id = 'taylor_swift_123';

UPDATE Concerts
SET available_tickets = available_tickets - 2
WHERE concert_id = 'taylor_swift_123';

INSERT INTO Orders (user_id, concert_id, num_tickets, total_amount, status)
VALUES ('user_789', 'taylor_swift_123', 2, 150.00, 'confirmed');

COMMIT;

Transfer money

-- Schema rule: CHECK (balance >= 0).
-- The database enforces this on every write.

BEGIN TRANSACTION;

UPDATE Accounts
SET balance = balance - 100.00
WHERE account_id = 'alice_account';

UPDATE Accounts
SET balance = balance + 100.00
WHERE account_id = 'bob_account';

INSERT INTO Transfers (from_account, to_account, amount, type)
VALUES ('alice_account', 'bob_account', 100.00, 'transfer');

COMMIT;

Reserve inventory

BEGIN TRANSACTION;

SELECT quantity FROM Products WHERE product_id = 'labubu';

UPDATE Products SET quantity = quantity - 1 WHERE product_id = 'labubu';

INSERT INTO Orders (customer_id, product_id, quantity, status)
VALUES ('customer_alice', 'labubu', 1, 'confirmed');

COMMIT;

Record a like

BEGIN TRANSACTION;

-- The Likes table has a UNIQUE (user_id, post_id) constraint; a duplicate
-- INSERT fails and the whole transaction rolls back.
INSERT INTO Likes (user_id, post_id, timestamp)
VALUES ('user_12345', 'viral_post_456', NOW());

UPDATE Posts
SET like_count = like_count + 1,
    last_activity = NOW()
WHERE post_id = 'viral_post_456';

COMMIT;

M4

Naive Concurrency

Concurrency control keeps shared data correct while transactions run together.

I/O lag: reads and writes take time

I/O lag is the time from read start (RS) to read end (RE), or write start (WS) to write end (WE). Here it takes 5 time units. In practice, I/O can take millions of CPU cycles.

Naive Way 1: run one at a time

The disk handles reads and writes while serial execution leaves the CPU idle. The broken arrows compress the waiting spans; they do not represent measured durations. T3 and T4 cannot run while T2 waits, even when their work touches unrelated rows.

Naive Way 2: run without coordination

Figure: Naive Way 2: run without coordination

Three side-by-side failure panels, each a tiny two-column schedule of T1 and T2 reading and writing one row with no coordination, time running top to bottom. Left, the lost update: both read 100, both write 101, so the count lands on 101 instead of 102. Middle, the dirty read: T1 writes 150, T2 reads it, then T1 aborts, so T2 acted on a value that never committed. Right, the stale read: T1 reads 20, T2 writes 30 and commits, T1 reads again and sees 30, disagreeing with itself inside one transaction. Each panel names its conflict type: write-write, write-read, read-write. Color key: red is the corrupted result each race produces, grey is the trace.

Three failure panels, one column each, read top to bottom: the starting value, four steps in time order, the result, and what went wrong. The conflict types are write-write for the lost update, write-read for the dirty read, and read-write for the stale read. An arrow after read means the read returns that value. Lost update steps: T1 reads 100, T2 reads 100, T1 writes 101, T2 writes 101, so the count lands on 101 instead of 102. Dirty read steps: T1 writes 150, T2 reads 150, T1 aborts, T2 acts on 150, a value that never committed. Stale read steps: T1 reads 20, T2 writes 30, T2 commits, T1 reads 30, so its two reads disagree. txn means transaction. The result row is drawn in red as the corrupted outcome.
Lost update	Dirty read	Stale read
play_count = 100	balance = 100	price = 20
read → 100	write 150	read → 20
read → 100	read → 150	write 30
write 101	ABORT	commit
write 101	acts on 150	read → 30
lands on 101, not 102	T2 used 150	T1 saw 20, then 30
one play silently vanishes	a value that never committed	two reads disagree in one txn

Uncontrolled concurrency corrupts one row three different ways. In a lost update, two transactions both read 100 and both write 101, so one play disappears. In a dirty read, one transaction reads another's uncommitted write and the writer then aborts, so the reader acted on a value that never existed. In a stale read, a transaction reads the same row twice and a committed write in between makes its two reads disagree.

How should transactions share the database?

Concurrency control overlaps independent work while ordering conflicting actions safely.

M4

A Quick Graph Refresher

A directed graph captures which operations must come before others.

Acyclic graphs have no directed cycle

Left: no directed cycle, so an order respecting every edge exists. Right: the cycle prevents such an order. A transaction schedule is conflict-serializable exactly when its conflict graph has no cycle.

A topological order respects every edge

Both A → B → C → D and A → C → B → D respect every edge. B and C have no ordering constraint between them. In a conflict graph, a topological order gives an equivalent serial transaction order.

M4

Correctness: Ensuring Safe Concurrent Execution

A correct concurrent schedule produces the result of a valid serial order.

Actions: a transaction's reads and writes

A transaction is a sequence of actions, each one a read or write of a single row, written T1.R(A) for transaction T1 reading row A. Blue labels are reads, orange labels are writes. Correctness tracks only their order, not the values they compute.

Three kinds of schedule

Figure: Serial, interleaved, and serializable schedules

Three labeled rows, each a schedule for T1 and T2 drawn as four action boxes left to right in time order, each box written like T1.R(A), blue for a read and orange for a write. The rows are Serial, Interleaved and Serializable. The Serializable row carries a second run of boxes after an equivalence sign, labeled a serial run. Color key: blue read, orange write.

Serial schedule: 4 actions in time order. T1.R(A) means T1 reads row A, T1.W(A) means T1 writes row A.
Serial
T1.R(A)	T1.W(A)	T2.R(B)	T2.W(B)

Interleaved schedule: the same 4 actions, mixed in time.
Interleaved
T1.R(A)	T2.R(B)	T1.W(A)	T2.W(B)

Serializable schedule, 2 rows: row 1 is the same interleaving, row 2 the serial run the figure marks it equivalent to.
Serializable
T1.R(A)	T2.R(B)	T1.W(A)	T2.W(B)
T1.R(A)	T1.W(A)	T2.R(B)	T2.W(B)

Serial runs one transaction's actions to completion, then the next. Interleaved mixes them in time. Serializable is an interleaving whose result matches some serial order. Blue boxes are reads, orange writes; the T1 or T2 prefix names the transaction, and the page tracks only the R/W order, the macro view.

When do actions conflict?

A conflict needs two transactions, the same row, and at least one write. Only read-read commutes; the other three each leave an order-dependent result, each a named anomaly: read-write a stale read, write-read a dirty read, write-write a lost update. Every conflict becomes a directed edge in the conflict graph, next.

The conflict-serializability test: build a conflict graph, then check for a cycle

The whole test in three steps. Build one node per transaction, add a directed edge for every conflict, then look for a cycle. No cycle (green) means a serial order respects every edge, so the schedule is conflict-serializable; a cycle (red) means two edges demand opposite orders, so none does.

A serial schedule: T1, then T2, then T3, with no overlap

Figure: A serial schedule: T1, then T2, then T3, with no overlap

A MacroSchedule shown as a table of Transaction, Action, Variable, Step, and Value, one row per operation in step order. Each transaction runs as one contiguous block, bracketed and labeled on the left, so the serial schedule reads as one block per transaction. Color key: blue is a read, orange is a write.

Serial schedule S1, run by MacroSchedule.Run() from start values A = 10, B = 22: 7 operations in step order. R is a read and W is a write of the named variable; Value is the value read or written. A bracket on the left groups each transaction's actions into one block: T1 takes steps 1 and 2, T2 steps 3 to 5, T3 steps 6 and 7, with no overlap. End values: A = 9, B = 20.
Transaction	Action	Variable	Step	Value
T1	R	A	1	10
T1	W	A	2	9
T2	R	A	3	9
T2	R	B	4	22
T2	W	B	5	21
T3	R	B	6	21
T3	W	B	7	20

The brackets on the left make the shape plain: each transaction's actions form one contiguous block, the visual signature of serial. It ends at A=9, B=20 with ACID intact, but with no parallelism it is the slowest of the three.

A serial schedule has no conflict cycle

Figure: A serial schedule has no conflict cycle

Conflict-serializability analysis: a table of conflicting actions (Txn 1, Txn 2, Variable, and the step in each), then a conflict graph with one node per transaction and a directed edge per conflict, and a verdict. A cycle (drawn in red) means the schedule is not conflict-serializable; an acyclic graph is serializable and equivalent to the serial order shown.

Conflicting actions in the serial schedule S1: 4 pairs. Two actions conflict when different transactions touch the same variable and at least one of them writes. Txn 1 is the transaction that acts first, at Step (Txn 1); Txn 2 is the one that acts later, at Step (Txn 2). An edge label names the variable and the two steps: A-(#2,#3) is the A pair at steps 2 and 3. Each pair becomes a directed edge from Txn 1 to Txn 2 in the conflict graph: an edge from T1 to T2 for the A pair (label A-(#2,#3)), and an edge from T2 to T3 carrying the three B pairs (labels B-(#4,#7), B-(#5,#6), B-(#5,#7)). The graph is the chain T1 to T2 to T3 with no cycle, so the verdict is: acyclic, conflict-serializable, equivalent serial order T1, then T2, then T3.
Txn 1	Txn 2	Variable	Step (Txn 1)	Step (Txn 2)
T1	T2	A	2	3
T2	T3	B	4	7
T2	T3	B	5	6
T2	T3	B	5	7

Equivalent serial schedule for the order T1, T2, T3: 7 operations, the same as S1 itself, since S1 is already serial. R is a read and W is a write of the named variable.
Transaction	Action	Variable	Step
T1	R	A	1
T1	W	A	2
T2	R	A	3
T2	R	B	4
T2	W	B	5
T3	R	B	6
T3	W	B	7

Even a serial schedule has conflicts wherever transactions touch a shared variable: a W-R on A (T1 → T2), a W-W on B (T2 → T3), four in all. They chain T1 → T2 → T3, which is exactly the serial order that produced them.

S1': the same three transactions, interleaved

Figure: S1': the same three transactions, interleaved

A MacroSchedule shown as a table of Transaction, Action, Variable, Step, and Value, one row per operation in step order. The transactions interleave, so no blocks are bracketed. Color key: blue is a read, orange is a write.

Interleaved schedule S1', run by MacroSchedule.Run() from start values A = 10, B = 22: the same 7 operations as the serial schedule, reordered. R is a read and W is a write of the named variable; Value is the value read or written. T1 and T2 alternate on A in steps 1 to 3, so T2 reads A = 10 at step 2 before T1 writes 9 at step 3. T2 then finishes on B, and T3 runs last. This figure draws no block brackets, since the transactions interleave. End values: A = 9, B = 20.
Transaction	Action	Variable	Step	Value
T1	R	A	1	10
T2	R	A	2	10
T1	W	A	3	9
T2	R	B	4	22
T2	W	B	5	21
T3	R	B	6	21
T3	W	B	7	20

S1' interleaves T1, T2, and T3 instead of running them serially. Whether the interleaving stays correct depends entirely on its conflict graph, built next.

S1' has no cycle in its conflict graph, so the interleaving is safe

Figure: S1' has no cycle in its conflict graph, so the interleaving is safe

Conflict-serializability analysis: a table of conflicting actions (Txn 1, Txn 2, Variable, and the step in each), then a conflict graph with one node per transaction and a directed edge per conflict, and a verdict. A cycle (drawn in red) means the schedule is not conflict-serializable; an acyclic graph is serializable and equivalent to the serial order shown.

Conflicting actions in the interleaved schedule S1': 4 pairs. Two actions conflict when different transactions touch the same variable and at least one of them writes. Txn 1 is the transaction that acts first, at Step (Txn 1); Txn 2 is the one that acts later, at Step (Txn 2). An edge label names the variable and the two steps: A-(#2,#3) is the A pair at steps 2 and 3. On A, T2 reads at step 2 before T1 writes at step 3, so that edge runs from T2 to T1 (label A-(#2,#3)). The three B pairs give one edge from T2 to T3 (labels B-(#4,#7), B-(#5,#6), B-(#5,#7)). The graph has edges T2 to T1 and T2 to T3 and no cycle, so the verdict is: acyclic, conflict-serializable, equivalent serial order T2, then T1, then T3.
Txn 1	Txn 2	Variable	Step (Txn 1)	Step (Txn 2)
T2	T1	A	2	3
T2	T3	B	4	7
T2	T3	B	5	6
T2	T3	B	5	7

Equivalent serial schedule for the order T2, T1, T3: 7 operations, steps renumbered 1 to 7. T2 runs all three of its actions first, then T1, then T3. R is a read and W is a write of the named variable.
Transaction	Action	Variable	Step
T2	R	A	1
T2	R	B	2
T2	W	B	3
T1	R	A	4
T1	W	A	5
T3	R	B	6
T3	W	B	7

The conflict graph of S1' has four conflicts and no cycle, so S1' is conflict-serializable: it matches the serial order T2 → T1 → T3 (or T2 → T3 → T1). The faster interleaving is still correct.

S2': a different interleaving, with an extra T2 write on B

Figure: S2': a different interleaving, with an extra T2 write on B

A MacroSchedule shown as a table of Transaction, Action, Variable, Step, and Value, one row per operation in step order. The transactions interleave, so no blocks are bracketed. Color key: blue is a read, orange is a write.

Interleaved schedule S2', run by MacroSchedule.Run() from start values A = 10, B = 22: 8 operations. R is a read and W is a write of the named variable; Value is the value read or written. Steps 1 to 7 are the same as S1'. The last row is the extra T2 write on B at step 9, after T3 has already written B at step 7; the figure draws no step 8. This figure draws no block brackets, since the transactions interleave. End values: A = 9, B = 20.
Transaction	Action	Variable	Step	Value
T1	R	A	1	10
T2	R	A	2	10
T1	W	A	3	9
T2	R	B	4	22
T2	W	B	5	21
T3	R	B	6	21
T3	W	B	7	20
T2	W	B	9	20

S2' is a different interleaving of the same three transactions. The extra T2 write on B breaks it; the conflict graph next shows how. Its final values happen to match the serial run, so the totals are not the tell: the cycle is.

S2' has a cycle in its conflict graph, so the interleaving is unsafe

Figure: S2' has a cycle in its conflict graph, so the interleaving is unsafe

Conflict-serializability analysis: a table of conflicting actions (Txn 1, Txn 2, Variable, and the step in each), then a conflict graph with one node per transaction and a directed edge per conflict, and a verdict. A cycle (drawn in red) means the schedule is not conflict-serializable; an acyclic graph is serializable and equivalent to the serial order shown.

Conflicting actions in the interleaved schedule S2': 6 pairs. Two actions conflict when different transactions touch the same variable and at least one of them writes. Txn 1 is the transaction that acts first, at Step (Txn 1); Txn 2 is the one that acts later, at Step (Txn 2). An edge label names the variable and the two steps: A-(#2,#3) is the A pair at steps 2 and 3. The first four pairs are the same as in S1'. The last two come from the extra T2 write on B at step 9: T3's read of B at step 6 and write of B at step 7 both come before it. In the conflict graph, the A pair gives a blue edge from T2 to T1 (label A-(#2,#3)). The B pairs give two red edges: from T2 to T3 (labels B-(#4,#7), B-(#5,#6), B-(#5,#7)) and back from T3 to T2 (labels B-(#6,#9), B-(#7,#9)), and all five B rows of this table are highlighted red. The red edges form the cycle T3 to T2 to T3, so the verdict is: NOT conflict-serializable. No equivalent serial schedule is shown.
Txn 1	Txn 2	Variable	Step (Txn 1)	Step (Txn 2)
T2	T1	A	2	3
T2	T3	B	4	7
T2	T3	B	5	6
T2	T3	B	5	7
T3	T2	B	6	9
T3	T2	B	7	9

Sliding an interleaved schedule into a serial one by swapping non-conflicting neighbours

Figure: Sliding an interleaved schedule into a serial one by swapping non-conflicting neighbours

An interleaved schedule of four actions across two transactions. T1's two tiles (read A, write B), highlighted in violet, start split apart with a T2 action between them. The goal is to swap non-conflicting neighbours to gather T1's actions together, and then T2's, into contiguous blocks, which is a serial schedule. Markers between tiles show which pairs may swap (violet) and the one write-write conflict on B that may not (red). One free swap of the middle pair gathers T1 into one block and T2 into the next, giving the serial order T1 then T2. Color key: violet marks T1 and the free swaps, red marks the conflict that cannot move.

The starting schedule: 4 actions interleaved, with T1's two actions split apart. R(A) is a read of row A, W(B) a write of row B. Between neighbours the figure marks the first pair R, R (two reads, free to swap), the middle pair A is not B (different rows, free to swap), and the last pair W, W on B (a write-write conflict, which cannot swap, drawn with a red cross).
Can we swap this into a serial schedule?
T1 R(A)	T2 R(A)	T1 W(B)	T2 W(B)

After one free swap of the middle pair, T2 R(A) with T1 W(B): the serial schedule, T1's block then T2's. The one conflict, the two writes on B, is what fixes T1 before T2.
T1 block		T2 block
T1 R(A)	T1 W(B)	T2 R(A)	T2 W(B)

Can we swap an interleaved schedule into a serial one? The goal is to gather each transaction's actions into one contiguous block. T1's two tiles (violet) start apart, with a T2 action between them. A neighbour pair may swap only when it does not conflict; here the middle pair touches different rows, so one swap drops T1 into a block and T2 into the next, leaving the serial order T1 then T2. The write-write conflict on B (red) is the one pair that cannot move. A schedule untangles like this exactly when its conflict graph is acyclic.

How schedule classes fit together

Each ring is a set of schedules, strictly contained in the next: every conflict-serializable schedule is serializable, every two-phase-locking (2PL) schedule is conflict-serializable, and Strict-2PL sits inside 2PL. The gap between serializable and CS is a few rare blind-write schedules (a write that never reads its row), serializable yet not CS. The containment is also a difficulty gradient: the outer ring is checkable only by brute force, CS by the mechanical cycle test, and the 2PL rings, which the Two-Phase Locking page builds a few pages on, need no test at all, since the protocol enforces membership.

M4

Locks Stack & the Lock Manager

SQL, database locks, OS mutexes, and hardware atomics coordinate concurrent work.

The concurrency full stack: one COMMIT, four layers down to one instruction

The lock manager decides what to lock, the OS mutex decides how, and the hardware's compare-and-swap is the one indivisible step everything reduces to. The guarantee returns up the right side: swapped atomically, mutex held, row locked, transaction isolated.

OS lock vs database lock manager: same word, different layer

The same word, two layers on one machine. The OS lock (grey) is one bit of state guarding a memory address it knows nothing about. The database lock manager (violet) locks at table, page, or row granularity, lets a transaction announce intent, and resolves deadlock for millions of transactions at once. The OS primitive cannot do any of that, so the database builds its own lock layer on top.

The lock manager: one component, two goals, three jobs

Every transaction asks one component, the lock manager, for its locks, and it keeps the lock table of who holds each row and who waits. It owes two goals: correct, equal to some serial order, and fast, overlapping the idle waits. Its first job is the one shown, granting a free row or queuing you behind the holder; scheduling many transactions and breaking deadlocks (greyed) each get their own page later.

M4

DB Locks Lifecycle

A transaction requests a lock, uses the protected row, and releases the lock.

The lock lifecycle, in the schedule notation

One lock through its cycle, in the notation the schedules ahead use: a green flag is the request (Req), a red flag the grant (Get), a blue box the read, an orange box the write, and a purple flag the release (Unl). T1 takes row A, reads then writes while holding it, and releases. T2 wants the same row: it requests, waits the whole hold, and gets it only once T1 releases.

Shared and exclusive locks

A shared lock (S) is for reading: several transactions can hold S on one row and read it together, because reads do not conflict. An exclusive lock (X) is for writing: only one transaction holds X, and everyone else waits.

Lock compatibility matrix: shared and exclusive locks

The one compatible pairing is shared-with-shared; every cell touching an exclusive lock forces a wait. This is the conflict rule from the Correctness page made operational: two operations collide only when they touch the same row and at least one writes.

M4

Two-Phase Locking

Two-phase locking acquires locks before releasing any of them.

end of lecture 1~69 min of figures

2PL: locks held rise during the growing phase, peak, then fall during the shrinking phase

2PL: the lock count only rises, then only falls. The peak is the moment the transaction holds everything it will ever need.

Strict 2PL (S2PL): locks held rise during the growing phase, plateau, then drop to zero in one step at COMMIT

Nothing is released early.

Why strict 2PL stops cascading aborts

Release a lock early (regular 2PL) and another transaction can read work you later undo, so its abort cascades into theirs. Strict 2PL holds every lock to commit, so no one ever builds on uncommitted work. It is the sous-chef who hands over a sauce only once the head chef has approved it.

M4

Microschedules & Deadlock

A microschedule shows how transactions interleave operations and acquire locks.

The lock manager: the component that decides who waits and who runs

The lock manager again, all three jobs in one view. Job one, grant or queue, came on the Locks Stack page; this page is jobs two and three: the microschedule it builds as it grants locks, and the WaitsFor cycle it watches for. The rest of the page is those two jobs in motion.

A read or write takes time, and interleaving fills the gap

Every read and write on the lock manager's timelines below is drawn as a start and an end (Rs to Re, or Ws to We) because the data has to travel to storage and back. While T1's read of B is in flight, the CPU is idle, so the lock manager grants T2 in that gap. The whole point of a microschedule is to make those overlaps visible.

Serial lock schedule T2 → T1 → T3 (completion 49 units)

Figure: Serial lock schedule T2 → T1 → T3 (completion 49 units)

A lock schedule timeline with each transaction on its own row and time on the X-axis (Req and Get as up-arrows, read/write start and end as boxes). It runs T2 first (times 1 to 9), then T1 (10 to 24), then T3 (25 to 48), with no overlap, finishing at 49 time units, the serial baseline the interleaved schedules must beat.

T2 runs first: 5 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T2 requests A at time 1, gets it at 2, starts reading A at 3, ends the read at 8, and unlocks A at 9. T2 never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T1 runs second: 7 operations in time order, all on A. T1 requests A at time 10, gets it at 11, reads A from 12 to 17, writes A from 18 to 23, and unlocks A at 24.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T3 runs last: 12 operations in time order, on B and then A. T3 requests B at time 25, gets it at 26, reads B from 27 to 32, writes B from 33 to 38, requests A at 39, gets it at 40, writes A from 41 to 46, then unlocks B at 47 and A at 48. Nothing overlaps: each transaction starts only after the one before it has unlocked, and the schedule completes at 49 time units, the serial baseline.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(B)
Unl(A)

Serial schedule S1 runs T2, then T1, then T3 with no overlap. It is correct by construction but slow: 49 time units end to end, the baseline the interleaved schedules below have to beat. (The serial order is whichever the lock manager picks; any order is equally correct.)

Interleaved lock schedule (completion 31 units)

Figure: Interleaved lock schedule (completion 31 units)

A lock schedule timeline with each transaction on its own row and time on the X-axis (Req and Get as up-arrows, read/write start and end as boxes), the per-transaction locks, and a WaitsFor graph. A red cycle in the WaitsFor graph is a deadlock.

T1's lane: 7 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T1 requests A at time 1 and waits until it gets A at 10. A is free until T2, which requested it at 2, is granted it first, at 3; T2 then holds A until 10. T1 then reads A from 11 to 16, writes A from 17 to 22, and unlocks A at 23. T1 holds A from 10 to 23.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T2's lane: 5 operations in time order, all on A. T2 requests A at time 2, gets it at 3, reads A from 4 to 9, and unlocks A at 10. T2 holds A from 3 to 10 and never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T3's lane: 12 operations in time order, on B and then A. T3 requests B at time 5, gets it at 6, reads B from 7 to 12, writes B from 13 to 18, then requests A at 19 and waits until it gets A at 23, because T1 holds A. T3 writes A from 24 to 29, unlocks A at 30 and B at 31. The last operation is at 31: the schedule completes at 31 time units.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(A)
Unl(B)

Per-Transaction Locks panel, T1: 1 lock. A is requested at 1, granted at 10, and unlocked at 23.
T1
A: {"Req": 1, "Get": 10, "Unl": 23}

Per-Transaction Locks panel, T2: 1 lock. A is requested at 2, granted at 3, and unlocked at 10.
T2
A: {"Req": 2, "Get": 3, "Unl": 10}

Per-Transaction Locks panel, T3: 2 locks. B is requested at 5, granted at 6, and unlocked at 31. A is requested at 19, granted at 23, and unlocked at 30. The WaitsFor graph beside this panel has two edges, each pointing from a waiter to the holder: T3 waits for T1 on A from 19 to 23, and T1 waits for T2 on A from 3 to 10. That is a chain T3 to T1 to T2 with no cycle, so there is no deadlock.
T3
B: {"Req": 5, "Get": 6, "Unl": 31}
A: {"Req": 19, "Get": 23, "Unl": 30}

When the lock manager interleaves the same transactions, S2 finishes in 31 units, well under the serial 49. Overlapping the lock-free stretches produces the speedup.

Interleaved lock schedule (completion 45 units)

Figure: Interleaved lock schedule (completion 45 units)

A lock schedule timeline with each transaction on its own row and time on the X-axis (Req and Get as up-arrows, read/write start and end as boxes), the per-transaction locks, and a WaitsFor graph. A red cycle in the WaitsFor graph is a deadlock.

T1's lane: 7 operations in time order, all on row A. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write, Unl the unlock. T1 requests A at time 5 and waits until it gets A at 24. It then reads A from 26 to 31, writes A from 32 to 37, and unlocks A at 38. T1 holds A from 24 to 38.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Unl(A)

T2's lane: 5 operations in time order, all on A. T2 requests A at time 1 and waits until it gets A at 38. It then reads A from 39 to 44 and unlocks A at 45, the last operation: the schedule completes at 45 time units. T2 never writes.
T2
Req(A)
Get(A)
Rs(A)
Re(A)
Unl(A)

T3's lane: 12 operations in time order, on B and then A. T3 requests B at time 2, gets it at 3, reads B from 4 to 9, writes B from 10 to 15, requests A at 16, gets it at 17, writes A from 18 to 23, then unlocks A at 24 and B at 25. T3 holds A from 17 to 24.
T3
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)
Get(A)
Ws(A)
We(A)
Unl(A)
Unl(B)

Per-Transaction Locks panel, T1: 1 lock. A is requested at 5, granted at 24, and unlocked at 38.
T1
A: {"Req": 5, "Get": 24, "Unl": 38}

Per-Transaction Locks panel, T2: 1 lock. A is requested at 1, granted at 38, and unlocked at 45.
T2
A: {"Req": 1, "Get": 38, "Unl": 45}

Per-Transaction Locks panel, T3: 2 locks. B is requested at 2, granted at 3, and unlocked at 25. A is requested at 16, granted at 17, and unlocked at 24. The WaitsFor graph beside this panel has three edges, each pointing from a waiter to the holder, all on A: T2 waits for T3 from 17 to 24, T1 waits for T3 from 17 to 24, and T2 waits for T1 from 24 to 38. The edges run T2 to T1 to T3, with T2 also waiting on T3. No cycle, so there is no deadlock.
T3
B: {"Req": 2, "Get": 3, "Unl": 25}
A: {"Req": 16, "Get": 17, "Unl": 24}

S3 is a different valid interleaving of the same transactions, yet it finishes in 45 units, barely better than serial. Interleaving helps only when it overlaps the right operations; the order the lock manager grants in matters, not just the decision to interleave.

Deadlock: 2 transactions, circular wait

Figure: Deadlock: 2 transactions, circular wait

A lock schedule timeline with each transaction on its own row and time on the X-axis (Req and Get as up-arrows, read/write start and end as boxes), the per-transaction locks, and a WaitsFor graph. A red cycle in the WaitsFor graph is a deadlock.

T1's lane, 7 operations in time order. Req is a lock request, Get the grant, Rs and Re the start and end of a read, Ws and We the start and end of a write. T1 requests A at time 1, gets it at 2, reads A from 3 to 8, writes A from 9 to 14, then requests B at 15 and waits, because T2 holds B. T1 keeps holding A while it waits. No unlock is drawn.
T1
Req(A)
Get(A)
Rs(A)
Re(A)
Ws(A)
We(A)
Req(B)

T2's lane, 7 operations in time order. T2 requests B at time 4, gets it at 5, reads B from 6 to 11, writes B from 12 to 17, then requests A at 18 and waits, because T1 holds A. T2 keeps holding B while it waits. No unlock is drawn.
T2
Req(B)
Get(B)
Rs(B)
Re(B)
Ws(B)
We(B)
Req(A)

Per-Transaction Locks panel, T1: 2 locks. A is requested at 1 and granted at 2. B is requested at 15 and has no grant.
T1
A: {"Req": 1, "Get": 2}
B: {"Req": 15}

Per-Transaction Locks panel, T2: 2 locks. A is requested at 18 and has no grant. B is requested at 4 and granted at 5. The WaitsFor graph beside this panel has two edges, each pointing from a waiter to the holder: T1 waits for T2 on B from time 15, and T2 waits for T1 on A from time 18, with no end time on either. The two edges close into a cycle between T1 and T2, drawn in red: a deadlock, and neither transaction can proceed.
T2
A: {"Req": 18}
B: {"Req": 4, "Get": 5}

The same transaction pattern under different timing deadlocks: each transaction holds a ticket the other needs, so the lock manager's WaitsFor graph forms a cycle and neither can proceed. Interleaving buys performance only until a cycle stops everything.

M4

Multi-Version Concurrency Control (MVCC)

MVCC lets readers use earlier row versions while writers create new ones.

When you pulled decides what you see.

One repository changes over time, and your checkout is frozen at the moment you pulled. Engineer C commits a change, which adds v2 (v1 plus the diff, violet). Engineer D pulls afterward and gets v2; Engineer B pulled earlier, so B still has v1 and C's change does not touch B. Same repository, but when you pulled decides what you see.

An uncommitted write is invisible until it commits.

Minnie updates V at 2:45 but does not commit XY34 until 3:03. In that in-flight window the committed value is still AB1, so Pluto (snapshot 2:50) and Mickey (snapshot 3:00) both read AB1, never the half-written XY34. Only a query whose snapshot falls after the commit, like 3:05, reads XY34. The write becomes visible at the commit, not when it starts.

Vacuum: delete versions no query still reads

A version is one value plus a timestamp, not a copy of the row. MVCC must keep an old version while any running query still reads it: here the query that opened at 2:50 still reads v3, and newer queries read v4, but nothing reads v1 or v2. Vacuum deletes the versions no running query needs, so the chain does not grow forever.

Why OLTP and OLAP get physically separated at scale

MVCC removes the reader-writer lock contention, but a long analytical scan still strains shared resources on the production database: it saturates CPU and IO, pollutes the buffer cache, and pins VACUUM so tables bloat. None is a lock problem, so the fix is physical: replicate the data to a separate columnar warehouse for analytics and keep the OLTP database user-facing only.

M4

Optimistic Concurrency Control

Optimistic concurrency control runs first, validates at commit, and retries conflicts.

Optimistic concurrency: run free, validate at commit, redo on a clash

Both transactions run lock-free and check only at commit. T1 validates clean and commits (green); T2 finds a row it read was written by T1, so it fails validation (red), aborts, and reruns. Under two-phase locking T2 would have waited; here the cost of never waiting is redoing the work on a clash.

M4

Connecting It All Together

Concurrency control combines a correctness standard with an execution strategy.

The same two-phase locking, at every scale

The same protocol stretches three ways. It distributes, holding two-phase locking across machines in different cities; it recovers, replaying the write-ahead log after a crash so committed work survives; and it scales, running millions of transactions a second on stock exchanges and bank ledgers. Same core, different operating point.

M4

Change Tracking: Log the Diff, Don't Copy

Log changes instead of copying the whole database.

The version problem: keep the past without copying it

Keeping every version by copying the whole database (red) is billions of rows a second under real load, impossible. Logging each change instead (violet) is a handful of small entries, and any past version replays from them, 10:31:04 included. You reach any moment without ever storing a full copy.

Google Docs version history is a log of edits, not fifty stored copies.

Google Docs keeps periodic snapshots and logs every edit between them, violet, not a full copy of every version. Any past version replays from a nearby snapshot forward. The same move a database log makes: save the change, reach any version.

A git commit is a snapshot that shares unchanged files, not a full copy. Move forward to redo, backward to undo.

Figure: A git commit is a snapshot that shares unchanged files, not a full copy. Move forward to redo, backward to undo.

Three commits run left to right along a time axis: a1b2, plus schema.sql, by Mia, Mon; c3d4, about four lines changed, by Theo, Tue; e5f6, minus dead code, by Mia, Wed. Each carries the note shares unchanged files. A green arrow runs left to right above the row, labeled replay forward to redo committed work, and a red arrow runs back below it, labeled replay backward to undo it. Color key: violet the commits, each with its author and time, green forward to redo, red backward to undo.

The three commits, one column each, left to right in time. The plus, tilde and minus marks read as added, changed and removed.
commit a1b2	commit c3d4	commit e5f6
+ schema.sql	~ 4 lines	- dead code
by Mia, Mon	by Theo, Tue	by Mia, Wed
shares unchanged files	shares unchanged files	shares unchanged files

A Git commit is a snapshot, not a full copy: files that did not change are shared, so history stays small. Moving forward to a later commit redoes work, green; reverting one undoes it, red. A database recovery log gives the same two moves.

M4

The WAL Log

Write-ahead logging records each change before its data page reaches disk.

The lifecycle of one update: append to the log, update the RAM page, flush the page to disk later

Figure: The lifecycle of one update: append to the log, update the RAM page, flush the page to disk later

The update, value A going from 19 to 22.8, sits at the left. Two grey arrows leave it: one up to the violet write-ahead log panel, one down to the red RAM buffer, drawn as a grid of 64 MB page slots with A's page marked dirty. A green arrow then crosses to the disk panel on the right, the same grid of durable slots, 19 of 2048 pages. A time axis along the bottom places steps one and two together at now and step three far to the right at later. Color key: violet is the durable sequential log, red is the volatile RAM buffer, green is the durable disk, grey is page structure.

The three writes one update makes, one column each, with when each happens. The log record is about 40 bytes and sequential; the RAM and disk pages are 64 MB each.
append to log	update RAM page	flush page to disk
durable now	now	later

One update, three writes in time order. ① Append the diff to the log (violet), durable at once; ② update A's page in the RAM buffer (red) in place, fast but volatile; ③ later, flush the whole 64 MB page to disk (green) as one write, start to end. Steps ① and ② happen now and the flush is deferred, so the log is always durable before the page reaches disk.

The WAL log as a table of diffs for T1

Figure: The WAL log as a table of diffs for T1

The log after T1 raises A and B by twenty percent. It is a growing append-only table: each write is one row holding the old value, orange, that undo needs and the new value, green, that redo needs. T1 writes A from 19 to 22.8 and B from 23 to 27.6, then a COMMIT record marks the transaction's end. Ellipsis rows show this is one stretch of a much longer log. Color key: orange is the old value, green is the new value, violet is the log itself.

The log for T1: 2 write rows, then a COMMIT record that ends the transaction. Each row holds the old value, which undo needs, and the new value, which redo needs. T1 writes A from 19 to 22.8 and B from 23 to 27.6. A row of dots above them shows this is one stretch of a longer log that only grows. Each row is about 40 bytes: header 12, txn 4, location 8, old 8, new 8.
Txn	Var	old value	new value
T1	A	19	22.8
T1	B	23	27.6
T1	COMMIT record

The log after two updates: A from 19 to 22.8 and B from 23 to 27.6. Each is one row with the old value (orange) and the new value (green), so the same log carries what it takes to put a change back or take it away. A commit record closes the transaction. These are the rows undo runs against when a transaction aborts, and redo when a crash hits.

The log is the version history

Figure: The WAL log is the version history: replay it to any past state

The log drawn top to bottom in time, each row an old-to-new change: T1 sets A to 22.8 and B to 27.6, then later T2 and T3 change them again. To see the state at any past moment, stop replaying the rows there. Stopping just after T1 gives the version A=22.8, B=27.6. Replaying forward uses the new values, stepping back uses the old, so the log reaches any version either way. Color key: orange is the old value, green is the new value, violet is the log.

The log in time order: 4 change rows. A marker after T1's second row reads "replay up to here": stopping the replay there gives the version at that moment, A = 22.8 and B = 27.6. Replaying forward redoes the new values; stepping back restores the old values, so the log reaches any version either way. A row of dots below shows the log goes on.
Txn	Var	old value	new value
T1	A	19	22.8
T1	B	23	27.6
T2	A	22.8	30
T3	B	27.6	33

The log read top to bottom is a full change history. To see the state at any past moment, stop replaying the rows there: just after T1, the version is A=22.8, B=27.6. Because each row carries both values, you can move either way, redoing new values forward or undoing old values back.

Small and sequential, not big and random

Without the log (grey), each change is a random I/O to its own scattered 64 MB data page, about 13 ms. With the log (violet), every change is a ~40 byte row appended to one growing file, one fast sequential stream: a 64 KB WAL page costs about 13 µs (~1,000× less), and a row in battery-backed NVRAM is durable in about 100 ns (~100,000× less). Small and sequential beats big and random.

Why log-before-data makes a crash recoverable

Figure: Why log-before-data makes a crash recoverable

Two orderings of the same two disk writes: the data page, drawn as a page block, and the log record, drawn as a WAL table row with columns Txn, Var, old value in orange and new value in green. On the left, data first: the crash hits before the log row lands, so the data page changed with no record of why, an unrecoverable state shown in red. On the right, log first as WAL demands: the crash hits before the data page moves, so the intent is in the durable log and recovery re-applies it, shown in green. Color key: red is the unrecoverable order, green is the recoverable WAL order, violet is the durable log.

Data first, the unrecoverable order. The data page on disk already holds A = 22.8 when the crash hits, and this log row never lands. The data changed and nothing remembers why. Unrecoverable, marked in red.
Txn	Var	old	new
T1	A	19	22.8

Log first, the WAL order. This log row is on disk when the crash hits, and the data page with A = 22.8 has not yet moved to disk. The intent is in the durable log, so recovery replays it. Recoverable, marked in green.
Txn	Var	old	new
T1	A	19	22.8

Data first (red): if the crash hits before the log row lands, the data changed with no row to replay, an inconsistency recovery cannot fix. Log first (green), the WAL order: a crash before the data page moves leaves the change sitting in the durable log, ready to re-apply. Log-before-data is the only order that keeps the data file recoverable.

M4

Undo for Aborts

Undo reverses an aborted transaction using the old values in its log.

Undo is a write too: it appends W-abort rows

Figure: Undo is logged: it appends W-abort rows to the log

A five-column log table, Txn, Action, Var, old value, new value, built in three stages. First T1's two original writes. Then, under a note that T1 aborts, the two W-abort rows undo appends, drawn in red. Last the abort record, its value columns dashes. Color key: orange is the old value, green is the new value, red marks undo's own W-abort rows.

T1's log rows in time order: the two original writes, then the three rows T1's abort appends. The W-abort rows are drawn in red in the figure.
Txn	Action	Var	old value	new value
T1	W	A	19	22.8
T1	W	B	23	27.6
T1	W-abort	B	27.6	23
T1	W-abort	A	22.8	19
T1	abort

T1's rows from the WAL Log page. When T1 aborts, undo does not just fix the data page, it appends its reversal to the log: a W-abort row for B (27.6 back to 23), then A (22.8 back to 19), then an abort record. The page ends at A=19, B=23. Because each reversal is itself a logged write, the log records the whole rollback, W-abort rows and all.

The log: TLong aborts and unwinds

Figure: The log for a long transaction TLong that aborts

A log table for TLong, which writes A0 and A1000 then aborts. The two forward writes raise A0 from 19 to 22.8 and A1000 from 27 to 32.4. Undo then walks the log backward, newest change first: it logs a W-abort that restores A1000 from 32.4 to 27, then a W-abort that restores A0 from 22.8 to 19, then a final abort record. The old value column drives each undo. Color key: violet is the log, red marks the undo writes that reverse the transaction, green is the restored data on disk.

The log for TLong: 2 forward writes, then undo appends 2 W-abort rows, newest write undone first, and a final abort record. The last column is the disk state after each row. Each W-abort, marked in red, reuses the old value of its forward row: A1000 from 32.4 back to 27, then A0 from 22.8 back to 19. The abort record has no variable or values; after the two W-abort rows, the disk is back at the start state. Undo does not erase log rows; the log records TLong's full rollback.
Time	Txn	Action	Var	old value	new value	disk state after
13	TLong	W	A0	19	22.8	A0 = 22.8
92	TLong	W	A1000	27	32.4	A1000 = 32.4
1000	TLong	W-abort	A1000	32.4	27	A1000 = 27
1000	TLong	W-abort	A0	22.8	19	A0 = 19
1000	TLong	abort				back to start state

TLong aborts. Undo walks the log backward, newest write first, restoring A1000 from 32.4 to 27, then A0 from 22.8 to 19, reusing the old value each forward row recorded. Each undo becomes its own W-abort row (red), so the log records the rollback itself. A final abort record closes the transaction.

M4

Recovery Post-Crash

Recovery preserves committed changes and removes unfinished work after a crash.

A crash leaves one question: which work survives?

The whole answer is in the **WAL**. Committed transactions are kept, green; transactions that never committed are reversed, orange. Recovery is the procedure that reads the log and enforces both.

Two passes over one log: replay down, then undo up

Figure: Crash recovery on one WAL: a forward replay rebuilds the crash state, then a backward undo reverses the unfinished transactions

A WAL drawn top to bottom in time order, with the page log columns: Time, Txn, Action, Var, old value, new value. Start state A=10, B=20, C=30, D=40, E=50, update f(x)=x times 1.2. The figure runs in five stages. First the log and the start state. Then a red CRASH line marks where the server stopped. Then the REPLAY pass runs down the left re-applying every logged row, original writes and the in-log abort rows alike, rebuilding the exact crash state A=12, B=20, C=43.2, D=48, E=60. Then the UNDO pass runs up the right and reverses only the uncommitted transactions newest-first: E 60 to 50, C 43.2 to 36, C 36 to 30. Finally the consistent state A=12, B=20, C=30, D=48, E=50. T1 and T4 committed and are kept; T2 aborted explicitly and was already rolled back in the log; T3 and T5 never committed and are undone. Color key: violet = the replay and undo passes and the rows undo removes, blue = durability, the committed work the replay keeps, orange = atomicity, the uncommitted work the undo removes, grey = rows left untouched, red = the crash.

The WAL for 5 transactions: 10 rows in time order, and the server crashes after row 10. Start state A=10, B=20, C=30, D=40, E=50; each write applies f(x) = x times 1.2. T1 and T4 commit (rows 3 and 9). T2 aborts on its own: row 6 is its W-abort putting B back from 24 to 20, and row 7 is its ABORT record. T3 and T5 never commit. At the crash, disk holds whatever was written before it, not a consistent state. REPLAY runs down all 10 rows, W-abort included, and rebuilds the crash state A=12, B=20, C=43.2, D=48, E=60. UNDO then runs up and reverses only T3 and T5, newest first: step 1 undoes E from 60 to 50 (row 10), step 2 undoes C from 43.2 to 36 (row 8), step 3 undoes C from 36 to 30 (row 2). Final, consistent state: A=12, B=20, C=30, D=48, E=50. T1 and T4 are kept (durability); T2, T3, T5 are gone (atomicity).
Time	Txn	Action	Var	old value	new value
1	T1	W	A	10	12
2	T3	W	C	30	36
3	T1	COMMIT
4	T2	W	B	20	24
5	T4	W	D	40	48
6	T2	W-abort	B	24	20
7	T2	ABORT
8	T3	W	C	36	43.2
9	T4	COMMIT
10	T5	W	E	50	60

Recovery as two passes over one log:

Just after the crash: the disk holds a half-written mix

Figure: Just after the crash: RAM is gone and the disk is an inconsistent mix of flushed and unflushed work

The instant after the crash. RAM is gone, every in-flight change with it. The disk survived but it is not consistent: it holds whatever was written before the power died. Some committed writes never flushed, so a committed value is missing. Some uncommitted writes did flush, so an uncommitted value is sitting on disk. The durable WAL is untouched and still holds the full history, which is how recovery sorts the mess out. Color key: red = RAM, now empty, green = the durable disk that is not yet consistent, violet = the durable, sequential WAL that survived and drives recovery.

Disk just after the crash: 3 values, not consistent. A=12 flushed: T1 committed it and it did reach disk. D=40 stale: T4 committed D from 40 to 48, but that write never flushed, so committed work is missing. E=60 wrong: T5 never committed, but its write flushed, so uncommitted work is present. RAM is gone, and every in-flight change with it.
Disk · not consistent
A=12 flushed
D=40 stale
E=60 wrong

The write-ahead log, durable and untouched by the crash: the 5 writes the figure shows, in log order: A from 10 to 12, C from 30 to 36, D from 40 to 48, C from 36 to 43.2, E from 50 to 60. With old and new values, it holds enough to rebuild and to undo.
WAL · durable, sequential
A: 10→12
C: 30→36
D: 40→48
C: 36→43.2
E: 50→60

Just after the crash. RAM, red, is gone with every in-flight change. The disk, green, survived but is not consistent: a committed write is missing, and an uncommitted write is wrongly present. The WAL, violet, is untouched, and it is the only thing recovery can use, because RAM holds nothing.

Recovery restores durability and atomicity across a crash

Two ACID guarantees fall out of the two passes, in the order the passes run. Durability, the violet D, comes from the replay: once you see COMMIT, that work is replayed and never undone, so it survives any failure. Atomicity, the blue A, comes from the undo pass: a transaction is all or nothing, so unfinished work is reversed. Both rest on the write-ahead rule at the base, the log reaching disk before the data.

M4

Transaction Manager: The Architecture

The transaction manager coordinates concurrency, logging, and recovery.

Five components of a transaction manager

Scheduling and locking provide isolation. Logging and recovery support atomicity and durability; deadlock detection breaks cycles of waiting. Application logic and constraints preserve consistency.

A no-conflict trace: three transactions on different tuples flow through the Transaction Manager, four of the five components fire

One coherent execution. The scheduler routes each transaction to a thread, the lock manager grants all three locks with no waiting (the rows do not overlap), and the WAL logs every change before its commit becomes durable. The deadlock detector stays quiet because there is no waits-for cycle, and the recovery manager only acts if the server crashes. ACID preserved.

Why the Transaction Manager scales: most transactions touch different data, so few of them ever conflict

In this example, most transactions access different rows. Actual contention depends on the workload; hash-based lock checks and sequential logging reduce overhead.

M4

Three Transactions, Three Variables

Trace three transactions through scheduling, locking, logging, commit, and abort.

One interleaved schedule, three transactions

One interleaved schedule, eight reads and writes in step order. T1 and T2 share A, T3 owns B and C, so the scheduler is free to interleave them. Reads are blue, writes orange, and the Value column is the variable right after each step. Under Strict 2PL every lock is held until COMMIT or ABORT, which is what keeps this interleaving safe.

Scenario 1: all three commit

Each write is logged to the WAL, then a COMMIT record follows, so the change is durable the moment the commit lands. Strict 2PL holds each lock until that COMMIT, so no transaction ever read another's uncommitted data. The database advances to one new consistent state: A=27.36, B=38.4, C=32.4, all durable (the violet D for Durability).

end of lecture 2~69 min of figures

Scenario 2: T3 aborts, T1 and T2 commit

The recovery manager reads T3's WAL entries backward and restores the old values, reverting C from 32.4 to 27 and B from 38.4 to 32, so T3 leaves no trace (the blue A for Atomicity). The final state is A=27.36, B=32, C=27.

M4

Problem Solving: The Taylor Swift Ticket Disaster

Correct transactions still need an application design that handles heavy demand.

Ticketdisaster.com checkout flow under Eras Tour load

The lock acquires the instant a user picks a zone and stays held through browsing and payment, so one slow user freezes a thousand seats for minutes. The three worst bottlenecks come next.

Fix 1: shrink the lock

Shrink the lock. A zone lock freezes a thousand seats, so nine hundred ninety-nine other fans wait on one. A seat-level lock blocks nobody else, and about a hundred times more fans browse at once.

Fix 2: cut lock duration

The old flow holds the zone lock through browsing and payment, five to ten minutes, so only about a hundred fans run at once. The fix does the slow steps in the queue with no lock and takes the lock only for the final write, about thirty seconds, so about ten thousand fans run at once.

Fix 3: fall back to async

Instead of blocking in real time, fans submit instantly with a timestamp, a background job processes them in order, and the confirmation arrives by email. The three-hour queue becomes a sixty-second submit.

M4

Where's the Next 100x?

Choose the next optimization by measuring contention, I/O, and coordination costs.

Where could the next 100× come from?

Choose the change that addresses the measured bottleneck. Improving Strict 2PL and choosing another protocol are both options.

Nested hierarchy: every S2PL schedule is a 2PL schedule, every 2PL schedule is conflict-serializable, every conflict-serializable schedule is serializable

Serializability is the correctness target. A scheduling rule may be more restrictive to make correctness practical to enforce.

Match the workload to the mechanism

These mechanisms solve different problems. LSM storage does not replace transaction concurrency control.

Scale the workload. Preserve correctness.

Distributed systems add communication and partial failures to the same correctness and performance questions.

end of lecture 3~15 min of figures

M4 Transactions, recovery, and the whole manager 1 of 78

‹ › ▶ Y Notes □ keys

M4 Transactions, recovery, and the whole manager

Correctness under concurrency, then surviving a crash · 78 figures · ~152 min · 3 lectures at this pace