Concurrency Control

7 pages · ~5 min✓ Reviewed

Builds on Transactions and ACID. Next up: SQL vs NoSQL.

DBMSPage 1

Serializability Mental Model

1. Serializable and Conflicts

Serializable schedule: interleaved run whose result equals some serial (one-at-a-time) order
Conflict needs same item
Conflict needs different transactions
Conflict needs at least one write

Pair	Conflict?
R-R	never
R-W	yes
W-R	yes
W-W	yes

2. Precedence Graph Test

Conflict serializable: swap adjacent non-conflicting ops until the schedule is serial
Acyclic graph ⇒ conflict serializable; a cycle ⇒ not

Node per transaction
Edge Ti→TjTi op conflicts with and precedes Tj op
Look for cycle
Topological sortequivalent serial order

3. How Far It Goes

Conflict serializable ⊂ serializable
View serializable also admits blind writes
Engines enforce only the conflict form: cheap to test

Remember

R-R never conflicts. One cycle in the precedence graph means no equivalent serial order.

DBMSPage 2

Shared and Exclusive Locks

1. Lock Modes and Compatibility

S lock = read; many holders at once
X lock = write; one holder, blocks every S and X request
Blocked requester waits in the queue

Held \ Request	S	X
S	allowed	wait
X	wait	wait

2. Upgrade S→X

Upgrade succeeds only if no other transaction holds S
Two transactions upgrading the same item deadlock

1T1, T2 hold S(A)
2T1 asks X(A)waits for T2
3T2 asks X(A)waits for T1
4Deadlock

3. Locks Alone Are Not Enough

Unlocking right after each operation allows non-serializable runs
Lost update: both read, both write, one write vanishes
Unrepeatable read: a re-read sees another commit

Remember

Serializability depends on when locks are released, not just on S and X modes.

DBMSPage 3

Two-Phase Locking and Deadlocks

1. The 2PL Rule

Growing: only acquire locks
Shrinking: only release; after the first unlock, never lock again
Guarantees conflict serializability
Serial order = order of the lock points

Growingacquire only
Lock pointlast lock taken
Shrinkingrelease only

2. Strict 2PL

	Holds until commit/abort	Prevents
Strict 2PL	all X locks	dirty reads, cascading aborts
Rigorous (strong strict)	X and S locks	same, plus commit order = serial order

Real engines use strict or rigorous 2PL, not the basic form.

3. Deadlocks

2PL does not prevent deadlock: T1 holds A, wants B; T2 holds B, wants A
Detect: wait-for graph; on a cycle, abort a victim (cheapest or youngest)
Crude alternative: lock timeout
Prevent: one global lock order, so no cycle can form

Timestamp scheme	Older wants younger's lock	Younger wants older's lock
wait-die	Older waits	Younger dies
wound-wait	Older wounds younger	Younger waits

After a deadlock abort

The victim is rolled back. The application must retry the transaction.

DBMSPage 4

MVCC Snapshots

1. Versions, Not Overwrites

Every write makes a new row version stamped with its txn ID
Old versions are kept: heap (PostgreSQL) or undo log (InnoDB, Oracle)
InnoDB, Oracle: update in place; undo rebuilds old rows

Engine	New version	Old version
PostgreSQL	new tuple	heap
InnoDB	in-place update	undo log
Oracle	in-place update	undo log

2. Snapshots and Write Skew

Reader sees a snapshot from txn (or statement) start
No read locks: readers never block writers, nor writers readers
Same-row writes serialize on a row lock; second waits or fails
Write skew under snapshot isolation (PostgreSQL REPEATABLE READ, Oracle)

T1, T2 read2 doctors on call
T1 updates Aliceoff call
T2 updates Boboff call
Invariant broken0 on call

3. Cleanup and Fixes

Old versions pile up: VACUUM (PostgreSQL), purge (InnoDB)
A long-running txn pins old versions and bloats storage

True SERIALIZABLE: PostgreSQL SSI aborts one txn
SELECT ... FOR UPDATE on the rows read
A constraint that encodes the invariant

Retry

SSI aborts one txn: retry it.

DBMSPage 5

Optimistic Concurrency Control

1. What OCC Is

No locks while the transaction runs
Read, then compute on private copies
Validate at commit: abort on conflict

2. Three Phases

Readwork on local copy
Validatedid anyone change what I read or wrote?
Writeapply changes

3. Version Column Pattern

Add a version column; bump it on every update
WHERE version=? is the validate step
0 rows affected = conflict: re-read, retry

sql

UPDATE items
SET qty = qty - 1, version = version + 1
WHERE id = 7 AND version = 3;

0 rows means someone else bumped the version

4. Pessimistic vs OCC

	Pessimistic (2PL, `FOR UPDATE`)	OCC
Wins when	high contention	low contention, long think-time (web forms)
On conflict	waits for lock	aborts and retries
Cost	blocked waiters	wasted aborted work

Check the count

Always check rows affected; ignoring it silently loses updates. Bound retries and use backoff.

DBMSPage 6

Concurrency Control Cheat Sheet

1. Conflicts and Locks

Conflict = same item + different transactions + at least one write
Precedence graph acyclic ⇒ conflict serializable
Upgrade S→X on one item by two transactions ⇒ deadlock

Held / Asked	S	X
S	ok	wait
X	wait	wait

2. 2PL and Deadlocks

Growacquire only
Lock pointlast lock
Shrinkrelease only
CommitStrict: X held till here

Deadlock fix: global lock order
Or wait-for graph cycle ⇒ abort a victim
Always retry the aborted transaction

3. MVCC and OCC

MVCC: readers never block writers; old versions live in the heap (PostgreSQL) or undo (InnoDB, Oracle)
Snapshot isolation still allows write skew
Fix: SERIALIZABLE or SELECT ... FOR UPDATE

	Pessimistic locks	OCC + version column
Best for	hot rows	rare conflicts
Cost	waiting	wasted work

Check the count

UPDATE ... WHERE version=? hitting 0 rows = conflict. Re-read, retry with backoff.

DBMSPage 7

Check yourself

T1 and T2 each run R(A) then W(A), interleaved as R1, R2, W1, W2. Is this conflict serializable?

No: R1 before W2 gives T1→T2, and R2 before W1 gives T2→T1.
The precedence graph has a cycle, so no serial order matches (a lost update).

Two transactions both hold an S lock on row X, then each requests an X lock. What happens?

Each waits for the other's S lock to go: a deadlock.
The engine aborts a victim, and the application must retry it.

Under snapshot isolation, the rule is one doctor on call. Both see 2 on call and each sets their own row off. Result?

Both commit and nobody is on call: write skew.
They wrote different rows, so no write conflict. Fix: SERIALIZABLE or FOR UPDATE.