Concurrency Control

Overview

Concurrency control determines permitted orders and outcomes when overlapping operations read and modify shared state. This covers parallel execution on multiple CPUs and situations where one operation proceeds while another waits for input or output.

Editors A and B read the same article. A changes and saves it first; if B later saves an edit based on the original, A's changes disappear. Database stock counts and reservations raise similar problems. Each operation can follow a sound procedure while their interleaving violates a shared rule.

The problem requires defining a unit of work, the data it shares, and the outcomes considered correct. An atomic update to a variable, a version check on a row, and serializability across a transaction protect different scopes.

This article focuses on database concurrency control and the relationship among locking, optimistic validation, and multiple versions. Operating-system mutexes and language-level atomic operations also coordinate shared state, but their boundaries and failure models differ from database transactions.

Timeline

• 1976: Eswaran, Gray, Lorie, and Traiger defined transactions, consistency, and schedules and analyzed their relationship with two-phase locking. Their paper also distinguished physical records from predicate-defined data sets.¹

• 1981: Kung and Robinson proposed optimistic methods that let work proceed before checking conflicts in On Optimistic Methods for Concurrency Control.²

• 1983: Philip A. Bernstein and Nathan Goodman's Multiversion Concurrency Control—Theory and Algorithms explained correctness of multiversion schedules and examined algorithms. It consolidated a theory for versioned execution; it does not establish the first invention date of MVCC.³

• 1995: Berenson and colleagues analyzed SQL isolation definitions and snapshot isolation, including write skew, in A Critique of ANSI SQL Isolation Levels.⁴

• January 1997: HTTP/1.1's RFC 2068 defined If-Match and explained using entity tags to avoid modifying an outdated resource after retrieval.⁵

• 2022: RFC 9110 specified the semantics of the If-Match condition.⁶

Lock protocols and protection targets (1976)

The multiuser database considered in Eswaran, Gray, Lorie, and Traiger's 1976 paper must account for interleaved reads and writes. Preserving integrity requires rules for acquiring and releasing locks as well as choosing what to lock. Under two-phase locking, a transaction acquires no new locks after it starts releasing them.¹

Reservations illustrate the paper's distinction between physical records and predicate-defined sets. Existing reservation rows and reservations that might satisfy a date condition are different protection targets. The logical scope of a constraint determines what concurrency control must protect.

Optimistic validation (1981)

In Kung and Robinson's 1981 optimistic methods, transactions pass through read, validation, and write phases. Relationships among read and write sets determine acceptable execution. Rare conflicts can leave room to reduce waiting, while failed validation discards the attempted work. Optimism describes proceeding until validation on the assumption that conflicts will be uncommon.²

A web editor's version check applies the idea to one row. The row is updated only when its version still matches the observed value, protecting a narrower scope than the paper's full transaction-validation algorithm.

A theory for multiple versions (1983)

Bernstein and Goodman's 1983 paper explains correctness for multiversion schedules and analyzes new and previously published algorithms within one theory. Retaining earlier versions changes waiting relationships between readers and writers. Which version to read and which execution to reject remain separate rules, so version storage and serializability conditions must be distinguished.³

Modern products combine methods. An MVCC database can lock conflicting writes, and an application's optimistic check can run alongside internal database write locks.

Snapshot isolation and write skew (1995)

Write skew, analyzed by Berenson and colleagues in 1995, shows where snapshot isolation and serializability diverge. Transactions can read the same snapshot, modify different rows, and jointly violate a constraint.⁴

Preventing a row-level lost update differs from preserving a rule across rows. Individual version checks can pass while a condition read across those rows no longer holds. The central question is which combined effects must match a serial execution, beyond the names locking, validation, or versioning.

HTTP conditional requests (1997–2022)

RFC 2068 defined HTTP/1.1 conditional requests in 1997, and RFC 9110 specified their semantics again in 2022. Database concurrency theory and HTTP preconditions address writes based on outdated observations at different layers. When a request includes If-Match, the server must carry that condition through to persistence.⁶

An editor can check versions when saving instead of holding a database lock throughout human editing. Waiting, reloading, or asking the user to merge after a conflict remains an application decision.

PostgreSQL row locks and the remaining protection scope

PostgreSQL's SELECT ... FOR UPDATE coordinates conflicting changes to selected rows and normally retains those locks until transaction end. These row locks leave ordinary SELECT queries unblocked while making operations that update, delete, or lock the same rows wait. Transactions waiting for one another's locks can deadlock.⁷

A query finding no reservation row has no reservation row to lock. A unique constraint, a lock on a representative resource row, or suitable isolation rules must express the actual business condition. PostgreSQL offers different isolation levels over MVCC.⁸⁷⁹

Lock protocols, optimistic validation, multiversion theory, and HTTP preconditions connect observations with changes to shared state. Identifying the protected scope is the basis for reading each contract.

A row-version condition example

This PostgreSQL example includes the observed-version condition in the write statement. Two updates in a fixed order demonstrate rejection of an outdated edit.

CREATE TEMP TABLE posts (
  id integer PRIMARY KEY,
  body text NOT NULL,
  version bigint NOT NULL
);
INSERT INTO posts VALUES (1, 'original', 0);

UPDATE posts
SET body = 'edited by A', version = version + 1
WHERE id = 1 AND version = 0
RETURNING body, version;

UPDATE posts
SET body = 'edited by B', version = version + 1
WHERE id = 1 AND version = 0
RETURNING body, version;

SELECT body, version FROM posts WHERE id = 1;

The first update returns edited by A, 1; the second returns zero rows, leaving A's content. Under the default isolation level, READ COMMITTED, overlapping updates also cause the second update to re-evaluate its WHERE condition against the changed row and return zero rows. Callers must distinguish zero rows from a successful change. Under REPEATABLE READ or higher, overlapping updates can instead raise a serialization error. This example checks only one row's version.