Transactions

The big picture: what is a transaction?

A transaction is a group of operations that the database treats as one single unit of work. You start it with BEGIN. You finish it in one of only two ways: COMMIT (keep everything) or ROLLBACK (throw everything away, as if nothing had happened).

BEGIN;
UPDATE accounts SET balance = balance - 10 WHERE id = 1;
UPDATE accounts SET balance = balance + 10 WHERE id = 2;
COMMIT;

Three enemies of your data

ACID: the four promises

ACID is a word made from four first letters. Each letter is one promise that a transaction makes. Let's meet them with the piggy bank transfer in mind.

Atomicity: all or nothing

If the server crashes after the debit and before the COMMIT, the database acts as if the transaction never existed. On restart it uses its log to undo the incomplete work. The command ROLLBACK (with no savepoint) asks for the same thing on purpose.

Atomicity only covers what is inside one transaction. In autocommit there is no BEGIN, so a debit and a credit sent as two commands are two separate transactions. If the program dies between them, the debit stays and the credit is lost. To keep two writes together, wrap them in BEGIN and COMMIT.

Savepoints and errors inside a transaction

A savepoint is a bookmark inside a transaction. ROLLBACK TO SAVEPOINT undoes only the work after the bookmark and keeps the transaction open.

BEGIN;
INSERT INTO logs (msg) VALUES ('a');
SAVEPOINT s1;
INSERT INTO logs (msg) VALUES ('b');
ROLLBACK TO SAVEPOINT s1;   -- undoes only 'b'
INSERT INTO logs (msg) VALUES ('c');
COMMIT;                     -- stores 'a' and 'c'

In PostgreSQL, when a command fails inside a transaction (for example a duplicate key), the whole transaction enters an aborted state. Every next command is refused with 'current transaction is aborted', and even a COMMIT just undoes everything. If you expect an error and want to go on, put a savepoint before the risky command.

Consistency: the rules stay true

Consistency in ACID means: when the transaction finishes, the database respects its integrity rules (primary keys, CHECK, foreign keys). During the transaction the rules may be broken for a moment, but not at COMMIT. It is the only ACID letter shared between the database and the program. The database only knows the rules that were declared. If the rule 'the sum of all balances never changes' is not declared, and a buggy transaction debits 100 and credits 90, the database commits it happily. The other three letters exist so that a correct program is not disturbed.

Durability: committed means saved

When the database says 'COMMIT done', the information needed to redo the transaction is already on persistent storage (usually in the log). Each COMMIT costs one disk write that must really reach the disk. PostgreSQL has a setting, synchronous_commit = off, that answers before that write. It is faster, but you accept a small window in which the latest transactions can be lost in a crash. Atomicity and consistency are not affected, because the log is still written in the right order.

A trap with ORMs

A transaction belongs to one connection. With an ORM such as Prisma, the object received by the callback (tx) is the only one that talks through that connection.

await prisma.$transaction(async (tx) => {
	const order = await tx.order.create({ data: { total: 100 } });
	await prisma.payment.create({ data: { orderId: order.id } }); // BUG: global client
	throw new Error("stock check failed");
});

Isolation levels and anomalies

Imagine two cooks sharing one recipe card. One cook crosses out a number while the other is reading it. If they do not agree on some rules, the cake goes wrong. Isolation is the set of rules that decide how much two transactions that run at the same time may see of each other's work. A mistake caused by this mixing is called an anomaly.

The five anomalies

The SQL standard only names the first three (dirty read, non-repeatable read and phantom). Lost update and write skew were left out of its table. So a database can follow the letter of a level and still not be serializable.

The four levels of the SQL standard

The standard defines each level by the list of phenomena it forbids. Going from weakest to strongest: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE. A higher level allows fewer anomalies and usually costs more (waiting or aborted transactions).

PostgreSQL is stricter than the standard

• The default level is READ COMMITTED (setting default_transaction_isolation).
• READ UNCOMMITTED is accepted but works exactly as READ COMMITTED. A dirty read never happens, at any level.
• REPEATABLE READ is snapshot isolation: the transaction sees the database as it was at its first command. So there are no phantoms either, although the standard would allow them.
• SERIALIZABLE is serializable snapshot isolation (SSI): snapshots, plus the tracking of who read and who wrote what.

The big difference between the first two real levels is how long the picture lasts. At READ COMMITTED every command takes a new snapshot, so two SELECT count(*) in the same transaction can give different answers. At REPEATABLE READ one snapshot serves the whole transaction.

Lost update, step by step

time   Session A                    Session B
1      SELECT stock -> 10
2                                    SELECT stock -> 10
3      UPDATE SET stock = 9; COMMIT
4                                    UPDATE SET stock = 9; COMMIT

