1. System Prerequisites
Concurrency Control — Locks & MVCC
In simple words
When many people use a database together, it needs a way to stop them corrupting each other's work. There are two main ways. Locking makes people wait: while someone is changing a row, others must wait their turn. MVCC (multi-version concurrency control) keeps old copies of a row, so people who are reading can keep reading the version from when they started while others write a new one — nobody has to wait for readers. Most modern databases use both: versions for reading, locks for writing.
What is Concurrency Control?
Concurrency control is the mechanism databases use to manage simultaneous access to the same data by multiple transactions, ensuring correctness without sacrificing performance.
Problem:
1000 transactions per second hitting the same database
Multiple transactions reading and writing the same rows
Without control → data corruption, lost updates, dirty reads
Two fundamental approaches:
1. Locking (Pessimistic) → prevent conflicts upfront by blocking access
2. MVCC (Optimistic) → allow concurrent reads, detect conflicts at write time
APPROACH 1 — LOCKING
Lock Types
Shared Lock (S Lock) — Read Lock
Purpose: Allows a transaction to READ a resource
Multiple transactions can hold shared locks simultaneously
Blocks: exclusive locks only
Analogy: A library book can be READ by multiple people simultaneously
(many readers hold shared lock)
But nobody can WRITE in it while someone is reading
(writer blocked by shared locks)
SQL:
SELECT * FROM orders WHERE id = 1 FOR SHARE; -- PostgreSQL
SELECT * FROM orders WHERE id = 1 LOCK IN SHARE MODE; -- MySQL
Compatibility:
Transaction holds S lock → another transaction wants S lock → ALLOWED ✅
Transaction holds S lock → another transaction wants X lock → BLOCKED ❌
Exclusive Lock (X Lock) — Write Lock
Purpose: Allows a transaction to WRITE (UPDATE/DELETE) a resource
Only ONE transaction can hold an exclusive lock at a time
Blocks: both shared and exclusive locks from others
Analogy: A document being edited exclusively — nobody else can read or write
SQL:
SELECT * FROM orders WHERE id = 1 FOR UPDATE; -- acquires X lock
UPDATE orders SET status = 'SHIPPED' WHERE id = 1; -- auto-acquires X lock
DELETE FROM orders WHERE id = 1; -- auto-acquires X lock
Compatibility:
Transaction holds X lock → another wants S lock → BLOCKED ❌
Transaction holds X lock → another wants X lock → BLOCKED ❌
Lock Compatibility Matrix
│ Wants S │ Wants X
──────────────┼───────────┼──────────
Holds S │ ✅ Allow │ ❌ Block
Holds X │ ❌ Block │ ❌ Block
No lock │ ✅ Allow │ ✅ Allow
Intention Locks (Table-Level Hints)
Intention locks signal that a transaction INTENDS to acquire row-level locks.
They prevent conflicts between row-level and table-level operations.
IS (Intention Shared): intention to set S locks on rows
IX (Intention Exclusive): intention to set X locks on rows
Example:
T1 is updating row 5 (holds IX on table, X on row 5)
T2 wants to lock the ENTIRE TABLE exclusively (ALTER TABLE)
→ T2 sees IX lock on table → knows T1 is working inside → BLOCKS
→ Without IX: T2 might lock the table while T1 is mid-update
Used internally by InnoDB — you don't set these manually
Lock Granularity
Locks can be applied at different levels — finer granularity = more concurrency.
COARSEST (least concurrency, least overhead)
┌─────────────────────┐
│ Database Lock │ Lock the entire database
│ │ (only for backup, rarely used)
├─────────────────────┤
│ Table Lock │ Lock the entire table
│ │ MySQL MyISAM uses table locks
│ │ Fast to acquire, but blocks ALL readers/writers
├─────────────────────┤
│ Page Lock │ Lock a disk page (8-16KB, holds many rows)
│ │ SQL Server uses page locks in some scenarios
├─────────────────────┤
│ Row Lock │ Lock individual rows ← InnoDB default
│ │ High concurrency: only rows being modified are locked
├─────────────────────┤
│ Column Lock │ Lock specific columns (not supported in most RDBMS)
└─────────────────────┘
FINEST (most concurrency, most overhead)
Table lock example (MyISAM):
T1 updates user_id=1 → entire users table is locked
T2 wants to read user_id=2 → BLOCKED until T1 finishes
10 concurrent updates → serial execution → throughput = 1/10x
Row lock example (InnoDB):
T1 updates user_id=1 → only row 1 is locked
T2 reads/writes user_id=2 → NOT BLOCKED → proceeds immediately
10 concurrent updates on different rows → all execute simultaneously
Gap Locks and Next-Key Locks (MySQL InnoDB)
These are critical for preventing phantom reads in REPEATABLE READ.
Gap Lock
Locks the GAP between index values, not the rows themselves.
Prevents other transactions from INSERTing rows into the gap.
Example:
Index on age: [18, 25, 30, 40, 55]
T1: SELECT * FROM users WHERE age BETWEEN 25 AND 40 FOR UPDATE;
→ InnoDB locks the gap: (25, 30] and (30, 40]
→ T2 cannot INSERT a row with age=28 → BLOCKED
→ Prevents phantom reads in this range
Next-Key Lock
Combination of row lock + gap lock on the range up to and including the row.
This is InnoDB's default locking for range queries in REPEATABLE READ.
Index values: [10, 20, 30]
Next-key locks cover: (-∞, 10], (10, 20], (20, 30], (30, +∞)
SELECT * FROM orders WHERE amount > 100 FOR UPDATE;
→ Locks all rows with amount > 100 + gaps between them
→ No phantom rows can be inserted in this range
Two-Phase Locking (2PL) — The Protocol
2PL is the standard protocol ensuring serializability using locks.
Phase 1 — Growing Phase:
Transaction acquires locks as needed
Cannot release ANY lock during this phase
Phase 2 — Shrinking Phase:
Transaction begins releasing locks (starting at COMMIT/ROLLBACK)
Cannot acquire NEW locks after first release
Timeline:
BEGIN
┌──── Growing phase ────┐ ┌─ Shrinking phase ─┐
acquire S(A) │ │ release S(A)
acquire X(B) │ │ release X(B)
acquire S(C) │ │ release S(C)
│ │
COMMIT/ROLLBACK
Why 2PL ensures correctness:
Prevents a transaction from acquiring a lock after releasing one
This prevents situations where T1 releases A, T2 modifies A,
T1 re-reads A → inconsistency
2PL makes the effective order of transactions equivalent to some serial order
Strict 2PL (used by most databases)
All locks held until COMMIT or ROLLBACK — no early release.
Prevents cascading rollbacks:
If T1 releases X(A) early and T2 reads A, then T1 rolls back →
T2 has read invalid data → T2 must also roll back (cascading)
Strict 2PL: hold all locks until end → no cascading rollbacks possible
APPROACH 2 — MVCC (Multi-Version Concurrency Control)
The Core Idea
Instead of blocking readers with write locks:
→ Keep MULTIPLE VERSIONS of each row
→ Readers see an appropriate older version (their snapshot)
→ Writers create a new version without disturbing readers
Result:
READERS NEVER BLOCK WRITERS
WRITERS NEVER BLOCK READERS
Only writer-writer conflicts need locks
Used by: PostgreSQL, MySQL InnoDB, Oracle, MongoDB, CockroachDB
How MVCC Works — InnoDB Implementation
Every row in InnoDB has two hidden system columns:
DB_TRX_ID: The ID of the last transaction that inserted or updated this row
DB_ROLL_PTR: Pointer to the undo log entry (previous version of this row)
Row in users table (visible columns + hidden):
┌─────────┬───────┬──────────────────┬────────────┬─────────────┐
│ user_id │ name │ email │ DB_TRX_ID │ DB_ROLL_PTR │
├─────────┼───────┼──────────────────┼────────────┼─────────────┤
│ 1 │ Alice │ alice@email.com │ TRX_100 │ → undo log │
└─────────┴───────┴──────────────────┴────────────┴─────────────┘
MVCC Read — How a Transaction Sees Data
When transaction T200 starts (transaction ID = 200):
InnoDB records the current read view:
"I will see data committed BEFORE transaction 200 started"
"I will NOT see data committed by transactions 200 or later"
T200 reads row for user_id=1:
Reads the row → sees DB_TRX_ID = 100
100 < 200 → T100 committed before T200 started → T200 CAN see this ✅
T201 (concurrent) updates user_id=1:
Creates new version of the row with DB_TRX_ID = 201
Old version moved to undo log
T200 reads user_id=1 again:
Row now has DB_TRX_ID = 201
201 >= 200 → T201 started after T200 → T200 CANNOT see T201's version ❌
→ InnoDB follows DB_ROLL_PTR to undo log → finds old version (TRX_ID=100) ✅
→ T200 reads the old version → consistent snapshot maintained
MVCC Snapshot Read timeline:
T100: UPDATE users SET name='Alicia' WHERE id=1 → COMMIT
↓
Row: {name:'Alicia', TRX_ID:100}
Undo log: {name:'Alice', TRX_ID:50}
T200 (starts after T100 commits):
read view: "see transactions < 200"
Reads user_id=1 → TRX_ID=100 < 200 → sees 'Alicia' ✅
T150 (started BEFORE T100 committed):
read view: "see transactions < 150"
Reads user_id=1 → TRX_ID=100 < 150 → sees 'Alicia'? No!
T100 was NOT committed when T150 started → follows undo log
Undo log: {name:'Alice', TRX_ID:50} < 150 → sees 'Alice' ✅
(correct: T150 started before T100's change → should see old value)
MVCC Write — How Updates Work
UPDATE users SET email = 'alice2@email.com' WHERE user_id = 1;
(by transaction T300)
Step 1: InnoDB acquires X lock on row for user_id=1
Step 2: Copy current row to UNDO LOG (for rollback + older readers)
Step 3: Update the row in place with new values + set DB_TRX_ID = T300
Step 4: If ROLLBACK: use undo log to restore old values
If COMMIT: undo log kept for older readers still needing the old version
Eventually purged by the purge thread when no reader needs it
Result:
Writers acquire X locks (writer-writer still serialized)
Readers with older snapshots read from undo log (never blocked)
MVCC Garbage Collection
Undo log versions accumulate over time.
The PURGE THREAD periodically cleans up old versions
that no active transaction can still read.
Problem: Long-running transactions prevent purge
T1 starts → takes a snapshot
T2, T3, ... T1000 make updates → new versions accumulate in undo log
T1 might need any version committed after it started
→ Purge thread cannot clean anything T1's snapshot needs
→ Undo log grows indefinitely → performance degrades
This is why long-running transactions are dangerous in MVCC systems:
→ bloat in undo log / rollback segments
→ PostgreSQL calls this "table bloat"
→ MySQL: undo log grows in ibdata1 file
Best practice: keep transactions short, never leave transactions open idle
Locking vs MVCC — The Critical Comparison
LOCKING MVCC
────────────────────────────────────────────────────────────────
Read-write conflict Readers BLOCK writers Readers NEVER block writers
Writers BLOCK readers Writers NEVER block readers
Write-write conflict Serialized via X locks Serialized via X locks (same)
Throughput Lower (blocking) Higher (non-blocking reads)
Memory overhead Low (just lock table) Higher (multiple row versions)
Long transactions OK Dangerous (undo log bloat)
Used in MySQL MyISAM MySQL InnoDB, PostgreSQL,
Old SQL Server Oracle, MongoDB, CockroachDB
Phantom reads Gap locks needed Snapshot prevents most phantoms
Deadlock Deep Dive
Deadlock detection (InnoDB approach):
Maintains a "waits-for" graph
Each node = transaction
Each edge = "T1 waits for lock held by T2"
Cycle in graph = deadlock
InnoDB scans the graph when a transaction waits for a lock
If cycle detected → choose victim (transaction with fewest rows locked)
→ Roll back the victim → other transaction proceeds
MySQL error: ERROR 1213 (40001): Deadlock found when trying to get lock
Application handling:
Always wrap transactions in retry logic for deadlock errors
try {
executeTransaction();
} catch (DeadlockException e) {
Thread.sleep(random.nextInt(100)); // random backoff
executeTransaction(); // retry
}
Lock Wait Timeout
If a transaction waits too long for a lock (not a deadlock):
MySQL:
innodb_lock_wait_timeout = 50 (seconds, default)
After 50 seconds of waiting → ERROR 1205: Lock wait timeout exceeded
Application handling:
catch (LockWaitTimeoutException e) → retry or fail gracefully
Tuning:
Short timeout (5-10s): fail fast, better user experience
Long timeout (50s+): risk of pile-up, queries stacking waiting for lock
Real-World Concurrency Control Patterns
1. Flash Sale Inventory (High Contention)
-- Problem: 10,000 users try to buy the SAME item simultaneously
-- Stock = 1 unit remaining
-- ❌ Without proper locking (Race condition)
BEGIN;
SELECT stock FROM inventory WHERE product_id = 'P01';
-- All 10,000 transactions read stock = 1
IF stock > 0 THEN
UPDATE inventory SET stock = stock - 1 WHERE product_id = 'P01';
-- All 10,000 try to update → oversell
END IF;
COMMIT;
-- ✅ With SELECT FOR UPDATE (Pessimistic)
BEGIN;
SELECT stock FROM inventory
WHERE product_id = 'P01' FOR UPDATE; -- only ONE transaction at a time
-- Other 9,999 transactions WAIT HERE
IF stock > 0 THEN
UPDATE inventory SET stock = stock - 1 WHERE product_id = 'P01';
COMMIT;
ELSE
ROLLBACK; -- out of stock
END IF;
-- ✅ Even better: Atomic UPDATE with WHERE guard (most efficient)
UPDATE inventory
SET stock = stock - 1
WHERE product_id = 'P01' AND stock > 0;
-- Affected rows = 1 → success
-- Affected rows = 0 → out of stock (no need for explicit lock or read)
2. Distributed Counter (Likes, Views)
Problem: UPDATE likes = likes + 1 on every view → massive lock contention
at Flipkart/YouTube scale = millions of updates/second
Solution 1: In-memory counter (Redis INCR — atomic, no DB lock)
INCR product:P01:views → atomic increment in Redis
Periodically flush to DB
Solution 2: Counter sharding
Instead of one row, maintain N counter rows
Randomly pick one row to update → N times less contention
Read total: SUM across all N rows
Solution 3: Eventual consistency
Accept that view count may lag by seconds
Background aggregation from event stream (Kafka)
Display approximate count → acceptable for views/likes
3. Account Balance Update (Bank)
-- Correct pattern for concurrent balance updates
UPDATE accounts
SET balance = balance - 1000
WHERE account_id = 1
AND balance >= 1000; -- atomic check + update in one statement
-- Check affected rows:
-- 1 → success (balance was sufficient, deducted)
-- 0 → insufficient balance (balance < 1000, or account not found)
-- This avoids a SELECT followed by UPDATE (race condition window)
-- The single UPDATE statement is atomic at the row level
MVCC in NoSQL Systems
MongoDB:
Document-level MVCC (since 4.0 with WiredTiger)
Multi-document transactions use MVCC for snapshots
Each document stores version metadata
CockroachDB:
MVCC across distributed nodes
Each key-value pair stores versions with timestamps
Transactions pick a read timestamp → see consistent snapshot globally
Cassandra:
Does NOT use MVCC in the traditional sense
Uses lightweight transactions (LWT) based on Paxos for compare-and-swap
Generally accepts eventual consistency — no MVCC needed
Redis:
Single-threaded → no concurrent writes → no MVCC needed
MULTI/EXEC (transactions) use optimistic locking via WATCH
How This Connects
- Transactions & Isolation Levels — this note is the implementation layer under that one: snapshot isolation = MVCC, gap locks = how InnoDB's REPEATABLE READ kills phantoms.
- ACID Properties — concurrency control delivers the "I"; the undo log it relies on is the same structure that gives "A" (rollback).
- Query Optimization & EXPLAIN Plans — an unindexed
UPDATE ... WHEREwidens the lock footprint from one row to a range/table, which is where surprise contention and deadlocks come from. - Redis as a Caching Engine — Redis
INCR/SET NXis the cross-process lock/counter you reach for when the hot row would otherwise melt the primary DB (flash-sale counters). - Module 4 — Sharding / Module 11 — Async — counter sharding and event-stream aggregation are how you remove write contention entirely instead of locking harder.
- Storage Engines - LSM-Tree vs B-Tree — the purge/vacuum problem (old versions piling up) is specific to MVCC-on-B-Tree; LSM engines handle obsolete versions during compaction.
In the Interview
When to say it. Any "last item in stock / last seat", any counter at scale, any "reader is blocked by a writer — why?", and any follow-up to an isolation-level answer asking how the level is enforced.
The ~20-second version:
"There are two mechanisms. Locking is pessimistic: a writer takes an exclusive lock and everyone else on that row waits — correct but it serialises access. MVCC keeps multiple versions of each row: when a transaction starts it gets a snapshot, and reads see the newest version committed before that point, following the undo log backwards if the current row is too new. So readers never block writers and writers never block readers — only writer-versus-writer still needs an exclusive lock. InnoDB and Postgres use both: MVCC for reads, row locks for writes. The catch with MVCC is long-running transactions — they pin an old snapshot so the purge/vacuum can't reclaim dead versions, and you get bloat. For a flash sale I don't rely on isolation alone: one atomic
UPDATE inventory SET stock = stock - 1 WHERE id = ? AND stock > 0and check rows-affected — no separate read, no race."
Follow-ups to expect:
- "Shared vs exclusive lock compatibility?" — Many S locks coexist; an X lock is incompatible with everything. S blocks a would-be writer; X blocks readers and writers.
- "What's a gap lock for?" — It locks the range between index values so no one can INSERT into it — that's how InnoDB stops phantoms at REPEATABLE READ.
- "Why are long transactions dangerous under MVCC specifically?" — Their snapshot keeps old row versions 'needed', so vacuum (Postgres) / purge (InnoDB undo) can't clean up → table/undo bloat → slower scans.
- "MVCC removes all locking?" — No. Writer-writer conflicts still serialise on exclusive row locks; MVCC only removes the reader-writer blocking.
- "Deadlock handling?" — The engine detects a cycle in the waits-for graph, rolls back the cheaper victim (
ERROR 1213), and the app retries with backoff.
Mistake to avoid: answering "I'd raise the isolation level to SERIALIZABLE" for a hot counter. That maximises contention. The scalable answers are an atomic single-statement update, counter sharding, or moving the increment to Redis / an event stream.
Quick Revision — 7 Lines
- Shared lock (S) = multiple readers allowed. Exclusive lock (X) = single writer, blocks all others.
- Row-level locking (InnoDB) >> Table-level locking (MyISAM) for concurrency.
- Gap locks + next-key locks prevent phantom inserts in MySQL REPEATABLE READ.
- MVCC = multiple row versions in undo log. Readers see snapshot, never blocked by writers.
- Writers in MVCC still acquire X locks — only reader-writer conflict is eliminated.
- Long transactions in MVCC = undo log bloat → performance degradation.
- Flash sale pattern: atomic UPDATE with WHERE stock > 0 — single statement, no separate read lock needed.
Quick-revision quiz
Question 1 of 18
The lock compatibility matrix: which combination is BLOCKED?