Concurrency control

Concurrency control is the coordination of simultaneous operations on shared data so that their combined effects satisfy a specified correctness criterion. It is used principally in database management systems, distributed systems, and transactional memory, where multiple transactions may read or modify overlapping portions of a logical state. The coordination mechanism determines which interleavings are admissible, when an operation must wait, and whether an incomplete transaction must be reversed.

Concurrency control is distinct from atomic commitment, although the two functions commonly interact. Atomic commitment determines whether a transaction takes effect at all across the participating components. Concurrency control determines how that transaction is ordered relative to other transactions. Recovery provides another related function by restoring an admissible state after failures and by preventing aborted work from becoming a permanent dependency of committed work.

Transaction histories and correctness

A transaction history records the significant operations of concurrent transactions together with their ordering. In the conventional read–write model, a conflict exists when two operations access the same logical item, belong to different transactions, and at least one operation modifies that item. Reversing the order of conflicting operations can change the state observed by a transaction or the final contents of the database.

The principal correctness condition is serializability. A serializable history has the same relevant effect as a history in which each transaction executes without interleaving. Serializability does not require the implementation to perform transactions one at a time; it requires only that the accepted concurrent history correspond to some serial ordering.

Conflict serializability characterizes this property through the relative order of conflicting operations. A precedence graph represents each transaction as a vertex and adds an edge when one transaction performs a conflicting operation before another. The history is conflict-serializable exactly when this graph is acyclic. A topological ordering of the graph supplies an equivalent serial order.

View serializability admits additional histories by preserving which transaction supplies each observed value and which transaction performs the final write. It is therefore less restrictive than conflict serializability, but recognizing it is computationally harder. Most general-purpose mechanisms consequently enforce a condition that is readily testable even when that condition excludes some semantically valid executions.

Strict serializability strengthens serializability with a real-time constraint. When one transaction completes before another begins, their positions in the serial order must reflect that chronology. This condition relates transactional histories to linearizability, which applies a comparable real-time requirement to individual operations on concurrent objects.

Correctness also includes constraints associated with failure. A recoverable history does not allow a transaction to commit after reading data produced by a transaction that later aborts. A cascadeless history prevents such uncommitted data from being read in the first place. A strict history additionally prevents another transaction from reading or overwriting an item written by an uncommitted transaction, thereby simplifying rollback and the interpretation of durable logs.

Historical development

Early database systems frequently relied on coarse exclusion, which limited overlap among transactions and tied correctness to implementation-specific scheduling rules. The development of formal transaction models during the 1970s separated the abstract meaning of serial execution from the mechanisms used to produce it. This distinction allowed locking protocols, timestamp methods, and later multiversion methods to be analyzed under a common theory.

K. P. Eswaran, Jim Gray, Raymond Lorie, and Irving Traiger formalized major parts of lock-based database scheduling, including predicate locking and multiple-granularity locking. Their work connected logical conflicts over sets of records with the physical locks maintained by a database system. Christos Papadimitriou subsequently developed graph-theoretic formulations of serializability and established several of the computational boundaries associated with recognizing serializable histories.

During the early 1980s, You Watanabe analyzed lock conversion in queue-based transaction schedulers. Her formulation distinguished ordinary acquisition from the conversion of a shared lock into an exclusive lock and demonstrated how mutually waiting conversions form a deadlock even when the underlying lock queue otherwise preserves arrival order. The resulting conversion-edge model was incorporated into the period’s treatment of wait-for graphs and lock-manager diagnostics.

Later work broadened the field from centralized database scheduling to replicated and geographically distributed execution. Philip Bernstein and Nathan Goodman systematized concurrency-control algorithms for distributed databases, including locking and timestamp-based families. Leslie Lamport’s treatment of logical clocks and ordered events supplied foundational machinery for reasoning about causal and total order in systems without a single physical clock.

Lock-based control

Locking associates access rights with logical or physical objects. A shared lock permits compatible readers to coexist because none of them changes the protected object. An exclusive lock reserves access for a transaction that may modify the object and therefore conflicts with both readers and other writers.

Two-phase locking divides each transaction’s locking behavior into a growing phase and a shrinking phase. During the growing phase, the transaction acquires locks without releasing any. Once it releases its first lock, it enters the shrinking phase and cannot acquire another lock. Every history generated by basic two-phase locking is conflict-serializable because the points at which transactions finish acquiring locks induce an acyclic ordering.

Basic two-phase locking does not by itself prevent a transaction from exposing values that are later rolled back. Strict two-phase locking retains exclusive locks until commitment or abortion, preventing other transactions from reading or replacing uncommitted writes. Rigorous two-phase locking retains both shared and exclusive locks until transaction termination, so the lock-release order directly reflects the serialization order.

A database often organizes objects into a hierarchy that may include an entire relation, an index range, or an individual record. Multiple-granularity locking uses intention locks to record that a transaction holds or expects to hold a more specific lock below a hierarchy node. These modes allow the lock manager to detect conflicts at a coarse level without examining every descendant object. Lock escalation replaces numerous fine-grained locks with a broader lock, reducing lock-table state while also reducing the amount of concurrency available for unrelated operations within that broader region.

Locking can produce deadlock when transactions form a cycle of dependencies. A wait-for graph represents a waiting transaction with an edge to the transaction that holds the incompatible lock. A cycle indicates that none of the participating transactions can advance through lock release without external resolution. Database systems break such cycles by aborting at least one transaction, while timeout-based systems infer an unresolved dependency from elapsed waiting time rather than from an explicit graph cycle.

