Concurrency Control 2PL, Deadlock, Isolation

Concurrency Control in DBMS

Concurrency control is the DBMS mechanism that keeps database results correct when multiple transactions execute at the same time. Without concurrency control, users may read temporary data, overwrite each other's updates, or produce reports from inconsistent intermediate states.

The goal is to gain the performance of concurrent execution while preserving results equivalent to a valid serial order. Isolation mechanisms prevent transactions from observing or overwriting unsafe intermediate state.

Why Concurrency Control is Needed

It improves database throughput by allowing many transactions to run together.
It prevents lost updates, dirty reads, unrepeatable reads, phantom reads, and incorrect summaries.
It helps preserve isolation, one of the ACID properties of transactions.
It ensures that concurrent schedules are equivalent to correct serial schedules.
It supports multi-user applications such as banking, ticket booking, inventory, and e-commerce.

Concurrency Example

Suppose two transactions try to update the same account balance at the same time. If both read the old value and write a new value independently, one update may be lost.

lost-update-schedule.txt

Initial balance A = 1000

T1: Read A = 1000
T2: Read A = 1000
T1: A = A + 200, Write A = 1200
T2: A = A - 100, Write A = 900

Final value becomes 900.
T1's update is lost because T2 overwrote it.

Important Terms

Term	Meaning
Transaction	A logical unit of work that should commit completely or roll back completely.
Schedule	The order in which operations of transactions are executed.
Serial Schedule	Transactions run one after another without interleaving.
Concurrent Schedule	Operations of multiple transactions are interleaved.
Conflict	Two operations from different transactions access the same item and at least one operation is a write.
Serializable Schedule	A concurrent schedule that gives the same result as some serial schedule.

Problems Without Concurrency Control

Problem	Description	Example
Lost Update	One transaction overwrites another transaction's update.	Two users update the same stock quantity and the later write removes the earlier change.
Dirty Read	A transaction reads data written by another uncommitted transaction.	T2 reads a salary change by T1, but T1 later rolls back.
Unrepeatable Read	A transaction reads the same row twice and gets different values.	T1 reads balance 5000; T2 updates it; T1 reads balance again and sees 4500.
Phantom Read	A repeated condition-based query returns a different set of rows.	T1 counts orders above 1000; T2 inserts a matching order; T1 counts again and sees one extra row.
Incorrect Summary	An aggregate reads some old values and some new values while updates are happening.	A report computes total account balance while a transfer is halfway complete.

Serializability

Serializability is the main correctness condition in concurrency control. A schedule is serializable if it produces the same final result as a serial schedule.

Two operations conflict if they are from different transactions, access the same data item, and at least one operation writes that item.

Type	Meaning	How It Is Checked
Conflict Serializability	The schedule can be transformed into a serial schedule by swapping non-conflicting operations.	Use a precedence graph. If the graph has no cycle, the schedule is conflict serializable.
View Serializability	The schedule has the same read-from relationships and final writes as a serial schedule.	Harder to test; it is more general than conflict serializability.

precedence-graph-example.txt

Schedule:
R1(A), W1(A), R2(A), W2(A), R1(B), W2(B), C1, C2

Conflicts:
W1(A) before R2(A) gives edge T1 -> T2
W1(A) before W2(A) gives edge T1 -> T2
R1(B) before W2(B) gives edge T1 -> T2

Graph has no cycle.
So the schedule is conflict serializable in order T1, T2.

Lock-Based Protocols

A lock is a permission to access a data item. Before a transaction reads or writes an item, it may need to acquire a lock. Locking is one of the most widely used concurrency control techniques.

Lock Type	Also Called	Allows	Blocks
Shared Lock (S)	Read lock	Many transactions can read the same item.	Writing by other transactions.
Exclusive Lock (X)	Write lock	One transaction can read and write the item.	All other reads and writes on the item.
Update Lock (U)	Conversion lock	A transaction plans to update after reading.	Some competing update attempts, depending on DBMS.
Intent Lock	Hierarchy lock	A transaction plans to lock lower-level objects such as rows.	Conflicting table-level locks.

locking-example.sql

START TRANSACTION;

SELECT balance
FROM accounts
WHERE account_id = 101
FOR UPDATE;

UPDATE accounts
SET balance = balance - 500
WHERE account_id = 101;

COMMIT;

Two-Phase Locking (2PL)

Two-Phase Locking is a locking protocol that guarantees conflict serializability. A transaction has two phases: first it only acquires locks, then it only releases locks.

