ResourcesDatabaseConcurrency Control
DatabaseCollege

Concurrency Control

Concurrency Control is a fundamental mechanism in a database management system (DBMS) that coordinates simultaneous execution of operations from multiple transactions to ensure the correctness and consistency of the database while maximizing system throughput and responsiveness.

This guide covers concurrency anomalies, lock-based protocols (including Two-Phase Locking), timestamp ordering, Multi-Version Concurrency Control (MVCC), deadlock handling, SQL isolation levels, walkthroughs, and a 10-question practice quiz.

1Introduction

Without proper concurrency control, concurrent transactions can interfere with each other, leading to data inconsistencies and violating the ACID properties (Atomicity, Consistency, Isolation, Durability) of transactions. Specifically, concurrency control primarily addresses the Isolation property, ensuring that the concurrent execution of transactions appears as if each transaction is executing in isolation from others.

Concurrency control is a core component of the transaction manager within the DBMS architecture, working alongside the recovery manager. It ensures that the database remains in a consistent state even when multiple users or applications are accessing and modifying data concurrently.

In Practice

Modern high-volume OLTP (Online Transaction Processing) systems, such as those powering e-commerce platforms, financial trading systems, and airline reservation systems, rely heavily on sophisticated concurrency control mechanisms. These systems must handle thousands of concurrent transactions per second, making efficient and correct concurrency control paramount for both performance and data integrity.

2Key Definitions

Essential terms for understanding concurrency control at the university level.

Transaction (T)

A logical unit of work: an atomic sequence of read/write operations that must execute entirely or not at all.

Schedule (S)

A sequence of operations from concurrent transactions indicating relative execution order.

Serial Schedule

Operations of different transactions are not interleaved -- transactions execute one after another.

Serializable Schedule

Equivalent to some serial schedule -- the gold standard for concurrent execution correctness.

Conflict

Two operations from different transactions on the same data item where at least one is a write (RW, WR, or WW).

Shared Lock (S-lock)

Allows multiple transactions to read concurrently. No writes permitted while S-locks are held.

Exclusive Lock (X-lock)

Grants exclusive access for reading and writing. No other locks (S or X) can be held simultaneously.

Deadlock

Two or more transactions indefinitely waiting for each other to release locks -- a circular wait.

Two-Phase Locking (2PL)

Protocol with growing phase (acquire locks) and shrinking phase (release locks) ensuring conflict serializability.

Timestamp Ordering (T/O)

Assigns unique timestamps to transactions and orders operations accordingly. Deadlock-free.

MVCC

Maintains multiple versions of data items so readers never block writers and vice versa.

Snapshot Isolation (SI)

Each transaction reads from a consistent snapshot at its start time. Prevents most anomalies but allows write skew.

3Concurrency Problems

Without proper concurrency control, concurrent execution of transactions can lead to various anomalies, violating database consistency and the Isolation property. Here are the four classic problems:

Lost Update (WW Conflict)

One transaction's write is overwritten by another transaction that read the old value.

Example: Account A =

00. T1 subtracts
0 (writes 90), T2 adds
0 (writes 120). T1's update is lost. Expected:
10, actual:
20.

Dirty Read (WR Conflict)

A transaction reads data written by another uncommitted transaction that later aborts.

Example: T1 writes A = 150 (uncommitted). T2 reads A = 150. T1 aborts, rolling A back to 100. T2 committed based on invalid data.

Non-Repeatable Read (RW Conflict)

A transaction reads the same data item twice and gets different values due to a committed update by another transaction.

Example: T1 reads A = 100. T2 updates A to 120 and commits. T1 reads A again and gets 120.

Phantom Read (Predicate-Based)

A transaction re-executes a query and finds new rows (“phantoms”) that were inserted by another committed transaction.

Example: T1 counts accounts with balance > 50 (finds 1). T2 inserts a new account with balance 60. T1 re-counts and finds 2.

4Lock-Based Protocols

Lock-based protocols are the most common approach to concurrency control. They ensure serializability by regulating access to data items through locks. A transaction must acquire a lock on a data item before it can access it.

Lock Compatibility Matrix

The lock compatibility matrix defines which types of locks can be held simultaneously on the same data item:

Held \ RequestedS-lockX-lock
S-lockCompatibleIncompatible
X-lockIncompatibleIncompatible

