Serializability, snapshots, and write skew

Prerequisites: Transactions, read/write conflicts, and directed graphs.

Learning objectives

• Build a precedence graph for a schedule.
• Explain MVCC visibility and write skew.
• Choose a retry-safe serializable transaction boundary.

A transaction groups operations into one logical unit. Serial execution runs whole transactions one after another. A concurrent schedule is serializable when its effects satisfy the relevant equivalence to some serial execution. Serializability concerns the combined history, not whether each individual query returned a plausible result. Real-time ordering is a separate requirement addressed by stricter models.

For conflict serializability, make one graph vertex per transaction. Add an edge Ti→Tj when Ti performs an operation before Tj on the same item, at least one operation is a write, and the operations conflict. An acyclic graph admits a serial ordering. A cycle rules out conflict serializability. Read-read pairs create no edge because swapping them does not change the observed database state.

Trace two transactions on x and y. T1 reads x, T2 writes x, T2 reads y, and T1 writes y. The x conflict gives T1→T2; the y conflict gives T2→T1. The cycle exposes incompatible ordering requirements. This is an analysis tool for simple schedules, not a complete model of every multiversion implementation or application invariant.

Multi-version concurrency control retains multiple versions so readers can observe a snapshot while writers create newer versions. This can reduce reader-writer blocking. Snapshot isolation typically gives each transaction a consistent snapshot and prevents certain concurrent write conflicts, but transactions writing different rows can still violate a shared invariant. PostgreSQL's actual isolation-level behavior is documented precisely and should not be inferred from a generic product label.

Consider two on-call doctors, Ana and Bo, both initially available. Each transaction reads both rows and checks that at least two doctors are available before taking its own doctor off call. Both read the initial snapshot. T1 sets Ana unavailable; T2 sets Bo unavailable. They write different rows, so a snapshot system without additional serializability protection may commit both, leaving nobody available. No serial execution of those guarded transactions produces that outcome. This anomaly is write skew.

Possible remedies include serializable isolation with full-transaction retries, locking a shared guard row, or a constraint design that actually represents the invariant. Merely adding an index or a transaction wrapper does not establish the needed guarantee. Retrying must restart the reads and decision, not only resubmit the final write. External effects such as sending email need separate coordination because a database rollback cannot unsend them.

Write a concurrent test with a deliberate barrier after both reads. State the forbidden final state and the permitted abort behavior. Correctness may require rejecting and retrying one transaction; universal success under every schedule is not the goal.

Practice problem

Two transactions each read seats A and B as available. T1 reserves A only if B remains available; T2 reserves B only if A remains available. They run from the same snapshot and write separate rows. Trace the resulting invariant failure, then give a valid serial outcome. Design a test that exposes the race and explain what the client should retry if serializable isolation aborts one transaction.

Worked solution

Both transactions observe the other seat available, so T1 reserves A and T2 reserves B. The final state has no available seat, violating the intended invariant that at least one remain free. In a serial T1-then-T2 execution, T1 reserves A; T2 then sees A reserved and leaves B available. A test should start both transactions, pause each after its reads, release both writes, and assert that either one decision changes or one transaction aborts under the chosen protection. On serialization failure, the client reruns the entire transaction, including reads and the conditional decision. Retrying only the write repeats the stale decision and defeats the protection.

Check your understanding

Two snapshot transactions read that A and B are both available, then separately mark A and B unavailable. Which mechanism is insufficient by itself to preserve at least one available row?

• A correctly represented database constraint enforcing the invariant.
• Preventing simultaneous writes to the same row only.
• A common guard-row lock protecting the decision.
• Serializable execution with full retries when required.

Explanation

The write sets are disjoint, so same-row write-conflict detection alone does not prevent write skew.

T1 reads x before T2 writes x; T2 reads y before T1 writes y. What does the conflict graph show?

• A cycle T1→T2→T1, so the schedule is not conflict-serializable.
• No edges because reads never conflict with writes.
• Only T1→T2, so T1 must run first.
• Only T2→T1, so T2 must run first.

Explanation

Each read-write conflict imposes a different ordering, and the two requirements form a cycle.

Primary reading

• Transaction isolation: PostgreSQL Global Development Group
• Database Systems: lectures, notes, and projects: Carnegie Mellon University

Open the study and save your work →