Transactions and the write-ahead log
How a database makes several changes count as one, and how it keeps a commit through a crash. Builds on ACID and BASE.
5 minute lesson
Begin, then commit or roll back
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;Everything between BEGIN and COMMIT is one transaction. Until the commit nothing is final: ROLLBACK, an error or a crash undoes all of it. After the commit all of it stays. There is no state in between.
A transaction takes 100 from account 1. Its second statement, which adds 100 to account 2, fails with an error. The application sends ROLLBACK.
What are the balances afterwards?
- Both as they were before the transaction
- Account 1 lower and account 2 unchanged
- Account 1 lower and account 2 higher
- Both set to zero until someone checks
Show the answer
- Both as they were before the transaction
Nothing in a transaction is final before the commit. The rollback undoes the first update as if it had never run, and the money is back in account 1. Without the transaction the first update would have stood alone, and 100 would be gone.
A rollback undoes everything since BEGIN. A transaction never half-happens.
Write it down before you do it
- Log first
Each change is first described in the write-ahead log, a file that is only ever appended to. At commit that log is forced onto the disk.
- Changedescribed
- Logon disk
- Confirm
Now the database confirms the commit. The data files themselves have not been touched yet. They are updated later, at leisure.
- Commitconfirmed
- Data filesnot yet updated
- Crash
The power fails. On restart the database reads the log and repeats every change that had not reached the data files. Nothing that was confirmed is lost.
- Logreplayed
- Data filescomplete again
A database confirms a commit. Its log is on disk, but the data files have not been updated yet. Then the machine loses power.
What happens to the committed change?
- It is redone from the log when the database restarts
- It is lost, as the data files never received it
- It is half applied and has to be fixed by hand
- It is resent by the application after a timeout
Show the answer
- It is redone from the log when the database restarts
The data files are behind, but the log holds a full description of the change, safely on disk. On restart the database goes through the log and applies everything the data files are missing. This is why the log is written first: the confirmation rests on the log, not on the data files.
A commit is safe once the log is on disk. After a crash the log is replayed.
Why a log
- It is cheap. A commit needs one append to the end of one file. Updating the data files would mean writes scattered all over the disk.
- It is shared. One flush of the log can commit many transactions that finished at the same moment.
- It is the full story. The log lists every change in order. A copy of the database on another machine can be kept up to date by replaying it.
How can a database confirm a commit before it has updated its data files, and still lose nothing in a crash?
Show the answer
It first appends a description of every change to the write-ahead log and forces the log to disk. Only then does it confirm. The data files are updated later. After a crash the database replays the log and redoes whatever had not reached the data files. The log append is one sequential write, which is why commits are fast.
Recap
- A transaction is everything between BEGIN and COMMIT: it happens completely or not at all.
- Changes go to the write-ahead log first. A commit is confirmed once the log is on disk.
- After a crash the log is replayed. The same log keeps replicas up to date.