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
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
|
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Locks, Blocks, and Deadlocks</title>
<link rel="stylesheet" href="gettingStarted.css" type="text/css" />
<meta name="generator" content="DocBook XSL Stylesheets V1.73.2" />
<link rel="start" href="index.html" title="Getting Started with Berkeley DB Transaction Processing" />
<link rel="up" href="txnconcurrency.html" title="Chapter 4. Concurrency" />
<link rel="prev" href="txnconcurrency.html" title="Chapter 4. Concurrency" />
<link rel="next" href="lockingsubsystem.html" title="The Locking Subsystem" />
</head>
<body>
<div xmlns="" class="navheader">
<div class="libver">
<p>Library Version 11.2.5.3</p>
</div>
<table width="100%" summary="Navigation header">
<tr>
<th colspan="3" align="center">Locks, Blocks, and Deadlocks</th>
</tr>
<tr>
<td width="20%" align="left"><a accesskey="p" href="txnconcurrency.html">Prev</a> </td>
<th width="60%" align="center">Chapter 4. Concurrency</th>
<td width="20%" align="right"> <a accesskey="n" href="lockingsubsystem.html">Next</a></td>
</tr>
</table>
<hr />
</div>
<div class="sect1" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h2 class="title" style="clear: both"><a id="blocking_deadlocks"></a>Locks, Blocks, and Deadlocks</h2>
</div>
</div>
</div>
<div class="toc">
<dl>
<dt>
<span class="sect2">
<a href="blocking_deadlocks.html#locks">Locks</a>
</span>
</dt>
<dt>
<span class="sect2">
<a href="blocking_deadlocks.html#blocks">Blocks</a>
</span>
</dt>
<dt>
<span class="sect2">
<a href="blocking_deadlocks.html#deadlocks">Deadlocks</a>
</span>
</dt>
</dl>
</div>
<p>
It is important to understand how locking works in a
concurrent application before continuing with a description of
the concurrency mechanisms DB makes available to you.
Blocking and deadlocking have important performance implications
for your application. Consequently, this section provides a
fundamental description of these concepts, and how they affect
DB operations.
</p>
<div class="sect2" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h3 class="title"><a id="locks"></a>Locks</h3>
</div>
</div>
</div>
<p>
When one thread of control wants to obtain access to an
object, it requests a <span class="emphasis"><em>lock</em></span> for that
object. This lock is what allows DB to provide your
application with its transactional isolation guarantees by
ensuring that:
</p>
<div class="itemizedlist">
<ul type="disc">
<li>
<p>
no other thread of control can read that object (in
the case of an exclusive lock), and
</p>
</li>
<li>
<p>
no other thread of control can modify that object
(in the case of an exclusive or non-exclusive lock).
</p>
</li>
</ul>
</div>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="lockresources"></a>Lock Resources</h4>
</div>
</div>
</div>
<p>
When locking occurs, there are conceptually three resources
in use:
</p>
<div class="orderedlist">
<ol type="1">
<li>
<p>
The locker.
</p>
<p>
This is the thing that holds the lock. In a
transactional application, the locker is a
transaction handle.
<span>
For non-transactional operations, the locker is a cursor or a
<span>Database or Store</span>
handle.
</span>
</p>
</li>
<li>
<p>
The lock.
</p>
<p>
This is the actual data structure that locks
the object. In DB, a locked
object structure in the lock manager
is representative of the object that
is locked.
</p>
</li>
<li>
<p>
The locked object.
</p>
<p>
The thing that your application
actually wants to lock.
In a DB
application, the locked object is usually a
<span>
database page, which in turn contains
multiple database entries (key and data).
<span>
However, for Queue databases,
individual database records are locked.
</span>
</span>
</p>
</li>
</ol>
</div>
<p>
You can configure how many total lockers, locks,
and locked objects your
application is allowed to support. See
<a class="xref" href="lockingsubsystem.html#configuringlock" title="Configuring the Locking Subsystem">Configuring the Locking Subsystem</a>
for details.
</p>
<p>
The following figure shows a transaction handle,
<code class="literal">Txn A</code>, that is holding a lock on
database
<span>page</span>
<code class="literal">002</code>. In this graphic, <code class="literal">Txn
A</code> is the locker, and the locked object is
<span>page</span>
<code class="literal">002</code>. Only a single lock is in use
in this operation.
</p>
<div class="mediaobject">
<img src="simplelock.jpg" />
</div>
</div>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="locktypes"></a>Types of Locks</h4>
</div>
</div>
</div>
<p>
DB applications support both exclusive and
non-exclusive locks. <span class="emphasis"><em>Exclusive
locks</em></span> are granted when a
locker wants to write to an object. For this reason,
exclusive locks are also sometimes called
<span class="emphasis"><em>write locks</em></span>.
</p>
<p>
An exclusive lock prevents any other locker from
obtaining any sort of a lock on the object. This
provides isolation by ensuring that no other locker can
observe or modify an exclusively locked object until the locker is done
writing to that object.
</p>
<p>
<span class="emphasis"><em>Non-exclusive locks</em></span> are granted
for read-only access. For this reason, non-exclusive
locks are also sometimes called <span class="emphasis"><em>read
locks</em></span>. Since multiple lockers can
simultaneously hold read locks on the same
object, read locks are also
sometimes called <span class="emphasis"><em>shared locks</em></span>.
</p>
<p>
A non-exclusive lock prevents any other locker from
modifying the locked object while the locker is still
reading the object. This is how transactional cursors are able to
achieve repeatable reads; by default, the
cursor's transaction holds
a read lock on any object that the cursor has examined until
such a time as the transaction is committed
or aborted.
<span>
You can avoid these read locks by using
snapshot isolation. See <a class="xref" href="isolation.html#snapshot_isolation" title="Using Snapshot Isolation">Using Snapshot Isolation</a>
for details.
</span>
</p>
<p>
In the following figure, <code class="literal">Txn A</code> and
<code class="literal">Txn B</code> are both holding read locks on
<span>page</span>
<code class="literal">002</code>, while <code class="literal">Txn C</code>
is holding a write lock on
<span>page</span>
<code class="literal">003</code>:
</p>
<div class="mediaobject">
<img src="rwlocks1.jpg" />
</div>
</div>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="locklifetime"></a>Lock Lifetime</h4>
</div>
</div>
</div>
<p>
A locker holds its locks until such a time as it does
not need the lock any more. What this means is:
</p>
<div class="orderedlist">
<ol type="1">
<li>
<p>
A transaction holds any locks that it obtains
until the transaction is committed or aborted.
</p>
</li>
<li>
<p>
All non-transaction operations hold locks
until such a time as the operation is completed.
For cursor operations, the lock is held until the cursor is moved to a new position or
closed.
</p>
</li>
</ol>
</div>
</div>
</div>
<div class="sect2" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h3 class="title"><a id="blocks"></a>Blocks</h3>
</div>
</div>
</div>
<p>
Simply put, a thread of control is blocked when it attempts
to obtain a lock, but that attempt is denied because some
other thread of control holds a conflicting lock.
Once blocked, the thread of control is temporarily unable
to make any forward progress until the requested lock is
obtained or the operation requesting the lock is
abandoned.
</p>
<p>
Be aware that when we talk about blocking, strictly
speaking the thread is not what is attempting to obtain the
lock. Rather, some object within the thread (such as a
cursor) is attempting to obtain the
lock. However, once a locker attempts to
obtain a lock, the entire thread of control must pause until the lock
request is in some way resolved.
</p>
<p>
For example, if <code class="literal">Txn A</code> holds a write lock (an exclusive
lock) on
<span>object</span>
002, then if <code class="literal">Txn B</code> tries to obtain a read <span class="emphasis"><em>or</em></span> write lock on
that
<span>object,</span>
the thread of control in which <code class="literal">Txn
B</code> is running
is blocked:
</p>
<div class="mediaobject">
<img src="writeblock.jpg" />
</div>
<p>
However, if <code class="literal">Txn A</code> only holds a read
lock (a shared lock) on
<span>object</span>
<code class="literal">002</code>, then only those handles that attempt to obtain a
write lock on that
<span>object</span>
will block.
</p>
<div class="mediaobject">
<img src="readblock.jpg" />
</div>
<div class="note" style="margin-left: 0.5in; margin-right: 0.5in;">
<h3 class="title">Note</h3>
<p>
The previous description describes DB's default
behavior when it cannot obtain a lock. It is
possible to configure DB transactions so that
they will not block. Instead, if a lock is
unavailable, the application is immediately notified of a
deadlock situation. See <a class="xref" href="txnnowait.html" title="No Wait on Blocks">No Wait on Blocks</a>
for more information.
</p>
</div>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="blockperformance"></a>Blocking and Application Performance</h4>
</div>
</div>
</div>
<p>
Multi-threaded
<span>
and multi-process
</span>
applications typically perform better than simple
single-threaded applications because the
application can perform one part of its workload
(updating
<span>a database record, </span>
for example) while it is waiting for some other
lengthy operation to complete (performing disk or
network I/O, for example). This performance
improvement is particularly noticeable if you use
hardware that offers multiple CPUs, because the threads
<span>
and processes
</span>
can run simultaneously.
</p>
<p>
That said, concurrent applications can see reduced
workload throughput if their threads of control are
seeing a large amount of lock contention. That is,
if threads are blocking on lock requests, then that
represents a performance penalty for your
application.
</p>
<p>
Consider once again the previous diagram of a blocked write lock request.
In that diagram, <code class="literal">Txn C</code> cannot
obtain its requested write lock because
<code class="literal">Txn A</code> and <code class="literal">Txn
B</code> are both already holding read locks on
the requested
<span>object.</span>
In this case, the thread in which
<code class="literal">Txn C</code> is running will pause until
such a time as <code class="literal">Txn C</code> either
obtains its write lock, or the operation
that is requesting the lock is abandoned.
The fact that <code class="literal">Txn
C</code>'s thread has temporarily halted all
forward progress represents a performance penalty
for your application.
</p>
<p>
Moreover, any read locks that are requested while
<code class="literal">Txn C</code> is waiting for its write
lock will also block until such a time as
<code class="literal">Txn C</code> has obtained and
subsequently released its write lock.
</p>
</div>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="blockavoidance"></a>Avoiding Blocks</h4>
</div>
</div>
</div>
<p>
Reducing lock contention is an important part of
performance tuning your concurrent DB
application. Applications that have multiple
threads of control obtaining exclusive (write)
locks are prone to contention issues. Moreover, as
you increase the numbers of lockers and as you
increase the time that a lock is held, you increase
the chances of your application seeing lock contention.
</p>
<p>
As you are designing your application, try to do
the following in order to reduce lock contention:
</p>
<div class="itemizedlist">
<ul type="disc">
<li>
<p>
Reduce the length of time your application
holds locks.
</p>
<p>
Shorter lived transactions will result in
shorter lock lifetimes, which will in turn
help to reduce lock contention.
</p>
<p>
In addition, by default transactional cursors hold read
locks until such a time as the transaction is completed.
For this reason, try to minimize the time you keep
transactional cursors opened, or reduce your isolation
levels – see below.
</p>
</li>
<li>
<p>
If possible, access heavily accessed (read
or write) items toward the end of the
transaction. This reduces the amount of
time that a heavily used
<span>
page
</span>
is locked by the transaction.
</p>
</li>
<li>
<p>
Reduce your application's isolation guarantees.
</p>
<p>
By reducing your isolation guarantees, you
reduce the situations in which a lock can
block another lock. Try using uncommitted reads
for your read operations in order to
prevent a read lock being blocked by a
write lock.
</p>
<p>
In addition, for cursors you can use degree
2 (read committed) isolation, which causes
the cursor to release its read locks as
soon as it is done reading the record (as
opposed to holding its read locks until the
transaction ends).
</p>
<p>
Be aware that reducing your
isolation guarantees can have
adverse consequences for your
application. Before deciding
to reduce your isolation, take
care to examine your
application's isolation
requirements.
For information on isolation
levels, see
<a class="xref" href="isolation.html" title="Isolation">Isolation</a>.
</p>
</li>
<li>
<p>
Use snapshot isolation for
read-only threads.
</p>
<p>
Snapshot isolation causes the
transaction to make a copy of the
page on which it is holding a lock.
When a reader makes a copy of a
page, write locks can still be
obtained for the original page.
This eliminates entirely read-write
contention.
</p>
<p>
Snapshot isolation is described in
<a class="xref" href="isolation.html#snapshot_isolation" title="Using Snapshot Isolation">Using Snapshot Isolation</a>.
</p>
</li>
<li>
<p>
Consider your data access patterns.
</p>
<p>
Depending on the nature of your application,
this may be something that you can not
do anything about. However, if it is
possible to create your threads such that
they operate only on non-overlapping
portions of your database, then you can
reduce lock contention because your
threads will rarely (if ever) block on one another's
locks.
</p>
</li>
</ul>
</div>
<div class="note" style="margin-left: 0.5in; margin-right: 0.5in;">
<h3 class="title">Note</h3>
<p>
It is possible to configure DB's transactions
so that they never wait on blocked lock requests.
Instead, if they are blocked on a lock request,
they will notify the application of a deadlock (see
the next section).
</p>
<p>
You configure this behavior on a transaction by
transaction basis. See <a class="xref" href="txnnowait.html" title="No Wait on Blocks">No Wait on Blocks</a> for more information.
</p>
</div>
</div>
</div>
<div class="sect2" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h3 class="title"><a id="deadlocks"></a>Deadlocks</h3>
</div>
</div>
</div>
<p>
A deadlock occurs when two or more threads of control are
blocked, each waiting on a resource held by the other
thread. When this happens, there is no
possibility of the threads ever making forward progress
unless some outside agent takes action to break the
deadlock.
</p>
<p>
For example, if
<code class="literal">Txn A</code> is
blocked by <code class="literal">Txn B</code> at the same time
<code class="literal">Txn B</code> is blocked by <code class="literal">Txn
A</code> then the threads of control containing
<code class="literal">Txn A</code> and <code class="literal">Txn B</code> are
deadlocked; neither thread can make
any forward progress because neither thread will ever release the lock
that is blocking the other thread.
</p>
<div class="mediaobject">
<img src="deadlock.jpg" />
</div>
<p>
When two threads of control deadlock, the only
solution is to have a mechanism external to the two threads
capable of recognizing the deadlock and notifying at least
one thread that it is in a deadlock situation.
Once notified, a thread of
control must abandon the attempted operation in order to
resolve the deadlock.
<span>
DB's locking subsystem offers a deadlock notification
mechanism. See
<a class="xref" href="lockingsubsystem.html#configdeadlkdetect" title="Configuring Deadlock Detection">Configuring Deadlock Detection</a>
for more information.
</span>
</p>
<p>
Note that when one locker in a thread of control is blocked
waiting on a lock held by another locker in that same
thread of the control, the thread is said to be
<span class="emphasis"><em>self-deadlocked</em></span>.
</p>
<div class="sect3" lang="en" xml:lang="en">
<div class="titlepage">
<div>
<div>
<h4 class="title"><a id="deadlockavoidance"></a>Deadlock Avoidance</h4>
</div>
</div>
</div>
<p>
The things that you do to avoid lock contention also
help to reduce deadlocks (see <a class="xref" href="blocking_deadlocks.html#blockavoidance" title="Avoiding Blocks">Avoiding Blocks</a>).
<span>
Beyond that, you can also do the following in order to
avoid deadlocks:
</span>
</p>
<div class="itemizedlist">
<ul type="disc">
<li>
<p>
Never have more than one active transaction at
a time in a thread. A common cause of this is
for a thread to be using auto-commit for one
operation while an explicit transaction is in
use in that thread at the same time.
</p>
</li>
<li>
<p>
Make sure all threads access data in the same
order as all other threads. So long as threads
lock database pages
in the same basic order, there is no
possibility of a deadlock (threads can still
block, however).
</p>
<p>
Be aware that if you are using secondary
databases (indexes), it is not possible to
obtain locks in a consistent order because you
cannot predict the order in which locks are
obtained in secondary databases. If you are
writing a concurrent application and you are
using secondary databases, you must be prepared
to handle deadlocks.
</p>
</li>
<li>
<p>
If you are using BTrees in which you are
constantly adding and then deleting data, turn
Btree reverse split off. See
<a class="xref" href="reversesplit.html" title="Reverse BTree Splits">Reverse BTree Splits</a>
for more information.
</p>
</li>
<li>
<p>
Declare a read/modify/write lock for those
situations where you are reading a record in
preparation of modifying and then writing the
record. Doing this causes DB to give your
read operation a write lock. This means that no
other thread of control can share a read lock
(which might cause contention), but it also
means that the writer thread will not have to
wait to obtain a write lock when it is ready to
write the modified data back to the database.
</p>
<p>
For information on declaring
read/modify/write locks, see
<a class="xref" href="readmodifywrite.html" title="Read/Modify/Write">Read/Modify/Write</a>.
</p>
</li>
</ul>
</div>
</div>
</div>
</div>
<div class="navfooter">
<hr />
<table width="100%" summary="Navigation footer">
<tr>
<td width="40%" align="left"><a accesskey="p" href="txnconcurrency.html">Prev</a> </td>
<td width="20%" align="center">
<a accesskey="u" href="txnconcurrency.html">Up</a>
</td>
<td width="40%" align="right"> <a accesskey="n" href="lockingsubsystem.html">Next</a></td>
</tr>
<tr>
<td width="40%" align="left" valign="top">Chapter 4. Concurrency </td>
<td width="20%" align="center">
<a accesskey="h" href="index.html">Home</a>
</td>
<td width="40%" align="right" valign="top"> The Locking Subsystem</td>
</tr>
</table>
</div>
</body>
</html>
|
