Transaction Processing

A transaction is a group of database operations that the system treats as a single, indivisible unit: either all of it happens or none of it does.

13 frameworks, from 1975 to today · Databases · Computer Science

still a working view ended · each leads to its entry below

Overview

A transaction is a group of database operations that the system treats as a single, indivisible unit: either all of it happens or none of it does123. Transaction processing is the set of techniques that make this promise real when many users act at once, when machines crash mid-write, and when data is spread across many computers1. The stakes are concrete. If a bank debits one account and crashes before crediting another, money vanishes; if two people book the last airline seat simultaneously, one must be told no. Almost every idea in this history is an answer to one of those two problems — concurrency (keeping simultaneous users from corrupting each other's work) and recovery (surviving crashes) — and to the tension between correctness and speed1.

Files, Locks, and the First Commercial Systems (1950s–1960s)

Early business computing ran batch jobs on magnetic tape: records were processed in sequence, one job at a time, so concurrency barely existed. The move to disk drives and interactive terminals in the early 1960s changed that. Disk storage allowed random access, and time-sharing allowed many users to touch the same files. The first commercial systems to face this — IBM's airline reservation work and the Sabre system, developed with American Airlines and operational by 1960 — had to prevent two agents from selling the same seat.

The practical answer was locking: before changing a record, a program claimed it, and other programs waited. But locks brought their own hazards. If two programs each held one lock and waited for the other's, both froze — a deadlock1. Early systems also had no principled notion of what a "correct" interleaving of operations even was, so designers argued from intuition. The theoretical groundwork came from E. F. Codd's relational model (1970), which gave data a clean logical form, and from early work on concurrency in operating systems. What was missing was a definition of correctness that a system could enforce mechanically.

Serializability: Defining Correctness (1970s)

The key idea, developed in the mid-1970s, was serializability. A schedule — the interleaved order in which the system actually executes operations from several transactions — is serializable if its effect is identical to running the transactions one after another in some order1. Since nobody disputes that serial execution is correct, serializability gives a precise, checkable standard for concurrent execution.

Researchers including K. P. Eswaran, Jim Gray, Raymond Lorie, and Irving Traiger at IBM published the central paper in 1976, introducing the conflict-based theory: two operations conflict if they touch the same data item and at least one writes it, and a schedule is serializable exactly when the conflicts can be ordered consistently. The same era produced the two-phase locking (2PL) protocol, in which a transaction acquires all its locks before releasing any — a growing phase, then a shrinking phase. 2PL guarantees serializability, and it became the workhorse of commercial databases. Its cost is blocking and the ever-present risk of deadlock, which systems detect by watching for cycles in the "waits-for" graph and aborting a victim.

A competing family, timestamp ordering, avoided locks entirely: each transaction got a timestamp at start, and the system checked each operation against the timestamps of operations already done on that item, aborting transactions that arrived "too late." It never blocks, but it aborts more under contention. Both approaches, and the theory behind them, were synthesized in Philip Bernstein and Nathan Goodman's influential survey work at the end of the decade.

ACID, Recovery, and the System R Legacy (1970s–1980s)

Alongside concurrency came the vocabulary of guarantees. Theo Härder and Andreas Reuter's 1983 paper named the ACID properties — atomicity (all or nothing), consistency (transactions move the database between valid states), isolation (concurrent transactions don't see each other's partial work), and durability (committed work survives crashes)4. The acronym crystallized ideas already embodied in IBM's System R prototype (mid-1970s), the project that also produced SQL and demonstrated that a relational system with transactions could perform well.

Durability and atomicity demanded recovery. The dominant technique became write-ahead logging: before a changed page is written to disk, a record of the change goes to a sequential log. After a crash, the log is replayed5. The culmination was ARIES, published by C. Mohan and colleagues at IBM in 1992, which combined write-ahead logging, repeating history during recovery, and fuzzy checkpointing so that recovery could proceed correctly even while the system kept accepting new work. ARIES-style recovery remains the standard architecture in most major database engines.

Distributed systems added a second problem: a transaction spanning several machines must commit everywhere or nowhere6. Two-phase commit (2PC) solved it with a coordinator that first asks all participants to prepare (and promise they can commit), then tells them all to commit7. Its weakness is equally famous: if the coordinator dies after some participants have prepared, they may block indefinitely. 2PC became the standard for distributed transactions, and its fragility motivated decades of later work.

Isolation Levels and the Cost of Correctness (1980s–1990s)

Full serializability is expensive: locks block, and blocking hurts throughput18. In 1976 Gray and colleagues had already proposed weaker isolation levels — read uncommitted, read committed, repeatable read, serializable — trading some anomalies for speed. The SQL standard later codified them, though ambiguously. In 1995 Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil published "A Critique of ANSI SQL Isolation Levels," showing that the standard's definitions were inconsistent and that real systems offered guarantees the standard didn't name. Their paper introduced snapshot isolation, a scheme in which each transaction reads from a consistent snapshot of the database as of its start. Snapshot isolation prevents many anomalies and never blocks readers, but it permits write skew — two transactions each reading data the other modifies, producing a state no serial order could reach — so it is not fully serializable.

Snapshot isolation's practical appeal grew with multiversion concurrency control, which keeps older versions of records so readers can see a stable past without waiting910. The idea dates to the late 1970s, but it became mainstream in the 1990s and 2000s as storage cheapened and read-heavy workloads dominated. Optimistic concurrency control, proposed by H. T. Kung and John Robinson in 1981, took the opposite stance to locking: let transactions run freely, validate at commit time, and abort conflicts. It suits workloads with low contention and became influential in main-memory systems decades later.

Replication, BASE, and the NoSQL Turn (2000s)

As web companies scaled across data centers, the cost of distributed coordination became the central issue. Eric Brewer's CAP theorem (conjectured 2000, proved by Seth Gilbert and Nancy Lynch in 2002) stated that a distributed system facing a network partition must sacrifice either consistency or availability11. In practice, large internet systems chose availability, and the resulting style was labeled BASE — basically available, soft state, eventual consistency — by Armando Fox and Eric Brewer around 2008, as an explicit counterpoint to ACID. Eventual consistency means replicas may diverge temporarily but converge if updates stop12. Systems such as Amazon's Dynamo (2007) embraced it. The trade-off was real: applications now had to reason about stale reads and conflicting writes themselves12.

Determinism, NewSQL, and the Present (2010s–today)

The reaction arrived quickly. A wave of systems — VoltDB, founded by Michael Stonebraker and colleagues around 2008–2010, and Calvin, published by Daniel Abadi and colleagues in 2012 — pursued deterministic transaction execution: if every replica processes the same transactions in the same order, no locking or distributed commit protocol is needed at execution time. Ordering becomes the hard problem, solved by consensus protocols such as Paxos and Raft. Meanwhile, "NewSQL" systems like Google Spanner (2012) showed that globally distributed, externally consistent transactions were achievable at scale by using synchronized clocks and consensus, narrowing the gap CAP had seemed to force open.

Today the field is plural. Main-memory engines exploit cheap RAM to run optimistic and multiversion schemes at high speed; cloud databases offer snapshot isolation by default and serializable mode on request; deterministic and consensus-replicated designs underpin globally distributed services; and weaker consistency remains the pragmatic choice for many large-scale applications. The open questions are familiar in shape: how to give programmers strong guarantees without paying serializability's price, how to make distributed commit cheap and non-blocking, and how to specify isolation precisely enough that a user knows what they are actually getting.

References

  1. Transaction processing (introduction, Description, Deadlocks), Wikipedia
  2. Database transaction, Wikipedia
  3. Atomicity (database systems), Wikipedia
  4. ACID, Wikipedia
  5. Algorithms for Recovery and Isolation Exploiting Semantics, Wikipedia
  6. Distributed transaction, Wikipedia
  7. Two-phase commit protocol, Wikipedia
  8. Concurrency control, Wikipedia
  9. Snapshot isolation, Wikipedia
  10. Multiversion concurrency control, Wikipedia
  11. CAP theorem (introduction, History), Wikipedia
  12. Eventual consistency, Wikipedia

The frameworks of Transaction Processing

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1975-Present

    Two-Phase Locking

    How do locks make concurrent transactions serializable?

    Fly to its tower in Nousfarer

  2. 1976-Present

    Isolation

    What guarantees does a transaction get against other transactions?

    Fly to its tower in Nousfarer

  3. 1976-Present

    Serializability Theory

    When is a concurrent execution equivalent to a serial one?

    Fly to its tower in Nousfarer

  4. 1976-1995

    Timestamp-based concurrency control

    Can concurrency be controlled without locks?

    Fly to its tower in Nousfarer

  5. 1978-Present

    Multiversion Concurrency Control

    How can readers see a stable past without blocking writers?

    Fly to its tower in Nousfarer

  6. 1978-Present

    Two-phase commit protocol

    How can a transaction commit everywhere or nowhere?

    Fly to its tower in Nousfarer

  7. 1981-Present

    Optimistic Concurrency Control

    Can transactions run freely and be checked at commit?

    Fly to its tower in Nousfarer

  8. 1983-Present

    ACID

    What guarantees must a transaction system provide?

    Fly to its tower in Nousfarer

  9. 1992-Present

    Weak Isolation Levels

    Which anomalies can be traded for speed?

    Fly to its tower in Nousfarer

  10. 1992-Present

    Write-Ahead Logging and ARIES Recovery

    How does a system recover after a crash mid-write?

    Fly to its tower in Nousfarer

  11. 2000-Present

    CAP Theorem and BASE

    What must a distributed system give up under partition?

    Fly to its tower in Nousfarer

  12. 2000-Present

    Eventual consistency and BASE

    Can replicas diverge and still converge?

    Fly to its tower in Nousfarer

  13. 2008-Present

    Deterministic Transaction Execution

    Can ordering transactions in advance remove coordination?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Two-Phase LockingIsolationSerializability TheoryTimestamp-based concurrency controlMultiversion Concurrency ControlTwo-phase commit protocolOptimistic Concurrency ControlACIDWeak Isolation LevelsWrite-Ahead Logging and ARIES RecoveryCAP Theorem and BASEEventual consistency and BASEDeterministic Transaction Execution

Beyond the field

Where Transaction Processing's ideas came from in other fields, and what they led to there: the strongest 12 of 36 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Transaction Processing is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Transaction Processing

Related fields

Fields its ideas are linked to

More in Databases

See where Transaction Processing sits on the Map of Human Knowledge