final stock = 9   (two sales, it should be 8)

This is possible at READ COMMITTED. At REPEATABLE READ in PostgreSQL, if a transaction tries to change a row that another transaction changed and committed after its snapshot, it is aborted with SQLSTATE 40001 (a code for 'could not serialize access'). It is not a bug: it is the contract. The program must retry the whole transaction.

There is also a trick that avoids the problem without a high level. A single statement such as the one below does the check and the write inside the database. If another transaction holds the row, the command waits; when that one commits, the WHERE is checked again on the new version of the row.

UPDATE accounts
SET balance = balance - 100
WHERE id = 1 AND balance >= 100;

Write skew: the doctors on call

rule: at least one doctor on call

time   Ana                           Beto
1      count on_call -> 2
2                                    count on_call -> 2
3      UPDATE Ana  on_call = false
4                                    UPDATE Beto on_call = false
5      COMMIT                        COMMIT

result: 0 doctors on call

REPEATABLE READ does not notice this, because it only checks two writes to the same row. SERIALIZABLE in PostgreSQL watches the dependencies between reads and writes, and aborts one of the two with 40001. It is the only level that stops write skew, and again the program must retry.

Locking: two-phase, pessimistic and optimistic

There are two big ways to stop transactions from stepping on each other: lock the data so others wait, or let everybody work and check at the end. Let's start with locks.

Shared and exclusive locks

Two-phase locking (2PL)

The rule: the life of a transaction has a growing phase, in which it only acquires locks, and a shrinking phase, in which it only releases them. After the first release, no new lock may be acquired. If every transaction follows this rule, the concurrent execution is equivalent to some serial order: it is serializable. But 2PL does not prevent deadlocks.

locks held
   ^
   |        /\
   |       /  \
   |      /    \
   |     /      \
   |    /        \
   +---+----------+--------> time
    growing   shrinking
    (only      (only
    acquire)   release)

In basic 2PL a write lock may be released before the end, which shows data that is not yet committed. Strict 2PL keeps the exclusive locks until COMMIT or ROLLBACK. This removes the problem of other transactions depending on data that may still be undone.

Pessimistic and optimistic

Pessimistic in SQL is SELECT ... FOR UPDATE: the transaction reads the rows and reserves them in the same command, which closes the window between reading and writing, where lost updates are born.

Optimistic control usually uses a version column. You read the row and its version without locking. When you write, you demand that the version is still the same, and you increase it.

UPDATE products
SET stock = stock - 1, version = version + 1
WHERE id = 1 AND version = 7;
-- UPDATE 0   <- someone wrote first

Details that matter in PostgreSQL

• Row locks only make queue those who also want a row lock: UPDATE, DELETE, SELECT FOR UPDATE and FOR SHARE. A plain SELECT is served by versions and is not blocked. So FOR UPDATE protects only if every concurrent transaction uses it too.
• Wrapping read, check and write in a transaction is not enough at READ COMMITTED, because a plain read does not reserve the row. This is how a checkout oversells stock. Three fixes: FOR UPDATE, a version column, or SERIALIZABLE with retry.
• With 200 buyers fighting for 10 units on one row, optimistic control wastes work (one write wins per round, the rest redo), while FOR UPDATE makes them wait in line. In this repository's overselling lab, the naive code created 150 to 180 orders for 10 units, and every fix created exactly 10.
• Row locks do not stop phantoms. A phantom is a new row that starts to match the query, and it does not exist yet to be locked. To stop it you must lock the condition itself: predicate locks, index range locks (next-key) or the whole table.

MVCC: many versions of a row

Locks make readers and writers wait for each other. Multiversion concurrency control (MVCC) has a cleverer idea: a write never destroys the old value. It adds a new version of the row. Each transaction sees the version that fits its own point in time.

Why MVCC is good

With pure locking, a long read holds back writes and a write holds back reads. With MVCC, reads are served by versions already committed, so readers do not block writers and writers do not block readers. But the conflict between two writes on the same row is still there: the second waits for the first. Then, depending on the level, it continues on the new version or is aborted.

Snapshots

A snapshot is only a visibility rule: it says which transactions count as already committed for the reader. For each row, the reader gets the newest version created by one of those transactions. No physical copy is made. A snapshot also remembers who was running when it was taken: those transactions are treated as uncommitted forever, even if they commit one instant later, and the same goes for those that start afterwards.

How PostgreSQL stores versions

PostgreSQL keeps all versions in the table itself. Each version has two hidden columns: xmin, the transaction that created it, and xmax, the transaction that expired it (deleted or replaced it). An UPDATE is really: mark the current version as expired and insert a new one.

