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