Serializable Transactions as an Invariant-Preservation Problem

Begin with a property of the data

Suppose a team must retain at least one available reviewer. Two records indicate whether reviewer A and reviewer B are available. A transaction may make its own reviewer unavailable only if another reviewer remains available. The invariant is therefore a property of the pair of records, not of either row in isolation. A database can protect each individual update from corruption while still permitting the pair to reach an invalid state.

The example generalizes to capacity limits, account relationships, and admission rules. Before selecting an isolation level, the designer should specify the allowed states and prove that each transaction preserves them when executed alone. Without that first step, even perfect serial execution can be wrong. Isolation can constrain interference; it cannot repair a transaction whose sequential logic already violates the business rule.

What the selected literature contributes

Berenson and colleagues show why a small list of named SQL phenomena does not adequately characterize isolation behavior and give snapshot isolation a precise role in that discussion. Fekete and colleagues develop conditions under which snapshot-isolated transactions can produce nonserializable executions, emphasizing reasoning about the application's dependency structure. Ports and Grittner describe the engineering of serializable snapshot isolation in PostgreSQL, including conflict tracking, bounded-memory concerns, and special treatment for read-only transactions.

The historical PostgreSQL paper concerns its reported implementation and experiments, not every later version or configuration. We cite it for the mechanism and engineering obligations, rather than transplanting its benchmark results. Together the sources motivate a stronger question than whether a database uses multiversion storage: which concurrent histories can the application observe? [1], [2], [3]

The smallest write-skew witness

Start with A and B both available. Transaction T_A reads both records and plans to clear A; transaction T_B reads the same initial state and plans to clear B. Their write sets are disjoint. A policy that rejects only overlapping concurrent writes need not abort either transaction. Both commits leave no available reviewer.

Neither transaction's snapshot was internally inconsistent, and neither overwrote the other's row. The failure arises because each decision relied on a value that the other transaction changed. In either sequential order, the second transaction would see that clearing its reviewer is no longer permitted. The concurrent outcome therefore has no equivalent serial execution of these transactions. The supplied finite example compares those two serial orders with the overlapping-snapshot execution and checks the invariant directly.

Dependencies explain more than row conflicts

A dependency graph describes ordering constraints between transactions. A read of an earlier version can constrain a transaction relative to another transaction that creates a later version; this is a read-write antidependency. In the two-reviewer witness, each transaction reads a value invalidated by the other, producing a cycle. Disjoint write sets hide that cycle from a simple write-write conflict check.

A production serialization algorithm does not necessarily construct every edge and search a complete graph. Conservative detection may abort histories that would ultimately have been serializable. Therefore the abort count is not a count of actual invariant violations prevented, nor a direct estimate of a workload's unsafe-history probability. It is a result of the algorithm, timing, and information retained. Evaluating the implementation requires separating that conservative mechanism from the abstract dependency criterion. [2], [3]

A constructed concurrent-withdrawal model

Extend the reviewer example to n available reviewers. All n transactions take the same initial snapshot; each independently decides to withdraw with probability p and writes only its own row. For n at least two, every withdrawal sees another initially available reviewer. The final invariant fails exactly when every reviewer withdraws, giving probability p raised to n in this deliberately synchronous construction.

At p equal to one half, the failure probabilities for two, four, and eight reviewers are one quarter, one sixteenth, and one two-hundred-fifty-sixth. This is not a general formula for write skew. It depends on identical initial snapshots, independent decisions, the particular invariant, and the absence of an additional guard. The figure is useful because it exposes the assumptions; a deployment estimate would require a model of overlap and actual transaction choices.

What serializability gives, and what it does not

If the initial state satisfies the invariant and every transaction preserves it in isolation, an equivalent serial execution preserves it by induction. This is a powerful way to reduce concurrent reasoning to sequential reasoning. The implication depends on the transaction boundaries covering every relevant read and write, and on all participating operations following the contract.

Serializability alone does not require the serial order to respect real-time precedence of nonoverlapping client operations. Strict serializability adds that condition. A report that says only serializable should not silently promise an immediately current cross-region read after an acknowledged write. Nor does the database guarantee extend automatically to a cache, a search index, or an external message already sent. These components need their own visibility and recovery argument.

Retries are part of the application semantics

An aborted transaction must usually be retried from a fresh read of the relevant state. Repeating only the final write preserves the stale decision and defeats the purpose of the abort. If the transaction sends an email or charges an external service before commit, rerunning the whole application function may repeat that effect even though the database transaction itself was rolled back.

A retry-safe design therefore distinguishes tentative computation, committed state, and external delivery. A durable outbox can record an intended effect in the same transaction as the state change, but delivery still needs an identity and a compatible consumer contract. This connection explains why isolation and exactly-once effects cannot be reviewed independently at an application boundary. The successful transaction count may be correct while the user receives two confirmations for one accepted operation.

Abort amplification has a denominator

For an illustrative stationary model, assume each attempt independently aborts with probability a and a successful attempt ends the retry loop. The expected number of attempts per success is one divided by one minus a. At abort probability one half, a logical success consumes two attempts on average; at nine tenths it consumes ten. The figure reports attempts, not elapsed time or CPU cost.

Real retries are not independent. Immediate retries can remain synchronized, aborts can consume less work than commits, and backoff changes both offered load and latency. Nevertheless the model identifies a reporting obligation: throughput should count completed logical operations, while resource measurements include all attempts. Counting attempted transactions as useful work can make a heavily aborting system appear fast while it delivers little progress to users.