SELECT ctid, xmin, stock FROM products WHERE id = 1;
--  (0,1) | 740 | 10
UPDATE products SET stock = 9 WHERE id = 1;
SELECT ctid, xmin, stock FROM products WHERE id = 1;
--  (0,2) | 752 | 9

A version is visible to a snapshot when the transaction in xmin is committed for it and the transaction in xmax is not. If xmax belongs to a transaction still in progress (or aborted), the version stays visible. That is how a pending DELETE or UPDATE stays invisible to others.

row version:  xmin = 100  xmax = 105  stock = 10

transaction 100: COMMITTED
transaction 105: IN PROGRESS
transaction 110: runs SELECT now

100 committed          -> created: OK
105 not committed yet  -> not expired for 110
=> transaction 110 SEES this version

The cost: dead versions and VACUUM

Each UPDATE or DELETE leaves a dead version behind. VACUUM (usually started by autovacuum) finds versions that no active snapshot can see and frees their space. A version can only be thrown away when nobody needs it. So a transaction left open for hours at REPEATABLE READ, doing nothing, pins the 'oldest needed point' in the past: every version created since then is kept. The tables and indexes grow (bloat) and queries get slower.

Snapshot isolation and its limit

Snapshot isolation applies one rule: among concurrent transactions that write the same row, only one may commit. It prevents the lost update. But it does not know what each transaction read, so it cannot notice write skew. Detecting write skew needs the tracking of reads, which is what PostgreSQL's SERIALIZABLE adds.

Deadlocks

Two children, two toys. Ana holds the car and wants the doll. Beto holds the doll and wants the car. Neither lets go before getting the other toy, so they wait forever. This is a deadlock: a group of transactions, each holding a lock and asking for a lock owned by another one of the group, forming a cycle. The wait never ends by itself.

T1 holds lock A, wants lock B
T2 holds lock B, wants lock A

   wait-for graph:

   +----+  waits for  +----+
   | T1 | ----------> | T2 |
   |    | <---------- |    |
   +----+  waits for  +----+

   a cycle = deadlock

The wait-for graph is the classic tool to detect deadlocks. While it has no cycle, there is always someone who waits for nobody and can finish. A cycle means circular waiting. The cure is to choose a victim in the cycle and abort it.

What PostgreSQL does

PostgreSQL does not prevent deadlocks, it detects them. When a lock wait is longer than deadlock_timeout (1 second by default), the server searches for a cycle. If it finds one, it aborts one transaction with error 40P01 (deadlock detected). The rollback of the victim frees its locks and the others go on.

How to deal with deadlocks in your application

• Retry. The victim is aborted as a whole, not only the statement that was waiting. Error 40P01 is transient. Catch it, ROLLBACK, and run the transaction again from BEGIN, with a limited number of attempts.
• Lock in the same order. A cycle only forms when transactions ask for the same locks in different orders. If every transfer always locks the account with the lowest id first, the second transaction stops at the first lock and holds nothing the first one needs. This is the simplest prevention.

Prevention by age: wait-die and wound-wait

Another way is to give each transaction a timestamp (its age) when it starts and allow waiting in one direction only. Since all the waits go the same way along the age line, a cycle is impossible.

Logging and recovery: the write-ahead log

How can a database promise atomicity and durability if the power can fail at any moment? The answer is a notebook called the log. Before changing anything important, the database writes down what it intends to do.

The rule of the write-ahead log (WAL)

Write-ahead logging: the log record of a change must reach stable storage (the disk) before the changed data page is written. And at COMMIT, the commit record must be on disk before the server tells the client 'COMMIT done'. The commit point of a transaction is the moment its commit record is safe. From then on the result is guaranteed, even if no data page has been written yet.

Why write the log and not the pages?

A transaction may change a few bytes in many different pages. Writing all those pages at commit means many random writes of whole pages. The log turns it into one sequential write with only the changes, which is fast. The pages go to disk later, in the background.

Checkpoints

Without help, after a crash the database would have to reread the whole log. A checkpoint writes to disk the pages that were changed in memory and marks that point in the log. After a crash, only the log after the last checkpoint is replayed. The older log can be recycled.

What recovery does after a crash

checkpoint        crash
    |                |
----+----------------+------> time
    T1 committed     T2 was still active

    T1 pages may NOT be on disk  -> REDO from the log
    T2 pages MAY be on disk      -> UNDO from the log