The point where a transaction gets its last lock is called the lock point. Under 2PL, transactions are serialized according to their lock points.

Phase	Meaning
Growing Phase	The transaction may acquire new locks but cannot release any lock.
Shrinking Phase	The transaction may release locks but cannot acquire any new lock.

Lock Granularity

Lock granularity means the size of the object being locked. A DBMS may lock a database, table, page, row, or even a field.

Smaller locks allow more concurrency but require the DBMS to manage more lock entries. Larger locks are cheaper to manage but block more transactions.

Granularity	Example	Concurrency	Overhead
Table Lock	Lock the whole employees table.	Low	Low
Page Lock	Lock a disk page containing many rows.	Medium	Medium
Row Lock	Lock one account row.	High	High

Deadlock

A deadlock occurs when two or more transactions wait for each other in a cycle. Because each transaction is waiting for a lock held by another transaction, none can continue.

In a wait-for graph, transactions are nodes and waiting relationships are edges. A cycle in the graph indicates a deadlock.

Method	How It Works
Prevention	Use rules that make deadlocks impossible, such as lock ordering or timestamp-based policies.
Detection	Periodically build a wait-for graph and check for cycles.
Recovery	Choose a victim transaction, abort it, release its locks, and restart it later.
Timeout	Abort a transaction if it waits longer than a configured time.

deadlock-schedule.txt

T1: lock-X(A)
T2: lock-X(B)
T1: request lock-X(B) and wait
T2: request lock-X(A) and wait

T1 waits for T2.
T2 waits for T1.
Cycle found, so deadlock exists.

Timestamp-Based Concurrency Control

In timestamp ordering, each transaction gets a unique timestamp when it starts. The DBMS uses timestamps to decide whether an operation is allowed or whether the transaction must restart.

Operation	Rule	Result
Read X	If TS(T) < WTS(X), the transaction is too old.	Abort and restart T.
Read X	If TS(T) >= WTS(X), the read is safe.	Read X and update RTS(X).
Write X	If TS(T) < RTS(X) or TS(T) < WTS(X), the write is too old.	Abort and restart T.
Write X	If timestamp checks pass, the write is safe.	Write X and update WTS(X).

TS(T) is the timestamp of transaction T.
RTS(X) is the largest timestamp of any transaction that successfully read item X.
WTS(X) is the largest timestamp of any transaction that successfully wrote item X.

Thomas Write Rule

Thomas Write Rule is an optimization for timestamp ordering. If a transaction tries to write an old value that has already been overwritten by a newer transaction, the DBMS can ignore that obsolete write instead of aborting the transaction.

thomas-write-rule.txt

If transaction T wants to write X:

1. If TS(T) < RTS(X), abort T.
2. If TS(T) < WTS(X), ignore the write because it is obsolete.
3. Otherwise, perform the write and set WTS(X) = TS(T).

Optimistic Concurrency Control

Optimistic concurrency control assumes conflicts are rare. Transactions execute without locking first, then the DBMS validates them before commit.

Phase	Meaning
Read Phase	The transaction reads database values and makes changes in a private workspace.
Validation Phase	The DBMS checks whether the transaction conflicts with other committed transactions.
Write Phase	If validation succeeds, changes are written to the database. If validation fails, the transaction restarts.

MVCC

Multiversion Concurrency Control (MVCC) keeps multiple versions of a row. Readers can view a consistent snapshot while writers create newer versions. This reduces blocking between reads and writes.

Readers usually do not block writers.
Writers usually do not block readers.
Each transaction sees a consistent snapshot based on its start time or statement time.
Old row versions must be cleaned up by the DBMS later.

mvcc-version-example.txt

Account row versions:

Version 1: balance = 1000, visible to transactions started before T2 commits
Version 2: balance = 1200, created by T2 after update

Old readers can continue seeing Version 1.
New readers can see Version 2 after T2 commits.

Isolation Levels

Isolation levels define how strongly one transaction is separated from other concurrent transactions. Stronger isolation prevents more anomalies but can reduce performance.

Isolation Level	Dirty Read	Unrepeatable Read	Phantom Read	Typical Performance
READ UNCOMMITTED	Possible	Possible	Possible	Highest
READ COMMITTED	Prevented	Possible	Possible	High
REPEATABLE READ	Prevented	Prevented	May be possible depending on DBMS.	Medium
SERIALIZABLE	Prevented	Prevented	Prevented	Lowest