Two-Phase Locking (2PL)

Two-Phase Locking (2PL) is a classic lock-based protocol that guarantees conflict serializability. It enforces two distinct phases for each transaction:

Growing Phase

A transaction can acquire locks but cannot release any locks. It accumulates all the locks it needs.

Shrinking Phase

A transaction can release locks but cannot acquire any new locks. Begins after the first lock release.

Two-Phase Locking (2PL) Timeline

Growing phase → Lock point → Shrinking phase

// Click Play to see 2PL phases in action
BEGIN
t=1
S(A)
t=2
S(B)
t=3
X(C)
t=4
−S(A)
t=5
−S(B)
t=6
COMMIT
t=7
← Growing Phase →
LP
← Shrinking →
End
Locks Held by T1
S(A)S(B)X(C)
The timeline shows lock count rising (growing phase), peaking at the lock point, then falling (shrinking phase). Click Play to step through.
Step 0 / 7

Strict 2PL and Rigorous 2PL

Strict 2PL

Holds all exclusive (X) locks until commit or abort. Ensures cascadelessness -- no cascading rollbacks.

Rigorous 2PL

Holds all locks (S and X) until commit or abort. Most common in commercial DBMSs. Ensures strictness and cascadelessness.

Multiple Granularity Locking

MGL allows different levels of lock granularity (database, table, row). Intention locks (IS, IX, SIX) signal that a transaction intends to lock descendants at a finer level. This balances concurrency (fine-grained) with overhead (coarse-grained).

5Timestamp-Based Protocols

Timestamp Ordering (T/O) protocols ensure serializability by assigning a unique, monotonically increasing timestamp to each transaction. Each data item X maintains a WTS(X) (write timestamp) and RTS(X) (read timestamp).

Basic T/O Rules

Read Rule

If TS(Ti) < WTS(X): abort Ti (too late to read -- a younger transaction already wrote X). Otherwise: read permitted, update RTS(X).

Write Rule

If TS(Ti) < RTS(X) or TS(Ti) < WTS(X): abort Ti (too late to write). Otherwise: write permitted, update WTS(X).

Thomas' Write Rule

An optimization: when TS(Ti) < WTS(X) but TS(Ti) ≥ RTS(X), instead of aborting, ignore the write. The value would be overwritten anyway by the younger transaction. This achieves view serializability and reduces unnecessary aborts.

Lock-Based vs. Timestamp-Based

FeatureLock-Based (2PL)Timestamp (T/O)
MechanismAcquire/release locks; blockingTimestamps; abort/restart
DeadlockPossible; needs detectionNot possible (deadlock-free)
AbortsLess frequentMore frequent
UsageWidely used in commercial DBMSLess common as primary mechanism

6Multi-Version Concurrency Control (MVCC)

Instead of overwriting data items in place, MVCC creates a new version whenever data is modified. Readers access older, committed versions without blocking writers, and writers proceed without blocking readers. Used in PostgreSQL, Oracle, SQL Server (Snapshot Isolation), and many modern systems.

Version Chain Concept

Each version has a creation timestamp (CrTS) and a deletion timestamp (DlTS). A reader with timestamp TS reads the version where CrTS ≤ TS < DlTS.

MVCC Version Chain

Multiple versions of X — readers see consistent snapshots without blocking writers

// Click Play to see how MVCC version chains work
Version Chain for item X
100
by T0
crTS=5
dlTS=10
→
200
by T1
crTS=10
dlTS=15
→
300
by T2
crTS=15
dlTS=∞
Timestamp Timeline
0510152025
Reader ts=8 → X=100Reader ts=12 → X=200Reader ts=20 → X=300
Three versions of X exist. Each reader sees a consistent snapshot based on its timestamp — no locks needed. Click Play to build the chain.
Step 0 / 6

Snapshot Isolation (SI)

SI Advantages

  • Readers never block writers
  • Writers never block readers
  • Prevents dirty reads, non-repeatable reads, and phantoms
  • First Committer Wins prevents lost updates

SI Limitation

Susceptible to write skew anomaly.

Example: Two accounts sum to

000. T1 checks sum > 0, decrements A. T2 checks sum > 0, decrements B. Both commit, violating the invariant.