Transactions are split into winners (they have a commit record in the log) and losers (they do not). Redo reapplies winners that may not have reached the pages. Undo removes the effects of losers that did reach them. A transaction that had changed three rows and had not issued COMMIT is undone completely. This is how atomicity survives a crash.

System crash against media failure

ARIES in a few lines

• Three phases: analysis (find out what was going on at the crash), redo, undo.
• Repeating history: redo reapplies the whole log, of winners and losers, until the database is identical to the instant of the crash. Only then does undo walk the log backwards, undoing the losers and writing each step as a compensation log record (CLR). So recovery stays correct even if it is interrupted and restarts.
• LSN: each log record has a log sequence number, and each page stores the LSN of the last change it received. During redo, a record is applied only if its LSN is greater than the page's. Running recovery twice applies nothing twice: redo is idempotent.

Torn pages and full-page writes

An ordinary log record says 'change this bit relative to the old content', so it assumes the page on disk is intact. If the crash happens in the middle of writing a page, the page ends up part new and part old (a torn page) and incremental redo breaks. In PostgreSQL, with full_page_writes = on, the first change to a page after a checkpoint writes the whole page image to the WAL. This gives recovery an intact starting point.

Distributed transactions and two-phase commit

Inside one database, the local log gives atomicity. But what if one transaction changes data in two different databases? Each one could commit or fail on its own, and you would end up with a debit in one place and no credit in the other. Two-phase commit (2PC) is a protocol that makes all of them agree on one outcome: all commit or all abort.

The two phases

Coordinator            Participants A, B, C
    |  PREPARE?  ------>  
    |  <------ yes/no
    |      (phase 1: vote)
    |
    |  all yes -> COMMIT  ---->
    |  any no  -> ABORT   ---->
    |      (phase 2: decision)

• Phase 1, prepare. The coordinator asks every participant if it can commit. Each one prepares and votes yes or no.
• Phase 2, decision. If all voted yes, the coordinator tells everyone to commit. If any voted no (or did not answer in time), it tells everyone to abort.
• The decision is unanimous: a single 'no' makes everything abort, because only each participant knows if its own part can be committed (a constraint may have failed, for example).

What a 'yes' means

Before voting, a participant may abort whenever it wants. After voting yes, it has made a promise: 'I can commit, whatever happens'. It can no longer commit or abort by itself, it must wait for the coordinator. To keep the promise even if it crashes right after, the participant must force-write the changes and a prepare record to its log before answering yes. When it comes back, it finds the prepared transaction and asks the coordinator what was decided.

The big problem: blocking

2PC is a blocking protocol. If all participants voted yes and the coordinator crashes before sending the decision, the participants are in doubt. They cannot choose alone, so they wait for the coordinator to return and read the decision from its log. Meanwhile their data stays locked. This window of uncertainty, with locks held, is the main cost of 2PC.

2PC building blocks in PostgreSQL

BEGIN;
UPDATE accounts SET balance = balance - 10 WHERE id = 1;
PREPARE TRANSACTION 'tx42';   -- durable, session is free
-- later, from any session:
COMMIT PREPARED 'tx42';       -- or: ROLLBACK PREPARED 'tx42';

• PREPARE TRANSACTION makes the transaction ready to commit and durable. It requires max_prepared_transactions greater than zero (the default is zero).
• If the coordinator never returns, the orphaned prepared transaction keeps holding its row locks. It is also still 'in progress', so VACUUM cannot clean old versions and tables bloat.
• Whoever uses the feature must watch the view pg_prepared_xacts.

Saga and outbox

Two-phase commit couples every participant: if one is down, nobody commits, and most message brokers do not take part in it anyway. Modern systems with many small services (microservices) usually give up the single transaction and build safety from smaller pieces. The two famous pieces are the saga and the outbox.

The dual-write bug

Your service must save an order in its database and announce OrderCreated to a broker. That is two different systems and no transaction around both. This is a dual write.

await db.insert(orders).values(order);          // 1: COMMIT in the database
// <- crash here
await broker.publish("order.created", order);   // 2: publish to the broker

Reversing the order does not fix it. Publish first and crash, and an event announces an order that never existed, which is usually worse. No ordering of two writes fixes a lack of atomicity between two systems.

The transactional outbox

The trick: turn two writes to two systems into one write to one system. The event becomes a row in an outbox table, inserted in the same local transaction as the order. The database now guarantees 'both or neither'.

BEGIN;
INSERT INTO orders (id, total) VALUES (1, 100);
INSERT INTO outbox (event_id, routing_key, payload) VALUES (...);
COMMIT;