isolation-levels.sql

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;

START TRANSACTION;

SELECT stock
FROM products
WHERE product_id = 10;

UPDATE products
SET stock = stock - 1
WHERE product_id = 10;

COMMIT;

Recoverable, Cascadeless, and Strict Schedules

Correct concurrency control must also support recovery. A schedule should avoid situations where one rollback forces many other transactions to roll back.

Schedule Type	Meaning	Quality
Recoverable	If T2 reads a value written by T1, T2 commits only after T1 commits.	Minimum requirement for safe recovery.
Cascadeless	Transactions read only committed data.	Avoids cascading rollback.
Strict	A transaction cannot read or write an item until the last transaction that wrote it commits or aborts.	Best for simple recovery.

Comparison of Concurrency Control Methods

Method	Main Idea	Advantages	Disadvantages
Locking	Transactions acquire locks before accessing data.	Easy to understand and widely used.	May cause deadlocks and blocking.
Timestamp Ordering	Transactions are ordered by timestamps.	No deadlock.	May cause frequent restarts.
Optimistic Control	Transactions run first and are validated before commit.	Good when conflicts are rare.	Costly when conflicts are common.
MVCC	Maintain multiple row versions for snapshots.	Great read concurrency.	Requires version cleanup and more storage management.

Best Practices

Keep transactions short so locks are held for less time.
Access tables and rows in a consistent order to reduce deadlocks.
Use indexes on search conditions so updates lock fewer rows.
Choose the lowest isolation level that still preserves correctness.
Retry transactions safely when deadlocks or serialization failures occur.
Avoid long user interactions while a transaction is open.
Use database constraints to catch invalid concurrent updates.

Concurrency Control Failure Cases

Mistake	Risk	Better Approach
Assuming concurrent transactions behave like serial transactions automatically	Lost updates and inconsistent reads may occur.	Use proper isolation, locks, constraints, or retry logic.
Using SERIALIZABLE for every operation	Unnecessary blocking and slower throughput.	Use it only for operations that truly require strict isolation.
Holding locks during slow application work	Other transactions wait longer and deadlock risk increases.	Keep only database work inside the transaction.
No retry logic for deadlocks	User operations fail even though retry would succeed.	Catch deadlock or serialization errors and retry safely.

Interview and Exam Questions

Use these concise answers for review, then trace a schedule or lock graph when the question asks for proof.

Question	Concise answer
What is concurrency control?	Coordination of simultaneous transactions so database correctness and isolation are preserved.
What is its main goal?	Make concurrent execution equivalent to a correct serial outcome while retaining useful concurrency.
What is conflict serializability?	A schedule can be transformed into a serial schedule by swapping only non-conflicting operations.
What is two-phase locking?	A transaction acquires locks during a growing phase and releases them during a shrinking phase.
What is a deadlock?	Transactions form a wait cycle in which none can proceed without intervention.
Why can timestamp ordering avoid deadlock?	It normally restarts conflicting transactions instead of making them wait in a circular lock dependency.
What is MVCC?	Multiple row versions let readers use a consistent snapshot while writers continue under the database's visibility rules.

Quick Revision Notes

Concurrency control protects correctness during simultaneous transaction execution.
Serializability is the main correctness goal.
Conflicting operations access the same item, belong to different transactions, and include at least one write.
Shared locks allow reads; exclusive locks allow writes and block other access.
2PL guarantees conflict serializability but can cause deadlock.
A wait-for graph cycle means deadlock.
Timestamp ordering avoids deadlock but may restart transactions.
MVCC improves read concurrency using multiple row versions.
Isolation levels trade correctness strength for concurrency and performance.

Concurrency SQL lab setup

CREATE TABLE lesson_concurrency (
    id INT PRIMARY KEY,
    description VARCHAR(120),
    amount DECIMAL(10,2),
    status VARCHAR(20)
);

INSERT INTO lesson_concurrency VALUES
(1, 'Concurrency normal case', 1000.00, 'active'),
(2, 'Concurrency boundary case', 0.00, 'review');

SELECT * FROM lesson_concurrency;

Concurrency reasoning query

BEGIN;
UPDATE lesson_concurrency
SET status = 'checked'
WHERE amount >= 0;

SELECT status, COUNT(*) AS rows_seen
FROM lesson_concurrency
GROUP BY status;
ROLLBACK;

-- Explanation: ROLLBACK lets you test the concept safely before committing changes.

Before you move on