Concurrency Control

The Overbooked Flight

Two airline booking agents are staring at their screens. Flight AA202 has exactly one seat left. Agent Maria in Chicago and Agent Raj in Mumbai both see "1 seat available" and both click Confirm Booking at the same time.

Without concurrency control, both bookings succeed. The plane has 151 seats and 152 passengers. The airline is facing lawsuits, a furious passenger is bumped at the gate, and the database is now lying about reality.

This is the concurrency problem — and every production database must solve it.

Why Concurrency Is Hard

Modern databases serve thousands of transactions per second. Running them one at a time would be catastrophically slow. But running them in parallel introduces three dangerous anomalies:

1. Dirty Read

Transaction B reads data that Transaction A has written but not yet committed. If A rolls back, B has read data that never officially existed.

Time  Transaction A                    Transaction B
----  ---------------------------------  --------------------------------
T1    UPDATE seats SET count = 0        
T2                                       SELECT count FROM seats  → 0  (dirty!)
T3    ROLLBACK  (count goes back to 1)  
T4                                       Books based on count=0 (WRONG)

2. Non-Repeatable Read

Transaction B reads the same row twice and gets different values because Transaction A modified it between the two reads.

Time  Transaction A                    Transaction B
----  ---------------------------------  --------------------------------
T1                                       SELECT price FROM products WHERE id=1  → $10
T2    UPDATE products SET price = $15 WHERE id=1; COMMIT;
T3                                       SELECT price FROM products WHERE id=1  → $15 (changed!)

3. Phantom Read

Transaction B runs the same query twice. Between the two runs, Transaction A inserts or deletes rows that match the query's filter. B sees "phantom" rows appear or disappear.

Time  Transaction A                    Transaction B
----  ---------------------------------  --------------------------------
T1                                       SELECT * FROM seats WHERE available=true  → 5 rows
T2    INSERT INTO seats ... (new row)    
T3                                       SELECT * FROM seats WHERE available=true  → 6 rows (phantom!)

Isolation Levels

SQL databases offer four standard isolation levels. Higher isolation = fewer anomalies = lower concurrency throughput.

-- Set the isolation level for a transaction
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN;
-- ... your queries
COMMIT;

PostgreSQL default: READ COMMITTED
MySQL InnoDB default: REPEATABLE READ

Locking

The classic approach to isolation is locking — a transaction acquires a lock on data before reading or writing it.

Shared Lock (S-Lock) — Read Lock

Multiple transactions can hold a shared lock on the same data simultaneously. Reading is safe in parallel.

Transaction A: S-Lock on row 42  ✓
Transaction B: S-Lock on row 42  ✓  (both can read)
Transaction C: X-Lock on row 42  ✗  (must wait)

Exclusive Lock (X-Lock) — Write Lock

Only one transaction can hold an exclusive lock. No other transaction can read or write the locked data.

Transaction A: X-Lock on row 42  ✓
Transaction B: S-Lock on row 42  ✗  (must wait)
Transaction C: X-Lock on row 42  ✗  (must wait)

Two-Phase Locking (2PL)

The standard protocol ensuring serializability:

Phase 1 — Growing Phase:    Acquire locks, never release
Phase 2 — Shrinking Phase:  Release locks, never acquire

[ LOCK POINT ] = the moment the last lock is acquired

All lock acquisitions happen before any release. This prevents cycles that cause inconsistency.

Optimistic vs Pessimistic Concurrency Control

Pessimistic (Lock-Based)

Assume conflicts will happen. Lock data before accessing it. Other transactions wait.

• Best for: high-conflict workloads, banking, inventory systems
• Cost: lock overhead, potential for deadlocks

Optimistic (No Locks During Read)

Assume conflicts are rare. Read without locking. At commit time, check if the data changed. If it did, abort and retry.

1. Read row (no lock), note version number = 5
2. Make changes locally
3. At commit: check if version is still 5
   - Still 5 → commit, increment version to 6
   - Now 6  → conflict! Rollback and retry

• Best for: low-conflict workloads, read-heavy systems, web apps
• Cost: occasional retries on conflict

MVCC — Multi-Version Concurrency Control

PostgreSQL, MySQL InnoDB, Oracle all use MVCC. Instead of blocking readers with locks, the database maintains multiple versions of each row.

Row 42 versions:
  version 1: balance=1000  (created by txn 10, valid before txn 15)
  version 2: balance=500   (created by txn 15, current)

Transaction A (started at txn_id=12) reads row 42:
  → Sees version 1 (balance=1000) — the version valid when it started

Transaction B (started at txn_id=16) reads row 42:
  → Sees version 2 (balance=500) — the current version

Key benefit: Readers never block writers. Writers never block readers. This is why PostgreSQL can handle high concurrency without readers waiting for each other.

Old versions are eventually cleaned up by the VACUUM process in PostgreSQL.

ASCII: Lock Compatibility Matrix

         | S-Lock | X-Lock |
---------+--------+--------+
S-Lock   |  YES   |   NO   |
X-Lock   |   NO   |   NO   |

YES = Compatible (both can proceed)
NO  = Incompatible (second must wait)

Isolation Level SQL Example

-- PostgreSQL: run in first terminal
BEGIN;
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT balance FROM accounts WHERE id = 1;
-- Returns: 1000

-- In a SECOND terminal, another transaction updates and commits:
-- UPDATE accounts SET balance = 900 WHERE id = 1; COMMIT;

-- Back in first terminal — same query
SELECT balance FROM accounts WHERE id = 1;
-- Still returns: 1000  (repeatable read protects you)

COMMIT;

Key Takeaways

• Dirty reads, non-repeatable reads, and phantom reads are the three concurrency anomalies databases must guard against.
• Isolation levels are a dial between data correctness and performance — choose the right level for each workload.
• Locks are the classic solution: shared locks for reads, exclusive locks for writes, governed by Two-Phase Locking.
• MVCC is the modern approach: multiple row versions let readers and writers operate simultaneously without blocking each other.
• Optimistic concurrency is ideal when conflicts are rare; pessimistic is safer when conflicts are frequent.

The airline seat problem is solved by using SERIALIZABLE isolation or an explicit SELECT ... FOR UPDATE lock on the seat row before booking — ensuring only one transaction can proceed.