A separate loop, the relay, reads the pending rows, publishes each to the broker, waits for the confirmation and marks the row as sent. A crash only delays the event, it cannot lose it. But the relay can die after publishing and before marking the row, and then it publishes the same event again. So the outbox gives at-least-once delivery, not exactly-once. The consumer must therefore be idempotent (next sections).

The saga

A saga splits a business operation into local transactions, one per service, chained by messages. Each step really commits in its own database, so it cannot be undone with ROLLBACK. If a later step fails, compensating transactions run: new inverse business operations such as cancel, refund or put back in stock. They undo the effect by meaning and leave the history visible.

Choreography and orchestration

What a saga gives up: isolation

Compared with a 2PC transaction, a saga loses isolation for the operation as a whole. There is no global lock, so the effects of step 1 are visible before the saga ends, and someone may act on a state that will be compensated. The defences are design choices: show an explicit intermediate state such as PENDING (a semantic lock), reread before acting, and choose the order of the steps carefully.

Idempotency and exactly-once effects

You press the elevator button. Nothing seems to happen, so you press it again, and again. The elevator comes only once. Pressing the button many times has the same result as pressing it once. That is idempotency: an operation is idempotent if doing it once, twice or ten times leaves the system in the same state.

Why we need it: retries

On a network, when an answer does not arrive, you cannot know if the request was lost or if it worked and the reply was lost. The safe thing is to try again. That is only safe if the operation is idempotent. Even database recovery depends on it: redo and undo must be repeatable.

Delivery guarantees

The moment of the ack defines the guarantee. If the consumer acknowledges as soon as it receives and then crashes while processing, the message is gone (at-most-once). If it acknowledges after processing, a crash between processing and the ack causes redelivery (at-least-once).

Why exactly-once delivery is impossible in general

When the acknowledgement does not arrive, the sender cannot tell whether the message was lost or processed with the reply lost. Resending gives at-least-once. Not resending gives at-most-once. There is no third choice on an unreliable network. What is achievable is an exactly-once effect: at-least-once delivery combined with idempotent processing.

Two tools

Idempotency key on an API. The client generates a unique value, for example in the header Idempotency-Key, and sends the same one in every attempt of the same operation. The server stores the key together with the result. A repetition gets the stored result and the charge happens only once.

Deduplication in a consumer. The consumer stores the id of each message in a processed_messages table with a unique key, in the same local transaction as the effect. Then 'I processed it' and 'the effect happened' are one atomic decision.

INSERT INTO processed_messages (message_id) VALUES ($1)
ON CONFLICT (message_id) DO NOTHING;
-- 1 row inserted: first time, do the work
-- 0 rows: seen before, skip it and just ack

CAP theorem and consistency models

To be fast and safe from failures, big systems keep copies (replicas) of the data on several computers called nodes. Copies bring a new question: if I write on one node, when do the other nodes show the new value? The answer depends on the consistency model that the system offers.

The CAP theorem

The slogan 'pick two of three' is misleading. Network failures happen whether you like it or not, so you cannot give up partition tolerance in a real distributed system. The theorem says only this: while a partition lasts, you must choose between answering with possibly stale data (availability) or refusing requests (consistency).

   [Node 1] ---- X ---- [Node 3]
       \                  /
        \                /
         +---- [Node 2] -+

network partition: Node 3 is cut off

CP system: Node 3 (minority) answers with an error
AP system: all nodes answer, conflicts are fixed later

PACELC extends the idea: if there is a Partition, choose Availability or Consistency; Else (no partition), choose Latency or Consistency. Even on a good day, being more consistent costs waiting time.

Quorums: R + W > N

Take N copies. A write waits for W confirmations and a read asks R nodes. If R + W > N, any set of R nodes overlaps with any set of W nodes, so every read hears at least one node that has the latest confirmed write. If R + W is N or less, a read may hit only nodes that never saw the write.

Consistency models, from weak to strong

Read-your-writes is usually built by reading from the primary right after writing, or by reading only from replicas that already applied the position of your last write.

Linearizability against serializability

Putting it all together

Every tool in this summary exists to answer one question: 'what could go wrong, and who prevents it?'. Here is the map.

Common mistakes

• Believing that BEGIN ... COMMIT alone stops overselling. At READ COMMITTED a plain read reserves nothing.
• Believing READ UNCOMMITTED shows dirty reads in PostgreSQL. It behaves as READ COMMITTED.
• Ignoring error 40001 or 40P01. They mean 'retry the whole transaction'.
• Ignoring the number of rows affected in optimistic control.
• Using the global client instead of tx inside an ORM transaction.
• Publishing to a broker and committing to a database as two separate steps.
• Deduplicating messages with SELECT then INSERT and no unique key.
• Mixing up the C of ACID and the C of CAP.