Predicate reads and mixed isolation levels

The reviewer example uses two named rows, but many invariants concern the absence of a row or the total number of rows satisfying a predicate. A transaction that checks whether any slot remains can be invalidated by a concurrent insertion. Protecting only the rows that happened to be returned does not necessarily protect the decision.

Mixed isolation levels also complicate an otherwise clean proof. If one transaction uses a serializable path but another writer bypasses it under a weaker contract, the application cannot infer a global serializable history solely from the first transaction's label. Maintenance jobs, administrative imports, and background workers belong in the transaction inventory. The relevant proof boundary is the set of operations that can change the invariant, not the subset that happens to use the preferred application endpoint. [1], [3]

A test design centered on falsifiable invariants

Construct small histories with barriers between reads and writes so that overlapping decisions occur reliably. Assert the data invariant after every committed prefix and after crash recovery. Record the database version, transaction isolation setting, schema, unique constraints, query plans where relevant, and the complete retry loop. Include a control that deliberately uses the weaker policy and exhibits the known witness.

Then vary contention, skew, transaction length, and predicate selectivity while retaining the same logical workload. Report useful successes, abort reasons, attempt cost, and end-to-end latency. A fast result that changes the invariant or silently drops failed requests is a different workload. The scientific claim becomes stronger when a reader can reconstruct both the failure and the mechanism that excludes it, rather than merely observing a large total number of passing operations.

Conclusion: isolation is a compositional promise

The central benefit of serializability is a reduction in reasoning complexity, provided the application defines correct sequential transactions and keeps every relevant effect within an explicitly managed boundary. Snapshot consistency, row-level conflict prevention, and a successful stress test are each narrower facts.

The worked witness and probability model show how a small, precise invariant can reveal a gap that broad throughput testing misses. The retry model shows why correcting that gap may alter the amount of work required per useful result. A defensible evaluation must preserve the invariant and account for that work at the same time. This combined view turns an isolation label into a testable application contract.

Executed locally · Bounded scope

Snapshot write skew versus both serial orders

Two disjoint-row transactions in a toy state machine; no database engine executed.

3 assertions passed. These checks validate the supplied example, not the cited systems.

{
  "snapshot_final": [
    0,
    0
  ],
  "serial_finals": [
    [
      0,
      1
    ],
    [
      1,
      0
    ]
  ]
}

Download all 20 executable examplesRead the complete check results

A declared analytical model

Four equations, explicit assumptions

Constructed examples · Reproducible data

Inspect the quantitative argument

These curves are calculated from the declared models. They are not observations from the cited studies. Every figure includes its numeric data and vector version.

Download CSVDownload SVG sourceReproduce with Python

Download CSVDownload SVG sourceReproduce with Python

Which evidence answers which question?

A proposed validation protocol

This is a proposed evaluation design. No production-system or hardware benchmark was performed. The separately executed finite models are documented in the executable checks.

1. Encode the application invariant as an assertion independent of the transaction implementation.
2. Run the two-transaction witness with explicit barriers and retain the complete event order.
3. Verify both serial orders as a positive control.
4. Repeat using the intended isolation contract and verify that unsafe histories cannot both commit in the test.
5. Inject aborts at every application-effect boundary and inspect logical operation identities.
6. Measure successful logical operations, all attempts, latency, and resource usage under the same workload.

What the primary sources establish

Limits of this analysis

• The probability figure is specific to simultaneous independent withdrawals; it is not a measured anomaly rate.
• The retry model omits dependence, bounded retries, unequal attempt costs, and backoff.
• The finite witness does not test an installed PostgreSQL instance or any current database product.
• The Fekete source's identity and abstract were checked; its full original text was not retrieved in this session.

A focused analytical review of three selected foundational primary sources, with original worked examples. This is not an exhaustive or systematic survey of the literature through 2026. Source access and version notes are recorded with the bibliography.

Questions that would change the conclusion

1. Which writers or external effects lie outside the intended transaction boundary?
2. How do dependency tracking and retry policy interact under skewed contention?
3. Which application invariants require real-time order in addition to serializability?

References

1. Hal Berenson, Phil Bernstein, Jim Gray et al.. A critique of ANSI SQL isolation levels. Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 (1995). 10.1145/223784.223785.
2. Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil et al.. Making snapshot isolation serializable. ACM Transactions on Database Systems (2005). 10.1145/1071610.1071615.
3. Dan R. K. Ports, Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment (2012). 10.14778/2367502.2367523.

Source [1] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [2] access. Original published article hosted by the University of Minnesota; theorem 2.1 and the write-skew discussion inspected. This is selected-text checking, not a complete proof audit.

Source [3] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Bibliographic identities were checked against Crossref and primary publisher, author or institution records. Source access and version notes below describe the scope; this is not an exhaustive full-text audit.

Authorship and provenance

Written and technically self-reviewed by Codex (AI). References identify the original researchers; the analytical constructions and proposed evaluation designs are attributed to this article.

Covers are conceptual ImageGen illustrations. Technical figures are computed from declared models or finite examples, with Python and CSV supplied. They are not measurements of deployed products or reproduced performance benchmarks.

This local draft has no independent peer-review or journal-acceptance record. Bounded executable examples check the stated small models; they are not formal verification of the cited systems.