Block D · Topics 18–23

Transactions

What happens when two users touch the same row at the same moment, and what survives when the power goes out mid-write. This block is where DBMS stops being about queries and starts being about guarantees.

ACID

atomicityconsistencyisolationdurability

Why transactions exist

A bank transfer is two statements — debit one account, credit another — and there is no acceptable outcome in which only one happens. A transaction is the mechanism for saying "these operations are one unit", and ACID names the four guarantees that makes worth relying on. The interview-grade answer says what each letter guarantees and how the database provides it.

Letter	Guarantees	Provided by	Costs
Atomicity	All operations happen, or none do. A failure mid-way leaves no trace.	The undo log — uncommitted changes can be rolled back	Logging overhead; long transactions hold log space
Consistency	The database moves from one valid state to another; constraints hold at commit.	Constraints, triggers, and the application's own invariants	Constraint checks on every write
Isolation	Concurrent transactions don't corrupt each other; ideally they behave as if run one at a time.	Locking (2PL) or multi-version concurrency control	Throughput, plus deadlocks and serialisation failures your app must retry
Durability	Once committed, it survives a crash — permanently.	The write-ahead log, forced to stable storage before commit returns	An fsync per commit — which is why commit rate is bounded by disk latency, not CPU

The nuance about "C"

Consistency is the odd one out, and saying so is a good sign. Atomicity, isolation and durability are properties the database implements. Consistency is largely a property you define — the database enforces the constraints you declared, but it has no idea that "total debits must equal total credits" unless you express it. Many people argue the C is there mostly to make the acronym pronounceable. Also worth distinguishing: the C in ACID is about integrity constraints, and the C in CAP is about replica agreement. Completely different things with the same name.

BEGIN;
  UPDATE accounts SET balance = balance - 100 WHERE id = 'alice';
  UPDATE accounts SET balance = balance + 100 WHERE id = 'bob';
  SAVEPOINT after_transfer;              -- partial rollback point
  INSERT INTO audit_log VALUES (...);
  -- ROLLBACK TO SAVEPOINT after_transfer;  -- undo just the insert
COMMIT;
-- If the process dies between the two UPDATEs, atomicity guarantees
-- neither is visible. If it dies immediately after COMMIT returns,
-- durability guarantees both are.

Schedules & serialisability

conflictsprecedence graphrecoverability

Why we need a formal test

"Isolation" needs a definition you can check. The standard is serialisability: a concurrent schedule is correct if it produces the same result as some order of running the transactions one after another. Note "some" — you don't have to match a particular order, just be equivalent to one.

Conflicting operations

Two operations conflict if they are from different transactions, on the same data item, and at least one is a write.

read–read → no conflict · read–write → conflict · write–read → conflict · write–write → conflict

Non-conflicting operations can be swapped freely without changing the outcome. That's the basis of the whole theory.

Testing with a precedence graph

Schedule S:   R1(A)  W2(A)  R2(B)  W1(B)

Draw a node per transaction. For each conflicting pair, draw an edge
from the transaction that acts FIRST to the one that acts SECOND:

  R1(A) then W2(A)  →  edge T1 → T2
  R2(B) then W1(B)  →  edge T2 → T1

  T1 ⇄ T2   ← a CYCLE

A cycle means NOT conflict-serialisable. No serial order can produce
this result, so the schedule is not correct under serialisability.

Contrast:   R1(A)  W1(A)  R2(A)  W2(A)
  edges all T1 → T2, no cycle → serialisable, equivalent to T1 then T2.

Conflict serialisability is a SUFFICIENT but not NECESSARY condition:
VIEW serialisability is a weaker, larger class that accepts some
schedules conflict-serialisability rejects — but testing it is
NP-complete, so real systems use the conflict test.

Recoverability — the other axis

Class	Property	Problem it avoids
Irrecoverable	T2 reads T1's uncommitted write and commits before T1	None — if T1 then aborts, you cannot undo T2's commit. Unacceptable.
Recoverable	T2 commits only after every transaction it read from has committed	Irrecoverable schedules
Cascadeless (ACA)	A transaction reads only committed data	Cascading rollback — one abort forcing a chain of others
Strict	No reading or writing of an uncommitted item	Makes recovery simple: undo just restores the before-image

The relationship: strict ⊂ cascadeless ⊂ recoverable. And strict 2PL produces strict schedules, which is exactly why it's the standard implementation — it gives serialisability and easy recovery together.

Concurrency control

2PLMVCCtimestamp orderingdeadlock

Two-phase locking

GROWING phase    acquire locks, never release
SHRINKING phase  release locks, never acquire
Once you release your first lock you may not acquire another. That single
rule is what guarantees serialisability.

Lock compatibility:        shared(S)   exclusive(X)
             shared(S)        ✓             ✗
          exclusive(X)        ✗             ✗

