Concurrency Control Protocols
Concurrency control protocols are the methods — locking, timestamp ordering, optimistic validation, and multiversioning — that schedule concurrent transactions so the result is equivalent to a serial execution.
Definition
A concurrency control protocol is a rule set governing how concurrent transactions acquire access to data so that every allowed schedule is serializable (or satisfies a chosen weaker isolation level), thereby preserving isolation without forcing transactions to run one at a time.
Scope
This topic covers the protocols that enforce serializability under concurrency: two-phase locking and its strict variant, with deadlock detection and prevention; timestamp-ordering protocols; optimistic concurrency control with read-validate-write phases; and multiversion concurrency control, including snapshot isolation. It treats how each protocol guarantees correct schedules and the trade-offs among blocking, aborts, and throughput. It excludes the definition of serializability itself and the recovery mechanisms that complement concurrency control.
Core questions
- How does two-phase locking guarantee serializable schedules?
- How are deadlocks detected, prevented, or resolved?
- How do timestamp-ordering and optimistic protocols differ from locking?
- How does multiversion concurrency control let readers avoid blocking writers?
- What are the throughput trade-offs among pessimistic and optimistic methods?
Key concepts
- two-phase locking
- strict and rigorous 2PL
- shared and exclusive locks
- deadlock detection and prevention
- timestamp ordering
- optimistic concurrency control
- multiversion concurrency control
- snapshot isolation
Key theories
- Two-phase locking
- If every transaction acquires all its locks before releasing any (a growing phase followed by a shrinking phase), all resulting schedules are conflict-serializable; strict two-phase locking additionally holds write locks until commit to ensure recoverability.
- Optimistic concurrency control
- Transactions execute without locking and are validated at commit time against concurrent transactions; conflicting transactions are aborted and retried, which performs well when contention is low.
- Multiversion concurrency control
- By keeping multiple versions of each data item, the system lets reads access a consistent snapshot without blocking writes; snapshot isolation is a widely used multiversion scheme, though it can permit certain non-serializable anomalies.
Clinical relevance
Concurrency control protocols determine how a database behaves under load: locking is robust but can cause deadlocks and contention, optimistic and multiversion methods enable high read concurrency, and the protocol choice directly shapes the throughput and latency of high-traffic transactional systems.
History
Two-phase locking and predicate locks were formalized by Eswaran and colleagues at System R in 1976; Kung and Robinson introduced optimistic concurrency control in 1981; and Bernstein, Hadzilacos, and Goodman's 1987 monograph unified the theory. Multiversion methods and snapshot isolation later became dominant in widely used database systems for their read-friendly behavior.
Debates
- Snapshot isolation versus serializability
- Snapshot isolation gives high concurrency by letting readers see a consistent snapshot, but it permits anomalies such as write skew that full serializability forbids; practitioners debate when its weaker guarantee is acceptable and when serializable variants are required.
Key figures
- Jim Gray
- Philip Bernstein
- H. T. Kung
Related topics
Seminal works
- eswaran1976
- kung1981
- bernstein1987
Frequently asked questions
- What causes a deadlock and how is it handled?
- A deadlock occurs when two or more transactions each hold a lock the other needs, so none can proceed. Systems handle it either by detection — building a waits-for graph, finding a cycle, and aborting a victim transaction — or by prevention schemes that order lock acquisition or use timestamps to decide which transaction waits versus aborts.
- When is optimistic concurrency control a good choice?
- Optimistic methods shine when conflicts are rare, because transactions run without locking overhead and only occasionally fail validation and retry. Under high contention they waste work on aborts and retries, so pessimistic locking or multiversion methods are usually preferred for write-heavy, conflict-prone workloads.