1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml"> 4 <head> 5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> 6 <title>Locks, Blocks, and Deadlocks</title> 7 <link rel="stylesheet" href="gettingStarted.css" type="text/css" /> 8 <meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /> 9 <link rel="start" href="index.html" title="Getting Started with Berkeley DB Transaction Processing" /> 10 <link rel="up" href="txnconcurrency.html" title="Chapter 4. Concurrency" /> 11 <link rel="prev" href="txnconcurrency.html" title="Chapter 4. Concurrency" /> 12 <link rel="next" href="lockingsubsystem.html" title="The Locking Subsystem" /> 13 </head> 14 <body> 15 <div class="navheader"> 16 <table width="100%" summary="Navigation header"> 17 <tr> 18 <th colspan="3" align="center">Locks, Blocks, and Deadlocks</th> 19 </tr> 20 <tr> 21 <td width="20%" align="left"><a accesskey="p" href="txnconcurrency.html">Prev</a> </td> 22 <th width="60%" align="center">Chapter 4. Concurrency</th> 23 <td width="20%" align="right"> <a accesskey="n" href="lockingsubsystem.html">Next</a></td> 24 </tr> 25 </table> 26 <hr /> 27 </div> 28 <div class="sect1" lang="en" xml:lang="en"> 29 <div class="titlepage"> 30 <div> 31 <div> 32 <h2 class="title" style="clear: both"><a id="blocking_deadlocks"></a>Locks, Blocks, and Deadlocks</h2> 33 </div> 34 </div> 35 </div> 36 <div class="toc"> 37 <dl> 38 <dt> 39 <span class="sect2"> 40 <a href="blocking_deadlocks.html#locks">Locks</a> 41 </span> 42 </dt> 43 <dt> 44 <span class="sect2"> 45 <a href="blocking_deadlocks.html#blocks">Blocks</a> 46 </span> 47 </dt> 48 <dt> 49 <span class="sect2"> 50 <a href="blocking_deadlocks.html#deadlocks">Deadlocks</a> 51 </span> 52 </dt> 53 </dl> 54 </div> 55 <p> 56 It is important to understand how locking works in a 57 concurrent application before continuing with a description of 58 the concurrency mechanisms DB makes available to you. 59 Blocking and deadlocking have important performance implications 60 for your application. Consequently, this section provides a 61 fundamental description of these concepts, and how they affect 62 DB operations. 63 </p> 64 <div class="sect2" lang="en" xml:lang="en"> 65 <div class="titlepage"> 66 <div> 67 <div> 68 <h3 class="title"><a id="locks"></a>Locks</h3> 69 </div> 70 </div> 71 </div> 72 <p> 73 When one thread of control wants to obtain access to an 74 object, it requests a <span class="emphasis"><em>lock</em></span> for that 75 object. This lock is what allows DB to provide your 76 application with its transactional isolation guarantees by 77 ensuring that: 78 </p> 79 <div class="itemizedlist"> 80 <ul type="disc"> 81 <li> 82 <p> 83 no other thread of control can read that object (in 84 the case of an exclusive lock), and 85 </p> 86 </li> 87 <li> 88 <p> 89 no other thread of control can modify that object 90 (in the case of an exclusive or non-exclusive lock). 91 </p> 92 </li> 93 </ul> 94 </div> 95 <div class="sect3" lang="en" xml:lang="en"> 96 <div class="titlepage"> 97 <div> 98 <div> 99 <h4 class="title"><a id="lockresources"></a>Lock Resources</h4> 100 </div> 101 </div> 102 </div> 103 <p> 104 When locking occurs, there are conceptually three resources 105 in use: 106 </p> 107 <div class="orderedlist"> 108 <ol type="1"> 109 <li> 110 <p> 111 The locker. 112 </p> 113 <p> 114 This is the thing that holds the lock. In a 115 transactional application, the locker is a 116 transaction handle. 117 <span> 118 For non-transactional operations, the locker is a cursor or a 119 120 121 <span>Database or Store</span> 122 123 handle. 124 </span> 125 126 </p> 127 </li> 128 <li> 129 <p> 130 The lock. 131 </p> 132 <p> 133 This is the actual data structure that locks 134 the object. In DB, a locked 135 object structure in the lock manager 136 is representative of the object that 137 is locked. 138 </p> 139 </li> 140 <li> 141 <p> 142 The locked object. 143 </p> 144 <p> 145 The thing that your application 146 actually wants to lock. 147 In a DB 148 application, the locked object is usually a 149 <span> 150 database page, which in turn contains 151 multiple database entries (key and data). 152 <span> 153 However, for Queue databases, 154 individual database records are locked. 155 </span> 156 157 </span> 158 159 </p> 160 </li> 161 </ol> 162 </div> 163 <p> 164 You can configure how many total lockers, locks, 165 and locked objects your 166 application is allowed to support. See 167 <a class="xref" href="lockingsubsystem.html#configuringlock" title="Configuring the Locking Subsystem">Configuring the Locking Subsystem</a> 168 for details. 169 </p> 170 <p> 171 The following figure shows a transaction handle, 172 <code class="literal">Txn A</code>, that is holding a lock on 173 database 174 <span>page</span> 175 176 <code class="literal">002</code>. In this graphic, <code class="literal">Txn 177 A</code> is the locker, and the locked object is 178 <span>page</span> 179 180 <code class="literal">002</code>. Only a single lock is in use 181 in this operation. 182 </p> 183 <div class="mediaobject"> 184 <img src="simplelock.jpg" /> 185 </div> 186 </div> 187 <div class="sect3" lang="en" xml:lang="en"> 188 <div class="titlepage"> 189 <div> 190 <div> 191 <h4 class="title"><a id="locktypes"></a>Types of Locks</h4> 192 </div> 193 </div> 194 </div> 195 <p> 196 DB applications support both exclusive and 197 non-exclusive locks. <span class="emphasis"><em>Exclusive 198 locks</em></span> are granted when a 199 locker wants to write to an object. For this reason, 200 exclusive locks are also sometimes called 201 <span class="emphasis"><em>write locks</em></span>. 202 </p> 203 <p> 204 An exclusive lock prevents any other locker from 205 obtaining any sort of a lock on the object. This 206 provides isolation by ensuring that no other locker can 207 observe or modify an exclusively locked object until the locker is done 208 writing to that object. 209 </p> 210 <p> 211 <span class="emphasis"><em>Non-exclusive locks</em></span> are granted 212 for read-only access. For this reason, non-exclusive 213 locks are also sometimes called <span class="emphasis"><em>read 214 locks</em></span>. Since multiple lockers can 215 simultaneously hold read locks on the same 216 object, read locks are also 217 sometimes called <span class="emphasis"><em>shared locks</em></span>. 218 </p> 219 <p> 220 A non-exclusive lock prevents any other locker from 221 modifying the locked object while the locker is still 222 reading the object. This is how transactional cursors are able to 223 achieve repeatable reads; by default, the 224 cursor's transaction holds 225 a read lock on any object that the cursor has examined until 226 such a time as the transaction is committed 227 or aborted. 228 <span> 229 You can avoid these read locks by using 230 snapshot isolation. See <a class="xref" href="isolation.html#snapshot_isolation" title="Using Snapshot Isolation">Using Snapshot Isolation</a> 231 for details. 232 </span> 233 </p> 234 <p> 235 In the following figure, <code class="literal">Txn A</code> and 236 <code class="literal">Txn B</code> are both holding read locks on 237 <span>page</span> 238 239 <code class="literal">002</code>, while <code class="literal">Txn C</code> 240 is holding a write lock on 241 <span>page</span> 242 243 <code class="literal">003</code>: 244 </p> 245 <div class="mediaobject"> 246 <img src="rwlocks1.jpg" /> 247 </div> 248 </div> 249 <div class="sect3" lang="en" xml:lang="en"> 250 <div class="titlepage"> 251 <div> 252 <div> 253 <h4 class="title"><a id="locklifetime"></a>Lock Lifetime</h4> 254 </div> 255 </div> 256 </div> 257 <p> 258 A locker holds its locks until such a time as it does 259 not need the lock any more. What this means is: 260 </p> 261 <div class="orderedlist"> 262 <ol type="1"> 263 <li> 264 <p> 265 A transaction holds any locks that it obtains 266 until the transaction is committed or aborted. 267 </p> 268 </li> 269 <li> 270 <p> 271 All non-transaction operations hold locks 272 until such a time as the operation is completed. 273 For cursor operations, the lock is held until the cursor is moved to a new position or 274 closed. 275 </p> 276 </li> 277 </ol> 278 </div> 279 </div> 280 </div> 281 <div class="sect2" lang="en" xml:lang="en"> 282 <div class="titlepage"> 283 <div> 284 <div> 285 <h3 class="title"><a id="blocks"></a>Blocks</h3> 286 </div> 287 </div> 288 </div> 289 <p> 290 Simply put, a thread of control is blocked when it attempts 291 to obtain a lock, but that attempt is denied because some 292 other thread of control holds a conflicting lock. 293 Once blocked, the thread of control is temporarily unable 294 to make any forward progress until the requested lock is 295 obtained or the operation requesting the lock is 296 abandoned. 297 </p> 298 <p> 299 Be aware that when we talk about blocking, strictly 300 speaking the thread is not what is attempting to obtain the 301 lock. Rather, some object within the thread (such as a 302 cursor) is attempting to obtain the 303 lock. However, once a locker attempts to 304 obtain a lock, the entire thread of control must pause until the lock 305 request is in some way resolved. 306 </p> 307 <p> 308 For example, if <code class="literal">Txn A</code> holds a write lock (an exclusive 309 lock) on 310 <span>object</span> 311 312 002, then if <code class="literal">Txn B</code> tries to obtain a read <span class="emphasis"><em>or</em></span> write lock on 313 that 314 <span>object,</span> 315 316 the thread of control in which <code class="literal">Txn 317 B</code> is running 318 is blocked: 319 </p> 320 <div class="mediaobject"> 321 <img src="writeblock.jpg" /> 322 </div> 323 <p> 324 However, if <code class="literal">Txn A</code> only holds a read 325 lock (a shared lock) on 326 <span>object</span> 327 328 <code class="literal">002</code>, then only those handles that attempt to obtain a 329 write lock on that 330 <span>object</span> 331 332 will block. 333 </p> 334 <div class="mediaobject"> 335 <img src="readblock.jpg" /> 336 </div> 337 <div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"> 338 <h3 class="title">Note</h3> 339 <p> 340 The previous description describes DB's default 341 behavior when it cannot obtain a lock. It is 342 possible to configure DB transactions so that 343 they will not block. Instead, if a lock is 344 unavailable, the application is immediately notified of a 345 deadlock situation. See <a class="xref" href="txnnowait.html" title="No Wait on Blocks">No Wait on Blocks</a> 346 for more information. 347 </p> 348 </div> 349 <div class="sect3" lang="en" xml:lang="en"> 350 <div class="titlepage"> 351 <div> 352 <div> 353 <h4 class="title"><a id="blockperformance"></a>Blocking and Application Performance</h4> 354 </div> 355 </div> 356 </div> 357 <p> 358 Multi-threaded 359 <span> 360 and multi-process 361 </span> 362 applications typically perform better than simple 363 single-threaded applications because the 364 application can perform one part of its workload 365 (updating 366 <span>a database record, </span> 367 368 for example) while it is waiting for some other 369 lengthy operation to complete (performing disk or 370 network I/O, for example). This performance 371 improvement is particularly noticeable if you use 372 hardware that offers multiple CPUs, because the threads 373 <span> 374 and processes 375 </span> 376 can run simultaneously. 377 </p> 378 <p> 379 That said, concurrent applications can see reduced 380 workload throughput if their threads of control are 381 seeing a large amount of lock contention. That is, 382 if threads are blocking on lock requests, then that 383 represents a performance penalty for your 384 application. 385 </p> 386 <p> 387 Consider once again the previous diagram of a blocked write lock request. 388 In that diagram, <code class="literal">Txn C</code> cannot 389 obtain its requested write lock because 390 <code class="literal">Txn A</code> and <code class="literal">Txn 391 B</code> are both already holding read locks on 392 the requested 393 <span>object.</span> 394 395 In this case, the thread in which 396 <code class="literal">Txn C</code> is running will pause until 397 such a time as <code class="literal">Txn C</code> either 398 obtains its write lock, or the operation 399 that is requesting the lock is abandoned. 400 The fact that <code class="literal">Txn 401 C</code>'s thread has temporarily halted all 402 forward progress represents a performance penalty 403 for your application. 404 </p> 405 <p> 406 Moreover, any read locks that are requested while 407 <code class="literal">Txn C</code> is waiting for its write 408 lock will also block until such a time as 409 <code class="literal">Txn C</code> has obtained and 410 subsequently released its write lock. 411 </p> 412 </div> 413 <div class="sect3" lang="en" xml:lang="en"> 414 <div class="titlepage"> 415 <div> 416 <div> 417 <h4 class="title"><a id="blockavoidance"></a>Avoiding Blocks</h4> 418 </div> 419 </div> 420 </div> 421 <p> 422 Reducing lock contention is an important part of 423 performance tuning your concurrent DB 424 application. Applications that have multiple 425 threads of control obtaining exclusive (write) 426 locks are prone to contention issues. Moreover, as 427 you increase the numbers of lockers and as you 428 increase the time that a lock is held, you increase 429 the chances of your application seeing lock contention. 430 </p> 431 <p> 432 As you are designing your application, try to do 433 the following in order to reduce lock contention: 434 </p> 435 <div class="itemizedlist"> 436 <ul type="disc"> 437 <li> 438 <p> 439 Reduce the length of time your application 440 holds locks. 441 </p> 442 <p> 443 Shorter lived transactions will result in 444 shorter lock lifetimes, which will in turn 445 help to reduce lock contention. 446 </p> 447 <p> 448 In addition, by default transactional cursors hold read 449 locks until such a time as the transaction is completed. 450 For this reason, try to minimize the time you keep 451 transactional cursors opened, or reduce your isolation 452 levels – see below. 453 </p> 454 </li> 455 <li> 456 <p> 457 If possible, access heavily accessed (read 458 or write) items toward the end of the 459 transaction. This reduces the amount of 460 time that a heavily used 461 <span> 462 page 463 </span> 464 465 is locked by the transaction. 466 </p> 467 </li> 468 <li> 469 <p> 470 Reduce your application's isolation guarantees. 471 </p> 472 <p> 473 By reducing your isolation guarantees, you 474 reduce the situations in which a lock can 475 block another lock. Try using uncommitted reads 476 for your read operations in order to 477 prevent a read lock being blocked by a 478 write lock. 479 </p> 480 <p> 481 In addition, for cursors you can use degree 482 2 (read committed) isolation, which causes 483 the cursor to release its read locks as 484 soon as it is done reading the record (as 485 opposed to holding its read locks until the 486 transaction ends). 487 </p> 488 <p> 489 Be aware that reducing your 490 isolation guarantees can have 491 adverse consequences for your 492 application. Before deciding 493 to reduce your isolation, take 494 care to examine your 495 application's isolation 496 requirements. 497 For information on isolation 498 levels, see 499 <a class="xref" href="isolation.html" title="Isolation">Isolation</a>. 500 </p> 501 </li> 502 <li> 503 <p> 504 Use snapshot isolation for 505 read-only threads. 506 </p> 507 <p> 508 Snapshot isolation causes the 509 transaction to make a copy of the 510 page on which it is holding a lock. 511 When a reader makes a copy of a 512 page, write locks can still be 513 obtained for the original page. 514 This eliminates entirely read-write 515 contention. 516 </p> 517 <p> 518 Snapshot isolation is described in 519 <a class="xref" href="isolation.html#snapshot_isolation" title="Using Snapshot Isolation">Using Snapshot Isolation</a>. 520 </p> 521 </li> 522 <li> 523 <p> 524 Consider your data access patterns. 525 </p> 526 <p> 527 Depending on the nature of your application, 528 this may be something that you can not 529 do anything about. However, if it is 530 possible to create your threads such that 531 they operate only on non-overlapping 532 portions of your database, then you can 533 reduce lock contention because your 534 threads will rarely (if ever) block on one another's 535 locks. 536 </p> 537 </li> 538 </ul> 539 </div> 540 <div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"> 541 <h3 class="title">Note</h3> 542 <p> 543 It is possible to configure DB's transactions 544 so that they never wait on blocked lock requests. 545 Instead, if they are blocked on a lock request, 546 they will notify the application of a deadlock (see 547 the next section). 548 </p> 549 <p> 550 You configure this behavior on a transaction by 551 transaction basis. See <a class="xref" href="txnnowait.html" title="No Wait on Blocks">No Wait on Blocks</a> for more information. 552 </p> 553 </div> 554 </div> 555 </div> 556 <div class="sect2" lang="en" xml:lang="en"> 557 <div class="titlepage"> 558 <div> 559 <div> 560 <h3 class="title"><a id="deadlocks"></a>Deadlocks</h3> 561 </div> 562 </div> 563 </div> 564 <p> 565 A deadlock occurs when two or more threads of control are 566 blocked, each waiting on a resource held by the other 567 thread. When this happens, there is no 568 possibility of the threads ever making forward progress 569 unless some outside agent takes action to break the 570 deadlock. 571 </p> 572 <p> 573 For example, if 574 <code class="literal">Txn A</code> is 575 blocked by <code class="literal">Txn B</code> at the same time 576 <code class="literal">Txn B</code> is blocked by <code class="literal">Txn 577 A</code> then the threads of control containing 578 <code class="literal">Txn A</code> and <code class="literal">Txn B</code> are 579 deadlocked; neither thread can make 580 any forward progress because neither thread will ever release the lock 581 that is blocking the other thread. 582 </p> 583 <div class="mediaobject"> 584 <img src="deadlock.jpg" /> 585 </div> 586 <p> 587 When two threads of control deadlock, the only 588 solution is to have a mechanism external to the two threads 589 capable of recognizing the deadlock and notifying at least 590 one thread that it is in a deadlock situation. 591 Once notified, a thread of 592 control must abandon the attempted operation in order to 593 resolve the deadlock. 594 595 <span> 596 DB's locking subsystem offers a deadlock notification 597 mechanism. See 598 <a class="xref" href="lockingsubsystem.html#configdeadlkdetect" title="Configuring Deadlock Detection">Configuring Deadlock Detection</a> 599 for more information. 600 </span> 601 602 603 </p> 604 <p> 605 Note that when one locker in a thread of control is blocked 606 waiting on a lock held by another locker in that same 607 thread of the control, the thread is said to be 608 <span class="emphasis"><em>self-deadlocked</em></span>. 609 </p> 610 <div class="sect3" lang="en" xml:lang="en"> 611 <div class="titlepage"> 612 <div> 613 <div> 614 <h4 class="title"><a id="deadlockavoidance"></a>Deadlock Avoidance</h4> 615 </div> 616 </div> 617 </div> 618 <p> 619 The things that you do to avoid lock contention also 620 help to reduce deadlocks (see <a class="xref" href="blocking_deadlocks.html#blockavoidance" title="Avoiding Blocks">Avoiding Blocks</a>). 621 622 <span> 623 Beyond that, you can also do the following in order to 624 avoid deadlocks: 625 </span> 626 627 628 </p> 629 <div class="itemizedlist"> 630 <ul type="disc"> 631 <li> 632 <p> 633 Never have more than one active transaction at 634 a time in a thread. A common cause of this is 635 for a thread to be using auto-commit for one 636 operation while an explicit transaction is in 637 use in that thread at the same time. 638 </p> 639 </li> 640 <li> 641 <p> 642 Make sure all threads access data in the same 643 order as all other threads. So long as threads 644 lock database pages 645 in the same basic order, there is no 646 possibility of a deadlock (threads can still 647 block, however). 648 </p> 649 <p> 650 Be aware that if you are using secondary 651 databases (indexes), it is not possible to 652 obtain locks in a consistent order because you 653 cannot predict the order in which locks are 654 obtained in secondary databases. If you are 655 writing a concurrent application and you are 656 using secondary databases, you must be prepared 657 to handle deadlocks. 658 </p> 659 </li> 660 <li> 661 <p> 662 If you are using BTrees in which you are 663 constantly adding and then deleting data, turn 664 Btree reverse split off. See 665 <a class="xref" href="reversesplit.html" title="Reverse BTree Splits">Reverse BTree Splits</a> 666 for more information. 667 </p> 668 </li> 669 <li> 670 <p> 671 Declare a read/modify/write lock for those 672 situations where you are reading a record in 673 preparation of modifying and then writing the 674 record. Doing this causes DB to give your 675 read operation a write lock. This means that no 676 other thread of control can share a read lock 677 (which might cause contention), but it also 678 means that the writer thread will not have to 679 wait to obtain a write lock when it is ready to 680 write the modified data back to the database. 681 </p> 682 <p> 683 For information on declaring 684 read/modify/write locks, see 685 <a class="xref" href="readmodifywrite.html" title="Read/Modify/Write">Read/Modify/Write</a>. 686 </p> 687 </li> 688 </ul> 689 </div> 690 </div> 691 </div> 692 </div> 693 <div class="navfooter"> 694 <hr /> 695 <table width="100%" summary="Navigation footer"> 696 <tr> 697 <td width="40%" align="left"><a accesskey="p" href="txnconcurrency.html">Prev</a> </td> 698 <td width="20%" align="center"> 699 <a accesskey="u" href="txnconcurrency.html">Up</a> 700 </td> 701 <td width="40%" align="right"> <a accesskey="n" href="lockingsubsystem.html">Next</a></td> 702 </tr> 703 <tr> 704 <td width="40%" align="left" valign="top">Chapter 4. Concurrency </td> 705 <td width="20%" align="center"> 706 <a accesskey="h" href="index.html">Home</a> 707 </td> 708 <td width="40%" align="right" valign="top"> The Locking Subsystem</td> 709 </tr> 710 </table> 711 </div> 712 </body> 713</html> 714