Variants:
  Basic 2PL     as above — serialisable, but allows cascading rollback
  Strict 2PL    hold all EXCLUSIVE locks until commit/abort
                → strict schedules, no cascading rollback. The standard.
  Rigorous 2PL  hold ALL locks (shared too) until commit — simpler, less concurrent
  Conservative  acquire every lock up front → deadlock-free, but poor
                utilisation and you must know your whole lock set in advance

Deadlock in a database

T1 locks row A and wants B; T2 locks B and wants A. Unlike an OS, a database can resolve this — it builds a wait-for graph, detects the cycle, and aborts a victim (usually the one with least work done), which the application must retry. That's why you see "deadlock detected, transaction rolled back" from Postgres but a permanent hang from a buggy multithreaded program: the database can roll back safely and the OS can't.

Prevention alternatives: wait-die and wound-wait, which use transaction timestamps so that only older-vs-younger orderings are allowed, making cycles impossible. Practical advice: access rows in a consistent order (e.g. always by ascending primary key) and keep transactions short — most application-level deadlocks come from two code paths locking the same two tables in opposite orders.

MVCC — how modern databases actually do it

The one-sentence version

Writers create new versions instead of overwriting, so readers never block writers and writers never block readers. Each transaction sees a consistent snapshot as of its start, without taking any read locks at all. That's the whole reason MVCC displaced pure locking for general-purpose databases — read-heavy workloads stop contending entirely.

Every row carries hidden version metadata:
   xmin  the transaction that created this version
   xmax  the transaction that deleted/superseded it (or null)

UPDATE = insert a new row version + mark the old one's xmax.
DELETE = just set xmax. Nothing is physically removed yet.

A transaction sees a version if:
   xmin is committed AND xmin ≤ my snapshot
   AND (xmax is null OR xmax > my snapshot OR xmax uncommitted)

Consequences you should be able to name:
· Readers take NO locks. A long analytical query cannot block writes.
· But writers still conflict with writers on the same row — MVCC does
  not remove write-write contention.
· Old versions accumulate as GARBAGE. Postgres needs VACUUM to reclaim
  them; without it you get TABLE BLOAT and, eventually, transaction-ID
  wraparound problems. MySQL keeps old versions in an undo log instead.
· A LONG-RUNNING TRANSACTION prevents cleanup of any version newer than
  its snapshot — which is why one forgotten open transaction can bloat
  a database. This is the single most common MVCC operational problem.

Approach	How	Best when
Pessimistic (2PL)	Lock before touching. Conflicts wait.	High contention — waiting beats repeatedly retrying
Optimistic (OCC)	Read, compute, then validate at commit; abort if something changed	Low contention — no locking overhead at all
MVCC	Snapshot reads, versioned writes	Read-heavy general-purpose workloads. What Postgres, MySQL/InnoDB and Oracle all do.
Timestamp ordering	Every transaction gets a timestamp; operations that would violate it are aborted	Mostly theoretical; the basis of some distributed schemes

-- Application-level optimistic concurrency, worth knowing verbatim:
UPDATE documents
   SET body = 'new', version = 8
 WHERE id = 42 AND version = 7;
-- 0 rows updated ⇒ someone else got there first ⇒ reload and retry.
-- No locks held across the user's thinking time. This is also exactly
-- what HTTP ETags + If-Match do at the API layer.

Isolation levels

dirty readphantomwrite skewSERIALIZABLE

Why there are dials

Full serialisability costs throughput, so the SQL standard defines weaker levels that permit specific anomalies in exchange for concurrency. The examinable content is the grid; the interview content is knowing which anomaly actually matters for your data.

The anomalies

Anomaly	What happens	Concrete example
Dirty read	You read another transaction's uncommitted write	You see a balance mid-transfer, then that transfer rolls back — you acted on data that never existed
Dirty write	You overwrite another transaction's uncommitted write	Two transactions interleave writes to two rows, leaving a mix of both
Non-repeatable read	You read the same row twice and get different values	A report totals a column, then re-reads it and the numbers don't reconcile
Phantom read	You re-run the same query and new rows appear	`COUNT(*) WHERE status='pending'` returns 5, then 6, within one transaction
Lost update	Two read-modify-writes, one silently overwrites the other	Two users each increment a counter from 5; the result is 6, not 7
Write skew	Two transactions each read a valid state and write different rows, jointly breaking an invariant	The on-call example below — the anomaly snapshot isolation cannot prevent

The grid

Level	Dirty read	Non-repeatable	Phantom	Write skew
Read uncommitted	Possible	Possible	Possible	Possible
Read committed (Postgres default)	Prevented	Possible	Possible	Possible
Repeatable read (MySQL default)	Prevented	Prevented	Possible (per the standard)	Possible
Snapshot isolation	Prevented	Prevented	Prevented	Possible
Serializable	Prevented	Prevented	Prevented	Prevented