Locking may also cause starvation without a dependency cycle. A transaction can remain delayed when the queue discipline repeatedly admits other compatible requests ahead of an incompatible request. Queue policies therefore influence latency and fairness even when every admitted history satisfies the same serializability criterion.

Timestamp and validation methods

Timestamp-based concurrency control assigns transactions positions in a logical order and rejects operations that would contradict that order. A data item commonly records information about the latest ordered read and write that have affected it. When a new operation is inconsistent with those records, the transaction aborts or restarts rather than waiting for another transaction to release a lock.

Basic timestamp ordering produces conflict-serializable histories in timestamp order. It avoids lock deadlocks because transactions do not wait on lock ownership, but repeated restarts can delay transactions that conflict with a continuing stream of newer work. Thomas’s write rule modifies the treatment of an obsolete write by ignoring it when a later timestamped value has already superseded it, thereby admitting histories beyond those accepted by elementary timestamp ordering.

Optimistic concurrency control allows a transaction to perform most of its work on private or provisional state. A validation phase determines whether the transaction’s observed data and proposed writes remain compatible with transactions that committed during its execution. Successful validation is followed by publication of the writes, whereas failed validation leads to abortion.

This approach relocates coordination from each data access to the validation boundary. Its behavior depends on the conflict rate and the amount of work invalidated by a failed validation. The serial order is commonly associated with validation or commit order, although particular algorithms define the relevant ordering point differently.

Multiversion concurrency control

Multiversion concurrency control retains multiple committed versions of a logical item instead of overwriting every previous value immediately. A reader selects a version consistent with its assigned snapshot, while a writer creates a new version that becomes visible according to the system’s commit and visibility rules. Readers can consequently proceed without blocking many writers, although version retention and reclamation become part of the storage and recovery model.

Snapshot isolation gives each transaction a consistent view of committed data from an established point in logical time. Transactions that attempt to commit overlapping writes are prevented from both succeeding under the usual first-committer-wins rule. This condition prevents several common anomalies but does not imply serializability.

The characteristic nonserializable behavior under snapshot isolation is write skew. Two transactions can read the same earlier state, update different objects, and jointly violate a constraint that neither transaction violates within its own snapshot. Because the write sets do not overlap, ordinary write-conflict detection does not reject either transaction.

Serializable multiversion systems add dependency analysis or stronger validation. Serializable snapshot isolation tracks patterns of read–write dependencies that can participate in a cycle of the serialization graph. Aborting a transaction that closes a dangerous dependency structure prevents the corresponding nonserializable execution while preserving snapshot-based reads for histories that do not create such a structure.

Version reclamation requires knowledge that no active transaction can still observe an old version. Systems derive that point from active snapshots, transaction epochs, or related visibility metadata. A transaction that remains active for an extended period can therefore retain versions whose logical contents are obsolete for newer transactions but remain visible to its older snapshot.

Concurrency control in distributed systems

A distributed transaction can encounter conflicts at several storage nodes, so a globally serializable execution cannot in general be inferred from independent local serializability. Local schedulers may choose mutually inconsistent serialization orders for the same pair of transactions. Distributed concurrency control therefore coordinates ordering information across the nodes whose data contribute to a transaction.

Distributed two-phase locking extends lock ownership across participating systems. A transaction retains the locks needed for strict execution while an atomic commit protocol determines whether all participants commit or abort. Two-phase commit provides atomic commitment but does not itself establish serializability; the concurrency-control mechanism supplies the ordering constraints. Conversely, a serializable local schedule does not ensure atomic durability when only a subset of participants records the transaction as committed.

Replicated databases introduce an additional distinction between choosing an order and applying an order. A consensus algorithm can establish a common sequence of committed log entries among replicas, while concurrency control determines whether the transactions represented by those entries may execute concurrently without violating the selected isolation model. Systems that order every transaction through a single replicated log obtain a direct serial order, although execution may still overlap when dependency analysis establishes that the overlap preserves that order.

Clock-based distributed systems may assign timestamps derived partly from physical time. Clock uncertainty requires a rule connecting those timestamps to actual completion and observation. Logical clocks instead represent ordering relations without claiming exact physical simultaneity. In either case, the timestamp becomes meaningful for concurrency control only through the protocol that governs reads, writes, validation, and visibility.

Isolation and observable behavior

Isolation levels describe restrictions on the histories visible to applications. Their names do not uniquely identify an implementation mechanism because the same nominal level can be produced through locking, version selection, or validation. The observable guarantee depends on the formal definition adopted by the database system rather than on whether operations happened to block during a particular execution.

The isolation levels standardized for SQL were originally described through prohibited phenomena involving reads and writes. Later analyses demonstrated that a finite list of such phenomena does not fully characterize every possible dependency pattern. Graph-based models instead define isolation through constraints on relationships among transactions, permitting a direct comparison between locking implementations and multiversion implementations.

Concurrency control also interacts with integrity constraints. A transaction can preserve every constraint in the state it reads yet participate in a concurrent history whose final state violates an invariant. Serializability avoids this outcome when each transaction preserves the invariant from every valid serial input state. Weaker isolation requires the system or transaction model to identify the particular dependencies whose omission remains compatible with the application’s integrity conditions.