-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path08-concurrency.html
More file actions
457 lines (427 loc) · 46.1 KB
/
Copy path08-concurrency.html
File metadata and controls
457 lines (427 loc) · 46.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0">
<script>try{var t=localStorage.getItem("dbms-theme")||"dark";document.documentElement.setAttribute("data-theme",t)}catch(e){document.documentElement.setAttribute("data-theme","dark")}</script>
<title>Concurrency Control — DBMS Illustrated</title>
<link rel="stylesheet" href="../css/style.css">
<style>:root{--topic-color:#EC4899}</style>
</head>
<body>
<div class="reading-progress" id="reading-progress"></div>
<nav class="navbar">
<div class="navbar-inner">
<a class="navbar-brand" href="../index.html"><span class="brand-icon" style="color:var(--primary-soft)">◆</span>DBMS Illustrated</a>
<div class="navbar-links"><a href="../index.html#topics">All Topics</a></div>
<div class="navbar-actions"><button class="btn-icon" id="theme-toggle" title="Toggle theme">☼</button></div>
</div>
</nav>
<div class="container">
<div class="breadcrumb">
<a href="../index.html">Home</a><span class="breadcrumb-sep">›</span>
<a href="../index.html#topics">Course</a><span class="breadcrumb-sep">›</span>
<span>Concurrency Control</span>
</div>
<div class="topic-header">
<div class="topic-badge">Topic 08</div>
<h1>Concurrency <span class="accent">Control</span></h1>
<p class="subtitle">When thousands of users are reading and writing the same data at the same moment, how does the database keep everything correct? If two people try to buy the last item in stock at the same time, only one should succeed. This topic explains the strategies databases use to manage that safely — from simple locks to multi-version snapshots.</p>
<div class="company-badges">
<span class="badge">PostgreSQL MVCC</span><span class="badge">InnoDB 2PL</span>
<span class="badge">Oracle</span><span class="badge">CockroachDB SSI</span><span class="badge">MySQL</span>
</div>
</div>
<div class="at-a-glance reveal">
<h3>At a Glance</h3>
<ul>
<li><strong>2PL (Two-Phase Locking)</strong> — a strategy where each transaction first collects all the locks it needs (growing phase), then releases them all at the end (shrinking phase). This strict discipline prevents transactions from interfering with each other in ways that would give incorrect results.</li>
<li><strong>Shared lock (S)</strong> — multiple readers can hold shared locks on the same row simultaneously. <strong>Exclusive lock (X)</strong> — only one transaction can write; all others must wait. Intent locks are a shorthand signal at the table level so the database does not have to scan every row lock to check compatibility.</li>
<li><strong>Deadlock</strong> — when two transactions are each waiting for the other's lock and neither can proceed. The database detects this circular wait, picks one transaction as the victim, rolls it back, and lets the other proceed. Your application needs to retry on this error.</li>
<li><strong>MVCC</strong> — instead of using locks for reads, the database keeps multiple versions of each row. Readers always see a consistent snapshot from when their transaction started. Readers never block writers. Writers never block readers.</li>
<li><strong>Gap locks</strong> (MySQL InnoDB) — a lock placed on the space between index values, not on any actual row. This prevents other transactions from inserting new rows into a range you are reading, which stops phantom rows from appearing.</li>
</ul>
</div>
<!-- ── Core Concepts ──────────────────────────────────────── -->
<div class="section-label">Core Concepts</div>
<div class="mini-cards">
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Two-Phase Locking (2PL)</h4>
<p>Two-Phase Locking is a set of rules that prevents concurrent transactions from producing incorrect results. Phase one (growing): the transaction acquires all the locks it needs — on every row it reads or writes. It never releases any locks during this phase. Phase two (shrinking): when the transaction is done with all its work, it releases all locks at once (on commit or rollback). This two-phase discipline guarantees that no two concurrent transactions can produce results that would be impossible in a sequential world. The version used in real databases holds all locks until commit to avoid a problem where one transaction's rollback forces another to also rollback.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>MVCC</h4>
<p>Multi-Version Concurrency Control (MVCC) is the reason you can read data quickly on a busy database without waiting for writers to finish. Instead of locking a row when a writer updates it, the database keeps the old version for readers and creates a new version for the writer. A reader sees a consistent snapshot of the database from the moment their transaction started — even if other transactions are updating rows at the same time. Readers never block writers. Writers never block readers. PostgreSQL and Oracle use MVCC for all reads — no read locks needed.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Deadlock</h4>
<p>Imagine Transaction A is holding the lock on Row 1 and waiting for Row 2. At the same time, Transaction B is holding the lock on Row 2 and waiting for Row 1. Both are stuck waiting for each other — forever. This is a deadlock. The database detects it by checking for these circular waits. When found, it picks one transaction as the "victim," rolls it back (freeing its locks), and lets the other proceed. This is a normal occurrence in a busy database — your application code needs to catch the deadlock error and retry the transaction.</p>
</div>
<div class="mini-card">
<div class="mini-card-icon"></div>
<h4>Optimistic Concurrency</h4>
<p>Optimistic concurrency is based on the assumption that conflicts are rare. Instead of locking rows when you read them, you just read freely. When you are ready to save your changes, you check whether anyone else changed the same data while you were working. If no conflict — great, commit. If someone else changed it — abort and try again. This works very well when conflicts are unlikely (most reads), but is inefficient if many transactions are competing for the same rows (they all keep retrying). A common implementation is a "version number" column — you read the version, and when writing, check that the version is still the same.</p>
</div>
</div>
<!-- ── Lock Compatibility ──────────────────────────────────── -->
<div class="section-label">Lock Types</div>
<h2 class="section-title">Lock Compatibility Matrix</h2>
<p class="section-desc">Different lock types have different compatibility rules. The matrix determines whether a lock request can be granted immediately or must wait. InnoDB adds intent locks (IS, IX) at the table level to enable efficient table-level lock checks without scanning all row locks.</p>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Requester ↓ / Holder →</th><th>IS</th><th>IX</th><th>S</th><th>SIX</th><th>X</th></tr>
</thead>
<tbody>
<tr><td><strong>Intent Shared (IS)</strong></td><td style="color:#10B981">Yes</td><td style="color:#10B981">Yes</td><td style="color:#10B981">Yes</td><td style="color:#10B981">Yes</td><td style="color:#EF4444">No</td></tr>
<tr><td><strong>Intent Exclusive (IX)</strong></td><td style="color:#10B981">Yes</td><td style="color:#10B981">Yes</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td></tr>
<tr><td><strong>Shared (S)</strong></td><td style="color:#10B981">Yes</td><td style="color:#EF4444">No</td><td style="color:#10B981">Yes</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td></tr>
<tr><td><strong>Shared + IX (SIX)</strong></td><td style="color:#10B981">Yes</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td></tr>
<tr><td><strong>Exclusive (X)</strong></td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td><td style="color:#EF4444">No</td></tr>
</tbody>
</table>
</div>
<!-- ── Two-Phase Locking ──────────────────────────────────── -->
<div class="section-label">Two-Phase Locking</div>
<h2 class="section-title">2PL Protocol</h2>
<p class="section-desc">2PL divides a transaction's lifetime into two strictly separated phases: a growing phase where locks are only acquired (never released), and a shrinking phase where locks are only released (never acquired). This ordering constraint is sufficient to guarantee that any concurrent execution schedule is serializable.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Growing phase</h4>
<p>In the first phase, the transaction accumulates all the locks it needs. Reading a row requires a shared lock (others can also read, but no one can write). Writing requires an exclusive lock (no one else can read or write). If a transaction needs to upgrade from read to write on the same row, it waits until all other readers release their locks first. During this entire phase, no locks are ever released — only acquired.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Lock point</h4>
<p>The moment a transaction releases its first lock is called the lock point. After this moment, the transaction cannot acquire any new locks. The order in which transactions reach their lock points effectively defines the order in which they "happened." Two transactions that never overlap in their lock sets can run truly in parallel. Two that do overlap must take turns, and their lock points determine which one went first in the equivalent sequential execution.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Strict 2PL (used by real databases)</h4>
<p>In theory, a transaction could release some locks early while still running. But this creates a danger: another transaction could read the partially-released data, and if the first transaction later rolls back, that second transaction made decisions based on data that never officially existed. This chain of failures is called a cascading abort. To prevent it, real databases use Strict 2PL: all locks are held until the very end (commit or rollback), then released all at once. This is slightly more conservative but prevents cascading failures entirely.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">4</div>
<div>
<h4>Lock granularity</h4>
<p>Locks can be applied at different scales: the whole table, a page of rows, or a single row. Locking an entire table is simple but heavy — it blocks everyone while one transaction is running. Locking individual rows is more precise and allows multiple transactions to work on different rows at the same time. To avoid scanning every row-level lock when someone wants to lock the whole table, databases use intent locks — a quick signal at the table level that says "there are row locks in here," allowing fast compatibility checks without looking at every row.</p>
</div>
</div>
</div>
<!-- ── Gap and Next-Key Locks ─────────────────────────────── -->
<div class="section-label">InnoDB Locks</div>
<h2 class="section-title">Gap Locks and Next-Key Locks</h2>
<p class="section-desc">MySQL InnoDB at REPEATABLE READ uses gap locks to prevent phantom reads without requiring SERIALIZABLE isolation. A gap lock locks the gap between two index values — preventing any INSERT that would fall into that gap.</p>
<div class="steps">
<div class="step-item">
<div class="step-num">1</div>
<div>
<h4>Record lock</h4>
<p>A record lock targets exactly one row. When you run <code>SELECT * FROM t WHERE id = 10 FOR UPDATE</code>, the database places a lock on the row with id=10. No other transaction can update or delete that specific row while your transaction holds the lock. It does not block inserts of unrelated rows — only this one record is protected.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">2</div>
<div>
<h4>Gap lock</h4>
<p>A gap lock protects the empty space between existing index values. Imagine you are reading all orders with id between 10 and 20. A gap lock on that range prevents any other transaction from inserting a new order that would fall inside it. This stops phantom rows — rows that would appear if you re-ran the same query. Importantly, two transactions can both hold gap locks on the same range at the same time without conflicting, because they are both just preventing inserts, not modifying anything.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">3</div>
<div>
<h4>Next-key lock</h4>
<p>A next-key lock is a record lock and a gap lock combined into one. It protects a specific existing row AND the empty space just before it. When InnoDB scans a range of rows, it places next-key locks on each row it touches, plus the gap after the last one. The result: no other transaction can modify any of those rows, and no transaction can insert a new row that would appear in that range. It is InnoDB's default strategy for range scans.</p>
</div>
</div>
<div class="step-item">
<div class="step-num">4</div>
<div>
<h4>Deadlocks with gap locks</h4>
<p>Gap locks can create surprising deadlocks. Imagine two transactions each trying to insert a row next to the other's gap lock. Transaction A holds a gap lock that blocks B's insert, and transaction B holds a gap lock that blocks A's insert. Neither can move forward — a deadlock. InnoDB detects this circular standoff automatically, picks the younger transaction as the victim, rolls it back, and lets the other proceed. Your application should catch error 1213 (ER_LOCK_DEADLOCK) and retry the transaction.</p>
</div>
</div>
</div>
<!-- ── Deadlock Handling ──────────────────────────────────── -->
<div class="section-label">Deadlocks</div>
<h2 class="section-title">Deadlock Detection and Prevention</h2>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Strategy</th><th>How It Works</th><th>Pros</th><th>Cons</th></tr>
</thead>
<tbody>
<tr><td>Deadlock detection</td><td>Maintain wait-for graph; detect cycles periodically; abort victim</td><td>No unnecessary aborts; maximum concurrency</td><td>Cycles can exist briefly; detection adds overhead</td></tr>
<tr><td>Timeout</td><td>Abort any transaction waiting for a lock longer than N ms</td><td>Simple; no graph maintenance</td><td>False positives (slow transactions aborted unnecessarily)</td></tr>
<tr><td>Wait-Die</td><td>Older Tx waits for younger; younger Tx dies instead of waiting</td><td>No cycles possible; deterministic</td><td>Extra aborts of young transactions under high load</td></tr>
<tr><td>Wound-Wait</td><td>Older Tx forces younger Tx to abort (wound); younger Tx waits for older</td><td>Older (more important) transactions rarely abort</td><td>Younger transactions are aggressively killed</td></tr>
<tr><td>Lock ordering</td><td>Application always acquires locks in a fixed global order</td><td>Eliminates deadlocks entirely; no overhead</td><td>Requires disciplined coding across all code paths</td></tr>
</tbody>
</table>
</div>
<!-- ── Code Block ─────────────────────────────────────────── -->
<div class="code-block">
<div class="cb-header"><span class="cb-lang">SQL — Locking Patterns</span></div>
<pre><span class="cmt">-- Explicit row lock: SELECT FOR UPDATE (pessimistic)</span>
<span class="kw">BEGIN</span>;
<span class="kw">SELECT</span> balance <span class="kw">FROM</span> accounts <span class="kw">WHERE</span> id = <span class="num">42</span> <span class="kw">FOR UPDATE</span>; <span class="cmt">-- X lock on row 42</span>
<span class="kw">UPDATE</span> accounts <span class="kw">SET</span> balance = balance - <span class="num">100</span> <span class="kw">WHERE</span> id = <span class="num">42</span>;
<span class="kw">COMMIT</span>;
<span class="cmt">-- Shared lock: FOR SHARE (read-with-lock, no exclusive needed)</span>
<span class="kw">SELECT</span> * <span class="kw">FROM</span> orders <span class="kw">WHERE</span> id = <span class="num">99</span> <span class="kw">FOR SHARE</span>;
<span class="cmt">-- Other transactions can also take FOR SHARE; only FOR UPDATE blocks</span>
<span class="cmt">-- Skip locked rows: non-blocking job queue pattern</span>
<span class="kw">BEGIN</span>;
<span class="kw">SELECT</span> id, payload <span class="kw">FROM</span> job_queue
<span class="kw">WHERE</span> status = <span class="str">'pending'</span>
<span class="kw">ORDER BY</span> priority <span class="kw">DESC</span>, created_at
<span class="kw">LIMIT</span> <span class="num">1</span>
<span class="kw">FOR UPDATE SKIP LOCKED</span>; <span class="cmt">-- skip rows locked by other workers</span>
<span class="kw">UPDATE</span> job_queue <span class="kw">SET</span> status = <span class="str">'processing'</span>, worker_id = :wid
<span class="kw">WHERE</span> id = :id;
<span class="kw">COMMIT</span>;
<span class="cmt">-- Lock timeout: abort if lock not acquired within 2 seconds</span>
<span class="kw">SET</span> lock_timeout = <span class="str">'2s'</span>; <span class="cmt">-- PostgreSQL</span>
<span class="kw">SET</span> innodb_lock_wait_timeout = <span class="num">2</span>; <span class="cmt">-- MySQL</span>
<span class="cmt">-- Advisory lock: application-level mutex (PostgreSQL)</span>
<span class="kw">SELECT</span> <span class="fn">pg_advisory_xact_lock</span>(<span class="num">12345</span>); <span class="cmt">-- acquired until COMMIT/ROLLBACK</span>
<span class="kw">SELECT</span> <span class="fn">pg_try_advisory_xact_lock</span>(<span class="num">12345</span>); <span class="cmt">-- non-blocking; returns false if busy</span>
<span class="cmt">-- Optimistic locking with version column</span>
<span class="kw">BEGIN</span>;
<span class="kw">SELECT</span> balance, version <span class="kw">FROM</span> accounts <span class="kw">WHERE</span> id = <span class="num">42</span>;
<span class="cmt">-- application computes new_balance, reads version=7</span>
<span class="kw">UPDATE</span> accounts
<span class="kw">SET</span> balance = :new_balance, version = version + <span class="num">1</span>
<span class="kw">WHERE</span> id = <span class="num">42</span> <span class="kw">AND</span> version = <span class="num">7</span>;
<span class="cmt">-- if 0 rows updated, someone else modified it — retry</span>
<span class="kw">COMMIT</span>;</pre>
</div>
<!-- ── MVCC vs 2PL ────────────────────────────────────────── -->
<div class="section-label">MVCC vs 2PL</div>
<h2 class="section-title">MVCC Compared to Locking</h2>
<div class="table-wrap">
<table class="compare-table">
<thead>
<tr><th>Property</th><th>2PL (Strict)</th><th>MVCC (Snapshot Isolation)</th><th>SSI (Serializable SI)</th></tr>
</thead>
<tbody>
<tr><td>Reads block writers?</td><td style="color:#EF4444">Yes (shared lock)</td><td style="color:#10B981">No</td><td style="color:#10B981">No</td></tr>
<tr><td>Writers block readers?</td><td style="color:#EF4444">Yes (excl. lock)</td><td style="color:#10B981">No</td><td style="color:#10B981">No</td></tr>
<tr><td>Prevents write skew?</td><td style="color:#10B981">Yes (X lock)</td><td style="color:#EF4444">No</td><td style="color:#10B981">Yes (anti-dep tracking)</td></tr>
<tr><td>Prevents phantom reads?</td><td style="color:#10B981">Yes (predicate lock)</td><td style="color:#EF4444">Not always</td><td style="color:#10B981">Yes</td></tr>
<tr><td>Deadlocks possible?</td><td style="color:#EF4444">Yes</td><td style="color:#10B981">No (read-only paths)</td><td style="color:#F59E0B">Serialization aborts</td></tr>
<tr><td>Garbage collection</td><td>N/A</td><td style="color:#EF4444">VACUUM needed</td><td style="color:#EF4444">VACUUM needed</td></tr>
<tr><td>Used by</td><td>InnoDB (for writes), DB2</td><td>PostgreSQL, Oracle, SQL Server RCSI</td><td>PostgreSQL SERIALIZABLE, CockroachDB</td></tr>
</tbody>
</table>
</div>
<!-- ── Interactive Demo ───────────────────────────────────── -->
<div class="section-label">Interactive Demo</div>
<h2 class="section-title">Two-Phase Locking Visualizer</h2>
<p class="section-desc">Step through a 3-transaction, 5-resource locking scenario. Watch Shared and Exclusive locks fill the table. A deadlock cycle forms and triggers rollback of one victim.</p>
<div class="diagram-box">
<svg viewBox="0 0 700 230" role="img" aria-label="Two-phase locking: growing phase, shrinking phase, and deadlock wait-for graph">
<!-- Phase timeline -->
<text x="30" y="28" class="svg-soft">Lock Phases</text>
<line x1="30" y1="38" x2="670" y2="38" class="svg-line"/>
<!-- Growing phase -->
<rect x="30" y="48" width="270" height="38" rx="6" class="svg-box-p"/>
<text x="165" y="66" text-anchor="middle" class="svg-label">GROWING PHASE</text>
<text x="165" y="81" text-anchor="middle" class="svg-soft">acquire locks, never release</text>
<!-- Lock point -->
<line x1="300" y1="38" x2="300" y2="105" class="svg-line" style="stroke:#EF4444"/>
<text x="300" y="118" text-anchor="middle" class="svg-soft" style="fill:#EF4444">Lock Point</text>
<!-- Shrinking phase -->
<rect x="310" y="48" width="260" height="38" rx="6" class="svg-box-c"/>
<text x="440" y="66" text-anchor="middle" class="svg-label">SHRINKING PHASE</text>
<text x="440" y="81" text-anchor="middle" class="svg-soft">release locks, never acquire</text>
<!-- Lock table -->
<text x="30" y="148" class="svg-soft">Lock Table</text>
<rect x="30" y="155" width="80" height="22" rx="4" class="svg-box"/>
<text x="70" y="170" text-anchor="middle" class="svg-mono" style="font-size:10px">Resource</text>
<rect x="115" y="155" width="60" height="22" rx="4" class="svg-box-p"/>
<text x="145" y="170" text-anchor="middle" class="svg-mono" style="font-size:10px">T1</text>
<rect x="180" y="155" width="60" height="22" rx="4" class="svg-box-c"/>
<text x="210" y="170" text-anchor="middle" class="svg-mono" style="font-size:10px">T2</text>
<rect x="245" y="155" width="60" height="22" rx="4" class="svg-box-a"/>
<text x="275" y="170" text-anchor="middle" class="svg-mono" style="font-size:10px">T3</text>
<!-- Rows -->
<rect x="30" y="180" width="80" height="22" rx="4" class="svg-box"/><text x="70" y="195" text-anchor="middle" class="svg-mono" style="font-size:10px">Row A</text>
<rect x="115" y="180" width="60" height="22" rx="4" style="fill:rgba(124,58,237,0.25);stroke:#7C3AED;stroke-width:1.5;rx:4"/><text x="145" y="195" text-anchor="middle" class="svg-mono" style="font-size:10px">X</text>
<rect x="180" y="180" width="60" height="22" rx="4" style="fill:rgba(14,165,233,0.12);stroke:#0EA5E9;stroke-width:1.5;rx:4"/><text x="210" y="195" text-anchor="middle" class="svg-mono" style="font-size:10px">WAIT</text>
<rect x="30" y="205" width="80" height="22" rx="4" class="svg-box"/><text x="70" y="220" text-anchor="middle" class="svg-mono" style="font-size:10px">Row B</text>
<rect x="180" y="205" width="60" height="22" rx="4" style="fill:rgba(14,165,233,0.25);stroke:#0EA5E9;stroke-width:1.5;rx:4"/><text x="210" y="220" text-anchor="middle" class="svg-mono" style="font-size:10px">X</text>
<rect x="115" y="205" width="60" height="22" rx="4" style="fill:rgba(124,58,237,0.12);stroke:#7C3AED;stroke-width:1.5;rx:4"/><text x="145" y="220" text-anchor="middle" class="svg-mono" style="font-size:10px">WAIT</text>
<!-- Wait-for graph -->
<text x="420" y="148" class="svg-soft">Wait-For Graph</text>
<circle cx="460" cy="188" r="22" style="fill:rgba(124,58,237,0.18);stroke:#7C3AED;stroke-width:2"/>
<text x="460" cy="192" text-anchor="middle" dominant-baseline="middle" class="svg-label" y="192">T1</text>
<circle cx="580" cy="188" r="22" style="fill:rgba(14,165,233,0.18);stroke:#0EA5E9;stroke-width:2"/>
<text x="580" text-anchor="middle" dominant-baseline="middle" class="svg-label" y="192">T2</text>
<line x1="482" y1="178" x2="558" y2="178" class="svg-line" style="stroke:#EF4444"/>
<line x1="558" y1="198" x2="482" y2="198" class="svg-line" style="stroke:#EF4444"/>
<text x="520" y="168" text-anchor="middle" class="svg-soft" style="fill:#EF4444;font-size:10px">DEADLOCK</text>
<!-- Packets -->
<circle class="pkt" cx="115" cy="190" r="5" fill="#7C3AED"/>
<circle class="pkt" cx="180" cy="216" r="5" fill="#0EA5E9"/>
</svg>
<p class="diagram-caption">2PL prevents non-serializable schedules by ensuring all locks are acquired before any are released. The deadlock is a cycle in the wait-for graph — T1 holds Row A and waits for Row B; T2 holds Row B and waits for Row A. The DBMS picks a victim and rolls back.</p>
</div>
<div class="demo-section" id="demo-concurrency">
<div class="demo-header">
<h3>2PL Lock Table</h3>
<div class="demo-controls">
<button class="demo-btn" data-action="run-2pl" style="background:var(--topic-color);color:#fff;border-color:var(--topic-color)">Run Simulation</button>
<button class="demo-btn" data-action="reset-2pl">Reset</button>
</div>
</div>
<div class="demo-canvas-wrap"></div>
<div class="demo-hint">S = Shared lock, X = Exclusive lock. Red = deadlock cycle. One transaction will be rolled back as the victim.</div>
</div>
<!-- ── Anti-patterns ──────────────────────────────────────── -->
<div class="section-label">Anti-patterns</div>
<div class="antipatterns">
<div class="antipattern">
<h4>Acquiring locks in inconsistent order</h4>
<p>If T1 locks row A then row B, and T2 locks row B then row A, a deadlock is guaranteed under concurrent execution. Always acquire locks in a consistent global order across all code paths — ascending primary key, alphabetical table name, or any deterministic ordering. This is the single most effective deadlock prevention technique.</p>
</div>
<div class="antipattern">
<h4>Table-level locks for row-level operations</h4>
<p><code>LOCK TABLE orders IN EXCLUSIVE MODE</code> when a row-level <code>FOR UPDATE</code> would suffice blocks every reader and writer on the table. Row-level locking has dramatically higher concurrency. Use table-level locks only for DDL operations or bulk imports that genuinely need exclusive table access.</p>
</div>
<div class="antipattern">
<h4>Not handling deadlock errors in application code</h4>
<p>Deadlocks are a normal outcome of concurrent transactions, not a bug. The DBMS will abort one transaction with SQLSTATE 40P01 (PostgreSQL) or error 1213 (MySQL). Application code must catch this specific error and retry the entire transaction — not crash, not surface a 500 error to the user. Implement exponential backoff and a retry limit.</p>
</div>
<div class="antipattern">
<h4>Long gaps between SELECT and UPDATE</h4>
<p>SELECT FOR UPDATE locks the row. If application code runs long logic (API call, file I/O) between the SELECT and the UPDATE, the lock is held for the entire duration. Every other transaction waiting for that row queues up. Keep the locked read-modify-write operation in a single short transaction. Prepare all inputs before BEGIN.</p>
</div>
<div class="antipattern">
<h4>Using advisory locks as a substitute for proper ACID transactions</h4>
<p>Advisory locks (<code>pg_advisory_lock</code>) are application-level mutual exclusion that the database does not understand in terms of data correctness. Relying on advisory locks instead of proper row locking for data mutations means the DBMS cannot help with deadlock detection or automatic abort. Use row-level locks for data protection; use advisory locks only for coarse-grained application-level serialization (e.g., "only one migration runs at a time").</p>
</div>
</div>
<!-- ── Quiz ──────────────────────────────────────────────── -->
<div class="section-label">Quiz</div>
<div class="quiz-section">
<div class="quiz-question">
<div class="quiz-q-num">Question 1 of 5</div>
<div class="quiz-q-text">Two-phase locking (2PL) guarantees:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="2PL can still deadlock — deadlock freedom requires additional protocols like Wound-Wait or consistent lock ordering."><span class="opt-letter">A</span>Complete deadlock freedom</div>
<div class="quiz-option" data-correct="true" data-explanation="2PL guarantees that the execution schedule of concurrent transactions is equivalent to some serial execution — serializability. The two-phase constraint (growing then shrinking) ensures the serialization order is consistent with the lock-point order."><span class="opt-letter">B</span>Serializability of concurrent transactions</div>
<div class="quiz-option" data-correct="false" data-explanation="2PL reduces throughput due to lock contention — it does not maximize write throughput."><span class="opt-letter">C</span>Maximum possible write throughput</div>
<div class="quiz-option" data-correct="false" data-explanation="2PL can require rollback to handle deadlocks and serialization conflicts."><span class="opt-letter">D</span>Zero transaction rollbacks</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 2 of 5</div>
<div class="quiz-q-text">MVCC (Multi-Version Concurrency Control) primarily eliminates:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="MVCC doesn't eliminate all deadlocks — write-write conflicts between concurrent writers can still deadlock."><span class="opt-letter">A</span>All deadlocks in the system</div>
<div class="quiz-option" data-correct="true" data-explanation="MVCC stores multiple row versions so readers see a consistent snapshot without locking. Readers never block writers (they read the old version) and writers never block readers (they create a new version). This is the fundamental benefit of MVCC over 2PL."><span class="opt-letter">B</span>Reader-writer blocking — readers don't block writers and writers don't block readers</div>
<div class="quiz-option" data-correct="false" data-explanation="MVCC actually uses more storage than locking because it keeps multiple versions of each row."><span class="opt-letter">C</span>Extra storage usage from row versioning</div>
<div class="quiz-option" data-correct="false" data-explanation="MVCC does not prevent write-write conflicts — two writers on the same row still conflict."><span class="opt-letter">D</span>All write-write conflicts</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 3 of 5</div>
<div class="quiz-q-text">A phantom read occurs when:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Reading uncommitted data is a dirty read — a different anomaly."><span class="opt-letter">A</span>A transaction reads data not yet committed by another transaction</div>
<div class="quiz-option" data-correct="false" data-explanation="A specific row returning different values is a non-repeatable read — different from phantom."><span class="opt-letter">B</span>A specific row returns a different value when re-read within the same transaction</div>
<div class="quiz-option" data-correct="true" data-explanation="A phantom read is when a range query executed twice in the same transaction returns different SETS of rows — new rows inserted by another committed transaction appeared (or disappeared) between the two executions. Prevented only at SERIALIZABLE isolation."><span class="opt-letter">C</span>A range query returns different rows on re-execution within the same transaction</div>
<div class="quiz-option" data-correct="false" data-explanation="A mutual wait cycle is a deadlock — not a phantom read."><span class="opt-letter">D</span>Two transactions form a mutual wait cycle</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 4 of 5</div>
<div class="quiz-q-text">In MySQL InnoDB, a gap lock prevents:</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Gap locks do not prevent modification of existing rows — record locks do that."><span class="opt-letter">A</span>Updates to rows within the locked range</div>
<div class="quiz-option" data-correct="true" data-explanation="A gap lock locks the 'gap' between index values, preventing other transactions from inserting new rows that would fall into that range. This prevents phantom reads at REPEATABLE READ without needing SERIALIZABLE."><span class="opt-letter">B</span>Insertion of new rows into the gap between locked index values</div>
<div class="quiz-option" data-correct="false" data-explanation="Gap locks do not prevent reads — shared locks do that."><span class="opt-letter">C</span>Reads from any row in the table</div>
<div class="quiz-option" data-correct="false" data-explanation="Gap locks are index-range-specific, not table-wide."><span class="opt-letter">D</span>Any access to the table by other transactions</div>
</div>
<div class="quiz-feedback"></div>
</div>
<div class="quiz-question">
<div class="quiz-q-num">Question 5 of 5</div>
<div class="quiz-q-text">Which strategy completely eliminates deadlocks without aborting transactions unnecessarily?</div>
<div class="quiz-options">
<div class="quiz-option" data-correct="false" data-explanation="Detection is reactive — it finds deadlocks after they occur and aborts a victim."><span class="opt-letter">A</span>Deadlock detection (wait-for graph cycle detection)</div>
<div class="quiz-option" data-correct="false" data-explanation="Timeout-based abort is imprecise — slow (but not deadlocked) transactions are also aborted."><span class="opt-letter">B</span>Lock timeout (abort after N seconds)</div>
<div class="quiz-option" data-correct="true" data-explanation="Consistent global lock ordering eliminates deadlocks entirely: if all transactions always acquire locks in the same order (e.g., ascending PK), a cycle in the wait-for graph can never form. No unnecessary aborts, no detection overhead."><span class="opt-letter">C</span>Consistent global lock ordering across all transactions</div>
<div class="quiz-option" data-correct="false" data-explanation="Wound-Wait prevents cycles but aborts the younger transaction whenever it waits for an older one — more unnecessary aborts than lock ordering."><span class="opt-letter">D</span>Wound-Wait protocol</div>
</div>
<div class="quiz-feedback"></div>
</div>
</div>
<!-- ── Interview Q&A ──────────────────────────────────────── -->
<div class="section-label">Interview Q&A</div>
<div class="qa-section">
<div class="qa-item">
<div class="qa-q">Explain 2PL and why it guarantees serializability.<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Two-Phase Locking divides a transaction's lifetime into two phases: (1) <strong>Growing phase:</strong> acquire locks (S or X), never release. (2) <strong>Shrinking phase:</strong> release locks, never acquire. The lock point is the instant the first lock is released. The serialization order of concurrent transactions equals their lock-point order. Why? Because no transaction can acquire new locks after its lock point. If T1's lock point comes before T2's, T2 must have waited for T1 to release at least one lock before it could proceed — the schedule is equivalent to T1 running before T2. <strong>Strict 2PL:</strong> hold all locks until commit. This additionally prevents dirty reads and cascading aborts. Most databases use Strict 2PL.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">How does deadlock detection work and how do you prevent deadlocks in application code?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Detection: the DBMS maintains a wait-for graph — nodes are transactions, a directed edge T1→T2 means T1 is waiting for a lock held by T2. A cycle = deadlock. PostgreSQL runs a lightweight cycle check before sleeping on a lock wait. MySQL InnoDB checks for deadlocks on every lock acquisition. Victim selection: typically the youngest transaction (minimum work lost) or smallest number of locks held. Prevention in application code: (1) <strong>Consistent lock ordering</strong> across all code paths — always lock rows in ascending PK order. (2) <strong>Keep transactions short</strong> — reduce the overlap window. (3) <strong>Retry on error 40P01/1213</strong> with exponential backoff. (4) <strong>Never wait for external I/O</strong> while holding locks. (5) Set <code>lock_timeout</code> to fail fast rather than wait indefinitely.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is the difference between optimistic and pessimistic concurrency control?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner"><strong>Pessimistic:</strong> assume conflicts will happen — prevent them upfront with locks. Acquire locks before reading or writing data. No conflict possible during execution because other transactions are blocked. Release locks on commit. Best under high contention. <strong>Optimistic:</strong> assume conflicts are rare. Execute without any locking — read data, compute result, validate at commit that no conflict occurred (i.e., no read row was modified by another committed transaction since you read it). If conflict: abort and retry. Best under low contention. Wasted work under high contention. Implementations: <code>SELECT FOR UPDATE</code> is pessimistic; version-column optimistic locking (<code>UPDATE … WHERE version = :v</code>, fail if 0 rows updated) is optimistic. MVCC snapshot isolation is conceptually optimistic for reads (free reads), but pessimistic for write-write conflicts (still uses row locks). SSI is fully optimistic — even write conflicts are validated at commit.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is SELECT FOR UPDATE SKIP LOCKED and when would you use it?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner"><code>SELECT … FOR UPDATE SKIP LOCKED</code> acquires an exclusive lock on the selected rows but, instead of blocking on rows already locked by other transactions, silently skips them. Use case: database-backed job queues. Multiple workers each run: <code>SELECT id, payload FROM jobs WHERE status='pending' LIMIT 1 FOR UPDATE SKIP LOCKED</code>. Each worker atomically claims a different job — no two workers claim the same job, and they don't block each other. Without SKIP LOCKED, all workers would queue waiting for the first pending job, creating a thundering herd when that job is released. Supports throughput of roughly 1K–5K jobs/sec from PostgreSQL. For higher throughput, use a dedicated queue (Redis, Kafka, SQS).</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What is Serializable Snapshot Isolation (SSI) and how does it differ from MVCC snapshot isolation?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">MVCC Snapshot Isolation (SI): each transaction reads a snapshot frozen at start time. Writers create new versions. Provides: no dirty reads, no non-repeatable reads, no lost updates. Vulnerability: write skew (two transactions read overlapping data, write non-overlapping data, violate an invariant together). SSI (used in PostgreSQL's SERIALIZABLE, CockroachDB): builds on SI and adds tracking of read-write anti-dependencies. If T1's snapshot includes rows later written by T2, and T2's snapshot includes rows later written by T1, a dangerous rw-anti-dependency cycle exists — one must abort. Implemented via "predicate locks" (SIREAD locks) that track what was read. Benefit: reads never block; no row-level lock acquisition for reads. Cost: some false-positive aborts (transactions aborted conservatively when a cycle might exist). Performance overhead is low under low-conflict workloads.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">Explain intent locks and why databases need them.<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Without intent locks, checking whether a table-level lock can be granted requires scanning all existing row-level locks on that table — O(n) in the number of locked rows. Intent locks solve this with a two-level hierarchy. Before acquiring a row-level shared lock, a transaction acquires an Intent Shared (IS) lock on the table. Before acquiring a row-level exclusive lock, it acquires an Intent Exclusive (IX) lock on the table. To grant a full table S lock, the DBMS only checks if any IX lock exists on the table — O(1). IS and IX are compatible with each other (multiple transactions can have row-level locks on the same table simultaneously), but IX conflicts with S (can't take a table-level read lock when rows have exclusive locks) and X conflicts with everything. This makes lock management at scale efficient without sacrificing correctness.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">How does PostgreSQL advisory lock work and when should you use it?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">PostgreSQL advisory locks are application-defined locks using 64-bit integer keys — not tied to specific rows or tables. They exist only in the lock manager, not in data. Two forms: session-level (<code>pg_advisory_lock(key)</code>) — held until explicitly released or session ends; transaction-level (<code>pg_advisory_xact_lock(key)</code>) — automatically released at commit/rollback. Use cases: distributed mutex for background jobs ("only one instance of the nightly job runs at a time"); application-level resource locking when DB row locking is too granular; preventing concurrent schema migrations. Non-blocking variant: <code>pg_try_advisory_xact_lock(key)</code> returns false if already locked. Do NOT use advisory locks for row-level data protection — the DBMS won't enforce it and you bypass all deadlock detection and ACID guarantees for that data.</div></div>
</div>
<div class="qa-item">
<div class="qa-q">What happens when a lock timeout occurs versus a deadlock?<span class="qa-chevron">▾</span></div>
<div class="qa-a"><div class="qa-a-inner">Lock timeout: a transaction waits for a lock longer than the configured timeout (e.g., <code>SET lock_timeout = '2s'</code>). The waiting transaction is aborted with error code 55P03 (lock_timeout, PostgreSQL) — not the lock holder. The lock holder continues normally. Lock timeout is a blunt instrument — it aborts potentially non-deadlocked transactions. Deadlock: two or more transactions are mutually waiting with no way to proceed. The DBMS detects the cycle and aborts one transaction (the "victim") with 40P01. Application response to both: catch the error and retry the transaction. The distinction matters for which transaction to retry: on timeout, only the waiting transaction needs retry; on deadlock, only the victim transaction needs retry (the winner continues). Both are transient failures — retry with exponential backoff is the correct pattern.</div></div>
</div>
</div>
<div class="section-label">Further Reading</div>
<div class="reading-links">
<a class="reading-link" href="https://www.postgresql.org/docs/current/explicit-locking.html" target="_blank">PostgreSQL Explicit Locking</a>
<a class="reading-link" href="https://www.postgresql.org/docs/current/transaction-iso.html" target="_blank">PostgreSQL Transaction Isolation</a>
<a class="reading-link" href="https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html" target="_blank">InnoDB Locking (MySQL Docs)</a>
<a class="reading-link" href="https://dl.acm.org/doi/10.1145/2168836.2168853" target="_blank">Serializable Snapshot Isolation Paper (Ports, Grittner 2012)</a>
</div>
<div class="topic-nav">
<a href="07-query-processing.html" class="topic-nav-link"><div class="topic-nav-arrow">←</div><div><div class="topic-nav-label">Previous</div><div class="topic-nav-title">Query Processing</div></div></a>
<a href="09-storage-engines.html" class="topic-nav-link next"><div class="topic-nav-arrow">→</div><div><div class="topic-nav-label">Next</div><div class="topic-nav-title">Storage Engines</div></div></a>
</div>
</div>
<footer class="site-footer">
<p class="footer-sub"><a href="../index.html">Back to Course</a> — DBMS Illustrated</p>
</footer>
<script src="../js/main.js"></script>
<script src="../js/demos.js"></script>
</body>
</html>