The implementation caveats that matter more than the grid

Postgres has no "read uncommitted". Asking for it silently gives you read committed, because MVCC makes dirty reads impossible by construction.
MySQL's "repeatable read" prevents phantoms in practice, via gap locks — stronger than the standard requires. So the same level name behaves differently in the two databases.
Postgres's "repeatable read" is really snapshot isolation, so it prevents phantoms but still allows write skew.
Postgres's SERIALIZABLE uses SSI (serialisable snapshot isolation) — it doesn't lock reads, it detects dangerous dependency patterns and aborts one transaction. So the cost isn't blocking, it's serialisation failures your application must catch and retry. If you choose SERIALIZABLE, retry logic is not optional.

Write skew — the one to be able to demonstrate

Invariant: at least one doctor must be on call at all times.
Currently Alice and Bob are both on call.

  T1 (Alice)                          T2 (Bob)
  BEGIN                               BEGIN
  SELECT count(*) FROM doctors
    WHERE on_call = true;  → 2
                                      SELECT count(*) FROM doctors
                                        WHERE on_call = true;  → 2
  -- 2 > 1, safe to go off call       -- 2 > 1, safe to go off call
  UPDATE doctors SET on_call=false
    WHERE name='alice';
                                      UPDATE doctors SET on_call=false
                                        WHERE name='bob';
  COMMIT                              COMMIT

→ nobody is on call. The invariant is broken.

Why snapshot isolation misses it:
· neither transaction read stale data — both snapshots were valid
· they wrote DIFFERENT rows, so there is no write-write conflict to detect
· each transaction alone is perfectly correct
The problem is the PREMISE each relied on was invalidated by the other.

Three fixes:
1. SERIALIZABLE — SSI detects the read-write dependency and aborts one.
2. Materialise the conflict: SELECT ... FOR UPDATE on the rows the
   decision depends on, forcing a real lock and serialising them.
3. Express the invariant as a database constraint the engine can enforce
   (harder for aggregate invariants — sometimes a summary row you lock).

Lost update, and how to prevent it

The everyday version of this problem. SELECT balance → application computes balance - 100 → UPDATE SET balance = 400. Two concurrent runs and one increment vanishes.

Three fixes, in order of preference: (1) do the arithmetic in the database — UPDATE … SET balance = balance - 100 — which is atomic and needs no extra machinery; (2) SELECT … FOR UPDATE to take an explicit row lock across the read-modify-write; (3) optimistic concurrency with a version column and a retry. Naming the first one shows you'd avoid the problem rather than manage it.

Say this

"I'd pick the level per operation rather than globally. Read committed for most reads — it's the Postgres default and prevents dirty reads, which is enough for a listing page. For a read-modify-write on money I wouldn't rely on isolation at all: I'd do the arithmetic in the UPDATE statement so it's atomic, or take FOR UPDATE. And I'd reserve SERIALIZABLE for genuine multi-row invariants — like 'at least one doctor on call' — where write skew is possible, remembering that in Postgres that means handling serialisation failures with retries rather than just accepting slower queries."

Recovery

WALcheckpointsARIESredo/undo

The core problem

A commit must be durable, but writing every modified page to its final location on every commit would mean scattered random I/O — far too slow. The write-ahead log resolves the tension: write a small sequential record of what you're about to do, and you can defer the actual page writes.

The WAL rule: the log record describing a change must reach stable storage before the changed data page does. And a commit returns only once the log up to that commit record is flushed.

Sequential log write ≈ one fsync (~1 ms on SSD).
Random page writes ≈ many I/Os, done later, in batches, coalesced.

That's why commit throughput is bounded by fsync latency — and why group commit (batching several transactions' commits into one fsync) is such an effective optimisation.

Log records and the two operations

A log record identifies the transaction, the page, and both images:
   <LSN, txn_id, page_id, BEFORE-image, AFTER-image>

   AFTER-image  → enables REDO  (reapply a committed change)
   BEFORE-image → enables UNDO  (roll back an uncommitted one)

Each page stores the LSN of the last log record applied to it, so
recovery can tell whether a change is already reflected on the page —
which is what makes redo idempotent and safe to repeat.

Checkpoints

Without checkpoints, recovery would have to replay the log from the beginning of time. A checkpoint records a known point and flushes dirty pages, so recovery only needs to start from the last one. The tradeoff is direct and worth stating: frequent checkpoints mean fast recovery and more steady I/O; infrequent checkpoints mean less I/O during normal running and a longer recovery. That's the RTO dial.

ARIES — the three phases

Crash. On restart:

