The Bank Transfer

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.

Not run yet · 4 tests

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

Drawing the diagram…

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:

droid session

[WAL] Recovery: records=32 replayed=10 discarded=0 rolled_back=1
Welcome 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

shell

$droid --db bank.db
Welcome 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
>.exit
exiting.. 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.

Loading starter code…

No run yet

4 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.