books / ddia / ch-07SHEET 7 / 11 · REV ASIGN IN
MODULE 7 · DESIGNING DATA-INTENSIVE APPLICATIONS CH 7

Transactions Without Tears

Summon every classic concurrency anomaly against your own store on demand, then kill each one at the exact isolation level theory says it takes.

The idea

A transaction is a promise about groups of operations. A single write is easy; the trouble starts when a real change is several writes that only make sense together, like debiting one account and crediting another, and something intrudes in the middle. A crash, or another client reading halfway through. The database's answer is to wrap the group and promise all-or-nothing, plus some degree of not seeing each other's mess.

That second promise is isolation, and it is not a switch but a dial. Turn it down and concurrent transactions interfere in specific, repeatable ways. A dirty read returns money from a transfer that later aborted. Read skew reads one account before a transfer and the other after, so a total-balance query sees cash vanish. A lost update has two clients read a counter at 42, both add one, and both write 43. You will construct each of these by hand before you fix anything.

The elegant fix for the read anomalies is to stop overwriting data. Keep multiple versions of every key, stamped with the transaction that wrote them, and give each transaction a snapshot of which transactions had committed when it began. Every read is answered from that frozen world. This is MVCC, and it is literally how PostgreSQL, InnoDB and SQLite in WAL mode work.

Then comes the trap. Snapshot isolation fixes reading and still lets two transactions ruin each other by writing different keys based on the same read. Two doctors both check that two people are on call, both leave, and the ward is empty. That is write skew, and only serializability kills it. You will build serializability twice, pessimistically with locks and optimistically with conflict detection at commit, and measure which one wins under low and high contention instead of memorizing the answer.

The bench — 4 exercises

EX 01

Summon the Demons

Deliberately produce a dirty read, a lost update and a write skew against a store with no isolation, then implement read committed and watch exactly one of them die.

  1. Wrap your key-value store in a BEGIN/READ/WRITE/COMMIT/ABORT shim with no isolation at all, and give it a way to pause a transaction at a named point so you can schedule interleavings by hand instead of racing with sleeps.
  2. Script three interleavings: a reader that observes a value written by a transaction that later aborts, two clients that both read a counter before either writes, and two clients that each check an on-call roster of two and then remove themselves.
  3. Assert the damage, not the schedule: an aborted value was returned, the final counter is lower than the acknowledged increments, the roster ended empty.
  4. Implement read committed with short-lived per-key write locks and reads that always answer from the last committed version.
  5. Re-run all three scripts and record which anomalies survive.
hint

For the lost update, the key is two reads before either write. Pause both transactions after their reads, then release the writes in either order.

hint

If an anomaly refuses to fire, print what each transaction actually read - usually one side saw the other's value because you released steps in the wrong order.

DONE WHEN

· All three anomalies reproduce on the naive store, verified by observable damage

· Under read committed the dirty-read script cannot produce a dirty read across many replays

· Lost update and write skew still reproduce under read committed

EX 02

Frozen Worlds

Replace single-value storage with version chains and snapshot visibility, so every transaction reads one consistent instant of the database - and see for yourself that write skew survives it.

  1. Give every key a chain of versions tagged with created_by and deleted_by transaction ids; never overwrite in place.
  2. Assign monotonically increasing transaction ids and capture, at BEGIN, the set of transactions already committed - that is the snapshot.
  3. Implement the visibility rule: a version is visible if its creator committed before your snapshot and it is not deleted by anything visible to you; keep short write locks so exactly one writer to a key commits.
  4. Add a vacuum pass that drops versions no live snapshot can see, and run a long churn workload to prove live-version count stops growing.
  5. Run your anomaly scripts against SQLite in rollback-journal and WAL modes and note which anomalies fire compared with your engine.
hint

Check a transaction's own uncommitted writes before you consult the snapshot - the neat rule statement forgets that case and it causes half the weird bugs.

hint

If write skew stops firing under snapshot isolation, you are over-locking and have accidentally built something stronger.

DONE WHEN

· Dirty read and read skew are impossible: total balance is constant across many seeded transfer-and-read schedules

· The write-skew script still reproduces under snapshot isolation

· Two concurrent writers to one key result in exactly one commit

· Live version count stays bounded under a long churn workload with rotating snapshots

EX 03

The Unlosable Update

Kill lost updates without serializability, using the two industrial idioms: push the read-modify-write into the storage layer, or detect the interleaving and retry.

  1. Add INCR key delta, executed entirely inside the storage layer under the key's write lock.
  2. Add CAS key expected new, which writes only if the current committed value equals expected and otherwise fails cleanly.
  3. Rewrite the counter workload twice - once with INCR, once as a client-side read-then-CAS retry loop.
  4. Hammer both with 16 concurrent clients doing 1,000 increments each and check the final count.
  5. Record the CAS retry counts at low and high contention in your notes.
hint

CAS must compare against the latest committed version, not your snapshot - that is the whole reason it detects concurrent commits.

hint

If your CAS never fails under the hammer, you have rebuilt the lost update with extra steps.

DONE WHEN

· The counter ends at exactly 16,000 under both primitives

· A commit injected between a client's read and its CAS causes a clean failure and retry, never a silent overwrite

· Retry counts are recorded and visibly higher under high contention

EX 04

Serializable, Twice

Build serializability pessimistically and optimistically, prove the on-call ward can never empty under either, and turn the trade-off into your own throughput numbers.

  1. Build 2PL: shared locks on read, exclusive on write with upgrade, all held until commit or abort, plus a waits-for graph, cycle detection and a youngest-transaction victim abort with driver retries.
  2. Build SSI on top of your snapshots: record each transaction's read set including the range predicates behind queries like 'doctors on call', and abort at commit anyone whose reads were overwritten by a concurrent commit.
  3. Hammer the on-call workload under both engines, including a variant where a transaction inserts a new shift, and check the invariant holds in every committed outcome.
  4. Force a deadlock cycle and confirm 2PL detects it and aborts a victim rather than hanging; force a stale-read commit and confirm SSI aborts it.
  5. Run the same bank workload at low and high key overlap under both engines and write a five-line verdict naming the winner per regime in terms of blocking versus aborts.
hint

In 2PL, lock the predicate itself and not just the rows it returned, so an insert has to queue behind you - that is where phantoms die.

hint

Read locks that release before commit are not 2PL; if write skew still fires, that is almost certainly why.

hint

A brute-force permutation check over small sampled histories is enough to verify a history is equivalent to some serial order.

DONE WHEN

· At least one doctor remains on call in every committed outcome across hundreds of seeded schedules, including the insert variant

· Sampled committed histories check out as equivalent to some serial order

· A constructed deadlock is detected and resolved without livelock across retries

· Both benchmark runs complete and the verdict names a different winner for low versus high contention

Go deeper (after the bench)

Read DDIA chapter 7 alongside this, and re-read the "Write Skew and Phantoms" section after exercise 02 makes write skew survive your own MVCC - it reads completely differently once you have watched it happen in your engine. Then look at Hermitage (github.com/ept/hermitage), Kleppmann's free test suite that runs exactly these anomalies against Postgres, MySQL, Oracle and others and records which isolation level actually stops which one; your exercise 01 scripts are a hand-built version of it.