Serializable Snapshot Isolation (SSI)

SSI extends Snapshot Isolation to achieve full serializability by detecting and aborting transactions that could lead to write skew. It tracks read-write dependencies between concurrent transactions and aborts when a dangerous cycle is detected. Implemented in PostgreSQL as its SERIALIZABLE isolation level.

7Deadlock Handling

Deadlocks are an inherent problem with lock-based concurrency control. A deadlock exists when two or more transactions form a circular wait for locks held by each other.

Wait-for Graph

A directed graph where nodes are transactions and edges represent “waits for” relationships. A cycle in the wait-for graph indicates a deadlock. The DBMS periodically checks for cycles.

Wait-For Graph: Deadlock Detection

A cycle in the wait-for graph indicates a deadlock. The DBMS must abort one transaction to break it.

T1T2T3T1 waits for X(A)held by T2T2 waits for S(B)held by T3T3 waits for X(C)held by T1DEADLOCK CYCLE

Prevention Strategies

Wait-Die (Non-Preemptive)

Older transaction waits for younger. Younger transaction dies (aborts) if it requests a lock held by older.

Wound-Wait (Preemptive)

Older transaction wounds (aborts) younger to acquire the lock. Younger transaction waits for older.

Deadlock vs. Livelock vs. Starvation

Deadlock

Transactions blocked indefinitely, waiting for each other. Cycle in wait-for graph.

Livelock

Transactions repeatedly aborted and restarted, making no progress despite not being blocked.

Starvation

A specific transaction is repeatedly denied access while others proceed. An unfairness problem.

8Isolation Levels

The SQL standard defines four isolation levels, each preventing a progressively larger set of anomalies. Higher levels offer stronger guarantees at the cost of performance.

Isolation LevelDirty ReadNon-RepeatablePhantom
READ UNCOMMITTEDPossiblePossiblePossible
READ COMMITTEDPreventedPossiblePossible
REPEATABLE READPreventedPreventedPossible
SERIALIZABLEPreventedPreventedPrevented
Implementation Note

Specific DBMS implementations may vary. PostgreSQL's READ COMMITTED uses MVCC so a read sees data committed before the current statement began. Its REPEATABLE READ and SERIALIZABLE use MVCC snapshots, with SERIALIZABLE adding SSI for write-skew detection.

9SQL Walkthroughs

Introductory

Concurrent Updates under Rigorous 2PL

-- Initial: account_id=1 balance=100, account_id=2 balance=200

-- Session 1 (T1): Subtract $50 from Account 1
BEGIN TRANSACTION;
UPDATE BankAccounts SET balance = balance - 50
  WHERE account_id = 1;
-- T1 acquires X-lock on row 1, writes balance=50
COMMIT;  -- T1 releases X-lock on row 1

-- Session 2 (T2): Add $50 to Account 2 (runs concurrently)
BEGIN TRANSACTION;
UPDATE BankAccounts SET balance = balance + 50
  WHERE account_id = 2;
-- T2 acquires X-lock on row 2, writes balance=250
COMMIT;  -- T2 releases X-lock on row 2

-- Result: Account 1=50, Account 2=250
-- No conflict: different data items, concurrent execution OK

Lines 4-7: T1 acquires an exclusive lock on row 1. Under Rigorous 2PL, this lock is held until COMMIT.

Lines 11-14: T2 acquires an exclusive lock on row 2 concurrently -- no conflict since different rows.

Key insight: When transactions operate on different data items, 2PL allows full concurrency with no blocking.

Intermediate

Deadlock: Cross-Account Transfers

-- T1: Transfer from Account 1 to Account 2
BEGIN TRANSACTION;
UPDATE BankAccounts SET balance = balance - 10
  WHERE account_id = 1;  -- X-lock on row 1
UPDATE BankAccounts SET balance = balance + 10
  WHERE account_id = 2;  -- BLOCKED: T2 holds X-lock on row 2

-- T2: Transfer from Account 2 to Account 1
BEGIN TRANSACTION;
UPDATE BankAccounts SET balance = balance - 10
  WHERE account_id = 2;  -- X-lock on row 2
UPDATE BankAccounts SET balance = balance + 10
  WHERE account_id = 1;  -- BLOCKED: T1 holds X-lock on row 1

