git.ozlabs.org Git - ccan/blob - ccan/tdb2/doc/design.lyx

   1 #LyX 1.6.7 created this file. For more info see http://www.lyx.org/
   2 \lyxformat 345
   3 \begin_document
   4 \begin_header
   5 \textclass article
   6 \use_default_options true
   7 \language english
   8 \inputencoding auto
   9 \font_roman default
  10 \font_sans default
  11 \font_typewriter default
  12 \font_default_family default
  13 \font_sc false
  14 \font_osf false
  15 \font_sf_scale 100
  16 \font_tt_scale 100
  17
  18 \graphics default
  19 \paperfontsize default
  20 \use_hyperref false
  21 \papersize default
  22 \use_geometry false
  23 \use_amsmath 1
  24 \use_esint 1
  25 \cite_engine basic
  26 \use_bibtopic false
  27 \paperorientation portrait
  28 \secnumdepth 3
  29 \tocdepth 3
  30 \paragraph_separation indent
  31 \defskip medskip
  32 \quotes_language english
  33 \papercolumns 1
  34 \papersides 1
  35 \paperpagestyle default
  36 \tracking_changes true
  37 \output_changes true
  38 \author "Rusty Russell,,,"
  39 \author ""
  40 \end_header
  41
  42 \begin_body
  43
  44 \begin_layout Title
  45 TDB2: A Redesigning The Trivial DataBase
  46 \end_layout
  47
  48 \begin_layout Author
  49 Rusty Russell, IBM Corporation
  50 \end_layout
  51
  52 \begin_layout Date
  53 1-December-2010
  54 \end_layout
  55
  56 \begin_layout Abstract
  57 The Trivial DataBase on-disk format is 32 bits; with usage cases heading
  58  towards the 4G limit, that must change.
  59  This required breakage provides an opportunity to revisit TDB's other design
  60  decisions and reassess them.
  61 \end_layout
  62
  63 \begin_layout Section
  64 Introduction
  65 \end_layout
  66
  67 \begin_layout Standard
  68 The Trivial DataBase was originally written by Andrew Tridgell as a simple
  69  key/data pair storage system with the same API as dbm, but allowing multiple
  70  readers and writers while being small enough (< 1000 lines of C) to include
  71  in SAMBA.
  72  The simple design created in 1999 has proven surprisingly robust and performant
  73 , used in Samba versions 3 and 4 as well as numerous other projects.
  74  Its useful life was greatly increased by the (backwards-compatible!) addition
  75  of transaction support in 2005.
  76 \end_layout
  77
  78 \begin_layout Standard
  79 The wider variety and greater demands of TDB-using code has lead to some
  80  organic growth of the API, as well as some compromises on the implementation.
  81  None of these, by themselves, are seen as show-stoppers, but the cumulative
  82  effect is to a loss of elegance over the initial, simple TDB implementation.
  83  Here is a table of the approximate number of lines of implementation code
  84  and number of API functions at the end of each year:
  85 \end_layout
  86
  87 \begin_layout Standard
  88 \begin_inset Tabular
  89 <lyxtabular version="3" rows="12" columns="3">
  90 <features>
  91 <column alignment="center" valignment="top" width="0">
  92 <column alignment="center" valignment="top" width="0">
  93 <column alignment="center" valignment="top" width="0">
  94 <row>
  95 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
  96 \begin_inset Text
  97
  98 \begin_layout Plain Layout
  99 Year End
 100 \end_layout
 101
 102 \end_inset
 103 </cell>
 104 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
 105 \begin_inset Text
 106
 107 \begin_layout Plain Layout
 108 API Functions
 109 \end_layout
 110
 111 \end_inset
 112 </cell>
 113 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
 114 \begin_inset Text
 115
 116 \begin_layout Plain Layout
 117 Lines of C Code Implementation
 118 \end_layout
 119
 120 \end_inset
 121 </cell>
 122 </row>
 123 <row>
 124 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 125 \begin_inset Text
 126
 127 \begin_layout Plain Layout
 128 1999
 129 \end_layout
 130
 131 \end_inset
 132 </cell>
 133 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 134 \begin_inset Text
 135
 136 \begin_layout Plain Layout
 137 13
 138 \end_layout
 139
 140 \end_inset
 141 </cell>
 142 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 143 \begin_inset Text
 144
 145 \begin_layout Plain Layout
 146 1195
 147 \end_layout
 148
 149 \end_inset
 150 </cell>
 151 </row>
 152 <row>
 153 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 154 \begin_inset Text
 155
 156 \begin_layout Plain Layout
 157 2000
 158 \end_layout
 159
 160 \end_inset
 161 </cell>
 162 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 163 \begin_inset Text
 164
 165 \begin_layout Plain Layout
 166 24
 167 \end_layout
 168
 169 \end_inset
 170 </cell>
 171 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 172 \begin_inset Text
 173
 174 \begin_layout Plain Layout
 175 1725
 176 \end_layout
 177
 178 \end_inset
 179 </cell>
 180 </row>
 181 <row>
 182 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 183 \begin_inset Text
 184
 185 \begin_layout Plain Layout
 186 2001
 187 \end_layout
 188
 189 \end_inset
 190 </cell>
 191 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 192 \begin_inset Text
 193
 194 \begin_layout Plain Layout
 195 32
 196 \end_layout
 197
 198 \end_inset
 199 </cell>
 200 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 201 \begin_inset Text
 202
 203 \begin_layout Plain Layout
 204 2228
 205 \end_layout
 206
 207 \end_inset
 208 </cell>
 209 </row>
 210 <row>
 211 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 212 \begin_inset Text
 213
 214 \begin_layout Plain Layout
 215 2002
 216 \end_layout
 217
 218 \end_inset
 219 </cell>
 220 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 221 \begin_inset Text
 222
 223 \begin_layout Plain Layout
 224 35
 225 \end_layout
 226
 227 \end_inset
 228 </cell>
 229 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 230 \begin_inset Text
 231
 232 \begin_layout Plain Layout
 233 2481
 234 \end_layout
 235
 236 \end_inset
 237 </cell>
 238 </row>
 239 <row>
 240 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 241 \begin_inset Text
 242
 243 \begin_layout Plain Layout
 244 2003
 245 \end_layout
 246
 247 \end_inset
 248 </cell>
 249 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 250 \begin_inset Text
 251
 252 \begin_layout Plain Layout
 253 35
 254 \end_layout
 255
 256 \end_inset
 257 </cell>
 258 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 259 \begin_inset Text
 260
 261 \begin_layout Plain Layout
 262 2552
 263 \end_layout
 264
 265 \end_inset
 266 </cell>
 267 </row>
 268 <row>
 269 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 270 \begin_inset Text
 271
 272 \begin_layout Plain Layout
 273 2004
 274 \end_layout
 275
 276 \end_inset
 277 </cell>
 278 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 279 \begin_inset Text
 280
 281 \begin_layout Plain Layout
 282 40
 283 \end_layout
 284
 285 \end_inset
 286 </cell>
 287 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 288 \begin_inset Text
 289
 290 \begin_layout Plain Layout
 291 2584
 292 \end_layout
 293
 294 \end_inset
 295 </cell>
 296 </row>
 297 <row>
 298 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 299 \begin_inset Text
 300
 301 \begin_layout Plain Layout
 302 2005
 303 \end_layout
 304
 305 \end_inset
 306 </cell>
 307 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 308 \begin_inset Text
 309
 310 \begin_layout Plain Layout
 311 38
 312 \end_layout
 313
 314 \end_inset
 315 </cell>
 316 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 317 \begin_inset Text
 318
 319 \begin_layout Plain Layout
 320 2647
 321 \end_layout
 322
 323 \end_inset
 324 </cell>
 325 </row>
 326 <row>
 327 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 328 \begin_inset Text
 329
 330 \begin_layout Plain Layout
 331 2006
 332 \end_layout
 333
 334 \end_inset
 335 </cell>
 336 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 337 \begin_inset Text
 338
 339 \begin_layout Plain Layout
 340 52
 341 \end_layout
 342
 343 \end_inset
 344 </cell>
 345 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 346 \begin_inset Text
 347
 348 \begin_layout Plain Layout
 349 3754
 350 \end_layout
 351
 352 \end_inset
 353 </cell>
 354 </row>
 355 <row>
 356 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 357 \begin_inset Text
 358
 359 \begin_layout Plain Layout
 360 2007
 361 \end_layout
 362
 363 \end_inset
 364 </cell>
 365 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 366 \begin_inset Text
 367
 368 \begin_layout Plain Layout
 369 66
 370 \end_layout
 371
 372 \end_inset
 373 </cell>
 374 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 375 \begin_inset Text
 376
 377 \begin_layout Plain Layout
 378 4398
 379 \end_layout
 380
 381 \end_inset
 382 </cell>
 383 </row>
 384 <row>
 385 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 386 \begin_inset Text
 387
 388 \begin_layout Plain Layout
 389 2008
 390 \end_layout
 391
 392 \end_inset
 393 </cell>
 394 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
 395 \begin_inset Text
 396
 397 \begin_layout Plain Layout
 398 71
 399 \end_layout
 400
 401 \end_inset
 402 </cell>
 403 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
 404 \begin_inset Text
 405
 406 \begin_layout Plain Layout
 407 4768
 408 \end_layout
 409
 410 \end_inset
 411 </cell>
 412 </row>
 413 <row>
 414 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
 415 \begin_inset Text
 416
 417 \begin_layout Plain Layout
 418 2009
 419 \end_layout
 420
 421 \end_inset
 422 </cell>
 423 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
 424 \begin_inset Text
 425
 426 \begin_layout Plain Layout
 427 73
 428 \end_layout
 429
 430 \end_inset
 431 </cell>
 432 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
 433 \begin_inset Text
 434
 435 \begin_layout Plain Layout
 436 5715
 437 \end_layout
 438
 439 \end_inset
 440 </cell>
 441 </row>
 442 </lyxtabular>
 443
 444 \end_inset
 445
 446
 447 \end_layout
 448
 449 \begin_layout Standard
 450 This review is an attempt to catalog and address all the known issues with
 451  TDB and create solutions which address the problems without significantly
 452  increasing complexity; all involved are far too aware of the dangers of
 453  second system syndrome in rewriting a successful project like this.
 454 \end_layout
 455
 456 \begin_layout Section
 457 API Issues
 458 \end_layout
 459
 460 \begin_layout Subsection
 461 tdb_open_ex Is Not Expandable
 462 \end_layout
 463
 464 \begin_layout Standard
 465 The tdb_open() call was expanded to tdb_open_ex(), which added an optional
 466  hashing function and an optional logging function argument.
 467  Additional arguments to open would require the introduction of a tdb_open_ex2
 468  call etc.
 469 \end_layout
 470
 471 \begin_layout Subsubsection
 472 Proposed Solution
 473 \begin_inset CommandInset label
 474 LatexCommand label
 475 name "attributes"
 476
 477 \end_inset
 478
 479
 480 \end_layout
 481
 482 \begin_layout Standard
 483 tdb_open() will take a linked-list of attributes:
 484 \end_layout
 485
 486 \begin_layout LyX-Code
 487 enum tdb_attribute {
 488 \end_layout
 489
 490 \begin_layout LyX-Code
 491     TDB_ATTRIBUTE_LOG = 0,
 492 \end_layout
 493
 494 \begin_layout LyX-Code
 495     TDB_ATTRIBUTE_HASH = 1
 496 \end_layout
 497
 498 \begin_layout LyX-Code
 499 };
 500 \end_layout
 501
 502 \begin_layout LyX-Code
 503 struct tdb_attribute_base {
 504 \end_layout
 505
 506 \begin_layout LyX-Code
 507     enum tdb_attribute attr;
 508 \end_layout
 509
 510 \begin_layout LyX-Code
 511     union tdb_attribute *next;
 512 \end_layout
 513
 514 \begin_layout LyX-Code
 515 };
 516 \end_layout
 517
 518 \begin_layout LyX-Code
 519 struct tdb_attribute_log {
 520 \end_layout
 521
 522 \begin_layout LyX-Code
 523     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_LOG */
 524 \end_layout
 525
 526 \begin_layout LyX-Code
 527     tdb_log_func log_fn;
 528 \end_layout
 529
 530 \begin_layout LyX-Code
 531     void *log_private;
 532 \end_layout
 533
 534 \begin_layout LyX-Code
 535 };
 536 \end_layout
 537
 538 \begin_layout LyX-Code
 539 struct tdb_attribute_hash {
 540 \end_layout
 541
 542 \begin_layout LyX-Code
 543     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_HASH */
 544 \end_layout
 545
 546 \begin_layout LyX-Code
 547     tdb_hash_func hash_fn;
 548 \end_layout
 549
 550 \begin_layout LyX-Code
 551     void *hash_private;
 552 \end_layout
 553
 554 \begin_layout LyX-Code
 555 };
 556 \end_layout
 557
 558 \begin_layout LyX-Code
 559 union tdb_attribute {
 560 \end_layout
 561
 562 \begin_layout LyX-Code
 563     struct tdb_attribute_base base;
 564 \end_layout
 565
 566 \begin_layout LyX-Code
 567     struct tdb_attribute_log log;
 568 \end_layout
 569
 570 \begin_layout LyX-Code
 571     struct tdb_attribute_hash hash;
 572 \end_layout
 573
 574 \begin_layout LyX-Code
 575 };
 576 \end_layout
 577
 578 \begin_layout Standard
 579 This allows future attributes to be added, even if this expands the size
 580  of the union.
 581 \end_layout
 582
 583 \begin_layout Subsubsection
 584 Status
 585 \end_layout
 586
 587 \begin_layout Standard
 588 Complete.
 589 \end_layout
 590
 591 \begin_layout Subsection
 592 tdb_traverse Makes Impossible Guarantees
 593 \end_layout
 594
 595 \begin_layout Standard
 596 tdb_traverse (and tdb_firstkey/tdb_nextkey) predate transactions, and it
 597  was thought that it was important to guarantee that all records which exist
 598  at the start and end of the traversal would be included, and no record
 599  would be included twice.
 600 \end_layout
 601
 602 \begin_layout Standard
 603 This adds complexity (see
 604 \begin_inset CommandInset ref
 605 LatexCommand ref
 606 reference "Reliable-Traversal-Adds"
 607
 608 \end_inset
 609
 610 ) and does not work anyway for records which are altered (in particular,
 611  those which are expanded may be effectively deleted and re-added behind
 612  the traversal).
 613 \end_layout
 614
 615 \begin_layout Subsubsection
 616 \begin_inset CommandInset label
 617 LatexCommand label
 618 name "traverse-Proposed-Solution"
 619
 620 \end_inset
 621
 622 Proposed Solution
 623 \end_layout
 624
 625 \begin_layout Standard
 626 Abandon the guarantee.
 627  You will see every record if no changes occur during your traversal, otherwise
 628  you will see some subset.
 629  You can prevent changes by using a transaction or the locking API.
 630 \end_layout
 631
 632 \begin_layout Subsubsection
 633 Status
 634 \end_layout
 635
 636 \begin_layout Standard
 637 Complete.
 638  Delete-during-traverse will still delete every record, too (assuming no
 639  other changes).
 640 \end_layout
 641
 642 \begin_layout Subsection
 643 Nesting of Transactions Is Fraught
 644 \end_layout
 645
 646 \begin_layout Standard
 647 TDB has alternated between allowing nested transactions and not allowing
 648  them.
 649  Various paths in the Samba codebase assume that transactions will nest,
 650  and in a sense they can: the operation is only committed to disk when the
 651  outer transaction is committed.
 652  There are two problems, however:
 653 \end_layout
 654
 655 \begin_layout Enumerate
 656 Canceling the inner transaction will cause the outer transaction commit
 657  to fail, and will not undo any operations since the inner transaction began.
 658  This problem is soluble with some additional internal code.
 659 \end_layout
 660
 661 \begin_layout Enumerate
 662 An inner transaction commit can be cancelled by the outer transaction.
 663  This is desirable in the way which Samba's database initialization code
 664  uses transactions, but could be a surprise to any users expecting a successful
 665  transaction commit to expose changes to others.
 666 \end_layout
 667
 668 \begin_layout Standard
 669 The current solution is to specify the behavior at tdb_open(), with the
 670  default currently that nested transactions are allowed.
 671  This flag can also be changed at runtime.
 672 \end_layout
 673
 674 \begin_layout Subsubsection
 675 Proposed Solution
 676 \end_layout
 677
 678 \begin_layout Standard
 679 Given the usage patterns, it seems that the
 680 \begin_inset Quotes eld
 681 \end_inset
 682
 683 least-surprise
 684 \begin_inset Quotes erd
 685 \end_inset
 686
 687  behavior of disallowing nested transactions should become the default.
 688  Additionally, it seems the outer transaction is the only code which knows
 689  whether inner transactions should be allowed, so a flag to indicate this
 690  could be added to tdb_transaction_start.
 691  However, this behavior can be simulated with a wrapper which uses tdb_add_flags
 692 () and tdb_remove_flags(), so the API should not be expanded for this relatively
 693 -obscure case.
 694 \end_layout
 695
 696 \begin_layout Subsubsection
 697 Status
 698 \end_layout
 699
 700 \begin_layout Standard
 701
 702 \change_deleted 0 1298979572
 703 Incomplete; nesting flag is still defined as per tdb1.
 704 \change_inserted 0 1298979584
 705 Complete; the nesting flag has been removed.
 706 \change_unchanged
 707
 708 \end_layout
 709
 710 \begin_layout Subsection
 711 Incorrect Hash Function is Not Detected
 712 \end_layout
 713
 714 \begin_layout Standard
 715 tdb_open_ex() allows the calling code to specify a different hash function
 716  to use, but does not check that all other processes accessing this tdb
 717  are using the same hash function.
 718  The result is that records are missing from tdb_fetch().
 719 \end_layout
 720
 721 \begin_layout Subsubsection
 722 Proposed Solution
 723 \end_layout
 724
 725 \begin_layout Standard
 726 The header should contain an example hash result (eg.
 727  the hash of 0xdeadbeef), and tdb_open_ex() should check that the given
 728  hash function produces the same answer, or fail the tdb_open call.
 729 \end_layout
 730
 731 \begin_layout Subsubsection
 732 Status
 733 \end_layout
 734
 735 \begin_layout Standard
 736 Complete.
 737 \end_layout
 738
 739 \begin_layout Subsection
 740 tdb_set_max_dead/TDB_VOLATILE Expose Implementation
 741 \end_layout
 742
 743 \begin_layout Standard
 744 In response to scalability issues with the free list (
 745 \begin_inset CommandInset ref
 746 LatexCommand ref
 747 reference "TDB-Freelist-Is"
 748
 749 \end_inset
 750
 751 ) two API workarounds have been incorporated in TDB: tdb_set_max_dead()
 752  and the TDB_VOLATILE flag to tdb_open.
 753  The latter actually calls the former with an argument of
 754 \begin_inset Quotes eld
 755 \end_inset
 756
 757 5
 758 \begin_inset Quotes erd
 759 \end_inset
 760
 761 .
 762 \end_layout
 763
 764 \begin_layout Standard
 765 This code allows deleted records to accumulate without putting them in the
 766  free list.
 767  On delete we iterate through each chain and free them in a batch if there
 768  are more than max_dead entries.
 769  These are never otherwise recycled except as a side-effect of a tdb_repack.
 770 \end_layout
 771
 772 \begin_layout Subsubsection
 773 Proposed Solution
 774 \end_layout
 775
 776 \begin_layout Standard
 777 With the scalability problems of the freelist solved, this API can be removed.
 778  The TDB_VOLATILE flag may still be useful as a hint that store and delete
 779  of records will be at least as common as fetch in order to allow some internal
 780  tuning, but initially will become a no-op.
 781 \end_layout
 782
 783 \begin_layout Subsubsection
 784 Status
 785 \end_layout
 786
 787 \begin_layout Standard
 788
 789 \change_deleted 0 1300360559
 790 Incomplete.
 791  TDB_VOLATILE still defined, but implementation should fail on unknown flags
 792  to be future-proof.
 793 \change_inserted 0 1300360588
 794 Complete.
 795  Unknown flags cause tdb_open() to fail as well, so they can be detected
 796  at runtime.
 797 \end_layout
 798
 799 \begin_layout Subsection
 800 \begin_inset CommandInset label
 801 LatexCommand label
 802 name "TDB-Files-Cannot"
 803
 804 \end_inset
 805
 806 TDB Files Cannot Be Opened Multiple Times In The Same Process
 807 \end_layout
 808
 809 \begin_layout Standard
 810 No process can open the same TDB twice; we check and disallow it.
 811  This is an unfortunate side-effect of fcntl locks, which operate on a per-file
 812  rather than per-file-descriptor basis, and do not nest.
 813  Thus, closing any file descriptor on a file clears all the locks obtained
 814  by this process, even if they were placed using a different file descriptor!
 815 \end_layout
 816
 817 \begin_layout Standard
 818 Note that even if this were solved, deadlock could occur if operations were
 819  nested: this is a more manageable programming error in most cases.
 820 \end_layout
 821
 822 \begin_layout Subsubsection
 823 Proposed Solution
 824 \end_layout
 825
 826 \begin_layout Standard
 827 We could lobby POSIX to fix the perverse rules, or at least lobby Linux
 828  to violate them so that the most common implementation does not have this
 829  restriction.
 830  This would be a generally good idea for other fcntl lock users.
 831 \end_layout
 832
 833 \begin_layout Standard
 834 Samba uses a wrapper which hands out the same tdb_context to multiple callers
 835  if this happens, and does simple reference counting.
 836  We should do this inside the tdb library, which already emulates lock nesting
 837  internally; it would need to recognize when deadlock occurs within a single
 838  process.
 839  This would create a new failure mode for tdb operations (while we currently
 840  handle locking failures, they are impossible in normal use and a process
 841  encountering them can do little but give up).
 842 \end_layout
 843
 844 \begin_layout Standard
 845 I do not see benefit in an additional tdb_open flag to indicate whether
 846  re-opening is allowed, as though there may be some benefit to adding a
 847  call to detect when a tdb_context is shared, to allow other to create such
 848  an API.
 849 \end_layout
 850
 851 \begin_layout Subsubsection
 852 Status
 853 \end_layout
 854
 855 \begin_layout Standard
 856 Incomplete.
 857 \end_layout
 858
 859 \begin_layout Subsection
 860 TDB API Is Not POSIX Thread-safe
 861 \end_layout
 862
 863 \begin_layout Standard
 864 The TDB API uses an error code which can be queried after an operation to
 865  determine what went wrong.
 866  This programming model does not work with threads, unless specific additional
 867  guarantees are given by the implementation.
 868  In addition, even otherwise-independent threads cannot open the same TDB
 869  (as in
 870 \begin_inset CommandInset ref
 871 LatexCommand ref
 872 reference "TDB-Files-Cannot"
 873
 874 \end_inset
 875
 876 ).
 877 \end_layout
 878
 879 \begin_layout Subsubsection
 880 Proposed Solution
 881 \end_layout
 882
 883 \begin_layout Standard
 884 Reachitecting the API to include a tdb_errcode pointer would be a great
 885  deal of churn
 886 \change_inserted 0 1298979557
 887 , but fortunately most functions return 0 on success and -1 on error: we
 888  can change these to return 0 on success and a negative error code on error,
 889  and the API remains similar to previous.
 890  The tdb_fetch, tdb_firstkey and tdb_nextkey functions need to take a TDB_DATA
 891  pointer and return an error code.
 892  It is also simpler to have tdb_nextkey replace its key argument in place,
 893  freeing up any old .dptr.
 894 \end_layout
 895
 896 \begin_layout Standard
 897
 898 \change_deleted 0 1298979438
 899 ; we are better to guarantee that the tdb_errcode is per-thread so the current
 900  programming model can be maintained.
 901 \end_layout
 902
 903 \begin_layout Standard
 904
 905 \change_deleted 0 1298979438
 906 This requires dynamic per-thread allocations, which is awkward with POSIX
 907  threads (pthread_key_create space is limited and we cannot simply allocate
 908  a key for every TDB).
 909 \change_unchanged
 910
 911 \end_layout
 912
 913 \begin_layout Standard
 914 Internal locking is required to make sure that fcntl locks do not overlap
 915  between threads, and also that the global list of tdbs is maintained.
 916 \end_layout
 917
 918 \begin_layout Standard
 919 The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe
 920  version of the library, and otherwise no overhead will exist.
 921  Alternatively, a hooking mechanism similar to that proposed for
 922 \begin_inset CommandInset ref
 923 LatexCommand ref
 924 reference "Proposed-Solution-locking-hook"
 925
 926 \end_inset
 927
 928  could be used to enable pthread locking at runtime.
 929 \end_layout
 930
 931 \begin_layout Subsubsection
 932 Status
 933 \end_layout
 934
 935 \begin_layout Standard
 936 Incomplete
 937 \change_inserted 0 1298979681
 938 ; API has been changed but thread safety has not been implemented.
 939 \change_deleted 0 1298979669
 940 .
 941 \change_unchanged
 942
 943 \end_layout
 944
 945 \begin_layout Subsection
 946 *_nonblock Functions And *_mark Functions Expose Implementation
 947 \end_layout
 948
 949 \begin_layout Standard
 950 CTDB
 951 \begin_inset Foot
 952 status collapsed
 953
 954 \begin_layout Plain Layout
 955 Clustered TDB, see http://ctdb.samba.org
 956 \end_layout
 957
 958 \end_inset
 959
 960  wishes to operate on TDB in a non-blocking manner.
 961  This is currently done as follows:
 962 \end_layout
 963
 964 \begin_layout Enumerate
 965 Call the _nonblock variant of an API function (eg.
 966  tdb_lockall_nonblock).
 967  If this fails:
 968 \end_layout
 969
 970 \begin_layout Enumerate
 971 Fork a child process, and wait for it to call the normal variant (eg.
 972  tdb_lockall).
 973 \end_layout
 974
 975 \begin_layout Enumerate
 976 If the child succeeds, call the _mark variant to indicate we already have
 977  the locks (eg.
 978  tdb_lockall_mark).
 979 \end_layout
 980
 981 \begin_layout Enumerate
 982 Upon completion, tell the child to release the locks (eg.
 983  tdb_unlockall).
 984 \end_layout
 985
 986 \begin_layout Enumerate
 987 Indicate to tdb that it should consider the locks removed (eg.
 988  tdb_unlockall_mark).
 989 \end_layout
 990
 991 \begin_layout Standard
 992 There are several issues with this approach.
 993  Firstly, adding two new variants of each function clutters the API for
 994  an obscure use, and so not all functions have three variants.
 995  Secondly, it assumes that all paths of the functions ask for the same locks,
 996  otherwise the parent process will have to get a lock which the child doesn't
 997  have under some circumstances.
 998  I don't believe this is currently the case, but it constrains the implementatio
 999 n.