1. ANALYSIS   Scan forward from the last checkpoint. Determine which
              transactions were in flight (the "losers") and which pages
              were dirty.

2. REDO       Scan forward and repeat history — reapply EVERY
              change, including those of transactions that will be
              undone. Sounds wasteful; it restores the exact state at
              the moment of the crash, which makes undo straightforward.
              Skipped per page where page.LSN ≥ record.LSN.

3. UNDO       Scan backward, rolling back the losers using before-images.
              Compensation log records (CLRs) are written for the undo
              work itself, so a crash DURING recovery doesn't undo
              things twice.

Two policies that determine what recovery must do:
  STEAL / NO-STEAL     may an uncommitted page be written to disk?
                       STEAL → yes → UNDO is required
  FORCE / NO-FORCE     must all pages be written at commit?
                       NO-FORCE → no → REDO is required
Real systems are STEAL + NO-FORCE — the most flexible for buffer
management, and therefore the one needing both redo and undo. That is
exactly why ARIES has both phases.

What the WAL gets you beyond crash recovery

Three things, and mentioning them shows operational awareness. Point-in-time recovery: restore a base backup and replay the WAL to any moment — which is how you recover from a bad migration at 14:32. Replication: stream the WAL to a replica and it applies the same changes; this is how physical streaming replication works. Change data capture: read the WAL to feed search indexes, caches and event streams (Debezium). The recovery log turns out to be the most useful integration point in the database.

Beyond one node

replication2PCshardingNoSQLCAP

Where DBMS meets system design

Everything above assumes one machine. The moment you add a second, you inherit a new set of problems — and this topic is the bridge to the system design data block, which covers them in depth.

Replication, briefly

One leader takes writes and streams its WAL to followers. Synchronous replication means a commit waits for a replica to acknowledge — no data loss on failover, higher write latency, and a stalled replica stalls writes. Asynchronous is fast but has a non-zero RPO: a leader failure loses whatever hadn't shipped. Semi-synchronous — wait for at least one replica — is usually the right default. The application-visible consequence is replication lag: read your own write from a follower and it may not be there yet, so route a user's reads to the leader briefly after they write.

Distributed transactions: 2PC

PHASE 1 — prepare
  coordinator → all participants: "can you commit?"
  each participant does the work, writes it durably, and replies
  YES (and is now BOUND — it must be able to commit if asked) or NO

PHASE 2 — commit
  all YES → coordinator writes its commit decision, then tells everyone
            to commit
  any NO  → tells everyone to abort

The fatal flaw: if the coordinator crashes after participants voted YES
but before delivering the decision, participants are blocked —
holding locks, unable to commit or abort, because only the coordinator
knows the outcome. This is why 2PC is avoided in high-throughput systems:
it converts one node's failure into everyone's outage.

Practical alternatives: keep the transaction inside one shard by
choosing the partition key well; or use a SAGA — a sequence of local
transactions with compensating actions — accepting that intermediate
states are visible. See the system design payments topic.

Sharding, and what it costs

Partition rows across nodes by a shard key to scale writes past one machine. What you lose is significant and worth listing: joins across shards (do them in the application or denormalise), transactions across shards (2PC or sagas), global unique constraints, global ordering, and cheap aggregates — COUNT(*) becomes a scatter-gather whose latency is the slowest shard's. Choose a key that is high-cardinality, evenly accessed, and present in your hot queries — that last one is what people get wrong.

SQL vs NoSQL, honestly

	Relational	NoSQL (varies by type)
Schema	Fixed, enforced by the database	Flexible — the constraint moves into application code, where it's enforced less reliably
Queries	Ad-hoc, joins, an optimiser	Designed around known access patterns; ad-hoc queries are expensive or impossible
Transactions	Multi-row ACID	Often single-document/single-partition only
Scaling	Vertical, then sharding (real work)	Horizontal by design
Consistency	Strong	Frequently tunable, often eventual by default

The answer that scores

"Start with Postgres unless something specific rules it out. A single primary handles tens of thousands of writes a second, which is past most estimates, and transactions plus joins plus ad-hoc queries are enormously valuable while the access patterns are still moving. Move to a distributed store for a named reason — write volume beyond one node, or a purely key-based access pattern at massive scale — and move one table, not the whole system." Reaching for Cassandra at 300 writes/second is the classic over-engineering flag.

And be precise about CAP: during a network partition you choose between consistency and availability. You don't choose P — networks partition regardless. A system described as "CA" is a single node.

One term to get right

BASE (Basically Available, Soft state, Eventually consistent) is offered as the counterpart to ACID. It's a useful label but not a formal guarantee — it describes what you get when you give up ACID's isolation and immediate consistency in exchange for availability and partition tolerance. Don't present it as an equally rigorous alternative; present it as a different point on the tradeoff curve.