-- DEADLOCK! T1 waits for T2, T2 waits for T1
-- DBMS detects cycle, aborts one transaction (victim)

Line 4: T1 acquires X-lock on Account 1.

Line 11: T2 acquires X-lock on Account 2.

Lines 6, 13: Each transaction blocks waiting for the other's lock -- circular wait = deadlock.

Key insight: Deadlocks arise when transactions acquire locks in different orders. Consistent lock ordering prevents this.

Advanced

Isolation Level: Dirty Read vs. READ COMMITTED

-- Session 1 (T1):
BEGIN TRANSACTION;
UPDATE BankAccounts SET balance = balance + 50
  WHERE account_id = 1;  -- balance now 150 (uncommitted)
-- DO NOT COMMIT YET

-- Session 2 (T2) with READ UNCOMMITTED:
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
BEGIN TRANSACTION;
SELECT balance FROM BankAccounts WHERE account_id = 1;
-- Returns 150 (DIRTY READ of uncommitted data!)
COMMIT;

-- Back in Session 1:
ROLLBACK;  -- balance reverts to 100
-- T2 committed a decision based on invalid data (150)

Lines 3-4: T1 updates balance to 150 but does not commit.

Line 10: At READ UNCOMMITTED, T2 reads the dirty value 150.

Line 15: T1 rolls back -- the value 150 was never valid. T2 committed based on phantom data.

Key insight: READ COMMITTED prevents dirty reads by only allowing transactions to see committed data.

Advanced

Phantom Read at REPEATABLE READ

-- Session 1 (T1):
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN TRANSACTION;
SELECT COUNT(*) FROM BankAccounts WHERE balance > 150;
-- Returns 1 (only account_id=2 with balance=200)

-- Session 2 (T2):
BEGIN TRANSACTION;
INSERT INTO BankAccounts (account_id, balance)
  VALUES (3, 180.00);
COMMIT;

-- Back in Session 1 (T1):
SELECT COUNT(*) FROM BankAccounts WHERE balance > 150;
-- Returns 2 (accounts 2 and 3) -- PHANTOM READ!
COMMIT;

Line 4: T1 counts 1 account matching the predicate.

Lines 9-10: T2 inserts a new row satisfying T1's predicate and commits.

Line 14: T1's same query now returns 2 -- the “phantom” row appeared.

Key insight: SERIALIZABLE isolation with predicate/range locks prevents phantom reads by locking the “gaps” where new rows could appear.

10Memory Aids

2PL Phases

“Grow locks, then Shrink locks.”

Remember the “lock point” where a transaction transitions from acquiring to releasing. After you release one lock, you can never acquire another.

Lock Compatibility

“Many readers, one writer.”

Multiple S-locks are compatible. As soon as anyone needs to write (X-lock), they need exclusive access. If an X-lock is held, nobody else can do anything.

Isolation Level Hierarchy

“U C R S” -- Uncommitted, Committed, Repeatable, Serializable.

Each level prevents the anomalies of the previous, plus one more. From least strict to most strict.

Deadlock Prevention

“Wait-Die, Wound-Wait -- the older always wins.”

In both schemes, older transactions (smaller timestamps) always get their way -- either by waiting for younger or by wounding (aborting) younger.

Conflict Serializability Test

“Build a precedence graph, check for cycles.”

If the precedence graph (based on conflicting operations) is acyclic, the schedule is conflict serializable.

11Common Mistakes

Confusing Serializability with Isolation Levels

Thinking isolation levels and serializability are the same thing

Serializability is the theoretical correctness criterion. Isolation levels are practical SQL implementations that approximate it to varying degrees. Only SERIALIZABLE guarantees true serializability.

Forgetting to Release Locks

Assuming locks are automatically managed without understanding the protocol

Locks must be released. In 2PL they are released in the shrinking phase. In Strict/Rigorous 2PL, X-locks (or all locks) are held until commit/abort. Unreleased locks lead to starvation and system stalls.

Assuming Locks Prevent All Anomalies

Believing that using locks at any isolation level prevents all problems

Only SERIALIZABLE isolation (via 2PL with predicate locks or SSI) prevents all standard anomalies. Lower isolation levels, even with locks, allow some anomalies.

Deadlock Handling Oversights

