The Bank Transfer
Four sessions, money moving, a deadlock, an auditor and a crash: every stage of the part at once
Run one scripted day at a bank, in which transfers commit, wait, deadlock and crash while an auditor keeps reading, and show that the total never changes, the victim leaves no trace, purge drains when the auditor ends, and recovery keeps every commit and nothing else.
- An invariant across transactions: transfers move money, never make it
- Each stage of the part protects one step of the script
- Readers and writers never block each other; writers queue and, in a cycle, one gives way
- Recovery after a crash leaves exactly the committed transfers
Why this stage exists
Each stage of this part answered one question in isolation. A bank asks all of them at once. Four accounts of 100 each, an index on the balance, and one rule that must always hold: the money adds up to 400.
Four sessions share the day:
- @4, the auditor, begins before anything happens and sums the balances again and again.
- @1 moves 10 from account 1 to account 2.
- @2 moves 20 from account 3 to account 4, and later 1 from account 4 to account 2.
- @3 tries to move 5 from account 2 to account 3.
The day, line by line
Every step leans on one stage:
| Step | What makes it right | Stage |
|---|---|---|
| the auditor's SUM never waits and never moves | its read view, rebuilt from undo | read-views |
| @3 cannot touch account 2 while @1 has it | X on the row, held until COMMIT | row-locks |
| @3 runs after @1's COMMIT, on @1's balance | parking and running again | lock-waits |
| @2 and @3 wait for each other | a cycle in the wait-for graph; the youngest gives way | deadlock |
| @3's −5, already applied, disappears | its undo records, newest first, by key | undo-log |
| several sessions on one leaf of accounts | undo by row, not by page | undo-log |
| the index on the balance agrees with every view | marked entries and the recheck | mvcc-indexes |
| old versions pile up while the auditor reads | the oldest view as the horizon | purge |
| they go when the auditor ends | no view open, so every committed record is dropped | read-views |
The auditor's every SUM is 400: it reads the day as it was before any transfer. A new session afterwards reads 90, 111, 80 and 119: @1's transfer, both of @2's, and nothing of @3's.
And then a crash
The next morning, @1 starts moving 50 from account 1 to account 2 and has taken it out of account 1 when @5 commits a small transfer of its own. Its commit logs the leaf holding all four accounts, with @1's −50 on it, and, because @1 is open, @1's undo record with it. The machine crashes.
At the next open, redo replays @5's commit, −50 included, and the undo pass rolls @1 back:
[WAL] Recovery: records=32 replayed=10 discarded=0 rolled_back=1Welcome to droid!>select sum(bal) from acct;SUM(bal)400(1 rows)[EXEC] rows_examined=4
Every commit survived, nothing else did, and the index and the file check out.
The algorithm in words
Reading the script
For each line, name the stage that makes it right.
- 1.The auditor's first SUM takes a read view (read-views): every later SUM is computed from it.
- 2.Each transfer's UPDATEs take X on their accounts (row-locks); one that needs a held account parks and resumes after the holder commits (lock-waits).
- 3.Two transfers each waiting for the other form a cycle; the youngest is rolled back by its undo records (deadlock, undo-log).
- 4.A commit beside an open transfer logs that transfer's undo with the page (undo-recovery); a crash rolls it back after redo.
- 5.While the auditor reads, kept versions pile up behind its view (purge); when it commits, no view is left and every kept version is dropped (read-views).
Output contract for this stage
This stage adds nothing to the contract. Every line it checks is defined in sections 80 to 90 of the output contract page.
What you should see when done
$droid --db bank.dbWelcome to droid!>create table acct (id int primary key, bal int);Create table statement executed successfully>insert into acct (id, bal) values (1, 100);Insert statement executed successfully (1 rows)>insert into acct (id, bal) values (2, 100);Insert statement executed successfully (1 rows)>@4 begin;@4| Begin statement executed successfully>@4 select sum(bal) from acct;@4| SUM(bal)@4| 200@4| (1 rows)@4| [EXEC] rows_examined=2>@1 update acct set bal = bal - 10 where id = 1;@1| Update statement executed successfully (1 rows)@1| [EXEC] rows_examined=1>@4 select sum(bal) from acct;@4| SUM(bal)@4| 200@4| (1 rows)@4| [EXEC] rows_examined=2>.exitexiting.. good bye!
Common bugs in this stage
Every bug of the part shows up here, and the script tells which:
- A SUM that is not 400. A read view or a version walk.
- A wrong balance after the day. Undo, or a resumed statement that read too early.
- A hang. A missed deadlock.
- A different total after the crash. The undo pass.
Language notes
The page above is the same for every language. This stage adds no code: if each earlier stage is right, the script passes.
Checklist
One line per thing the tests check. The tags name the test cases.
- The auditor's total is 400 every time it askssum-is-invariant
- The deadlock victim's transfer leaves no tracevictim-transfer-absent
- Old versions are kept while the auditor reads, and dropped when it commitspurge-after-reader-ends
- After a crash the total is unchanged and the open transfer is goneafter-crash