1000
1001 \end_layout
1002
1003 \begin_layout Subsubsection
1004 \begin_inset CommandInset label
1005 LatexCommand label
1006 name "Proposed-Solution-locking-hook"
1007
1008 \end_inset
1009
1010 Proposed Solution
1011 \end_layout
1012
1013 \begin_layout Standard
1014 Implement a hook for locking methods, so that the caller can control the
1015  calls to create and remove fcntl locks.
1016  In this scenario, ctdbd would operate as follows:
1017 \end_layout
1018
1019 \begin_layout Enumerate
1020 Call the normal API function, eg tdb_lockall().
1021 \end_layout
1022
1023 \begin_layout Enumerate
1024 When the lock callback comes in, check if the child has the lock.
1025  Initially, this is always false.
1026  If so, return 0.
1027  Otherwise, try to obtain it in non-blocking mode.
1028  If that fails, return EWOULDBLOCK.
1029 \end_layout
1030
1031 \begin_layout Enumerate
1032 Release locks in the unlock callback as normal.
1033 \end_layout
1034
1035 \begin_layout Enumerate
1036 If tdb_lockall() fails, see if we recorded a lock failure; if so, call the
1037  child to repeat the operation.
1038 \end_layout
1039
1040 \begin_layout Enumerate
1041 The child records what locks it obtains, and returns that information to
1042  the parent.
1043 \end_layout
1044
1045 \begin_layout Enumerate
1046 When the child has succeeded, goto 1.
1047 \end_layout
1048
1049 \begin_layout Standard
1050 This is flexible enough to handle any potential locking scenario, even when
1051  lock requirements change.
1052  It can be optimized so that the parent does not release locks, just tells
1053  the child which locks it doesn't need to obtain.
1054 \end_layout
1055
1056 \begin_layout Standard
1057 It also keeps the complexity out of the API, and in ctdbd where it is needed.
1058 \end_layout
1059
1060 \begin_layout Subsubsection
1061 Status
1062 \end_layout
1063
1064 \begin_layout Standard
1065 Incomplete.
1066 \end_layout
1067
1068 \begin_layout Subsection
1069 tdb_chainlock Functions Expose Implementation
1070 \end_layout
1071
1072 \begin_layout Standard
1073 tdb_chainlock locks some number of records, including the record indicated
1074  by the given key.
1075  This gave atomicity guarantees; no-one can start a transaction, alter,
1076  read or delete that key while the lock is held.
1077 \end_layout
1078
1079 \begin_layout Standard
1080 It also makes the same guarantee for any other key in the chain, which is
1081  an internal implementation detail and potentially a cause for deadlock.
1082 \end_layout
1083
1084 \begin_layout Subsubsection
1085 Proposed Solution
1086 \end_layout
1087
1088 \begin_layout Standard
1089 None.
1090  It would be nice to have an explicit single entry lock which effected no
1091  other keys.
1092  Unfortunately, this won't work for an entry which doesn't exist.
1093  Thus while chainlock may be implemented more efficiently for the existing
1094  case, it will still have overlap issues with the non-existing case.
1095  So it is best to keep the current (lack of) guarantee about which records
1096  will be effected to avoid constraining our implementation.
1097 \end_layout
1098
1099 \begin_layout Subsection
1100 Signal Handling is Not Race-Free
1101 \end_layout
1102
1103 \begin_layout Standard
1104 The tdb_setalarm_sigptr() call allows the caller's signal handler to indicate
1105  that the tdb locking code should return with a failure, rather than trying
1106  again when a signal is received (and errno == EAGAIN).
1107  This is usually used to implement timeouts.
1108 \end_layout
1109
1110 \begin_layout Standard
1111 Unfortunately, this does not work in the case where the signal is received
1112  before the tdb code enters the fcntl() call to place the lock: the code
1113  will sleep within the fcntl() code, unaware that the signal wants it to
1114  exit.
1115  In the case of long timeouts, this does not happen in practice.
1116 \end_layout
1117
1118 \begin_layout Subsubsection
1119 Proposed Solution
1120 \end_layout
1121
1122 \begin_layout Standard
1123 The locking hooks proposed in
1124 \begin_inset CommandInset ref
1125 LatexCommand ref
1126 reference "Proposed-Solution-locking-hook"
1127
1128 \end_inset
1129
1130  would allow the user to decide on whether to fail the lock acquisition
1131  on a signal.
1132  This allows the caller to choose their own compromise: they could narrow
1133  the race by checking immediately before the fcntl call.
1134 \begin_inset Foot
1135 status collapsed
1136
1137 \begin_layout Plain Layout
1138 It may be possible to make this race-free in some implementations by having
1139  the signal handler alter the struct flock to make it invalid.
1140  This will cause the fcntl() lock call to fail with EINVAL if the signal
1141  occurs before the kernel is entered, otherwise EAGAIN.
1142 \end_layout
1143
1144 \end_inset
1145
1146
1147 \end_layout
1148
1149 \begin_layout Subsubsection
1150 Status
1151 \end_layout
1152
1153 \begin_layout Standard
1154 Incomplete.
1155 \end_layout
1156
1157 \begin_layout Subsection
1158 The API Uses Gratuitous Typedefs, Capitals
1159 \end_layout
1160
1161 \begin_layout Standard
1162 typedefs are useful for providing source compatibility when types can differ
1163  across implementations, or arguably in the case of function pointer definitions
1164  which are hard for humans to parse.
1165  Otherwise it is simply obfuscation and pollutes the namespace.
1166 \end_layout
1167
1168 \begin_layout Standard
1169 Capitalization is usually reserved for compile-time constants and macros.
1170 \end_layout
1171
1172 \begin_layout Description
1173 TDB_CONTEXT There is no reason to use this over 'struct tdb_context'; the
1174  definition isn't visible to the API user anyway.
1175 \end_layout
1176
1177 \begin_layout Description
1178 TDB_DATA There is no reason to use this over struct TDB_DATA; the struct
1179  needs to be understood by the API user.
1180 \end_layout
1181
1182 \begin_layout Description
1183 struct
1184 \begin_inset space ~
1185 \end_inset
1186
1187 TDB_DATA This would normally be called 'struct tdb_data'.
1188 \end_layout
1189
1190 \begin_layout Description
1191 enum
1192 \begin_inset space ~
1193 \end_inset
1194
1195 TDB_ERROR Similarly, this would normally be enum tdb_error.
1196 \end_layout
1197
1198 \begin_layout Subsubsection
1199 Proposed Solution
1200 \end_layout
1201
1202 \begin_layout Standard
1203 None.
1204  Introducing lower case variants would please pedants like myself, but if
1205  it were done the existing ones should be kept.
1206  There is little point forcing a purely cosmetic change upon tdb users.
1207 \end_layout
1208
1209 \begin_layout Subsection
1210 \begin_inset CommandInset label
1211 LatexCommand label
1212 name "tdb_log_func-Doesnt-Take"
1213
1214 \end_inset
1215
1216 tdb_log_func Doesn't Take The Private Pointer
1217 \end_layout
1218
1219 \begin_layout Standard
1220 For API compatibility reasons, the logging function needs to call tdb_get_loggin
1221 g_private() to retrieve the pointer registered by the tdb_open_ex for logging.
1222 \end_layout
1223
1224 \begin_layout Subsubsection
1225 Proposed Solution
1226 \end_layout
1227
1228 \begin_layout Standard
1229 It should simply take an extra argument, since we are prepared to break
1230  the API/ABI.
1231 \end_layout
1232
1233 \begin_layout Subsubsection
1234 Status
1235 \end_layout
1236
1237 \begin_layout Standard
1238 Complete.
1239 \end_layout
1240
1241 \begin_layout Subsection
1242 Various Callback Functions Are Not Typesafe
1243 \end_layout
1244
1245 \begin_layout Standard
1246 The callback functions in tdb_set_logging_function (after
1247 \begin_inset CommandInset ref
1248 LatexCommand ref
1249 reference "tdb_log_func-Doesnt-Take"
1250
1251 \end_inset
1252
1253  is resolved), tdb_parse_record, tdb_traverse, tdb_traverse_read and tdb_check
1254  all take void * and must internally convert it to the argument type they
1255  were expecting.
1256 \end_layout
1257
1258 \begin_layout Standard
1259 If this type changes, the compiler will not produce warnings on the callers,
1260  since it only sees void *.
1261 \end_layout
1262
1263 \begin_layout Subsubsection
1264 Proposed Solution
1265 \end_layout
1266
1267 \begin_layout Standard
1268 With careful use of macros, we can create callback functions which give
1269  a warning when used on gcc and the types of the callback and its private
1270  argument differ.
1271  Unsupported compilers will not give a warning, which is no worse than now.
1272  In addition, the callbacks become clearer, as they need not use void *
1273  for their parameter.
1274 \end_layout
1275
1276 \begin_layout Standard
1277 See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html
1278 \end_layout
1279
1280 \begin_layout Subsubsection
1281 Status
1282 \end_layout
1283
1284 \begin_layout Standard
1285
1286 \change_deleted 0 1300360712
1287 Incomplete.
1288 \change_inserted 0 1300360716
1289 Complete.
1290 \change_unchanged
1291
1292 \end_layout
1293
1294 \begin_layout Subsection
1295 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic
1296 \end_layout
1297
1298 \begin_layout Standard
1299 The TDB_CLEAR_IF_FIRST flag to tdb_open indicates that the TDB file should
1300  be cleared if the caller discovers it is the only process with the TDB
1301  open.
1302  However, if any caller does not specify TDB_CLEAR_IF_FIRST it will not
1303  be detected, so will have the TDB erased underneath them (usually resulting
1304  in a crash).
1305 \end_layout
1306
1307 \begin_layout Standard
1308 There is a similar issue on fork(); if the parent exits (or otherwise closes
1309  the tdb) before the child calls tdb_reopen_all() to establish the lock
1310  used to indicate the TDB is opened by someone, a TDB_CLEAR_IF_FIRST opener
1311  at that moment will believe it alone has opened the TDB and will erase
1312  it.
1313 \end_layout
1314
1315 \begin_layout Subsubsection
1316 Proposed Solution
1317 \end_layout
1318
1319 \begin_layout Standard
1320 Remove TDB_CLEAR_IF_FIRST.
1321  Other workarounds are possible, but see
1322 \begin_inset CommandInset ref
1323 LatexCommand ref
1324 reference "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1325
1326 \end_inset
1327
1328 .
1329 \end_layout
1330
1331 \begin_layout Subsubsection
1332 Status
1333 \end_layout
1334
1335 \begin_layout Standard
1336
1337 \change_deleted 0 1298979699
1338 Incomplete, TDB_CLEAR_IF_FIRST still defined, but not implemented.
1339 \change_inserted 0 1298979700
1340 Complete.
1341 \change_unchanged
1342
1343 \end_layout
1344
1345 \begin_layout Subsection
1346 Extending The Header Is Difficult
1347 \end_layout
1348
1349 \begin_layout Standard
1350 We have reserved (zeroed) words in the TDB header, which can be used for
1351  future features.
1352  If the future features are compulsory, the version number must be updated
1353  to prevent old code from accessing the database.
1354  But if the future feature is optional, we have no way of telling if older
1355  code is accessing the database or not.
1356 \end_layout
1357
1358 \begin_layout Subsubsection
1359 Proposed Solution
1360 \end_layout
1361
1362 \begin_layout Standard
1363 The header should contain a
1364 \begin_inset Quotes eld
1365 \end_inset
1366
1367 format variant
1368 \begin_inset Quotes erd
1369 \end_inset
1370
1371  value (64-bit).
1372  This is divided into two 32-bit parts:
1373 \end_layout
1374
1375 \begin_layout Enumerate
1376 The lower part reflects the format variant understood by code accessing
1377  the database.
1378 \end_layout
1379
1380 \begin_layout Enumerate
1381 The upper part reflects the format variant you must understand to write
1382  to the database (otherwise you can only open for reading).
1383 \end_layout
1384
1385 \begin_layout Standard
1386 The latter field can only be written at creation time, the former should
1387  be written under the OPEN_LOCK when opening the database for writing, if
1388  the variant of the code is lower than the current lowest variant.
1389 \end_layout
1390
1391 \begin_layout Standard
1392 This should allow backwards-compatible features to be added, and detection
1393  if older code (which doesn't understand the feature) writes to the database.
1394 \end_layout
1395
1396 \begin_layout Subsubsection
1397 Status
1398 \end_layout
1399
1400 \begin_layout Standard
1401
1402 \change_deleted 0 1300360753
1403 Incomplete.
1404 \change_inserted 0 1300360754
1405 Complete.
1406 \change_unchanged
1407
1408 \end_layout
1409
1410 \begin_layout Subsection
1411 Record Headers Are Not Expandible
1412 \end_layout
1413
1414 \begin_layout Standard
1415 If we later want to add (say) checksums on keys and data, it would require
1416  another format change, which we'd like to avoid.
1417 \end_layout
1418
1419 \begin_layout Subsubsection
1420 Proposed Solution
1421 \end_layout
1422
1423 \begin_layout Standard
1424 We often have extra padding at the tail of a record.
1425  If we ensure that the first byte (if any) of this padding is zero, we will
1426  have a way for future changes to detect code which doesn't understand a
1427  new format: the new code would write (say) a 1 at the tail, and thus if
1428  there is no tail or the first byte is 0, we would know the extension is
1429  not present on that record.
1430 \end_layout
1431
1432 \begin_layout Subsubsection
1433 Status
1434 \end_layout
1435
1436 \begin_layout Standard
1437 Incomplete.
1438 \end_layout
1439
1440 \begin_layout Subsection
1441 TDB Does Not Use Talloc
1442 \end_layout
1443
1444 \begin_layout Standard
1445 Many users of TDB (particularly Samba) use the talloc allocator, and thus
1446  have to wrap TDB in a talloc context to use it conveniently.
1447 \end_layout
1448
1449 \begin_layout Subsubsection
1450 Proposed Solution
1451 \end_layout
1452
1453 \begin_layout Standard
1454 The allocation within TDB is not complicated enough to justify the use of
1455  talloc, and I am reluctant to force another (excellent) library on TDB
1456  users.
1457  Nonetheless a compromise is possible.
1458  An attribute (see
1459 \begin_inset CommandInset ref
1460 LatexCommand ref
1461 reference "attributes"
1462
1463 \end_inset
1464
1465 ) can be added later to tdb_open() to provide an alternate allocation mechanism,
1466  specifically for talloc but usable by any other allocator (which would
1467  ignore the
1468 \begin_inset Quotes eld
1469 \end_inset
1470
1471 context
1472 \begin_inset Quotes erd
1473 \end_inset
1474
1475  argument).
1476 \end_layout
1477
1478 \begin_layout Standard
1479 This would form a talloc heirarchy as expected, but the caller would still
1480  have to attach a destructor to the tdb context returned from tdb_open to
1481  close it.
1482  All TDB_DATA fields would be children of the tdb_context, and the caller
1483  would still have to manage them (using talloc_free() or talloc_steal()).
1484 \end_layout
1485
1486 \begin_layout Subsubsection
1487 Status
1488 \end_layout
1489
1490 \begin_layout Standard
1491 Deferred.
1492 \end_layout
1493
1494 \begin_layout Section
1495 Performance And Scalability Issues
1496 \end_layout
1497
1498 \begin_layout Subsection
1499 \begin_inset CommandInset label
1500 LatexCommand label
1501 name "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1502
1503 \end_inset
1504
1505 TDB_CLEAR_IF_FIRST Imposes Performance Penalty
1506 \end_layout
1507
1508 \begin_layout Standard
1509 When TDB_CLEAR_IF_FIRST is specified, a 1-byte read lock is placed at offset
1510  4 (aka.
1511  the ACTIVE_LOCK).
1512  While these locks never conflict in normal tdb usage, they do add substantial
1513  overhead for most fcntl lock implementations when the kernel scans to detect
1514  if a lock conflict exists.
1515  This is often a single linked list, making the time to acquire and release
1516  a fcntl lock O(N) where N is the number of processes with the TDB open,
1517  not the number actually doing work.
1518 \end_layout
1519
1520 \begin_layout Standard
1521 In a Samba server it is common to have huge numbers of clients sitting idle,
1522  and thus they have weaned themselves off the TDB_CLEAR_IF_FIRST flag.
1523 \begin_inset Foot
1524 status collapsed
1525
1526 \begin_layout Plain Layout
1527 There is a flag to tdb_reopen_all() which is used for this optimization:
1528  if the parent process will outlive the child, the child does not need the
1529  ACTIVE_LOCK.
1530  This is a workaround for this very performance issue.
1531 \end_layout
1532
1533 \end_inset
1534
1535
1536 \end_layout
1537
1538 \begin_layout Subsubsection
1539 Proposed Solution
1540 \end_layout
1541
1542 \begin_layout Standard
1543 Remove the flag.
1544  It was a neat idea, but even trivial servers tend to know when they are
1545  initializing for the first time and can simply unlink the old tdb at that
1546  point.
1547 \end_layout
1548
1549 \begin_layout Subsubsection
1550 Status
1551 \end_layout
1552
1553 \begin_layout Standard
1554
1555 \change_deleted 0 1298979837
1556 Incomplete; TDB_CLEAR_IF_FIRST still defined, but does nothing.
1557 \change_inserted 0 1298979837
1558 Complete.
1559 \change_unchanged
1560
1561 \end_layout
1562
1563 \begin_layout Subsection
1564 TDB Files Have a 4G Limit
1565 \end_layout
1566
1567 \begin_layout Standard
1568 This seems to be becoming an issue (so much for
1569 \begin_inset Quotes eld
1570 \end_inset
1571
1572 trivial
1573 \begin_inset Quotes erd
1574 \end_inset
1575
1576 !), particularly for ldb.
1577 \end_layout
1578
1579 \begin_layout Subsubsection
1580 Proposed Solution
1581 \end_layout
1582
1583 \begin_layout Standard
1584 A new, incompatible TDB format which uses 64 bit offsets internally rather
1585  than 32 bit as now.
1586  For simplicity of endian conversion (which TDB does on the fly if required),
1587  all values will be 64 bit on disk.
1588  In practice, some upper bits may be used for other purposes, but at least
1589  56 bits will be available for file offsets.
1590 \end_layout
1591
1592 \begin_layout Standard
1593 tdb_open() will automatically detect the old version, and even create them
1594  if TDB_VERSION6 is specified to tdb_open.
1595 \end_layout
1596
1597 \begin_layout Standard
1598 32 bit processes will still be able to access TDBs larger than 4G (assuming
1599  that their off_t allows them to seek to 64 bits), they will gracefully
1600  fall back as they fail to mmap.
1601  This can happen already with large TDBs.
1602 \end_layout
1603
1604 \begin_layout Standard
1605 Old versions of tdb will fail to open the new TDB files (since 28 August
1606  2009, commit 398d0c29290: prior to that any unrecognized file format would
1607  be erased and initialized as a fresh tdb!)
1608 \end_layout
1609
1610 \begin_layout Subsubsection
1611 Status
1612 \end_layout
1613
1614 \begin_layout Standard
1615 Complete.
1616 \end_layout
1617
1618 \begin_layout Subsection
1619 TDB Records Have a 4G Limit
1620 \end_layout
1621
1622 \begin_layout Standard
1623 This has not been a reported problem, and the API uses size_t which can
1624  be 64 bit on 64 bit platforms.
1625  However, other limits may have made such an issue moot.
1626 \end_layout
1627
1628 \begin_layout Subsubsection
1629 Proposed Solution
1630 \end_layout
1631
1632 \begin_layout Standard
1633 Record sizes will be 64 bit, with an error returned on 32 bit platforms
1634  which try to access such records (the current implementation would return
1635  TDB_ERR_OOM in a similar case).
1636  It seems unlikely that 32 bit keys will be a limitation, so the implementation
1637  may not support this (see
1638 \begin_inset CommandInset ref
1639 LatexCommand ref
1640 reference "sub:Records-Incur-A"
1641
1642 \end_inset
1643
1644 ).
1645 \end_layout
1646
1647 \begin_layout Subsubsection
1648 Status
1649 \end_layout
1650
1651 \begin_layout Standard
1652 Complete.
1653 \end_layout
1654
1655 \begin_layout Subsection
1656 Hash Size Is Determined At TDB Creation Time
1657 \end_layout
1658
1659 \begin_layout Standard
1660 TDB contains a number of hash chains in the header; the number is specified
1661  at creation time, and defaults to 131.
1662  This is such a bottleneck on large databases (as each hash chain gets quite
1663  long), that LDB uses 10,000 for this hash.
1664  In general it is impossible to know what the 'right' answer is at database
1665  creation time.
1666 \end_layout
1667
1668 \begin_layout Subsubsection
1669 \begin_inset CommandInset label
1670 LatexCommand label
1671 name "sub:Hash-Size-Solution"
1672
1673 \end_inset
1674
1675 Proposed Solution
1676 \end_layout
1677
1678 \begin_layout Standard
1679 After comprehensive performance testing on various scalable hash variants
1680 \begin_inset Foot
1681 status collapsed
1682
1683 \begin_layout Plain Layout
1684 http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoying
1685  because I was previously convinced that an expanding tree of hashes would
1686  be very close to optimal.
1687 \end_layout
1688
1689 \end_inset
1690
1691 , it became clear that it is hard to beat a straight linear hash table which
1692  doubles in size when it reaches saturation.
1693  Unfortunately, altering the hash table introduces serious locking complications
1694 : the entire hash table needs to be locked to enlarge the hash table, and
1695  others might be holding locks.
1696  Particularly insidious are insertions done under tdb_chainlock.
1697 \end_layout
1698
1699 \begin_layout Standard
1700 Thus an expanding layered hash will be used: an array of hash groups, with
1701  each hash group exploding into pointers to lower hash groups once it fills,
1702  turning into a hash tree.
1703  This has implications for locking: we must lock the entire group in case
1704  we need to expand it, yet we don't know how deep the tree is at that point.
1705 \end_layout
1706
1707 \begin_layout Standard
1708 Note that bits from the hash table entries should be stolen to hold more
1709  hash bits to reduce the penalty of collisions.
1710  We can use the otherwise-unused lower 3 bits.
1711  If we limit the size of the database to 64 exabytes, we can use the top
1712  8 bits of the hash entry as well.
1713  These 11 bits would reduce false positives down to 1 in 2000 which is more
1714  than we need: we can use one of the bits to indicate that the extra hash
1715  bits are valid.
1716  This means we can choose not to re-hash all entries when we expand a hash
1717  group; simply use the next bits we need and mark them invalid.
1718 \end_layout
1719
1720 \begin_layout Subsubsection
1721 Status
1722 \end_layout
1723
1724 \begin_layout Standard
1725 Complete.
1726 \end_layout
1727
1728 \begin_layout Subsection
1729 \begin_inset CommandInset label
1730 LatexCommand label
1731 name "TDB-Freelist-Is"
1732
1733 \end_inset
1734
1735 TDB Freelist Is Highly Contended
1736 \end_layout
1737
1738 \begin_layout Standard
1739 TDB uses a single linked list for the free list.
1740  Allocation occurs as follows, using heuristics which have evolved over
1741  time:
1742 \end_layout
1743
1744 \begin_layout Enumerate
1745 Get the free list lock for this whole operation.
1746 \end_layout
1747
1748 \begin_layout Enumerate
1749 Multiply length by 1.25, so we always over-allocate by 25%.
1750 \end_layout
1751
1752 \begin_layout Enumerate
1753 Set the slack multiplier to 1.
1754 \end_layout
1755
1756 \begin_layout Enumerate
1757 Examine the current freelist entry: if it is > length but < the current
1758  best case, remember it as the best case.
1759 \end_layout
1760
1761 \begin_layout Enumerate
1762 Multiply the slack multiplier by 1.05.
1763 \end_layout
1764
1765 \begin_layout Enumerate
1766 If our best fit so far is less than length * slack multiplier, return it.
1767  The slack will be turned into a new free record if it's large enough.
1768 \end_layout
1769
1770 \begin_layout Enumerate
1771 Otherwise, go onto the next freelist entry.
1772 \end_layout
1773
1774 \begin_layout Standard
1775 Deleting a record occurs as follows:
1776 \end_layout
1777
1778 \begin_layout Enumerate
1779 Lock the hash chain for this whole operation.
1780 \end_layout
1781
1782 \begin_layout Enumerate
1783 Walk the chain to find the record, keeping the prev pointer offset.
1784 \end_layout
1785
1786 \begin_layout Enumerate
1787 If max_dead is non-zero:
1788 \end_layout
1789
1790 \begin_deeper
1791 \begin_layout Enumerate
1792 Walk the hash chain again and count the dead records.
1793 \end_layout
1794
1795 \begin_layout Enumerate
1796 If it's more than max_dead, bulk free all the dead ones (similar to steps
1797  4 and below, but the lock is only obtained once).
1798 \end_layout
1799
1800 \begin_layout Enumerate
1801 Simply mark this record as dead and return.
1802
1803 \end_layout
1804
1805 \end_deeper
1806 \begin_layout Enumerate
1807 Get the free list lock for the remainder of this operation.
1808 \end_layout
1809
1810 \begin_layout Enumerate
1811 \begin_inset CommandInset label
1812 LatexCommand label
1813 name "right-merging"
1814
1815 \end_inset
1816
1817 Examine the following block to see if it is free; if so, enlarge the current
1818  block and remove that block from the free list.
1819  This was disabled, as removal from the free list was O(entries-in-free-list).
1820 \end_layout
1821
1822 \begin_layout Enumerate
1823 Examine the preceeding block to see if it is free: for this reason, each
1824  block has a 32-bit tailer which indicates its length.
1825  If it is free, expand it to cover our new block and return.
1826 \end_layout
1827
1828 \begin_layout Enumerate
1829 Otherwise, prepend ourselves to the free list.
1830 \end_layout
1831
1832 \begin_layout Standard
1833 Disabling right-merging (step
1834 \begin_inset CommandInset ref
1835 LatexCommand ref
1836 reference "right-merging"
1837
1838 \end_inset
1839
1840 ) causes fragmentation; the other heuristics proved insufficient to address
1841  this, so the final answer to this was that when we expand the TDB file
1842  inside a transaction commit, we repack the entire tdb.
1843 \end_layout
1844
1845 \begin_layout Standard
1846 The single list lock limits our allocation rate; due to the other issues
1847  this is not currently seen as a bottleneck.
1848 \end_layout
1849
1850 \begin_layout Subsubsection
1851 Proposed Solution
1852 \end_layout
1853
1854 \begin_layout Standard
1855 The first step is to remove all the current heuristics, as they obviously
1856  interact, then examine them once the lock contention is addressed.
1857 \end_layout
1858
1859 \begin_layout Standard
1860 The free list must be split to reduce contention.
1861  Assuming perfect free merging, we can at most have 1 free list entry for
1862  each entry.
1863  This implies that the number of free lists is related to the size of the
1864  hash table, but as it is rare to walk a large number of free list entries
1865  we can use far fewer, say 1/32 of the number of hash buckets.
1866 \end_layout
1867
1868 \begin_layout Standard
1869 It seems tempting to try to reuse the hash implementation which we use for
1870  records here, but we have two ways of searching for free entries: for allocatio
1871 n we search by size (and possibly zone) which produces too many clashes
1872  for our hash table to handle well, and for coalescing we search by address.
1873  Thus an array of doubly-linked free lists seems preferable.
1874 \end_layout
1875
1876 \begin_layout Standard
1877 There are various benefits in using per-size free lists (see
1878 \begin_inset CommandInset ref
1879 LatexCommand ref
1880 reference "sub:TDB-Becomes-Fragmented"
1881
1882 \end_inset
1883
1884 ) but it's not clear this would reduce contention in the common case where
1885  all processes are allocating/freeing the same size.
1886  Thus we almost certainly need to divide in other ways: the most obvious
1887  is to divide the file into zones, and using a free list (or table of free
1888  lists) for each.
1889  This approximates address ordering.
1890 \end_layout
1891
1892 \begin_layout Standard
1893 Unfortunately it is difficult to know what heuristics should be used to
1894  determine zone sizes, and our transaction code relies on being able to
1895  create a
1896 \begin_inset Quotes eld
1897 \end_inset
1898
1899 recovery area
1900 \begin_inset Quotes erd
1901 \end_inset
1902
1903  by simply appending to the file (difficult if it would need to create a
1904  new zone header).
1905  Thus we use a linked-list of free tables; currently we only ever create
1906  one, but if there is more than one we choose one at random to use.
1907  In future we may use heuristics to add new free tables on contention.
1908  We only expand the file when all free tables are exhausted.
1909 \end_layout
1910
1911 \begin_layout Standard
1912 The basic algorithm is as follows.
1913  Freeing is simple:
1914 \end_layout
1915
1916 \begin_layout Enumerate
1917 Identify the correct free list.
1918 \end_layout
1919
1920 \begin_layout Enumerate
1921 Lock the corresponding list.
1922 \end_layout
1923
1924 \begin_layout Enumerate
1925 Re-check the list (we didn't have a lock, sizes could have changed): relock
1926  if necessary.
1927 \end_layout
1928
1929 \begin_layout Enumerate
1930 Place the freed entry in the list.
1931 \end_layout
1932
1933 \begin_layout Standard
1934 Allocation is a little more complicated, as we perform delayed coalescing
1935  at this point:
1936 \end_layout
1937
1938 \begin_layout Enumerate
1939 Pick a free table; usually the previous one.
1940 \end_layout
1941
1942 \begin_layout Enumerate
1943 Lock the corresponding list.
1944 \end_layout
1945
1946 \begin_layout Enumerate
1947 If the top entry is -large enough, remove it from the list and return it.
1948 \end_layout
1949
1950 \begin_layout Enumerate
1951 Otherwise, coalesce entries in the list.If there was no entry large enough,
1952  unlock the list and try the next largest list
1953 \end_layout
1954
1955 \begin_layout Enumerate
1956 If no list has an entry which meets our needs, try the next free table.
1957 \end_layout
1958
1959 \begin_layout Enumerate
1960 If no zone satisfies, expand the file.
1961 \end_layout
1962
1963 \begin_layout Standard
1964 This optimizes rapid insert/delete of free list entries by not coalescing
1965  them all the time..
1966  First-fit address ordering ordering seems to be fairly good for keeping
1967  fragmentation low (see
1968 \begin_inset CommandInset ref
1969 LatexCommand ref
1970 reference "sub:TDB-Becomes-Fragmented"
1971
1972 \end_inset
1973
1974 ).
1975  Note that address ordering does not need a tailer to coalesce, though if
1976  we needed one we could have one cheaply: see
1977 \begin_inset CommandInset ref
1978 LatexCommand ref
1979 reference "sub:Records-Incur-A"
1980
1981 \end_inset
1982
1983 .
1984
1985 \end_layout
1986
1987 \begin_layout Standard
1988 Each free entry has the free table number in the header: less than 255.
1989  It also contains a doubly-linked list for easy deletion.
1990 \end_layout
1991
1992 \begin_layout Subsection
1993 \begin_inset CommandInset label
1994 LatexCommand label
1995 name "sub:TDB-Becomes-Fragmented"
1996
1997 \end_inset
1998
1999 TDB Becomes Fragmented
2000 \end_layout
2001
2002 \begin_layout Standard
2003 Much of this is a result of allocation strategy
2004 \begin_inset Foot
2005 status collapsed
2006
2007 \begin_layout Plain Layout
2008 The Memory Fragmentation Problem: Solved? Johnstone & Wilson 1995 ftp://ftp.cs.ute
2009 xas.edu/pub/garbage/malloc/ismm98.ps
2010 \end_layout
2011
2012 \end_inset
2013
2014  and deliberate hobbling of coalescing; internal fragmentation (aka overallocati
2015 on) is deliberately set at 25%, and external fragmentation is only cured
2016  by the decision to repack the entire db when a transaction commit needs
2017  to enlarge the file.
2018 \end_layout
2019
2020 \begin_layout Subsubsection
2021 Proposed Solution
2022 \end_layout
2023
2024 \begin_layout Standard
2025 The 25% overhead on allocation works in practice for ldb because indexes
2026  tend to expand by one record at a time.
2027  This internal fragmentation can be resolved by having an
2028 \begin_inset Quotes eld
2029 \end_inset
2030
2031 expanded
2032 \begin_inset Quotes erd
2033 \end_inset
2034
2035  bit in the header to note entries that have previously expanded, and allocating
2036  more space for them.
2037 \end_layout
2038
2039 \begin_layout Standard
2040 There are is a spectrum of possible solutions for external fragmentation:
2041  one is to use a fragmentation-avoiding allocation strategy such as best-fit
2042  address-order allocator.
2043  The other end of the spectrum would be to use a bump allocator (very fast
2044  and simple) and simply repack the file when we reach the end.
2045 \end_layout
2046
2047 \begin_layout Standard
2048 There are three problems with efficient fragmentation-avoiding allocators:
2049  they are non-trivial, they tend to use a single free list for each size,
2050  and there's no evidence that tdb allocation patterns will match those recorded
2051  for general allocators (though it seems likely).
2052 \end_layout
2053
2054 \begin_layout Standard
2055 Thus we don't spend too much effort on external fragmentation; we will be
2056  no worse than the current code if we need to repack on occasion.
2057  More effort is spent on reducing freelist contention, and reducing overhead.
2058 \end_layout
2059
2060 \begin_layout Subsection
2061 \begin_inset CommandInset label
2062 LatexCommand label
2063 name "sub:Records-Incur-A"
2064
2065 \end_inset
2066
2067 Records Incur A 28-Byte Overhead
2068 \end_layout
2069
2070 \begin_layout Standard
2071 Each TDB record has a header as follows:
2072 \end_layout
2073
2074 \begin_layout LyX-Code
2075 struct tdb_record {
2076 \end_layout
2077
2078 \begin_layout LyX-Code
2079         tdb_off_t next; /* offset of the next record in the list */
2080 \end_layout
2081
2082 \begin_layout LyX-Code
2083         tdb_len_t rec_len; /* total byte length of record */
2084 \end_layout
2085
2086 \begin_layout LyX-Code
2087         tdb_len_t key_len; /* byte length of key */
2088 \end_layout
2089
2090 \begin_layout LyX-Code
2091         tdb_len_t data_len; /* byte length of data */
2092 \end_layout
2093
2094 \begin_layout LyX-Code
2095         uint32_t full_hash; /* the full 32 bit hash of the key */
2096 \end_layout
2097
2098 \begin_layout LyX-Code
2099         uint32_t magic;   /* try to catch errors */
2100 \end_layout
2101
2102 \begin_layout LyX-Code
2103         /* the following union is implied:
2104 \end_layout
2105
2106 \begin_layout LyX-Code
2107                 union {
2108 \end_layout
2109
2110 \begin_layout LyX-Code
2111                         char record[rec_len];
2112 \end_layout
2113
2114 \begin_layout LyX-Code
2115                         struct {
2116 \end_layout
2117
2118 \begin_layout LyX-Code
2119                                 char key[key_len];
2120 \end_layout
2121
2122 \begin_layout LyX-Code
2123                                 char data[data_len];
2124 \end_layout
2125
2126 \begin_layout LyX-Code
2127                         }
2128 \end_layout
2129
2130 \begin_layout LyX-Code
2131                         uint32_t totalsize; (tailer)
2132 \end_layout
2133
2134 \begin_layout LyX-Code
2135                 }
2136 \end_layout
2137
2138 \begin_layout LyX-Code
2139         */
2140 \end_layout
2141
2142 \begin_layout LyX-Code
2143 };
2144 \end_layout
2145
2146 \begin_layout Standard
2147 Naively, this would double to a 56-byte overhead on a 64 bit implementation.
2148 \end_layout
2149
2150 \begin_layout Subsubsection
2151 Proposed Solution
2152 \end_layout
2153
2154 \begin_layout Standard
2155 We can use various techniques to reduce this for an allocated block:
2156 \end_layout
2157
2158 \begin_layout Enumerate
2159 The 'next' pointer is not required, as we are using a flat hash table.
2160 \end_layout
2161
2162 \begin_layout Enumerate
2163 'rec_len' can instead be expressed as an addition to key_len and data_len
2164  (it accounts for wasted or overallocated length in the record).
2165  Since the record length is always a multiple of 8, we can conveniently
2166  fit it in 32 bits (representing up to 35 bits).
2167 \end_layout
2168
2169 \begin_layout Enumerate
2170 'key_len' and 'data_len' can be reduced.
2171  I'm unwilling to restrict 'data_len' to 32 bits, but instead we can combine
2172  the two into one 64-bit field and using a 5 bit value which indicates at
2173  what bit to divide the two.
2174  Keys are unlikely to scale as fast as data, so I'm assuming a maximum key
2175  size of 32 bits.
2176 \end_layout
2177
2178 \begin_layout Enumerate
2179 'full_hash' is used to avoid a memcmp on the
2180 \begin_inset Quotes eld
2181 \end_inset
2182
2183 miss
2184 \begin_inset Quotes erd
2185 \end_inset
2186
2187  case, but this is diminishing returns after a handful of bits (at 10 bits,
2188  it reduces 99.9% of false memcmp).
2189  As an aside, as the lower bits are already incorporated in the hash table
2190  resolution, the upper bits should be used here.
2191  Note that it's not clear that these bits will be a win, given the extra
2192  bits in the hash table itself (see
2193 \begin_inset CommandInset ref
2194 LatexCommand ref
2195 reference "sub:Hash-Size-Solution"
2196
2197 \end_inset
2198
2199 ).
2200 \end_layout
2201
2202 \begin_layout Enumerate
2203 'magic' does not need to be enlarged: it currently reflects one of 5 values
2204  (used, free, dead, recovery, and unused_recovery).
2205  It is useful for quick sanity checking however, and should not be eliminated.
2206 \end_layout
2207
2208 \begin_layout Enumerate
2209 'tailer' is only used to coalesce free blocks (so a block to the right can
2210  find the header to check if this block is free).
2211  This can be replaced by a single 'free' bit in the header of the following
2212  block (and the tailer only exists in free blocks).
2213 \begin_inset Foot
2214 status collapsed
2215
2216 \begin_layout Plain Layout
2217 This technique from Thomas Standish.
2218  Data Structure Techniques.
2219  Addison-Wesley, Reading, Massachusetts, 1980.
2220 \end_layout
2221
2222 \end_inset
2223
2224  The current proposed coalescing algorithm doesn't need this, however.
2225 \end_layout
2226
2227 \begin_layout Standard
2228 This produces a 16 byte used header like this:
2229 \end_layout
2230
2231 \begin_layout LyX-Code
2232 struct tdb_used_record {
2233 \end_layout
2234
2235 \begin_layout LyX-Code
2236         uint32_t used_magic : 16,
2237 \end_layout
2238
2239 \begin_layout LyX-Code
2240
2241 \end_layout
2242
2243 \begin_layout LyX-Code
2244                  key_data_divide: 5,
2245 \end_layout
2246
2247 \begin_layout LyX-Code
2248                  top_hash: 11;
2249 \end_layout
2250
2251 \begin_layout LyX-Code
2252         uint32_t extra_octets;
2253 \end_layout
2254
2255 \begin_layout LyX-Code
2256         uint64_t key_and_data_len;
2257 \end_layout
2258
2259 \begin_layout LyX-Code
2260 };
2261 \end_layout
2262
2263 \begin_layout Standard
2264 And a free record like this:
2265 \end_layout
2266
2267 \begin_layout LyX-Code
2268 struct tdb_free_record {
2269 \end_layout
2270
2271 \begin_layout LyX-Code
2272         uint64_t free_magic: 8,
2273 \end_layout
2274
2275 \begin_layout LyX-Code
2276                    prev : 56;
2277 \end_layout
2278
2279 \begin_layout LyX-Code
2280
2281 \end_layout
2282
2283 \begin_layout LyX-Code
2284         uint64_t free_table: 8,
2285 \end_layout
2286
2287 \begin_layout LyX-Code
2288                  total_length : 56
2289 \end_layout
2290
2291 \begin_layout LyX-Code
2292         uint64_t next;;
2293 \end_layout
2294
2295 \begin_layout LyX-Code
2296 };
2297 \end_layout
2298
2299 \begin_layout Standard
2300
2301 \change_deleted 0 1291206079
2302
2303 \change_unchanged
2304 Note that by limiting valid offsets to 56 bits, we can pack everything we
2305  need into 3 64-byte words, meaning our minimum record size is 8 bytes.
2306 \end_layout
2307
2308 \begin_layout Subsubsection
2309 Status
2310 \end_layout
2311
2312 \begin_layout Standard
2313 Complete.
2314 \end_layout
2315
2316 \begin_layout Subsection
2317 Transaction Commit Requires 4 fdatasync
2318 \end_layout
2319
2320 \begin_layout Standard
2321 The current transaction algorithm is:
2322 \end_layout
2323
2324 \begin_layout Enumerate
2325 write_recovery_data();
2326 \end_layout
2327
2328 \begin_layout Enumerate
2329 sync();
2330 \end_layout
2331
2332 \begin_layout Enumerate
2333 write_recovery_header();
2334 \end_layout
2335
2336 \begin_layout Enumerate
2337 sync();
2338 \end_layout
2339
2340 \begin_layout Enumerate
2341 overwrite_with_new_data();
2342 \end_layout
2343
2344 \begin_layout Enumerate
2345 sync();
2346 \end_layout
2347
2348 \begin_layout Enumerate
2349 remove_recovery_header();
2350 \end_layout
2351
2352 \begin_layout Enumerate
2353 sync();
2354 \end_layout
2355
2356 \begin_layout Standard
2357 On current ext3, each sync flushes all data to disk, so the next 3 syncs
2358  are relatively expensive.
2359  But this could become a performance bottleneck on other filesystems such
2360  as ext4.
2361 \end_layout
2362
2363 \begin_layout Subsubsection
2364 Proposed Solution
2365 \end_layout
2366
2367 \begin_layout Standard
2368 Neil Brown points out that this is overzealous, and only one sync is needed:
2369 \end_layout
2370
2371 \begin_layout Enumerate
2372 Bundle the recovery data, a transaction counter and a strong checksum of
2373  the new data.
2374 \end_layout
2375
2376 \begin_layout Enumerate
2377 Strong checksum that whole bundle.
2378 \end_layout
2379
2380 \begin_layout Enumerate
2381 Store the bundle in the database.
2382 \end_layout
2383
2384 \begin_layout Enumerate
2385 Overwrite the oldest of the two recovery pointers in the header (identified
2386  using the transaction counter) with the offset of this bundle.
2387 \end_layout
2388
2389 \begin_layout Enumerate
2390 sync.
2391 \end_layout
2392
2393 \begin_layout Enumerate
2394 Write the new data to the file.
2395 \end_layout
2396
2397 \begin_layout Standard
2398 Checking for recovery means identifying the latest bundle with a valid checksum
2399  and using the new data checksum to ensure that it has been applied.
2400  This is more expensive than the current check, but need only be done at
2401  open.
2402  For running databases, a separate header field can be used to indicate
2403  a transaction in progress; we need only check for recovery if this is set.
2404 \end_layout
2405
2406 \begin_layout Subsubsection
2407 Status
2408 \end_layout
2409
2410 \begin_layout Standard
2411 Deferred.
2412 \end_layout
2413
2414 \begin_layout Subsection
2415 \begin_inset CommandInset label
2416 LatexCommand label
2417 name "sub:TDB-Does-Not"
2418
2419 \end_inset
2420
2421 TDB Does Not Have Snapshot Support
2422 \end_layout
2423
2424 \begin_layout Subsubsection
2425 Proposed SolutionNone.
2426  At some point you say
2427 \begin_inset Quotes eld
2428 \end_inset
2429
2430 use a real database
2431 \begin_inset Quotes erd
2432 \end_inset
2433
2434  (but see
2435 \begin_inset CommandInset ref
2436 LatexCommand ref
2437 reference "replay-attribute"
2438
2439 \end_inset
2440
2441 ).
2442 \end_layout
2443
2444 \begin_layout Standard
2445 But as a thought experiment, if we implemented transactions to only overwrite
2446  free entries (this is tricky: there must not be a header in each entry
2447  which indicates whether it is free, but use of presence in metadata elsewhere),
2448  and a pointer to the hash table, we could create an entirely new commit
2449  without destroying existing data.
2450  Then it would be easy to implement snapshots in a similar way.
2451 \end_layout
2452
2453 \begin_layout Standard
2454 This would not allow arbitrary changes to the database, such as tdb_repack
2455  does, and would require more space (since we have to preserve the current
2456  and future entries at once).
2457  If we used hash trees rather than one big hash table, we might only have
2458  to rewrite some sections of the hash, too.
2459 \end_layout
2460
2461 \begin_layout Standard
2462 We could then implement snapshots using a similar method, using multiple
2463  different hash tables/free tables.
2464 \end_layout
2465
2466 \begin_layout Subsubsection
2467 Status
2468 \end_layout
2469
2470 \begin_layout Standard
2471 Deferred.
2472 \end_layout
2473
2474 \begin_layout Subsection
2475 Transactions Cannot Operate in Parallel
2476 \end_layout
2477
2478 \begin_layout Standard
2479 This would be useless for ldb, as it hits the index records with just about
2480  every update.
2481  It would add significant complexity in resolving clashes, and cause the
2482  all transaction callers to write their code to loop in the case where the
2483  transactions spuriously failed.
2484 \end_layout
2485
2486 \begin_layout Subsubsection
2487 Proposed Solution
2488 \end_layout
2489
2490 \begin_layout Standard
2491 None (but see
2492 \begin_inset CommandInset ref
2493 LatexCommand ref
2494 reference "replay-attribute"
2495
2496 \end_inset
2497
2498 ).
2499  We could solve a small part of the problem by providing read-only transactions.
2500  These would allow one write transaction to begin, but it could not commit
2501  until all r/o transactions are done.
2502  This would require a new RO_TRANSACTION_LOCK, which would be upgraded on
2503  commit.
2504 \end_layout
2505
2506 \begin_layout Subsubsection
2507 Status
2508 \end_layout
2509
2510 \begin_layout Standard
2511 Deferred.
2512 \end_layout
2513
2514 \begin_layout Subsection
2515 Default Hash Function Is Suboptimal
2516 \end_layout
2517
2518 \begin_layout Standard
2519 The Knuth-inspired multiplicative hash used by tdb is fairly slow (especially
2520  if we expand it to 64 bits), and works best when the hash bucket size is
2521  a prime number (which also means a slow modulus).
2522  In addition, it is highly predictable which could potentially lead to a
2523  Denial of Service attack in some TDB uses.
2524 \end_layout
2525
2526 \begin_layout Subsubsection
2527 Proposed Solution
2528 \end_layout
2529
2530 \begin_layout Standard
2531 The Jenkins lookup3 hash
2532 \begin_inset Foot
2533 status open
2534
2535 \begin_layout Plain Layout
2536 http://burtleburtle.net/bob/c/lookup3.c
2537 \end_layout
2538
2539 \end_inset
2540
2541  is a fast and superbly-mixing hash.
2542  It's used by the Linux kernel and almost everything else.
2543  This has the particular properties that it takes an initial seed, and produces
2544  two 32 bit hash numbers, which we can combine into a 64-bit hash.
2545 \end_layout
2546
2547 \begin_layout Standard
2548 The seed should be created at tdb-creation time from some random source,
2549  and placed in the header.
2550  This is far from foolproof, but adds a little bit of protection against
2551  hash bombing.
2552 \end_layout
2553
2554 \begin_layout Subsubsection
2555 Status
2556 \end_layout
2557
2558 \begin_layout Standard
2559 Complete.
2560 \end_layout
2561
2562 \begin_layout Subsection
2563 \begin_inset CommandInset label
2564 LatexCommand label
2565 name "Reliable-Traversal-Adds"
2566
2567 \end_inset
2568
2569 Reliable Traversal Adds Complexity
2570 \end_layout
2571
2572 \begin_layout Standard
2573 We lock a record during traversal iteration, and try to grab that lock in
2574  the delete code.
2575  If that grab on delete fails, we simply mark it deleted and continue onwards;
2576  traversal checks for this condition and does the delete when it moves off
2577  the record.
2578 \end_layout
2579
2580 \begin_layout Standard
2581 If traversal terminates, the dead record may be left indefinitely.
2582 \end_layout
2583
2584 \begin_layout Subsubsection
2585 Proposed Solution
2586 \end_layout
2587
2588 \begin_layout Standard
2589 Remove reliability guarantees; see
2590 \begin_inset CommandInset ref
2591 LatexCommand ref
2592 reference "traverse-Proposed-Solution"
2593
2594 \end_inset
2595
2596 .
2597 \end_layout
2598
2599 \begin_layout Subsubsection
2600 Status
2601 \end_layout
2602
2603 \begin_layout Standard
2604 Complete.
2605 \end_layout
2606
2607 \begin_layout Subsection
2608 Fcntl Locking Adds Overhead
2609 \end_layout
2610
2611 \begin_layout Standard
2612 Placing a fcntl lock means a system call, as does removing one.
2613  This is actually one reason why transactions can be faster (everything
2614  is locked once at transaction start).
2615  In the uncontended case, this overhead can theoretically be eliminated.
2616 \end_layout
2617
2618 \begin_layout Subsubsection
2619 Proposed Solution
2620 \end_layout
2621
2622 \begin_layout Standard
2623 None.
2624 \end_layout
2625
2626 \begin_layout Standard
2627 We tried this before with spinlock support, in the early days of TDB, and
2628  it didn't make much difference except in manufactured benchmarks.
2629 \end_layout
2630
2631 \begin_layout Standard
2632 We could use spinlocks (with futex kernel support under Linux), but it means
2633  that we lose automatic cleanup when a process dies with a lock.
2634  There is a method of auto-cleanup under Linux, but it's not supported by
2635  other operating systems.
2636  We could reintroduce a clear-if-first-style lock and sweep for dead futexes
2637  on open, but that wouldn't help the normal case of one concurrent opener
2638  dying.
2639  Increasingly elaborate repair schemes could be considered, but they require
2640  an ABI change (everyone must use them) anyway, so there's no need to do
2641  this at the same time as everything else.
2642 \end_layout
2643
2644 \begin_layout Subsection
2645 Some Transactions Don't Require Durability
2646 \end_layout
2647
2648 \begin_layout Standard
2649 Volker points out that gencache uses a CLEAR_IF_FIRST tdb for normal (fast)
2650  usage, and occasionally empties the results into a transactional TDB.
2651  This kind of usage prioritizes performance over durability: as long as
2652  we are consistent, data can be lost.
2653 \end_layout
2654
2655 \begin_layout Standard
2656 This would be more neatly implemented inside tdb: a
2657 \begin_inset Quotes eld
2658 \end_inset
2659
2660 soft
2661 \begin_inset Quotes erd
2662 \end_inset
2663
2664  transaction commit (ie.
2665  syncless) which meant that data may be reverted on a crash.
2666 \end_layout
2667
2668 \begin_layout Subsubsection
2669 Proposed Solution
2670 \end_layout
2671
2672 \begin_layout Standard
2673 None.
2674 \end_layout
2675
2676 \begin_layout Standard
2677 Unfortunately any transaction scheme which overwrites old data requires
2678  a sync before that overwrite to avoid the possibility of corruption.
2679 \end_layout
2680
2681 \begin_layout Standard
2682 It seems possible to use a scheme similar to that described in
2683 \begin_inset CommandInset ref
2684 LatexCommand ref
2685 reference "sub:TDB-Does-Not"
2686
2687 \end_inset
2688
2689 ,where transactions are committed without overwriting existing data, and
2690  an array of top-level pointers were available in the header.
2691  If the transaction is
2692 \begin_inset Quotes eld
2693 \end_inset
2694
2695 soft
2696 \begin_inset Quotes erd
2697 \end_inset
2698
2699  then we would not need a sync at all: existing processes would pick up
2700  the new hash table and free list and work with that.
2701 \end_layout
2702
2703 \begin_layout Standard
2704 At some later point, a sync would allow recovery of the old data into the
2705  free lists (perhaps when the array of top-level pointers filled).
2706  On crash, tdb_open() would examine the array of top levels, and apply the
2707  transactions until it encountered an invalid checksum.
2708 \end_layout
2709
2710 \begin_layout Subsection
2711 Tracing Is Fragile, Replay Is External
2712 \end_layout
2713
2714 \begin_layout Standard
2715 The current TDB has compile-time-enabled tracing code, but it often breaks
2716  as it is not enabled by default.
2717  In a similar way, the ctdb code has an external wrapper which does replay
2718  tracing so it can coordinate cluster-wide transactions.
2719 \end_layout
2720
2721 \begin_layout Subsubsection
2722 Proposed Solution
2723 \begin_inset CommandInset label
2724 LatexCommand label
2725 name "replay-attribute"
2726
2727 \end_inset
2728
2729
2730 \end_layout
2731
2732 \begin_layout Standard
2733 Tridge points out that an attribute can be later added to tdb_open (see
2734
2735 \begin_inset CommandInset ref
2736 LatexCommand ref
2737 reference "attributes"
2738
2739 \end_inset
2740
2741 ) to provide replay/trace hooks, which could become the basis for this and
2742  future parallel transactions and snapshot support.
2743 \end_layout
2744
2745 \begin_layout Subsubsection
2746 Status
2747 \end_layout
2748
2749 \begin_layout Standard
2750 Deferred.
2751 \end_layout
2752
2753 \end_body
2754 \end_document