Not having a detection/prevention strategy or choosing a poor victim

A robust DBMS must have a deadlock strategy (detection + recovery, or prevention). Victim selection should consider transaction age and work done to minimize wasted effort.

Misunderstanding MVCC Version Visibility

Assuming a reader sees the most recent physical version

In MVCC, a transaction reads the latest committed version whose creation timestamp is ≤ the reader's start timestamp. It does not simply read the most recent physical version.

REPEATABLE READ Does Not Prevent Phantoms

Believing REPEATABLE READ stops phantom reads

REPEATABLE READ prevents changes to existing tuples that are re-read, but does not prevent new tuples from appearing (phantom reads). This requires SERIALIZABLE isolation.

Confusing MGL with General Lock Types

Treating intention locks as general-purpose locks

MGL is a strategy for managing locks at different hierarchical levels (database, table, row). Intention locks (IS, IX, SIX) are specific to MGL -- they signal intent for lower-level locking, not general-purpose access control like S or X locks.

Frequently Asked Questions

What is the primary goal of concurrency control?
The primary goal is to ensure the database remains in a consistent state and that concurrent transactions appear to execute in isolation (satisfying the ACID Isolation property), while maximizing system throughput and minimizing response time.
How does 2PL guarantee serializability?
Two-Phase Locking guarantees conflict serializability by ensuring that once a transaction releases a lock, it cannot acquire any new locks. This creates a "lock point" for each transaction, effectively imposing a serial order on conflicting operations and preventing cycles in the precedence graph.
What is the difference between a dirty read and a non-repeatable read?
A dirty read occurs when a transaction reads data written by another transaction that has not yet committed (and might later abort). A non-repeatable read occurs when a transaction reads the same data item twice and gets different values because another committed transaction modified the item between the two reads.
Why is MVCC often preferred in modern databases, especially for read-heavy workloads?
MVCC significantly increases concurrency by allowing readers to access older, consistent versions of data without blocking writers, and writers to proceed without blocking readers. This is particularly beneficial for read-heavy workloads (like OLAP or reporting) where traditional lock-based systems would suffer from reader-writer contention.
Can a deadlock occur with Timestamp Ordering protocols?
No, Timestamp Ordering protocols are inherently deadlock-free. They resolve conflicts by aborting and restarting transactions based on timestamp rules rather than blocking them indefinitely, thus preventing circular waits.
When should I use SERIALIZABLE isolation versus READ COMMITTED?
Use SERIALIZABLE when absolute data consistency and correctness are paramount, and your application cannot tolerate any anomalies (e.g., financial transactions where even write skew is unacceptable). Use READ COMMITTED when higher throughput and lower latency are critical, and your application can tolerate (or explicitly handle) non-repeatable reads and phantom reads.

Practice Quiz

Test your understanding of concurrency control -- select the correct answer for each question.

1.Which of the following is NOT a standard anomaly caused by lack of concurrency control?

2.A schedule is considered serializable if it is equivalent to:

3.In Two-Phase Locking (2PL), during the shrinking phase, a transaction can:

4.Which type of lock allows multiple transactions to read a data item concurrently?

5.A deadlock can be detected by finding a cycle in which graph?

6.Which SQL isolation level prevents dirty reads but allows non-repeatable reads?

7.In Timestamp Ordering, if transaction Ti attempts to write data item X and TS(Ti) < RTS(X), what typically happens?

8.What is the primary advantage of Multi-Version Concurrency Control (MVCC)?

9.Which isolation level is susceptible to the write skew anomaly?

10.The Wait-Die deadlock prevention scheme states that if an older transaction (Ti) requests a lock held by a younger transaction (Tj), Ti should:

Study Tips

  • Draw wait-for graphs: Given a set of concurrent transactions and their lock requests, draw the wait-for graph and check for cycles to identify deadlocks.
  • Trace through schedules: Manually apply 2PL rules to a schedule -- track which locks each transaction holds, when the lock point is reached, and verify conflict serializability.
  • Compare isolation levels: Create scenarios with dirty reads, non-repeatable reads, and phantom reads, then determine which isolation level would prevent each anomaly.
  • Practice timestamp ordering: Given transaction timestamps and data item RTS/WTS values, determine whether each read/write operation is permitted or causes an abort.

Related Topics