tdb2: make tests work in parallel.
[ccan] / ccan / tdb2 / doc / design.lyx,v
1 head    1.13;
2 access;
3 symbols;
4 locks; strict;
5 comment @# @;
6
7
8 1.13
9 date    2011.03.01.11.46.54;    author rusty;   state Exp;
10 branches;
11 next    1.12;
12
13 1.12
14 date    2010.12.01.12.20.49;    author rusty;   state Exp;
15 branches;
16 next    1.11;
17
18 1.11
19 date    2010.12.01.11.55.20;    author rusty;   state Exp;
20 branches;
21 next    1.10;
22
23 1.10
24 date    2010.09.14.00.33.57;    author rusty;   state Exp;
25 branches;
26 next    1.9;
27
28 1.9
29 date    2010.09.09.07.25.12;    author rusty;   state Exp;
30 branches;
31 next    1.8;
32
33 1.8
34 date    2010.09.02.02.29.05;    author rusty;   state Exp;
35 branches;
36 next    1.7;
37
38 1.7
39 date    2010.09.01.10.58.12;    author rusty;   state Exp;
40 branches;
41 next    1.6;
42
43 1.6
44 date    2010.08.02.00.21.43;    author rusty;   state Exp;
45 branches;
46 next    1.5;
47
48 1.5
49 date    2010.08.02.00.21.16;    author rusty;   state Exp;
50 branches;
51 next    1.4;
52
53 1.4
54 date    2010.05.10.13.09.11;    author rusty;   state Exp;
55 branches;
56 next    1.3;
57
58 1.3
59 date    2010.05.10.11.58.37;    author rusty;   state Exp;
60 branches;
61 next    1.2;
62
63 1.2
64 date    2010.05.10.05.35.13;    author rusty;   state Exp;
65 branches;
66 next    1.1;
67
68 1.1
69 date    2010.05.04.02.29.16;    author rusty;   state Exp;
70 branches;
71 next    ;
72
73
74 desc
75 @First draft
76 @
77
78
79 1.13
80 log
81 @Thread-safe API
82 @
83 text
84 @#LyX 1.6.7 created this file. For more info see http://www.lyx.org/
85 \lyxformat 345
86 \begin_document
87 \begin_header
88 \textclass article
89 \use_default_options true
90 \language english
91 \inputencoding auto
92 \font_roman default
93 \font_sans default
94 \font_typewriter default
95 \font_default_family default
96 \font_sc false
97 \font_osf false
98 \font_sf_scale 100
99 \font_tt_scale 100
100
101 \graphics default
102 \paperfontsize default
103 \use_hyperref false
104 \papersize default
105 \use_geometry false
106 \use_amsmath 1
107 \use_esint 1
108 \cite_engine basic
109 \use_bibtopic false
110 \paperorientation portrait
111 \secnumdepth 3
112 \tocdepth 3
113 \paragraph_separation indent
114 \defskip medskip
115 \quotes_language english
116 \papercolumns 1
117 \papersides 1
118 \paperpagestyle default
119 \tracking_changes true
120 \output_changes true
121 \author "Rusty Russell,,," 
122 \author "" 
123 \end_header
124
125 \begin_body
126
127 \begin_layout Title
128 TDB2: A Redesigning The Trivial DataBase
129 \end_layout
130
131 \begin_layout Author
132 Rusty Russell, IBM Corporation
133 \end_layout
134
135 \begin_layout Date
136 1-December-2010
137 \end_layout
138
139 \begin_layout Abstract
140 The Trivial DataBase on-disk format is 32 bits; with usage cases heading
141  towards the 4G limit, that must change.
142  This required breakage provides an opportunity to revisit TDB's other design
143  decisions and reassess them.
144 \end_layout
145
146 \begin_layout Section
147 Introduction
148 \end_layout
149
150 \begin_layout Standard
151 The Trivial DataBase was originally written by Andrew Tridgell as a simple
152  key/data pair storage system with the same API as dbm, but allowing multiple
153  readers and writers while being small enough (< 1000 lines of C) to include
154  in SAMBA.
155  The simple design created in 1999 has proven surprisingly robust and performant
156 , used in Samba versions 3 and 4 as well as numerous other projects.
157  Its useful life was greatly increased by the (backwards-compatible!) addition
158  of transaction support in 2005.
159 \end_layout
160
161 \begin_layout Standard
162 The wider variety and greater demands of TDB-using code has lead to some
163  organic growth of the API, as well as some compromises on the implementation.
164  None of these, by themselves, are seen as show-stoppers, but the cumulative
165  effect is to a loss of elegance over the initial, simple TDB implementation.
166  Here is a table of the approximate number of lines of implementation code
167  and number of API functions at the end of each year:
168 \end_layout
169
170 \begin_layout Standard
171 \begin_inset Tabular
172 <lyxtabular version="3" rows="12" columns="3">
173 <features>
174 <column alignment="center" valignment="top" width="0">
175 <column alignment="center" valignment="top" width="0">
176 <column alignment="center" valignment="top" width="0">
177 <row>
178 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
179 \begin_inset Text
180
181 \begin_layout Plain Layout
182 Year End
183 \end_layout
184
185 \end_inset
186 </cell>
187 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
188 \begin_inset Text
189
190 \begin_layout Plain Layout
191 API Functions
192 \end_layout
193
194 \end_inset
195 </cell>
196 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
197 \begin_inset Text
198
199 \begin_layout Plain Layout
200 Lines of C Code Implementation
201 \end_layout
202
203 \end_inset
204 </cell>
205 </row>
206 <row>
207 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
208 \begin_inset Text
209
210 \begin_layout Plain Layout
211 1999
212 \end_layout
213
214 \end_inset
215 </cell>
216 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
217 \begin_inset Text
218
219 \begin_layout Plain Layout
220 13
221 \end_layout
222
223 \end_inset
224 </cell>
225 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
226 \begin_inset Text
227
228 \begin_layout Plain Layout
229 1195
230 \end_layout
231
232 \end_inset
233 </cell>
234 </row>
235 <row>
236 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
237 \begin_inset Text
238
239 \begin_layout Plain Layout
240 2000
241 \end_layout
242
243 \end_inset
244 </cell>
245 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
246 \begin_inset Text
247
248 \begin_layout Plain Layout
249 24
250 \end_layout
251
252 \end_inset
253 </cell>
254 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
255 \begin_inset Text
256
257 \begin_layout Plain Layout
258 1725
259 \end_layout
260
261 \end_inset
262 </cell>
263 </row>
264 <row>
265 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
266 \begin_inset Text
267
268 \begin_layout Plain Layout
269 2001
270 \end_layout
271
272 \end_inset
273 </cell>
274 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
275 \begin_inset Text
276
277 \begin_layout Plain Layout
278 32
279 \end_layout
280
281 \end_inset
282 </cell>
283 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
284 \begin_inset Text
285
286 \begin_layout Plain Layout
287 2228
288 \end_layout
289
290 \end_inset
291 </cell>
292 </row>
293 <row>
294 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
295 \begin_inset Text
296
297 \begin_layout Plain Layout
298 2002
299 \end_layout
300
301 \end_inset
302 </cell>
303 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
304 \begin_inset Text
305
306 \begin_layout Plain Layout
307 35
308 \end_layout
309
310 \end_inset
311 </cell>
312 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
313 \begin_inset Text
314
315 \begin_layout Plain Layout
316 2481
317 \end_layout
318
319 \end_inset
320 </cell>
321 </row>
322 <row>
323 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
324 \begin_inset Text
325
326 \begin_layout Plain Layout
327 2003
328 \end_layout
329
330 \end_inset
331 </cell>
332 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
333 \begin_inset Text
334
335 \begin_layout Plain Layout
336 35
337 \end_layout
338
339 \end_inset
340 </cell>
341 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
342 \begin_inset Text
343
344 \begin_layout Plain Layout
345 2552
346 \end_layout
347
348 \end_inset
349 </cell>
350 </row>
351 <row>
352 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
353 \begin_inset Text
354
355 \begin_layout Plain Layout
356 2004
357 \end_layout
358
359 \end_inset
360 </cell>
361 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
362 \begin_inset Text
363
364 \begin_layout Plain Layout
365 40
366 \end_layout
367
368 \end_inset
369 </cell>
370 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
371 \begin_inset Text
372
373 \begin_layout Plain Layout
374 2584
375 \end_layout
376
377 \end_inset
378 </cell>
379 </row>
380 <row>
381 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
382 \begin_inset Text
383
384 \begin_layout Plain Layout
385 2005
386 \end_layout
387
388 \end_inset
389 </cell>
390 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
391 \begin_inset Text
392
393 \begin_layout Plain Layout
394 38
395 \end_layout
396
397 \end_inset
398 </cell>
399 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
400 \begin_inset Text
401
402 \begin_layout Plain Layout
403 2647
404 \end_layout
405
406 \end_inset
407 </cell>
408 </row>
409 <row>
410 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
411 \begin_inset Text
412
413 \begin_layout Plain Layout
414 2006
415 \end_layout
416
417 \end_inset
418 </cell>
419 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
420 \begin_inset Text
421
422 \begin_layout Plain Layout
423 52
424 \end_layout
425
426 \end_inset
427 </cell>
428 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
429 \begin_inset Text
430
431 \begin_layout Plain Layout
432 3754
433 \end_layout
434
435 \end_inset
436 </cell>
437 </row>
438 <row>
439 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
440 \begin_inset Text
441
442 \begin_layout Plain Layout
443 2007
444 \end_layout
445
446 \end_inset
447 </cell>
448 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
449 \begin_inset Text
450
451 \begin_layout Plain Layout
452 66
453 \end_layout
454
455 \end_inset
456 </cell>
457 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
458 \begin_inset Text
459
460 \begin_layout Plain Layout
461 4398
462 \end_layout
463
464 \end_inset
465 </cell>
466 </row>
467 <row>
468 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
469 \begin_inset Text
470
471 \begin_layout Plain Layout
472 2008
473 \end_layout
474
475 \end_inset
476 </cell>
477 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
478 \begin_inset Text
479
480 \begin_layout Plain Layout
481 71
482 \end_layout
483
484 \end_inset
485 </cell>
486 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
487 \begin_inset Text
488
489 \begin_layout Plain Layout
490 4768
491 \end_layout
492
493 \end_inset
494 </cell>
495 </row>
496 <row>
497 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
498 \begin_inset Text
499
500 \begin_layout Plain Layout
501 2009
502 \end_layout
503
504 \end_inset
505 </cell>
506 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
507 \begin_inset Text
508
509 \begin_layout Plain Layout
510 73
511 \end_layout
512
513 \end_inset
514 </cell>
515 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
516 \begin_inset Text
517
518 \begin_layout Plain Layout
519 5715
520 \end_layout
521
522 \end_inset
523 </cell>
524 </row>
525 </lyxtabular>
526
527 \end_inset
528
529
530 \end_layout
531
532 \begin_layout Standard
533 This review is an attempt to catalog and address all the known issues with
534  TDB and create solutions which address the problems without significantly
535  increasing complexity; all involved are far too aware of the dangers of
536  second system syndrome in rewriting a successful project like this.
537 \end_layout
538
539 \begin_layout Section
540 API Issues
541 \end_layout
542
543 \begin_layout Subsection
544 tdb_open_ex Is Not Expandable
545 \end_layout
546
547 \begin_layout Standard
548 The tdb_open() call was expanded to tdb_open_ex(), which added an optional
549  hashing function and an optional logging function argument.
550  Additional arguments to open would require the introduction of a tdb_open_ex2
551  call etc.
552 \end_layout
553
554 \begin_layout Subsubsection
555 Proposed Solution
556 \begin_inset CommandInset label
557 LatexCommand label
558 name "attributes"
559
560 \end_inset
561
562
563 \end_layout
564
565 \begin_layout Standard
566 tdb_open() will take a linked-list of attributes:
567 \end_layout
568
569 \begin_layout LyX-Code
570 enum tdb_attribute {
571 \end_layout
572
573 \begin_layout LyX-Code
574     TDB_ATTRIBUTE_LOG = 0,
575 \end_layout
576
577 \begin_layout LyX-Code
578     TDB_ATTRIBUTE_HASH = 1
579 \end_layout
580
581 \begin_layout LyX-Code
582 };
583 \end_layout
584
585 \begin_layout LyX-Code
586 struct tdb_attribute_base {
587 \end_layout
588
589 \begin_layout LyX-Code
590     enum tdb_attribute attr;
591 \end_layout
592
593 \begin_layout LyX-Code
594     union tdb_attribute *next;
595 \end_layout
596
597 \begin_layout LyX-Code
598 };
599 \end_layout
600
601 \begin_layout LyX-Code
602 struct tdb_attribute_log {
603 \end_layout
604
605 \begin_layout LyX-Code
606     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_LOG */
607 \end_layout
608
609 \begin_layout LyX-Code
610     tdb_log_func log_fn;
611 \end_layout
612
613 \begin_layout LyX-Code
614     void *log_private;
615 \end_layout
616
617 \begin_layout LyX-Code
618 };
619 \end_layout
620
621 \begin_layout LyX-Code
622 struct tdb_attribute_hash {
623 \end_layout
624
625 \begin_layout LyX-Code
626     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_HASH */
627 \end_layout
628
629 \begin_layout LyX-Code
630     tdb_hash_func hash_fn;
631 \end_layout
632
633 \begin_layout LyX-Code
634     void *hash_private;
635 \end_layout
636
637 \begin_layout LyX-Code
638 };
639 \end_layout
640
641 \begin_layout LyX-Code
642 union tdb_attribute {
643 \end_layout
644
645 \begin_layout LyX-Code
646     struct tdb_attribute_base base;
647 \end_layout
648
649 \begin_layout LyX-Code
650     struct tdb_attribute_log log;
651 \end_layout
652
653 \begin_layout LyX-Code
654     struct tdb_attribute_hash hash;
655 \end_layout
656
657 \begin_layout LyX-Code
658 };
659 \end_layout
660
661 \begin_layout Standard
662 This allows future attributes to be added, even if this expands the size
663  of the union.
664 \end_layout
665
666 \begin_layout Subsubsection
667 Status
668 \end_layout
669
670 \begin_layout Standard
671 Complete.
672 \end_layout
673
674 \begin_layout Subsection
675 tdb_traverse Makes Impossible Guarantees
676 \end_layout
677
678 \begin_layout Standard
679 tdb_traverse (and tdb_firstkey/tdb_nextkey) predate transactions, and it
680  was thought that it was important to guarantee that all records which exist
681  at the start and end of the traversal would be included, and no record
682  would be included twice.
683 \end_layout
684
685 \begin_layout Standard
686 This adds complexity (see
687 \begin_inset CommandInset ref
688 LatexCommand ref
689 reference "Reliable-Traversal-Adds"
690
691 \end_inset
692
693 ) and does not work anyway for records which are altered (in particular,
694  those which are expanded may be effectively deleted and re-added behind
695  the traversal).
696 \end_layout
697
698 \begin_layout Subsubsection
699 \begin_inset CommandInset label
700 LatexCommand label
701 name "traverse-Proposed-Solution"
702
703 \end_inset
704
705 Proposed Solution
706 \end_layout
707
708 \begin_layout Standard
709 Abandon the guarantee.
710  You will see every record if no changes occur during your traversal, otherwise
711  you will see some subset.
712  You can prevent changes by using a transaction or the locking API.
713 \end_layout
714
715 \begin_layout Subsubsection
716 Status
717 \end_layout
718
719 \begin_layout Standard
720 Complete.
721  Delete-during-traverse will still delete every record, too (assuming no
722  other changes).
723 \end_layout
724
725 \begin_layout Subsection
726 Nesting of Transactions Is Fraught
727 \end_layout
728
729 \begin_layout Standard
730 TDB has alternated between allowing nested transactions and not allowing
731  them.
732  Various paths in the Samba codebase assume that transactions will nest,
733  and in a sense they can: the operation is only committed to disk when the
734  outer transaction is committed.
735  There are two problems, however:
736 \end_layout
737
738 \begin_layout Enumerate
739 Canceling the inner transaction will cause the outer transaction commit
740  to fail, and will not undo any operations since the inner transaction began.
741  This problem is soluble with some additional internal code.
742 \end_layout
743
744 \begin_layout Enumerate
745 An inner transaction commit can be cancelled by the outer transaction.
746  This is desirable in the way which Samba's database initialization code
747  uses transactions, but could be a surprise to any users expecting a successful
748  transaction commit to expose changes to others.
749 \end_layout
750
751 \begin_layout Standard
752 The current solution is to specify the behavior at tdb_open(), with the
753  default currently that nested transactions are allowed.
754  This flag can also be changed at runtime.
755 \end_layout
756
757 \begin_layout Subsubsection
758 Proposed Solution
759 \end_layout
760
761 \begin_layout Standard
762 Given the usage patterns, it seems that the 
763 \begin_inset Quotes eld
764 \end_inset
765
766 least-surprise
767 \begin_inset Quotes erd
768 \end_inset
769
770  behavior of disallowing nested transactions should become the default.
771  Additionally, it seems the outer transaction is the only code which knows
772  whether inner transactions should be allowed, so a flag to indicate this
773  could be added to tdb_transaction_start.
774  However, this behavior can be simulated with a wrapper which uses tdb_add_flags
775 () and tdb_remove_flags(), so the API should not be expanded for this relatively
776 -obscure case.
777 \end_layout
778
779 \begin_layout Subsubsection
780 Status
781 \end_layout
782
783 \begin_layout Standard
784
785 \change_deleted 0 1298979572
786 Incomplete; nesting flag is still defined as per tdb1.
787 \change_inserted 0 1298979584
788 Complete; the nesting flag has been removed.
789 \change_unchanged
790
791 \end_layout
792
793 \begin_layout Subsection
794 Incorrect Hash Function is Not Detected
795 \end_layout
796
797 \begin_layout Standard
798 tdb_open_ex() allows the calling code to specify a different hash function
799  to use, but does not check that all other processes accessing this tdb
800  are using the same hash function.
801  The result is that records are missing from tdb_fetch().
802 \end_layout
803
804 \begin_layout Subsubsection
805 Proposed Solution
806 \end_layout
807
808 \begin_layout Standard
809 The header should contain an example hash result (eg.
810  the hash of 0xdeadbeef), and tdb_open_ex() should check that the given
811  hash function produces the same answer, or fail the tdb_open call.
812 \end_layout
813
814 \begin_layout Subsubsection
815 Status
816 \end_layout
817
818 \begin_layout Standard
819 Complete.
820 \end_layout
821
822 \begin_layout Subsection
823 tdb_set_max_dead/TDB_VOLATILE Expose Implementation
824 \end_layout
825
826 \begin_layout Standard
827 In response to scalability issues with the free list (
828 \begin_inset CommandInset ref
829 LatexCommand ref
830 reference "TDB-Freelist-Is"
831
832 \end_inset
833
834 ) two API workarounds have been incorporated in TDB: tdb_set_max_dead()
835  and the TDB_VOLATILE flag to tdb_open.
836  The latter actually calls the former with an argument of 
837 \begin_inset Quotes eld
838 \end_inset
839
840 5
841 \begin_inset Quotes erd
842 \end_inset
843
844 .
845 \end_layout
846
847 \begin_layout Standard
848 This code allows deleted records to accumulate without putting them in the
849  free list.
850  On delete we iterate through each chain and free them in a batch if there
851  are more than max_dead entries.
852  These are never otherwise recycled except as a side-effect of a tdb_repack.
853 \end_layout
854
855 \begin_layout Subsubsection
856 Proposed Solution
857 \end_layout
858
859 \begin_layout Standard
860 With the scalability problems of the freelist solved, this API can be removed.
861  The TDB_VOLATILE flag may still be useful as a hint that store and delete
862  of records will be at least as common as fetch in order to allow some internal
863  tuning, but initially will become a no-op.
864 \end_layout
865
866 \begin_layout Subsubsection
867 Status
868 \end_layout
869
870 \begin_layout Standard
871 Incomplete.
872  TDB_VOLATILE still defined, but implementation should fail on unknown flags
873  to be future-proof.
874 \end_layout
875
876 \begin_layout Subsection
877 \begin_inset CommandInset label
878 LatexCommand label
879 name "TDB-Files-Cannot"
880
881 \end_inset
882
883 TDB Files Cannot Be Opened Multiple Times In The Same Process
884 \end_layout
885
886 \begin_layout Standard
887 No process can open the same TDB twice; we check and disallow it.
888  This is an unfortunate side-effect of fcntl locks, which operate on a per-file
889  rather than per-file-descriptor basis, and do not nest.
890  Thus, closing any file descriptor on a file clears all the locks obtained
891  by this process, even if they were placed using a different file descriptor!
892 \end_layout
893
894 \begin_layout Standard
895 Note that even if this were solved, deadlock could occur if operations were
896  nested: this is a more manageable programming error in most cases.
897 \end_layout
898
899 \begin_layout Subsubsection
900 Proposed Solution
901 \end_layout
902
903 \begin_layout Standard
904 We could lobby POSIX to fix the perverse rules, or at least lobby Linux
905  to violate them so that the most common implementation does not have this
906  restriction.
907  This would be a generally good idea for other fcntl lock users.
908 \end_layout
909
910 \begin_layout Standard
911 Samba uses a wrapper which hands out the same tdb_context to multiple callers
912  if this happens, and does simple reference counting.
913  We should do this inside the tdb library, which already emulates lock nesting
914  internally; it would need to recognize when deadlock occurs within a single
915  process.
916  This would create a new failure mode for tdb operations (while we currently
917  handle locking failures, they are impossible in normal use and a process
918  encountering them can do little but give up).
919 \end_layout
920
921 \begin_layout Standard
922 I do not see benefit in an additional tdb_open flag to indicate whether
923  re-opening is allowed, as though there may be some benefit to adding a
924  call to detect when a tdb_context is shared, to allow other to create such
925  an API.
926 \end_layout
927
928 \begin_layout Subsubsection
929 Status
930 \end_layout
931
932 \begin_layout Standard
933 Incomplete.
934 \end_layout
935
936 \begin_layout Subsection
937 TDB API Is Not POSIX Thread-safe
938 \end_layout
939
940 \begin_layout Standard
941 The TDB API uses an error code which can be queried after an operation to
942  determine what went wrong.
943  This programming model does not work with threads, unless specific additional
944  guarantees are given by the implementation.
945  In addition, even otherwise-independent threads cannot open the same TDB
946  (as in 
947 \begin_inset CommandInset ref
948 LatexCommand ref
949 reference "TDB-Files-Cannot"
950
951 \end_inset
952
953 ).
954 \end_layout
955
956 \begin_layout Subsubsection
957 Proposed Solution
958 \end_layout
959
960 \begin_layout Standard
961 Reachitecting the API to include a tdb_errcode pointer would be a great
962  deal of churn
963 \change_inserted 0 1298979557
964 , but fortunately most functions return 0 on success and -1 on error: we
965  can change these to return 0 on success and a negative error code on error,
966  and the API remains similar to previous.
967  The tdb_fetch, tdb_firstkey and tdb_nextkey functions need to take a TDB_DATA
968  pointer and return an error code.
969  It is also simpler to have tdb_nextkey replace its key argument in place,
970  freeing up any old .dptr.
971 \end_layout
972
973 \begin_layout Standard
974
975 \change_deleted 0 1298979438
976 ; we are better to guarantee that the tdb_errcode is per-thread so the current
977  programming model can be maintained.
978 \end_layout
979
980 \begin_layout Standard
981
982 \change_deleted 0 1298979438
983 This requires dynamic per-thread allocations, which is awkward with POSIX
984  threads (pthread_key_create space is limited and we cannot simply allocate
985  a key for every TDB).
986 \change_unchanged
987
988 \end_layout
989
990 \begin_layout Standard
991 Internal locking is required to make sure that fcntl locks do not overlap
992  between threads, and also that the global list of tdbs is maintained.
993 \end_layout
994
995 \begin_layout Standard
996 The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe
997  version of the library, and otherwise no overhead will exist.
998  Alternatively, a hooking mechanism similar to that proposed for 
999 \begin_inset CommandInset ref
1000 LatexCommand ref
1001 reference "Proposed-Solution-locking-hook"
1002
1003 \end_inset
1004
1005  could be used to enable pthread locking at runtime.
1006 \end_layout
1007
1008 \begin_layout Subsubsection
1009 Status
1010 \end_layout
1011
1012 \begin_layout Standard
1013 Incomplete
1014 \change_inserted 0 1298979681
1015 ; API has been changed but thread safety has not been implemented.
1016 \change_deleted 0 1298979669
1017 .
1018 \change_unchanged
1019
1020 \end_layout
1021
1022 \begin_layout Subsection
1023 *_nonblock Functions And *_mark Functions Expose Implementation
1024 \end_layout
1025
1026 \begin_layout Standard
1027 CTDB
1028 \begin_inset Foot
1029 status collapsed
1030
1031 \begin_layout Plain Layout
1032 Clustered TDB, see http://ctdb.samba.org
1033 \end_layout
1034
1035 \end_inset
1036
1037  wishes to operate on TDB in a non-blocking manner.
1038  This is currently done as follows:
1039 \end_layout
1040
1041 \begin_layout Enumerate
1042 Call the _nonblock variant of an API function (eg.
1043  tdb_lockall_nonblock).
1044  If this fails:
1045 \end_layout
1046
1047 \begin_layout Enumerate
1048 Fork a child process, and wait for it to call the normal variant (eg.
1049  tdb_lockall).
1050 \end_layout
1051
1052 \begin_layout Enumerate
1053 If the child succeeds, call the _mark variant to indicate we already have
1054  the locks (eg.
1055  tdb_lockall_mark).
1056 \end_layout
1057
1058 \begin_layout Enumerate
1059 Upon completion, tell the child to release the locks (eg.
1060  tdb_unlockall).
1061 \end_layout
1062
1063 \begin_layout Enumerate
1064 Indicate to tdb that it should consider the locks removed (eg.
1065  tdb_unlockall_mark).
1066 \end_layout
1067
1068 \begin_layout Standard
1069 There are several issues with this approach.
1070  Firstly, adding two new variants of each function clutters the API for
1071  an obscure use, and so not all functions have three variants.
1072  Secondly, it assumes that all paths of the functions ask for the same locks,
1073  otherwise the parent process will have to get a lock which the child doesn't
1074  have under some circumstances.
1075  I don't believe this is currently the case, but it constrains the implementatio
1076 n.
1077  
1078 \end_layout
1079
1080 \begin_layout Subsubsection
1081 \begin_inset CommandInset label
1082 LatexCommand label
1083 name "Proposed-Solution-locking-hook"
1084
1085 \end_inset
1086
1087 Proposed Solution
1088 \end_layout
1089
1090 \begin_layout Standard
1091 Implement a hook for locking methods, so that the caller can control the
1092  calls to create and remove fcntl locks.
1093  In this scenario, ctdbd would operate as follows:
1094 \end_layout
1095
1096 \begin_layout Enumerate
1097 Call the normal API function, eg tdb_lockall().
1098 \end_layout
1099
1100 \begin_layout Enumerate
1101 When the lock callback comes in, check if the child has the lock.
1102  Initially, this is always false.
1103  If so, return 0.
1104  Otherwise, try to obtain it in non-blocking mode.
1105  If that fails, return EWOULDBLOCK.
1106 \end_layout
1107
1108 \begin_layout Enumerate
1109 Release locks in the unlock callback as normal.
1110 \end_layout
1111
1112 \begin_layout Enumerate
1113 If tdb_lockall() fails, see if we recorded a lock failure; if so, call the
1114  child to repeat the operation.
1115 \end_layout
1116
1117 \begin_layout Enumerate
1118 The child records what locks it obtains, and returns that information to
1119  the parent.
1120 \end_layout
1121
1122 \begin_layout Enumerate
1123 When the child has succeeded, goto 1.
1124 \end_layout
1125
1126 \begin_layout Standard
1127 This is flexible enough to handle any potential locking scenario, even when
1128  lock requirements change.
1129  It can be optimized so that the parent does not release locks, just tells
1130  the child which locks it doesn't need to obtain.
1131 \end_layout
1132
1133 \begin_layout Standard
1134 It also keeps the complexity out of the API, and in ctdbd where it is needed.
1135 \end_layout
1136
1137 \begin_layout Subsubsection
1138 Status
1139 \end_layout
1140
1141 \begin_layout Standard
1142 Incomplete.
1143 \end_layout
1144
1145 \begin_layout Subsection
1146 tdb_chainlock Functions Expose Implementation
1147 \end_layout
1148
1149 \begin_layout Standard
1150 tdb_chainlock locks some number of records, including the record indicated
1151  by the given key.
1152  This gave atomicity guarantees; no-one can start a transaction, alter,
1153  read or delete that key while the lock is held.
1154 \end_layout
1155
1156 \begin_layout Standard
1157 It also makes the same guarantee for any other key in the chain, which is
1158  an internal implementation detail and potentially a cause for deadlock.
1159 \end_layout
1160
1161 \begin_layout Subsubsection
1162 Proposed Solution
1163 \end_layout
1164
1165 \begin_layout Standard
1166 None.
1167  It would be nice to have an explicit single entry lock which effected no
1168  other keys.
1169  Unfortunately, this won't work for an entry which doesn't exist.
1170  Thus while chainlock may be implemented more efficiently for the existing
1171  case, it will still have overlap issues with the non-existing case.
1172  So it is best to keep the current (lack of) guarantee about which records
1173  will be effected to avoid constraining our implementation.
1174 \end_layout
1175
1176 \begin_layout Subsection
1177 Signal Handling is Not Race-Free
1178 \end_layout
1179
1180 \begin_layout Standard
1181 The tdb_setalarm_sigptr() call allows the caller's signal handler to indicate
1182  that the tdb locking code should return with a failure, rather than trying
1183  again when a signal is received (and errno == EAGAIN).
1184  This is usually used to implement timeouts.
1185 \end_layout
1186
1187 \begin_layout Standard
1188 Unfortunately, this does not work in the case where the signal is received
1189  before the tdb code enters the fcntl() call to place the lock: the code
1190  will sleep within the fcntl() code, unaware that the signal wants it to
1191  exit.
1192  In the case of long timeouts, this does not happen in practice.
1193 \end_layout
1194
1195 \begin_layout Subsubsection
1196 Proposed Solution
1197 \end_layout
1198
1199 \begin_layout Standard
1200 The locking hooks proposed in
1201 \begin_inset CommandInset ref
1202 LatexCommand ref
1203 reference "Proposed-Solution-locking-hook"
1204
1205 \end_inset
1206
1207  would allow the user to decide on whether to fail the lock acquisition
1208  on a signal.
1209  This allows the caller to choose their own compromise: they could narrow
1210  the race by checking immediately before the fcntl call.
1211 \begin_inset Foot
1212 status collapsed
1213
1214 \begin_layout Plain Layout
1215 It may be possible to make this race-free in some implementations by having
1216  the signal handler alter the struct flock to make it invalid.
1217  This will cause the fcntl() lock call to fail with EINVAL if the signal
1218  occurs before the kernel is entered, otherwise EAGAIN.
1219 \end_layout
1220
1221 \end_inset
1222
1223
1224 \end_layout
1225
1226 \begin_layout Subsubsection
1227 Status
1228 \end_layout
1229
1230 \begin_layout Standard
1231 Incomplete.
1232 \end_layout
1233
1234 \begin_layout Subsection
1235 The API Uses Gratuitous Typedefs, Capitals
1236 \end_layout
1237
1238 \begin_layout Standard
1239 typedefs are useful for providing source compatibility when types can differ
1240  across implementations, or arguably in the case of function pointer definitions
1241  which are hard for humans to parse.
1242  Otherwise it is simply obfuscation and pollutes the namespace.
1243 \end_layout
1244
1245 \begin_layout Standard
1246 Capitalization is usually reserved for compile-time constants and macros.
1247 \end_layout
1248
1249 \begin_layout Description
1250 TDB_CONTEXT There is no reason to use this over 'struct tdb_context'; the
1251  definition isn't visible to the API user anyway.
1252 \end_layout
1253
1254 \begin_layout Description
1255 TDB_DATA There is no reason to use this over struct TDB_DATA; the struct
1256  needs to be understood by the API user.
1257 \end_layout
1258
1259 \begin_layout Description
1260 struct
1261 \begin_inset space ~
1262 \end_inset
1263
1264 TDB_DATA This would normally be called 'struct tdb_data'.
1265 \end_layout
1266
1267 \begin_layout Description
1268 enum
1269 \begin_inset space ~
1270 \end_inset
1271
1272 TDB_ERROR Similarly, this would normally be enum tdb_error.
1273 \end_layout
1274
1275 \begin_layout Subsubsection
1276 Proposed Solution
1277 \end_layout
1278
1279 \begin_layout Standard
1280 None.
1281  Introducing lower case variants would please pedants like myself, but if
1282  it were done the existing ones should be kept.
1283  There is little point forcing a purely cosmetic change upon tdb users.
1284 \end_layout
1285
1286 \begin_layout Subsection
1287 \begin_inset CommandInset label
1288 LatexCommand label
1289 name "tdb_log_func-Doesnt-Take"
1290
1291 \end_inset
1292
1293 tdb_log_func Doesn't Take The Private Pointer
1294 \end_layout
1295
1296 \begin_layout Standard
1297 For API compatibility reasons, the logging function needs to call tdb_get_loggin
1298 g_private() to retrieve the pointer registered by the tdb_open_ex for logging.
1299 \end_layout
1300
1301 \begin_layout Subsubsection
1302 Proposed Solution
1303 \end_layout
1304
1305 \begin_layout Standard
1306 It should simply take an extra argument, since we are prepared to break
1307  the API/ABI.
1308 \end_layout
1309
1310 \begin_layout Subsubsection
1311 Status
1312 \end_layout
1313
1314 \begin_layout Standard
1315 Complete.
1316 \end_layout
1317
1318 \begin_layout Subsection
1319 Various Callback Functions Are Not Typesafe
1320 \end_layout
1321
1322 \begin_layout Standard
1323 The callback functions in tdb_set_logging_function (after 
1324 \begin_inset CommandInset ref
1325 LatexCommand ref
1326 reference "tdb_log_func-Doesnt-Take"
1327
1328 \end_inset
1329
1330  is resolved), tdb_parse_record, tdb_traverse, tdb_traverse_read and tdb_check
1331  all take void * and must internally convert it to the argument type they
1332  were expecting.
1333 \end_layout
1334
1335 \begin_layout Standard
1336 If this type changes, the compiler will not produce warnings on the callers,
1337  since it only sees void *.
1338 \end_layout
1339
1340 \begin_layout Subsubsection
1341 Proposed Solution
1342 \end_layout
1343
1344 \begin_layout Standard
1345 With careful use of macros, we can create callback functions which give
1346  a warning when used on gcc and the types of the callback and its private
1347  argument differ.
1348  Unsupported compilers will not give a warning, which is no worse than now.
1349  In addition, the callbacks become clearer, as they need not use void *
1350  for their parameter.
1351 \end_layout
1352
1353 \begin_layout Standard
1354 See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html
1355 \end_layout
1356
1357 \begin_layout Subsubsection
1358 Status
1359 \end_layout
1360
1361 \begin_layout Standard
1362 Incomplete.
1363 \end_layout
1364
1365 \begin_layout Subsection
1366 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic
1367 \end_layout
1368
1369 \begin_layout Standard
1370 The TDB_CLEAR_IF_FIRST flag to tdb_open indicates that the TDB file should
1371  be cleared if the caller discovers it is the only process with the TDB
1372  open.
1373  However, if any caller does not specify TDB_CLEAR_IF_FIRST it will not
1374  be detected, so will have the TDB erased underneath them (usually resulting
1375  in a crash).
1376 \end_layout
1377
1378 \begin_layout Standard
1379 There is a similar issue on fork(); if the parent exits (or otherwise closes
1380  the tdb) before the child calls tdb_reopen_all() to establish the lock
1381  used to indicate the TDB is opened by someone, a TDB_CLEAR_IF_FIRST opener
1382  at that moment will believe it alone has opened the TDB and will erase
1383  it.
1384 \end_layout
1385
1386 \begin_layout Subsubsection
1387 Proposed Solution
1388 \end_layout
1389
1390 \begin_layout Standard
1391 Remove TDB_CLEAR_IF_FIRST.
1392  Other workarounds are possible, but see 
1393 \begin_inset CommandInset ref
1394 LatexCommand ref
1395 reference "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1396
1397 \end_inset
1398
1399 .
1400 \end_layout
1401
1402 \begin_layout Subsubsection
1403 Status
1404 \end_layout
1405
1406 \begin_layout Standard
1407
1408 \change_deleted 0 1298979699
1409 Incomplete, TDB_CLEAR_IF_FIRST still defined, but not implemented.
1410 \change_inserted 0 1298979700
1411 Complete.
1412 \change_unchanged
1413
1414 \end_layout
1415
1416 \begin_layout Subsection
1417 Extending The Header Is Difficult
1418 \end_layout
1419
1420 \begin_layout Standard
1421 We have reserved (zeroed) words in the TDB header, which can be used for
1422  future features.
1423  If the future features are compulsory, the version number must be updated
1424  to prevent old code from accessing the database.
1425  But if the future feature is optional, we have no way of telling if older
1426  code is accessing the database or not.
1427 \end_layout
1428
1429 \begin_layout Subsubsection
1430 Proposed Solution
1431 \end_layout
1432
1433 \begin_layout Standard
1434 The header should contain a 
1435 \begin_inset Quotes eld
1436 \end_inset
1437
1438 format variant
1439 \begin_inset Quotes erd
1440 \end_inset
1441
1442  value (64-bit).
1443  This is divided into two 32-bit parts:
1444 \end_layout
1445
1446 \begin_layout Enumerate
1447 The lower part reflects the format variant understood by code accessing
1448  the database.
1449 \end_layout
1450
1451 \begin_layout Enumerate
1452 The upper part reflects the format variant you must understand to write
1453  to the database (otherwise you can only open for reading).
1454 \end_layout
1455
1456 \begin_layout Standard
1457 The latter field can only be written at creation time, the former should
1458  be written under the OPEN_LOCK when opening the database for writing, if
1459  the variant of the code is lower than the current lowest variant.
1460 \end_layout
1461
1462 \begin_layout Standard
1463 This should allow backwards-compatible features to be added, and detection
1464  if older code (which doesn't understand the feature) writes to the database.
1465 \end_layout
1466
1467 \begin_layout Subsubsection
1468 Status
1469 \end_layout
1470
1471 \begin_layout Standard
1472 Incomplete.
1473 \end_layout
1474
1475 \begin_layout Subsection
1476 Record Headers Are Not Expandible
1477 \end_layout
1478
1479 \begin_layout Standard
1480 If we later want to add (say) checksums on keys and data, it would require
1481  another format change, which we'd like to avoid.
1482 \end_layout
1483
1484 \begin_layout Subsubsection
1485 Proposed Solution
1486 \end_layout
1487
1488 \begin_layout Standard
1489 We often have extra padding at the tail of a record.
1490  If we ensure that the first byte (if any) of this padding is zero, we will
1491  have a way for future changes to detect code which doesn't understand a
1492  new format: the new code would write (say) a 1 at the tail, and thus if
1493  there is no tail or the first byte is 0, we would know the extension is
1494  not present on that record.
1495 \end_layout
1496
1497 \begin_layout Subsubsection
1498 Status
1499 \end_layout
1500
1501 \begin_layout Standard
1502 Incomplete.
1503 \end_layout
1504
1505 \begin_layout Subsection
1506 TDB Does Not Use Talloc
1507 \end_layout
1508
1509 \begin_layout Standard
1510 Many users of TDB (particularly Samba) use the talloc allocator, and thus
1511  have to wrap TDB in a talloc context to use it conveniently.
1512 \end_layout
1513
1514 \begin_layout Subsubsection
1515 Proposed Solution
1516 \end_layout
1517
1518 \begin_layout Standard
1519 The allocation within TDB is not complicated enough to justify the use of
1520  talloc, and I am reluctant to force another (excellent) library on TDB
1521  users.
1522  Nonetheless a compromise is possible.
1523  An attribute (see 
1524 \begin_inset CommandInset ref
1525 LatexCommand ref
1526 reference "attributes"
1527
1528 \end_inset
1529
1530 ) can be added later to tdb_open() to provide an alternate allocation mechanism,
1531  specifically for talloc but usable by any other allocator (which would
1532  ignore the 
1533 \begin_inset Quotes eld
1534 \end_inset
1535
1536 context
1537 \begin_inset Quotes erd
1538 \end_inset
1539
1540  argument).
1541 \end_layout
1542
1543 \begin_layout Standard
1544 This would form a talloc heirarchy as expected, but the caller would still
1545  have to attach a destructor to the tdb context returned from tdb_open to
1546  close it.
1547  All TDB_DATA fields would be children of the tdb_context, and the caller
1548  would still have to manage them (using talloc_free() or talloc_steal()).
1549 \end_layout
1550
1551 \begin_layout Subsubsection
1552 Status
1553 \end_layout
1554
1555 \begin_layout Standard
1556 Deferred.
1557 \end_layout
1558
1559 \begin_layout Section
1560 Performance And Scalability Issues
1561 \end_layout
1562
1563 \begin_layout Subsection
1564 \begin_inset CommandInset label
1565 LatexCommand label
1566 name "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1567
1568 \end_inset
1569
1570 TDB_CLEAR_IF_FIRST Imposes Performance Penalty
1571 \end_layout
1572
1573 \begin_layout Standard
1574 When TDB_CLEAR_IF_FIRST is specified, a 1-byte read lock is placed at offset
1575  4 (aka.
1576  the ACTIVE_LOCK).
1577  While these locks never conflict in normal tdb usage, they do add substantial
1578  overhead for most fcntl lock implementations when the kernel scans to detect
1579  if a lock conflict exists.
1580  This is often a single linked list, making the time to acquire and release
1581  a fcntl lock O(N) where N is the number of processes with the TDB open,
1582  not the number actually doing work.
1583 \end_layout
1584
1585 \begin_layout Standard
1586 In a Samba server it is common to have huge numbers of clients sitting idle,
1587  and thus they have weaned themselves off the TDB_CLEAR_IF_FIRST flag.
1588 \begin_inset Foot
1589 status collapsed
1590
1591 \begin_layout Plain Layout
1592 There is a flag to tdb_reopen_all() which is used for this optimization:
1593  if the parent process will outlive the child, the child does not need the
1594  ACTIVE_LOCK.
1595  This is a workaround for this very performance issue.
1596 \end_layout
1597
1598 \end_inset
1599
1600
1601 \end_layout
1602
1603 \begin_layout Subsubsection
1604 Proposed Solution
1605 \end_layout
1606
1607 \begin_layout Standard
1608 Remove the flag.
1609  It was a neat idea, but even trivial servers tend to know when they are
1610  initializing for the first time and can simply unlink the old tdb at that
1611  point.
1612 \end_layout
1613
1614 \begin_layout Subsubsection
1615 Status
1616 \end_layout
1617
1618 \begin_layout Standard
1619
1620 \change_deleted 0 1298979837
1621 Incomplete; TDB_CLEAR_IF_FIRST still defined, but does nothing.
1622 \change_inserted 0 1298979837
1623 Complete.
1624 \change_unchanged
1625
1626 \end_layout
1627
1628 \begin_layout Subsection
1629 TDB Files Have a 4G Limit
1630 \end_layout
1631
1632 \begin_layout Standard
1633 This seems to be becoming an issue (so much for 
1634 \begin_inset Quotes eld
1635 \end_inset
1636
1637 trivial
1638 \begin_inset Quotes erd
1639 \end_inset
1640
1641 !), particularly for ldb.
1642 \end_layout
1643
1644 \begin_layout Subsubsection
1645 Proposed Solution
1646 \end_layout
1647
1648 \begin_layout Standard
1649 A new, incompatible TDB format which uses 64 bit offsets internally rather
1650  than 32 bit as now.
1651  For simplicity of endian conversion (which TDB does on the fly if required),
1652  all values will be 64 bit on disk.
1653  In practice, some upper bits may be used for other purposes, but at least
1654  56 bits will be available for file offsets.
1655 \end_layout
1656
1657 \begin_layout Standard
1658 tdb_open() will automatically detect the old version, and even create them
1659  if TDB_VERSION6 is specified to tdb_open.
1660 \end_layout
1661
1662 \begin_layout Standard
1663 32 bit processes will still be able to access TDBs larger than 4G (assuming
1664  that their off_t allows them to seek to 64 bits), they will gracefully
1665  fall back as they fail to mmap.
1666  This can happen already with large TDBs.
1667 \end_layout
1668
1669 \begin_layout Standard
1670 Old versions of tdb will fail to open the new TDB files (since 28 August
1671  2009, commit 398d0c29290: prior to that any unrecognized file format would
1672  be erased and initialized as a fresh tdb!)
1673 \end_layout
1674
1675 \begin_layout Subsubsection
1676 Status
1677 \end_layout
1678
1679 \begin_layout Standard
1680 Complete.
1681 \end_layout
1682
1683 \begin_layout Subsection
1684 TDB Records Have a 4G Limit
1685 \end_layout
1686
1687 \begin_layout Standard
1688 This has not been a reported problem, and the API uses size_t which can
1689  be 64 bit on 64 bit platforms.
1690  However, other limits may have made such an issue moot.
1691 \end_layout
1692
1693 \begin_layout Subsubsection
1694 Proposed Solution
1695 \end_layout
1696
1697 \begin_layout Standard
1698 Record sizes will be 64 bit, with an error returned on 32 bit platforms
1699  which try to access such records (the current implementation would return
1700  TDB_ERR_OOM in a similar case).
1701  It seems unlikely that 32 bit keys will be a limitation, so the implementation
1702  may not support this (see 
1703 \begin_inset CommandInset ref
1704 LatexCommand ref
1705 reference "sub:Records-Incur-A"
1706
1707 \end_inset
1708
1709 ).
1710 \end_layout
1711
1712 \begin_layout Subsubsection
1713 Status
1714 \end_layout
1715
1716 \begin_layout Standard
1717 Complete.
1718 \end_layout
1719
1720 \begin_layout Subsection
1721 Hash Size Is Determined At TDB Creation Time
1722 \end_layout
1723
1724 \begin_layout Standard
1725 TDB contains a number of hash chains in the header; the number is specified
1726  at creation time, and defaults to 131.
1727  This is such a bottleneck on large databases (as each hash chain gets quite
1728  long), that LDB uses 10,000 for this hash.
1729  In general it is impossible to know what the 'right' answer is at database
1730  creation time.
1731 \end_layout
1732
1733 \begin_layout Subsubsection
1734 \begin_inset CommandInset label
1735 LatexCommand label
1736 name "sub:Hash-Size-Solution"
1737
1738 \end_inset
1739
1740 Proposed Solution
1741 \end_layout
1742
1743 \begin_layout Standard
1744 After comprehensive performance testing on various scalable hash variants
1745 \begin_inset Foot
1746 status collapsed
1747
1748 \begin_layout Plain Layout
1749 http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoying
1750  because I was previously convinced that an expanding tree of hashes would
1751  be very close to optimal.
1752 \end_layout
1753
1754 \end_inset
1755
1756 , it became clear that it is hard to beat a straight linear hash table which
1757  doubles in size when it reaches saturation.
1758  Unfortunately, altering the hash table introduces serious locking complications
1759 : the entire hash table needs to be locked to enlarge the hash table, and
1760  others might be holding locks.
1761  Particularly insidious are insertions done under tdb_chainlock.
1762 \end_layout
1763
1764 \begin_layout Standard
1765 Thus an expanding layered hash will be used: an array of hash groups, with
1766  each hash group exploding into pointers to lower hash groups once it fills,
1767  turning into a hash tree.
1768  This has implications for locking: we must lock the entire group in case
1769  we need to expand it, yet we don't know how deep the tree is at that point.
1770 \end_layout
1771
1772 \begin_layout Standard
1773 Note that bits from the hash table entries should be stolen to hold more
1774  hash bits to reduce the penalty of collisions.
1775  We can use the otherwise-unused lower 3 bits.
1776  If we limit the size of the database to 64 exabytes, we can use the top
1777  8 bits of the hash entry as well.
1778  These 11 bits would reduce false positives down to 1 in 2000 which is more
1779  than we need: we can use one of the bits to indicate that the extra hash
1780  bits are valid.
1781  This means we can choose not to re-hash all entries when we expand a hash
1782  group; simply use the next bits we need and mark them invalid.
1783 \end_layout
1784
1785 \begin_layout Subsubsection
1786 Status
1787 \end_layout
1788
1789 \begin_layout Standard
1790 Complete.
1791 \end_layout
1792
1793 \begin_layout Subsection
1794 \begin_inset CommandInset label
1795 LatexCommand label
1796 name "TDB-Freelist-Is"
1797
1798 \end_inset
1799
1800 TDB Freelist Is Highly Contended
1801 \end_layout
1802
1803 \begin_layout Standard
1804 TDB uses a single linked list for the free list.
1805  Allocation occurs as follows, using heuristics which have evolved over
1806  time:
1807 \end_layout
1808
1809 \begin_layout Enumerate
1810 Get the free list lock for this whole operation.
1811 \end_layout
1812
1813 \begin_layout Enumerate
1814 Multiply length by 1.25, so we always over-allocate by 25%.
1815 \end_layout
1816
1817 \begin_layout Enumerate
1818 Set the slack multiplier to 1.
1819 \end_layout
1820
1821 \begin_layout Enumerate
1822 Examine the current freelist entry: if it is > length but < the current
1823  best case, remember it as the best case.
1824 \end_layout
1825
1826 \begin_layout Enumerate
1827 Multiply the slack multiplier by 1.05.
1828 \end_layout
1829
1830 \begin_layout Enumerate
1831 If our best fit so far is less than length * slack multiplier, return it.
1832  The slack will be turned into a new free record if it's large enough.
1833 \end_layout
1834
1835 \begin_layout Enumerate
1836 Otherwise, go onto the next freelist entry.
1837 \end_layout
1838
1839 \begin_layout Standard
1840 Deleting a record occurs as follows:
1841 \end_layout
1842
1843 \begin_layout Enumerate
1844 Lock the hash chain for this whole operation.
1845 \end_layout
1846
1847 \begin_layout Enumerate
1848 Walk the chain to find the record, keeping the prev pointer offset.
1849 \end_layout
1850
1851 \begin_layout Enumerate
1852 If max_dead is non-zero:
1853 \end_layout
1854
1855 \begin_deeper
1856 \begin_layout Enumerate
1857 Walk the hash chain again and count the dead records.
1858 \end_layout
1859
1860 \begin_layout Enumerate
1861 If it's more than max_dead, bulk free all the dead ones (similar to steps
1862  4 and below, but the lock is only obtained once).
1863 \end_layout
1864
1865 \begin_layout Enumerate
1866 Simply mark this record as dead and return.
1867  
1868 \end_layout
1869
1870 \end_deeper
1871 \begin_layout Enumerate
1872 Get the free list lock for the remainder of this operation.
1873 \end_layout
1874
1875 \begin_layout Enumerate
1876 \begin_inset CommandInset label
1877 LatexCommand label
1878 name "right-merging"
1879
1880 \end_inset
1881
1882 Examine the following block to see if it is free; if so, enlarge the current
1883  block and remove that block from the free list.
1884  This was disabled, as removal from the free list was O(entries-in-free-list).
1885 \end_layout
1886
1887 \begin_layout Enumerate
1888 Examine the preceeding block to see if it is free: for this reason, each
1889  block has a 32-bit tailer which indicates its length.
1890  If it is free, expand it to cover our new block and return.
1891 \end_layout
1892
1893 \begin_layout Enumerate
1894 Otherwise, prepend ourselves to the free list.
1895 \end_layout
1896
1897 \begin_layout Standard
1898 Disabling right-merging (step 
1899 \begin_inset CommandInset ref
1900 LatexCommand ref
1901 reference "right-merging"
1902
1903 \end_inset
1904
1905 ) causes fragmentation; the other heuristics proved insufficient to address
1906  this, so the final answer to this was that when we expand the TDB file
1907  inside a transaction commit, we repack the entire tdb.
1908 \end_layout
1909
1910 \begin_layout Standard
1911 The single list lock limits our allocation rate; due to the other issues
1912  this is not currently seen as a bottleneck.
1913 \end_layout
1914
1915 \begin_layout Subsubsection
1916 Proposed Solution
1917 \end_layout
1918
1919 \begin_layout Standard
1920 The first step is to remove all the current heuristics, as they obviously
1921  interact, then examine them once the lock contention is addressed.
1922 \end_layout
1923
1924 \begin_layout Standard
1925 The free list must be split to reduce contention.
1926  Assuming perfect free merging, we can at most have 1 free list entry for
1927  each entry.
1928  This implies that the number of free lists is related to the size of the
1929  hash table, but as it is rare to walk a large number of free list entries
1930  we can use far fewer, say 1/32 of the number of hash buckets.
1931 \end_layout
1932
1933 \begin_layout Standard
1934 It seems tempting to try to reuse the hash implementation which we use for
1935  records here, but we have two ways of searching for free entries: for allocatio
1936 n we search by size (and possibly zone) which produces too many clashes
1937  for our hash table to handle well, and for coalescing we search by address.
1938  Thus an array of doubly-linked free lists seems preferable.
1939 \end_layout
1940
1941 \begin_layout Standard
1942 There are various benefits in using per-size free lists (see 
1943 \begin_inset CommandInset ref
1944 LatexCommand ref
1945 reference "sub:TDB-Becomes-Fragmented"
1946
1947 \end_inset
1948
1949 ) but it's not clear this would reduce contention in the common case where
1950  all processes are allocating/freeing the same size.
1951  Thus we almost certainly need to divide in other ways: the most obvious
1952  is to divide the file into zones, and using a free list (or table of free
1953  lists) for each.
1954  This approximates address ordering.
1955 \end_layout
1956
1957 \begin_layout Standard
1958 Unfortunately it is difficult to know what heuristics should be used to
1959  determine zone sizes, and our transaction code relies on being able to
1960  create a 
1961 \begin_inset Quotes eld
1962 \end_inset
1963
1964 recovery area
1965 \begin_inset Quotes erd
1966 \end_inset
1967
1968  by simply appending to the file (difficult if it would need to create a
1969  new zone header).
1970  Thus we use a linked-list of free tables; currently we only ever create
1971  one, but if there is more than one we choose one at random to use.
1972  In future we may use heuristics to add new free tables on contention.
1973  We only expand the file when all free tables are exhausted.
1974 \end_layout
1975
1976 \begin_layout Standard
1977 The basic algorithm is as follows.
1978  Freeing is simple:
1979 \end_layout
1980
1981 \begin_layout Enumerate
1982 Identify the correct free list.
1983 \end_layout
1984
1985 \begin_layout Enumerate
1986 Lock the corresponding list.
1987 \end_layout
1988
1989 \begin_layout Enumerate
1990 Re-check the list (we didn't have a lock, sizes could have changed): relock
1991  if necessary.
1992 \end_layout
1993
1994 \begin_layout Enumerate
1995 Place the freed entry in the list.
1996 \end_layout
1997
1998 \begin_layout Standard
1999 Allocation is a little more complicated, as we perform delayed coalescing
2000  at this point:
2001 \end_layout
2002
2003 \begin_layout Enumerate
2004 Pick a free table; usually the previous one.
2005 \end_layout
2006
2007 \begin_layout Enumerate
2008 Lock the corresponding list.
2009 \end_layout
2010
2011 \begin_layout Enumerate
2012 If the top entry is -large enough, remove it from the list and return it.
2013 \end_layout
2014
2015 \begin_layout Enumerate
2016 Otherwise, coalesce entries in the list.If there was no entry large enough,
2017  unlock the list and try the next largest list
2018 \end_layout
2019
2020 \begin_layout Enumerate
2021 If no list has an entry which meets our needs, try the next free table.
2022 \end_layout
2023
2024 \begin_layout Enumerate
2025 If no zone satisfies, expand the file.
2026 \end_layout
2027
2028 \begin_layout Standard
2029 This optimizes rapid insert/delete of free list entries by not coalescing
2030  them all the time..
2031  First-fit address ordering ordering seems to be fairly good for keeping
2032  fragmentation low (see 
2033 \begin_inset CommandInset ref
2034 LatexCommand ref
2035 reference "sub:TDB-Becomes-Fragmented"
2036
2037 \end_inset
2038
2039 ).
2040  Note that address ordering does not need a tailer to coalesce, though if
2041  we needed one we could have one cheaply: see 
2042 \begin_inset CommandInset ref
2043 LatexCommand ref
2044 reference "sub:Records-Incur-A"
2045
2046 \end_inset
2047
2048 .
2049  
2050 \end_layout
2051
2052 \begin_layout Standard
2053 Each free entry has the free table number in the header: less than 255.
2054  It also contains a doubly-linked list for easy deletion.
2055 \end_layout
2056
2057 \begin_layout Subsection
2058 \begin_inset CommandInset label
2059 LatexCommand label
2060 name "sub:TDB-Becomes-Fragmented"
2061
2062 \end_inset
2063
2064 TDB Becomes Fragmented
2065 \end_layout
2066
2067 \begin_layout Standard
2068 Much of this is a result of allocation strategy
2069 \begin_inset Foot
2070 status collapsed
2071
2072 \begin_layout Plain Layout
2073 The Memory Fragmentation Problem: Solved? Johnstone & Wilson 1995 ftp://ftp.cs.ute
2074 xas.edu/pub/garbage/malloc/ismm98.ps
2075 \end_layout
2076
2077 \end_inset
2078
2079  and deliberate hobbling of coalescing; internal fragmentation (aka overallocati
2080 on) is deliberately set at 25%, and external fragmentation is only cured
2081  by the decision to repack the entire db when a transaction commit needs
2082  to enlarge the file.
2083 \end_layout
2084
2085 \begin_layout Subsubsection
2086 Proposed Solution
2087 \end_layout
2088
2089 \begin_layout Standard
2090 The 25% overhead on allocation works in practice for ldb because indexes
2091  tend to expand by one record at a time.
2092  This internal fragmentation can be resolved by having an 
2093 \begin_inset Quotes eld
2094 \end_inset
2095
2096 expanded
2097 \begin_inset Quotes erd
2098 \end_inset
2099
2100  bit in the header to note entries that have previously expanded, and allocating
2101  more space for them.
2102 \end_layout
2103
2104 \begin_layout Standard
2105 There are is a spectrum of possible solutions for external fragmentation:
2106  one is to use a fragmentation-avoiding allocation strategy such as best-fit
2107  address-order allocator.
2108  The other end of the spectrum would be to use a bump allocator (very fast
2109  and simple) and simply repack the file when we reach the end.
2110 \end_layout
2111
2112 \begin_layout Standard
2113 There are three problems with efficient fragmentation-avoiding allocators:
2114  they are non-trivial, they tend to use a single free list for each size,
2115  and there's no evidence that tdb allocation patterns will match those recorded
2116  for general allocators (though it seems likely).
2117 \end_layout
2118
2119 \begin_layout Standard
2120 Thus we don't spend too much effort on external fragmentation; we will be
2121  no worse than the current code if we need to repack on occasion.
2122  More effort is spent on reducing freelist contention, and reducing overhead.
2123 \end_layout
2124
2125 \begin_layout Subsection
2126 \begin_inset CommandInset label
2127 LatexCommand label
2128 name "sub:Records-Incur-A"
2129
2130 \end_inset
2131
2132 Records Incur A 28-Byte Overhead
2133 \end_layout
2134
2135 \begin_layout Standard
2136 Each TDB record has a header as follows:
2137 \end_layout
2138
2139 \begin_layout LyX-Code
2140 struct tdb_record {
2141 \end_layout
2142
2143 \begin_layout LyX-Code
2144         tdb_off_t next; /* offset of the next record in the list */
2145 \end_layout
2146
2147 \begin_layout LyX-Code
2148         tdb_len_t rec_len; /* total byte length of record */
2149 \end_layout
2150
2151 \begin_layout LyX-Code
2152         tdb_len_t key_len; /* byte length of key */
2153 \end_layout
2154
2155 \begin_layout LyX-Code
2156         tdb_len_t data_len; /* byte length of data */
2157 \end_layout
2158
2159 \begin_layout LyX-Code
2160         uint32_t full_hash; /* the full 32 bit hash of the key */
2161 \end_layout
2162
2163 \begin_layout LyX-Code
2164         uint32_t magic;   /* try to catch errors */
2165 \end_layout
2166
2167 \begin_layout LyX-Code
2168         /* the following union is implied:
2169 \end_layout
2170
2171 \begin_layout LyX-Code
2172                 union {
2173 \end_layout
2174
2175 \begin_layout LyX-Code
2176                         char record[rec_len];
2177 \end_layout
2178
2179 \begin_layout LyX-Code
2180                         struct {
2181 \end_layout
2182
2183 \begin_layout LyX-Code
2184                                 char key[key_len];
2185 \end_layout
2186
2187 \begin_layout LyX-Code
2188                                 char data[data_len];
2189 \end_layout
2190
2191 \begin_layout LyX-Code
2192                         }
2193 \end_layout
2194
2195 \begin_layout LyX-Code
2196                         uint32_t totalsize; (tailer)
2197 \end_layout
2198
2199 \begin_layout LyX-Code
2200                 }
2201 \end_layout
2202
2203 \begin_layout LyX-Code
2204         */
2205 \end_layout
2206
2207 \begin_layout LyX-Code
2208 };
2209 \end_layout
2210
2211 \begin_layout Standard
2212 Naively, this would double to a 56-byte overhead on a 64 bit implementation.
2213 \end_layout
2214
2215 \begin_layout Subsubsection
2216 Proposed Solution
2217 \end_layout
2218
2219 \begin_layout Standard
2220 We can use various techniques to reduce this for an allocated block:
2221 \end_layout
2222
2223 \begin_layout Enumerate
2224 The 'next' pointer is not required, as we are using a flat hash table.
2225 \end_layout
2226
2227 \begin_layout Enumerate
2228 'rec_len' can instead be expressed as an addition to key_len and data_len
2229  (it accounts for wasted or overallocated length in the record).
2230  Since the record length is always a multiple of 8, we can conveniently
2231  fit it in 32 bits (representing up to 35 bits).
2232 \end_layout
2233
2234 \begin_layout Enumerate
2235 'key_len' and 'data_len' can be reduced.
2236  I'm unwilling to restrict 'data_len' to 32 bits, but instead we can combine
2237  the two into one 64-bit field and using a 5 bit value which indicates at
2238  what bit to divide the two.
2239  Keys are unlikely to scale as fast as data, so I'm assuming a maximum key
2240  size of 32 bits.
2241 \end_layout
2242
2243 \begin_layout Enumerate
2244 'full_hash' is used to avoid a memcmp on the 
2245 \begin_inset Quotes eld
2246 \end_inset
2247
2248 miss
2249 \begin_inset Quotes erd
2250 \end_inset
2251
2252  case, but this is diminishing returns after a handful of bits (at 10 bits,
2253  it reduces 99.9% of false memcmp).
2254  As an aside, as the lower bits are already incorporated in the hash table
2255  resolution, the upper bits should be used here.
2256  Note that it's not clear that these bits will be a win, given the extra
2257  bits in the hash table itself (see 
2258 \begin_inset CommandInset ref
2259 LatexCommand ref
2260 reference "sub:Hash-Size-Solution"
2261
2262 \end_inset
2263
2264 ).
2265 \end_layout
2266
2267 \begin_layout Enumerate
2268 'magic' does not need to be enlarged: it currently reflects one of 5 values
2269  (used, free, dead, recovery, and unused_recovery).
2270  It is useful for quick sanity checking however, and should not be eliminated.
2271 \end_layout
2272
2273 \begin_layout Enumerate
2274 'tailer' is only used to coalesce free blocks (so a block to the right can
2275  find the header to check if this block is free).
2276  This can be replaced by a single 'free' bit in the header of the following
2277  block (and the tailer only exists in free blocks).
2278 \begin_inset Foot
2279 status collapsed
2280
2281 \begin_layout Plain Layout
2282 This technique from Thomas Standish.
2283  Data Structure Techniques.
2284  Addison-Wesley, Reading, Massachusetts, 1980.
2285 \end_layout
2286
2287 \end_inset
2288
2289  The current proposed coalescing algorithm doesn't need this, however.
2290 \end_layout
2291
2292 \begin_layout Standard
2293 This produces a 16 byte used header like this:
2294 \end_layout
2295
2296 \begin_layout LyX-Code
2297 struct tdb_used_record {
2298 \end_layout
2299
2300 \begin_layout LyX-Code
2301         uint32_t used_magic : 16,
2302 \end_layout
2303
2304 \begin_layout LyX-Code
2305
2306 \end_layout
2307
2308 \begin_layout LyX-Code
2309                  key_data_divide: 5,
2310 \end_layout
2311
2312 \begin_layout LyX-Code
2313                  top_hash: 11;
2314 \end_layout
2315
2316 \begin_layout LyX-Code
2317         uint32_t extra_octets;
2318 \end_layout
2319
2320 \begin_layout LyX-Code
2321         uint64_t key_and_data_len;
2322 \end_layout
2323
2324 \begin_layout LyX-Code
2325 };
2326 \end_layout
2327
2328 \begin_layout Standard
2329 And a free record like this:
2330 \end_layout
2331
2332 \begin_layout LyX-Code
2333 struct tdb_free_record {
2334 \end_layout
2335
2336 \begin_layout LyX-Code
2337         uint64_t free_magic: 8,
2338 \end_layout
2339
2340 \begin_layout LyX-Code
2341                    prev : 56;
2342 \end_layout
2343
2344 \begin_layout LyX-Code
2345
2346 \end_layout
2347
2348 \begin_layout LyX-Code
2349         uint64_t free_table: 8,
2350 \end_layout
2351
2352 \begin_layout LyX-Code
2353                  total_length : 56
2354 \end_layout
2355
2356 \begin_layout LyX-Code
2357         uint64_t next;;
2358 \end_layout
2359
2360 \begin_layout LyX-Code
2361 };
2362 \end_layout
2363
2364 \begin_layout Standard
2365
2366 \change_deleted 0 1291206079
2367  
2368 \change_unchanged
2369 Note that by limiting valid offsets to 56 bits, we can pack everything we
2370  need into 3 64-byte words, meaning our minimum record size is 8 bytes.
2371 \end_layout
2372
2373 \begin_layout Subsubsection
2374 Status
2375 \end_layout
2376
2377 \begin_layout Standard
2378 Complete.
2379 \end_layout
2380
2381 \begin_layout Subsection
2382 Transaction Commit Requires 4 fdatasync
2383 \end_layout
2384
2385 \begin_layout Standard
2386 The current transaction algorithm is:
2387 \end_layout
2388
2389 \begin_layout Enumerate
2390 write_recovery_data();
2391 \end_layout
2392
2393 \begin_layout Enumerate
2394 sync();
2395 \end_layout
2396
2397 \begin_layout Enumerate
2398 write_recovery_header();
2399 \end_layout
2400
2401 \begin_layout Enumerate
2402 sync();
2403 \end_layout
2404
2405 \begin_layout Enumerate
2406 overwrite_with_new_data();
2407 \end_layout
2408
2409 \begin_layout Enumerate
2410 sync();
2411 \end_layout
2412
2413 \begin_layout Enumerate
2414 remove_recovery_header();
2415 \end_layout
2416
2417 \begin_layout Enumerate
2418 sync(); 
2419 \end_layout
2420
2421 \begin_layout Standard
2422 On current ext3, each sync flushes all data to disk, so the next 3 syncs
2423  are relatively expensive.
2424  But this could become a performance bottleneck on other filesystems such
2425  as ext4.
2426 \end_layout
2427
2428 \begin_layout Subsubsection
2429 Proposed Solution
2430 \end_layout
2431
2432 \begin_layout Standard
2433 Neil Brown points out that this is overzealous, and only one sync is needed:
2434 \end_layout
2435
2436 \begin_layout Enumerate
2437 Bundle the recovery data, a transaction counter and a strong checksum of
2438  the new data.
2439 \end_layout
2440
2441 \begin_layout Enumerate
2442 Strong checksum that whole bundle.
2443 \end_layout
2444
2445 \begin_layout Enumerate
2446 Store the bundle in the database.
2447 \end_layout
2448
2449 \begin_layout Enumerate
2450 Overwrite the oldest of the two recovery pointers in the header (identified
2451  using the transaction counter) with the offset of this bundle.
2452 \end_layout
2453
2454 \begin_layout Enumerate
2455 sync.
2456 \end_layout
2457
2458 \begin_layout Enumerate
2459 Write the new data to the file.
2460 \end_layout
2461
2462 \begin_layout Standard
2463 Checking for recovery means identifying the latest bundle with a valid checksum
2464  and using the new data checksum to ensure that it has been applied.
2465  This is more expensive than the current check, but need only be done at
2466  open.
2467  For running databases, a separate header field can be used to indicate
2468  a transaction in progress; we need only check for recovery if this is set.
2469 \end_layout
2470
2471 \begin_layout Subsubsection
2472 Status
2473 \end_layout
2474
2475 \begin_layout Standard
2476 Deferred.
2477 \end_layout
2478
2479 \begin_layout Subsection
2480 \begin_inset CommandInset label
2481 LatexCommand label
2482 name "sub:TDB-Does-Not"
2483
2484 \end_inset
2485
2486 TDB Does Not Have Snapshot Support
2487 \end_layout
2488
2489 \begin_layout Subsubsection
2490 Proposed SolutionNone.
2491  At some point you say 
2492 \begin_inset Quotes eld
2493 \end_inset
2494
2495 use a real database
2496 \begin_inset Quotes erd
2497 \end_inset
2498
2499  (but see 
2500 \begin_inset CommandInset ref
2501 LatexCommand ref
2502 reference "replay-attribute"
2503
2504 \end_inset
2505
2506 ).
2507 \end_layout
2508
2509 \begin_layout Standard
2510 But as a thought experiment, if we implemented transactions to only overwrite
2511  free entries (this is tricky: there must not be a header in each entry
2512  which indicates whether it is free, but use of presence in metadata elsewhere),
2513  and a pointer to the hash table, we could create an entirely new commit
2514  without destroying existing data.
2515  Then it would be easy to implement snapshots in a similar way.
2516 \end_layout
2517
2518 \begin_layout Standard
2519 This would not allow arbitrary changes to the database, such as tdb_repack
2520  does, and would require more space (since we have to preserve the current
2521  and future entries at once).
2522  If we used hash trees rather than one big hash table, we might only have
2523  to rewrite some sections of the hash, too.
2524 \end_layout
2525
2526 \begin_layout Standard
2527 We could then implement snapshots using a similar method, using multiple
2528  different hash tables/free tables.
2529 \end_layout
2530
2531 \begin_layout Subsubsection
2532 Status
2533 \end_layout
2534
2535 \begin_layout Standard
2536 Deferred.
2537 \end_layout
2538
2539 \begin_layout Subsection
2540 Transactions Cannot Operate in Parallel
2541 \end_layout
2542
2543 \begin_layout Standard
2544 This would be useless for ldb, as it hits the index records with just about
2545  every update.
2546  It would add significant complexity in resolving clashes, and cause the
2547  all transaction callers to write their code to loop in the case where the
2548  transactions spuriously failed.
2549 \end_layout
2550
2551 \begin_layout Subsubsection
2552 Proposed Solution
2553 \end_layout
2554
2555 \begin_layout Standard
2556 None (but see 
2557 \begin_inset CommandInset ref
2558 LatexCommand ref
2559 reference "replay-attribute"
2560
2561 \end_inset
2562
2563 ).
2564  We could solve a small part of the problem by providing read-only transactions.
2565  These would allow one write transaction to begin, but it could not commit
2566  until all r/o transactions are done.
2567  This would require a new RO_TRANSACTION_LOCK, which would be upgraded on
2568  commit.
2569 \end_layout
2570
2571 \begin_layout Subsubsection
2572 Status
2573 \end_layout
2574
2575 \begin_layout Standard
2576 Deferred.
2577 \end_layout
2578
2579 \begin_layout Subsection
2580 Default Hash Function Is Suboptimal
2581 \end_layout
2582
2583 \begin_layout Standard
2584 The Knuth-inspired multiplicative hash used by tdb is fairly slow (especially
2585  if we expand it to 64 bits), and works best when the hash bucket size is
2586  a prime number (which also means a slow modulus).
2587  In addition, it is highly predictable which could potentially lead to a
2588  Denial of Service attack in some TDB uses.
2589 \end_layout
2590
2591 \begin_layout Subsubsection
2592 Proposed Solution
2593 \end_layout
2594
2595 \begin_layout Standard
2596 The Jenkins lookup3 hash
2597 \begin_inset Foot
2598 status open
2599
2600 \begin_layout Plain Layout
2601 http://burtleburtle.net/bob/c/lookup3.c
2602 \end_layout
2603
2604 \end_inset
2605
2606  is a fast and superbly-mixing hash.
2607  It's used by the Linux kernel and almost everything else.
2608  This has the particular properties that it takes an initial seed, and produces
2609  two 32 bit hash numbers, which we can combine into a 64-bit hash.
2610 \end_layout
2611
2612 \begin_layout Standard
2613 The seed should be created at tdb-creation time from some random source,
2614  and placed in the header.
2615  This is far from foolproof, but adds a little bit of protection against
2616  hash bombing.
2617 \end_layout
2618
2619 \begin_layout Subsubsection
2620 Status
2621 \end_layout
2622
2623 \begin_layout Standard
2624 Complete.
2625 \end_layout
2626
2627 \begin_layout Subsection
2628 \begin_inset CommandInset label
2629 LatexCommand label
2630 name "Reliable-Traversal-Adds"
2631
2632 \end_inset
2633
2634 Reliable Traversal Adds Complexity
2635 \end_layout
2636
2637 \begin_layout Standard
2638 We lock a record during traversal iteration, and try to grab that lock in
2639  the delete code.
2640  If that grab on delete fails, we simply mark it deleted and continue onwards;
2641  traversal checks for this condition and does the delete when it moves off
2642  the record.
2643 \end_layout
2644
2645 \begin_layout Standard
2646 If traversal terminates, the dead record may be left indefinitely.
2647 \end_layout
2648
2649 \begin_layout Subsubsection
2650 Proposed Solution
2651 \end_layout
2652
2653 \begin_layout Standard
2654 Remove reliability guarantees; see 
2655 \begin_inset CommandInset ref
2656 LatexCommand ref
2657 reference "traverse-Proposed-Solution"
2658
2659 \end_inset
2660
2661 .
2662 \end_layout
2663
2664 \begin_layout Subsubsection
2665 Status
2666 \end_layout
2667
2668 \begin_layout Standard
2669 Complete.
2670 \end_layout
2671
2672 \begin_layout Subsection
2673 Fcntl Locking Adds Overhead
2674 \end_layout
2675
2676 \begin_layout Standard
2677 Placing a fcntl lock means a system call, as does removing one.
2678  This is actually one reason why transactions can be faster (everything
2679  is locked once at transaction start).
2680  In the uncontended case, this overhead can theoretically be eliminated.
2681 \end_layout
2682
2683 \begin_layout Subsubsection
2684 Proposed Solution
2685 \end_layout
2686
2687 \begin_layout Standard
2688 None.
2689 \end_layout
2690
2691 \begin_layout Standard
2692 We tried this before with spinlock support, in the early days of TDB, and
2693  it didn't make much difference except in manufactured benchmarks.
2694 \end_layout
2695
2696 \begin_layout Standard
2697 We could use spinlocks (with futex kernel support under Linux), but it means
2698  that we lose automatic cleanup when a process dies with a lock.
2699  There is a method of auto-cleanup under Linux, but it's not supported by
2700  other operating systems.
2701  We could reintroduce a clear-if-first-style lock and sweep for dead futexes
2702  on open, but that wouldn't help the normal case of one concurrent opener
2703  dying.
2704  Increasingly elaborate repair schemes could be considered, but they require
2705  an ABI change (everyone must use them) anyway, so there's no need to do
2706  this at the same time as everything else.
2707 \end_layout
2708
2709 \begin_layout Subsection
2710 Some Transactions Don't Require Durability
2711 \end_layout
2712
2713 \begin_layout Standard
2714 Volker points out that gencache uses a CLEAR_IF_FIRST tdb for normal (fast)
2715  usage, and occasionally empties the results into a transactional TDB.
2716  This kind of usage prioritizes performance over durability: as long as
2717  we are consistent, data can be lost.
2718 \end_layout
2719
2720 \begin_layout Standard
2721 This would be more neatly implemented inside tdb: a 
2722 \begin_inset Quotes eld
2723 \end_inset
2724
2725 soft
2726 \begin_inset Quotes erd
2727 \end_inset
2728
2729  transaction commit (ie.
2730  syncless) which meant that data may be reverted on a crash.
2731 \end_layout
2732
2733 \begin_layout Subsubsection
2734 Proposed Solution
2735 \end_layout
2736
2737 \begin_layout Standard
2738 None.
2739 \end_layout
2740
2741 \begin_layout Standard
2742 Unfortunately any transaction scheme which overwrites old data requires
2743  a sync before that overwrite to avoid the possibility of corruption.
2744 \end_layout
2745
2746 \begin_layout Standard
2747 It seems possible to use a scheme similar to that described in 
2748 \begin_inset CommandInset ref
2749 LatexCommand ref
2750 reference "sub:TDB-Does-Not"
2751
2752 \end_inset
2753
2754 ,where transactions are committed without overwriting existing data, and
2755  an array of top-level pointers were available in the header.
2756  If the transaction is 
2757 \begin_inset Quotes eld
2758 \end_inset
2759
2760 soft
2761 \begin_inset Quotes erd
2762 \end_inset
2763
2764  then we would not need a sync at all: existing processes would pick up
2765  the new hash table and free list and work with that.
2766 \end_layout
2767
2768 \begin_layout Standard
2769 At some later point, a sync would allow recovery of the old data into the
2770  free lists (perhaps when the array of top-level pointers filled).
2771  On crash, tdb_open() would examine the array of top levels, and apply the
2772  transactions until it encountered an invalid checksum.
2773 \end_layout
2774
2775 \begin_layout Subsection
2776 Tracing Is Fragile, Replay Is External
2777 \end_layout
2778
2779 \begin_layout Standard
2780 The current TDB has compile-time-enabled tracing code, but it often breaks
2781  as it is not enabled by default.
2782  In a similar way, the ctdb code has an external wrapper which does replay
2783  tracing so it can coordinate cluster-wide transactions.
2784 \end_layout
2785
2786 \begin_layout Subsubsection
2787 Proposed Solution
2788 \begin_inset CommandInset label
2789 LatexCommand label
2790 name "replay-attribute"
2791
2792 \end_inset
2793
2794
2795 \end_layout
2796
2797 \begin_layout Standard
2798 Tridge points out that an attribute can be later added to tdb_open (see
2799  
2800 \begin_inset CommandInset ref
2801 LatexCommand ref
2802 reference "attributes"
2803
2804 \end_inset
2805
2806 ) to provide replay/trace hooks, which could become the basis for this and
2807  future parallel transactions and snapshot support.
2808 \end_layout
2809
2810 \begin_layout Subsubsection
2811 Status
2812 \end_layout
2813
2814 \begin_layout Standard
2815 Deferred.
2816 \end_layout
2817
2818 \end_body
2819 \end_document
2820 @
2821
2822
2823 1.12
2824 log
2825 @Add status, some fixes, linked freelists.
2826 @
2827 text
2828 @d53 1
2829 a53 7
2830
2831 \change_deleted 0 1291204535
2832 14-September
2833 \change_inserted 0 1291204533
2834 1-December
2835 \change_unchanged
2836 -2010
2837 a580 2
2838 \change_inserted 0 1291204563
2839
2840 a583 2
2841
2842 \change_inserted 0 1291204572
2843 a587 2
2844
2845 \change_inserted 0 1291204573
2846 a588 2
2847 \change_unchanged
2848
2849 a629 2
2850 \change_inserted 0 1291204588
2851
2852 a632 2
2853
2854 \change_inserted 0 1291204588
2855 a636 2
2856
2857 \change_inserted 0 1291204631
2858 a639 2
2859 \change_unchanged
2860
2861 a693 2
2862 \change_inserted 0 1291204639
2863
2864 a696 2
2865
2866 \change_inserted 0 1291204640
2867 d702 1
2868 a702 1
2869 \change_inserted 0 1291204665
2870 d704 2
2871 a728 2
2872 \change_inserted 0 1291204671
2873
2874 a731 2
2875
2876 \change_inserted 0 1291204671
2877 a735 2
2878
2879 \change_inserted 0 1291204673
2880 a736 2
2881 \change_unchanged
2882
2883 a780 2
2884 \change_inserted 0 1291204731
2885
2886 a783 2
2887
2888 \change_inserted 0 1291204732
2889 a787 2
2890
2891 \change_inserted 0 1291204779
2892 a790 2
2893 \change_unchanged
2894
2895 a842 2
2896 \change_inserted 0 1291204830
2897
2898 a845 2
2899
2900 \change_inserted 0 1291204831
2901 a849 2
2902
2903 \change_inserted 0 1291204834
2904 a850 2
2905 \change_unchanged
2906
2907 d879 9
2908 a887 2
2909  deal of churn; we are better to guarantee that the tdb_errcode is per-thread
2910  so the current programming model can be maintained.
2911 d891 9
2912 d903 2
2913 a922 2
2914 \change_inserted 0 1291204847
2915
2916 a925 2
2917
2918 \change_inserted 0 1291204847
2919 d930 5
2920 a934 3
2921
2922 \change_inserted 0 1291204852
2923 Incomplete.
2924 a1051 2
2925 \change_inserted 0 1291204881
2926
2927 a1054 2
2928
2929 \change_inserted 0 1291204881
2930 a1058 2
2931
2932 \change_inserted 0 1291204885
2933 a1059 2
2934 \change_unchanged
2935
2936 a1140 2
2937 \change_inserted 0 1291204898
2938
2939 a1143 2
2940
2941 \change_inserted 0 1291204898
2942 a1147 2
2943
2944 \change_inserted 0 1291204901
2945 a1148 2
2946 \change_unchanged
2947
2948 a1224 2
2949 \change_inserted 0 1291204908
2950
2951 a1227 2
2952
2953 \change_inserted 0 1291204908
2954 a1231 2
2955
2956 \change_inserted 0 1291204908
2957 a1232 2
2958 \change_unchanged
2959
2960 a1271 2
2961 \change_inserted 0 1291204917
2962
2963 a1274 2
2964
2965 \change_inserted 0 1291204917
2966 a1278 2
2967
2968 \change_inserted 0 1291204920
2969 a1279 2
2970 \change_unchanged
2971
2972 a1316 2
2973 \change_inserted 0 1291204927
2974
2975 a1319 2
2976
2977 \change_inserted 0 1291204928
2978 d1325 1
2979 a1325 1
2980 \change_inserted 0 1291204942
2981 d1327 2
2982 a1381 2
2983 \change_inserted 0 1291205003
2984
2985 a1384 2
2986
2987 \change_inserted 0 1291205004
2988 a1388 2
2989
2990 \change_inserted 0 1291205007
2991 a1411 2
2992 \change_inserted 0 1291205019
2993
2994 a1414 2
2995
2996 \change_inserted 0 1291205019
2997 a1418 2
2998
2999 \change_inserted 0 1291205023
3000 a1419 2
3001 \change_unchanged
3002
3003 a1465 2
3004 \change_inserted 0 1291205029
3005
3006 a1468 2
3007
3008 \change_inserted 0 1291205029
3009 a1472 2
3010
3011 \change_inserted 0 1291206020
3012 a1473 2
3013 \change_unchanged
3014
3015 a1528 2
3016 \change_inserted 0 1291205043
3017
3018 a1531 2
3019
3020 \change_inserted 0 1291205043
3021 d1537 1
3022 a1537 1
3023 \change_inserted 0 1291205057
3024 d1539 2
3025 a1589 2
3026 \change_inserted 0 1291205062
3027
3028 a1592 2
3029
3030 \change_inserted 0 1291205062
3031 a1596 2
3032
3033 \change_inserted 0 1291205062
3034 a1597 2
3035 \change_unchanged
3036
3037 a1626 2
3038 \change_inserted 0 1291205072
3039
3040 a1629 2
3041
3042 \change_inserted 0 1291205073
3043 a1633 2
3044
3045 \change_inserted 0 1291205073
3046 a1634 2
3047 \change_unchanged
3048
3049 a1674 4
3050
3051 \change_deleted 0 1291204504
3052  
3053 \change_unchanged
3054 a1699 2
3055 \change_inserted 0 1291205079
3056
3057 a1702 2
3058
3059 \change_inserted 0 1291205080
3060 a1706 2
3061
3062 \change_inserted 0 1291205080
3063 a1707 2
3064 \change_unchanged
3065
3066 a1833 2
3067 \change_inserted 0 1291205090
3068
3069 d1869 2
3070 a1870 7
3071  is to divide the file into zones, and using a free list (or 
3072 \change_inserted 0 1291205498
3073 table
3074 \change_deleted 0 1291205497
3075 set
3076 \change_unchanged
3077  of free lists) for each.
3078 a1871 2
3079 \change_inserted 0 1291205203
3080
3081 a1874 2
3082
3083 \change_inserted 0 1291205358
3084 a1890 21
3085 \change_unchanged
3086
3087 \end_layout
3088
3089 \begin_layout Standard
3090
3091 \change_deleted 0 1291205198
3092 Note that this means we need to split the free lists when we expand the
3093  file; this is probably acceptable when we double the hash table size, since
3094  that is such an expensive operation already.
3095  In the case of increasing the file size, there is an optimization we can
3096  use: if we use M in the formula above as the file size rounded up to the
3097  next power of 2, we only need reshuffle free lists when the file size crosses
3098  a power of 2 boundary, 
3099 \emph on
3100 and 
3101 \emph default
3102 reshuffling the free lists is trivial: we simply merge every consecutive
3103  pair of free lists.
3104 \change_unchanged
3105
3106 d1899 1
3107 a1899 7
3108 Identify the correct 
3109 \change_inserted 0 1291205366
3110 free list
3111 \change_deleted 0 1291205364
3112 zone
3113 \change_unchanged
3114 .
3115 d1907 2
3116 a1908 7
3117 Re-check the 
3118 \change_inserted 0 1291205372
3119 list
3120 \change_deleted 0 1291205371
3121 zone
3122 \change_unchanged
3123  (we didn't have a lock, sizes could have changed): relock if necessary.
3124 d1912 1
3125 a1912 5
3126 Place the freed entry in the list
3127 \change_deleted 0 1291205382
3128  for that zone
3129 \change_unchanged
3130 .
3131 d1921 1
3132 a1921 15
3133 Pick a 
3134 \change_deleted 0 1291205403
3135 zone either the zone we last freed into, or based on a 
3136 \begin_inset Quotes eld
3137 \end_inset
3138
3139 random
3140 \begin_inset Quotes erd
3141 \end_inset
3142
3143  number.
3144 \change_inserted 0 1291205411
3145 free table; usually the previous one.
3146 \change_unchanged
3147
3148 a1925 10
3149 \change_deleted 0 1291205432
3150
3151 \end_layout
3152
3153 \begin_layout Enumerate
3154
3155 \change_deleted 0 1291205428
3156 Re-check the zone: relock if necessary.
3157 \change_unchanged
3158
3159 d1934 1
3160 a1934 7
3161  unlock the list and try the next 
3162 \change_inserted 0 1291205455
3163 largest list
3164 \change_deleted 0 1291205452
3165 zone.
3166 \change_inserted 0 1291205457
3167
3168 a1937 2
3169
3170 \change_inserted 0 1291205476
3171 a1938 2
3172 \change_unchanged
3173
3174 a1966 2
3175 \change_inserted 0 1291205542
3176
3177 a1969 2
3178
3179 \change_inserted 0 1291205591
3180 a1971 70
3181 \change_unchanged
3182
3183 \end_layout
3184
3185 \begin_layout Standard
3186
3187 \change_deleted 0 1291205539
3188 I anticipate that the number of entries in each free zone would be small,
3189  but it might be worth using one free entry to hold pointers to the others
3190  for cache efficiency.
3191 \change_unchanged
3192
3193 \end_layout
3194
3195 \begin_layout Standard
3196
3197 \change_deleted 0 1291205534
3198 \begin_inset CommandInset label
3199 LatexCommand label
3200 name "freelist-in-zone"
3201
3202 \end_inset
3203
3204 If we want to avoid locking complexity (enlarging the free lists when we
3205  enlarge the file) we could place the array of free lists at the beginning
3206  of each zone.
3207  This means existing array lists never move, but means that a record cannot
3208  be larger than a zone.
3209  That in turn implies that zones should be variable sized (say, power of
3210  2), which makes the question 
3211 \begin_inset Quotes eld
3212 \end_inset
3213
3214 what zone is this record in?
3215 \begin_inset Quotes erd
3216 \end_inset
3217
3218  much harder (and 
3219 \begin_inset Quotes eld
3220 \end_inset
3221
3222 pick a random zone
3223 \begin_inset Quotes erd
3224 \end_inset
3225
3226 , but that's less common).
3227  It could be done with as few as 4 bits from the record header.
3228 \begin_inset Foot
3229 status collapsed
3230
3231 \begin_layout Plain Layout
3232 Using 
3233 \begin_inset Formula $2^{16+N*3}$
3234 \end_inset
3235
3236 means 0 gives a minimal 65536-byte zone, 15 gives the maximal 
3237 \begin_inset Formula $2^{61}$
3238 \end_inset
3239
3240  byte zone.
3241  Zones range in factor of 8 steps.
3242  Given the zone size for the zone the current record is in, we can determine
3243  the start of the zone.
3244 \end_layout
3245
3246 \end_inset
3247
3248
3249 \change_inserted 0 1291205139
3250
3251 d2218 1
3252 a2218 5
3253         uint32_t 
3254 \change_inserted 0 1291205758
3255 used_
3256 \change_unchanged
3257 magic : 16,
3258 a2222 4
3259 \change_deleted 0 1291205693
3260                  prev_is_free: 1,
3261 \change_unchanged
3262
3263 d2230 1
3264 a2230 7
3265                  top_hash: 1
3266 \change_inserted 0 1291205704
3267 1
3268 \change_deleted 0 1291205704
3269 0
3270 \change_unchanged
3271 ;
3272 d2254 1
3273 a2254 9
3274         uint
3275 \change_inserted 0 1291205725
3276 64
3277 \change_deleted 0 1291205723
3278 32
3279 \change_unchanged
3280 _t 
3281 \change_inserted 0 1291205753
3282 free_magic: 8,
3283 a2257 2
3284
3285 \change_inserted 0 1291205746
3286 a2262 24
3287 \change_deleted 0 1291205749
3288 free_magic;
3289 \change_unchanged
3290
3291 \end_layout
3292
3293 \begin_layout LyX-Code
3294         uint64_t 
3295 \change_inserted 0 1291205786
3296 free_table: 8,
3297 \end_layout
3298
3299 \begin_layout LyX-Code
3300
3301 \change_inserted 0 1291205788
3302                  
3303 \change_unchanged
3304 total_length
3305 \change_inserted 0 1291205792
3306  : 56
3307 \change_deleted 0 1291205790
3308 ;
3309 \change_unchanged
3310
3311 d2266 1
3312 a2266 7
3313         uint64_t 
3314 \change_deleted 0 1291205801
3315 prev, 
3316 \change_unchanged
3317 next;
3318 \change_deleted 0 1291205811
3319
3320 d2270 1
3321 a2270 3
3322
3323 \change_deleted 0 1291205811
3324         ...
3325 d2274 1
3326 a2274 5
3327
3328 \change_deleted 0 1291205808
3329         uint64_t tailer
3330 \change_unchanged
3331 ;
3332 d2283 5
3333 a2287 16
3334 \change_deleted 0 1291205827
3335 We might want to take some bits from the used record's top_hash (and the
3336  free record which has 32 bits of padding to spare anyway) if we use variable
3337  sized zones.
3338  See 
3339 \begin_inset CommandInset ref
3340 LatexCommand ref
3341 reference "freelist-in-zone"
3342
3343 \end_inset
3344
3345 .
3346
3347 \change_inserted 0 1291205885
3348  Note that by limiting valid offsets to 56 bits, we can pack everything
3349  we need into 3 64-byte words, meaning our minimum record size is 8 bytes.
3350 a2290 2
3351
3352 \change_inserted 0 1291205886
3353 a2294 2
3354
3355 \change_inserted 0 1291205886
3356 a2295 2
3357 \change_unchanged
3358
3359 a2385 2
3360 \change_inserted 0 1291205894
3361
3362 a2388 2
3363
3364 \change_inserted 0 1291205894
3365 a2392 2
3366
3367 \change_inserted 0 1291205902
3368 a2393 2
3369 \change_unchanged
3370
3371 a2415 4
3372
3373 \change_deleted 0 1291204504
3374  
3375 \change_unchanged
3376 a2445 2
3377 \change_inserted 0 1291205910
3378
3379 a2448 2
3380
3381 \change_inserted 0 1291205910
3382 a2452 2
3383
3384 \change_inserted 0 1291205914
3385 a2453 2
3386 \change_unchanged
3387
3388 a2485 2
3389 \change_inserted 0 1291205919
3390
3391 a2488 2
3392
3393 \change_inserted 0 1291205919
3394 a2492 2
3395
3396 \change_inserted 0 1291205922
3397 a2493 2
3398 \change_unchanged
3399
3400 a2533 2
3401 \change_inserted 0 1291205929
3402
3403 a2536 2
3404
3405 \change_inserted 0 1291205929
3406 a2540 2
3407
3408 \change_inserted 0 1291205929
3409 a2541 2
3410 \change_unchanged
3411
3412 a2578 2
3413 \change_inserted 0 1291205932
3414
3415 a2581 2
3416
3417 \change_inserted 0 1291205933
3418 a2585 2
3419
3420 \change_inserted 0 1291205933
3421 a2586 2
3422 \change_unchanged
3423
3424 a2724 2
3425 \change_inserted 0 1291205944
3426
3427 a2727 2
3428
3429 \change_inserted 0 1291205945
3430 a2731 2
3431
3432 \change_inserted 0 1291205948
3433 a2732 2
3434 \change_unchanged
3435
3436 @
3437
3438
3439 1.11
3440 log
3441 @Merge changes
3442 @
3443 text
3444 @d53 7
3445 a59 1
3446 14-September-2010
3447 d587 16
3448 d644 18
3449 d716 16
3450 d753 16
3451 d813 18
3452 d883 16
3453 d953 16
3454 d1084 16
3455 d1181 16
3456 d1273 16
3457 d1328 16
3458 d1381 16
3459 d1447 19
3460 a1465 2
3461  if older code (which doesn't understand the feature) writes to the database.Reco
3462 rd Headers Are Not Expandible
3463 d1484 16
3464 d1546 16
3465 d1617 16
3466 d1680 16
3467 d1725 16
3468 d1810 16
3469 d1951 8
3470 a1958 3
3471 Proposed SolutionThe first step is to remove all the current heuristics,
3472  as they obviously interact, then examine them once the lock contention
3473  is addressed.
3474 d1989 7
3475 a1995 2
3476  is to divide the file into zones, and using a free list (or set of free
3477  lists) for each.
3478 d1997 2
3479 d2002 25
3480 d2039 2
3481 d2049 7
3482 a2055 1
3483 Identify the correct zone.
3484 d2063 7
3485 a2069 2
3486 Re-check the zone (we didn't have a lock, sizes could have changed): relock
3487  if necessary.
3488 d2073 5
3489 a2077 1
3490 Place the freed entry in the list for that zone.
3491 d2086 3
3492 a2088 1
3493 Pick a zone either the zone we last freed into, or based on a 
3494 d2097 4
3495 d2105 2
3496 d2110 2
3497 d2113 2
3498 d2123 15
3499 a2137 1
3500  unlock the list and try the next zone.
3501 d2166 11
3502 d2180 2
3503 d2185 2
3504 d2190 2
3505 d2223 1
3506 a2223 1
3507 status open
3508 d2243 2
3509 d2491 5
3510 a2495 1
3511         uint32_t magic : 16,
3512 d2499 2
3513 d2502 2
3514 d2511 7
3515 a2517 1
3516                  top_hash: 10;
3517 d2541 29
3518 a2569 1
3519         uint32_t free_magic;
3520 d2573 11
3521 a2583 1
3522         uint64_t total_length;
3523 d2587 7
3524 a2593 1
3525         uint64_t prev, next;
3526 d2597 2
3527 d2603 5
3528 a2607 1
3529         uint64_t tailer;
3530 d2615 2
3531 d2628 18
3532 d2736 16
3533 d2808 16
3534 d2856 16
3535 d2912 16
3536 d2965 16
3537 d3119 16
3538 @
3539
3540
3541 1.10
3542 log
3543 @Tracing attribute, talloc support.
3544 @
3545 text
3546 @d1 1
3547 a1 1
3548 #LyX 1.6.5 created this file. For more info see http://www.lyx.org/
3549 d53 1
3550 a53 7
3551
3552 \change_deleted 0 1283307542
3553 26-July
3554 \change_inserted 0 1284423485
3555 14-September
3556 \change_unchanged
3557 -2010
3558 a472 2
3559 \change_inserted 0 1284422789
3560
3561 a479 2
3562 \change_unchanged
3563
3564 a838 2
3565
3566 \change_inserted 0 1284016998
3567 a846 2
3568 \change_unchanged
3569
3570 a1194 2
3571 \change_inserted 0 1284015637
3572
3573 a1197 2
3574
3575 \change_inserted 0 1284015716
3576 a1201 2
3577
3578 \change_inserted 0 1284015906
3579 a1210 2
3580
3581 \change_inserted 0 1284015637
3582 a1214 2
3583
3584 \change_inserted 0 1284016114
3585 a1227 2
3586
3587 \change_inserted 0 1284016149
3588 a1232 2
3589
3590 \change_inserted 0 1284016639
3591 a1237 2
3592
3593 \change_inserted 0 1284016821
3594 a1243 2
3595
3596 \change_inserted 0 1284016803
3597 d1245 2
3598 a1246 9
3599  if older code (which doesn't understand the feature) writes to the database.
3600 \change_deleted 0 1284016101
3601
3602 \end_layout
3603
3604 \begin_layout Subsection
3605
3606 \change_inserted 0 1284015634
3607 Record Headers Are Not Expandible
3608 a1249 2
3609
3610 \change_inserted 0 1284015634
3611 a1254 2
3612
3613 \change_inserted 0 1284015634
3614 a1258 2
3615
3616 \change_inserted 0 1284422552
3617 a1267 2
3618
3619 \change_inserted 0 1284422568
3620 a1271 2
3621
3622 \change_inserted 0 1284422646
3623 a1276 2
3624
3625 \change_inserted 0 1284422656
3626 a1280 2
3627
3628 \change_inserted 0 1284423065
3629 a1305 2
3630
3631 \change_inserted 0 1284423042
3632 a1310 2
3633 \change_unchanged
3634
3635 a1457 2
3636
3637 \change_inserted 0 1283336713
3638 a1463 2
3639
3640 \change_unchanged
3641 d1482 2
3642 d1485 1
3643 a1485 51
3644 \change_deleted 0 1283307675
3645 There are three details which become important:
3646 \end_layout
3647
3648 \begin_layout Enumerate
3649
3650 \change_deleted 0 1283307675
3651 On encountering a full bucket, we use the next bucket.
3652 \end_layout
3653
3654 \begin_layout Enumerate
3655
3656 \change_deleted 0 1283307675
3657 Extra hash bits are stored with the offset, to reduce comparisons.
3658 \end_layout
3659
3660 \begin_layout Enumerate
3661
3662 \change_deleted 0 1283307675
3663 A marker entry is used on deleting an entry.
3664 \end_layout
3665
3666 \begin_layout Standard
3667
3668 \change_deleted 0 1283307675
3669 The doubling of the table must be done under a transaction; we will not
3670  reduce it on deletion, so it will be an unusual case.
3671  It will either be placed at the head (other entries will be moved out the
3672  way so we can expand).
3673  We could have a pointer in the header to the current hashtable location,
3674  but that pointer would have to be read frequently to check for hashtable
3675  moves.
3676 \end_layout
3677
3678 \begin_layout Standard
3679
3680 \change_deleted 0 1283307675
3681 The locking for this is slightly more complex than the chained case; we
3682  currently have one lock per bucket, and that means we would need to expand
3683  the lock if we overflow to the next bucket.
3684  The frequency of such collisions will effect our locking heuristics: we
3685  can always lock more buckets than we need.
3686 \end_layout
3687
3688 \begin_layout Standard
3689
3690 \change_deleted 0 1283307675
3691 One possible optimization is to only re-check the hash size on an insert
3692  or a lookup miss.
3693
3694 \change_inserted 0 1283307770
3695 a1492 2
3696
3697 \change_inserted 0 1283336187
3698 a1500 2
3699
3700 \change_inserted 0 1283336586
3701 a1510 2
3702 \change_unchanged
3703
3704 d1636 3
3705 a1638 8
3706 Proposed Solution
3707 \change_deleted 0 1283336858
3708
3709 \end_layout
3710
3711 \begin_layout Standard
3712 The first step is to remove all the current heuristics, as they obviously
3713  interact, then examine them once the lock contention is addressed.
3714 a1647 2
3715 \change_inserted 0 1283336910
3716
3717 a1650 2
3718
3719 \change_inserted 0 1283337052
3720 a1655 2
3721 \change_unchanged
3722
3723 a1776 2
3724 \change_inserted 0 1283309850
3725
3726 a1779 2
3727
3728 \change_inserted 0 1283337216
3729 a1813 2
3730
3731 \change_inserted 0 1284424151
3732 a1825 2
3733 \change_unchanged
3734
3735 a1830 2
3736 \change_unchanged
3737
3738 a2031 2
3739
3740 \change_inserted 0 1283336739
3741 a2040 2
3742 \change_unchanged
3743
3744 a2117 2
3745 \change_inserted 0 1283337133
3746
3747 a2120 2
3748
3749 \change_inserted 0 1283337139
3750 a2121 2
3751 \change_unchanged
3752
3753 a2136 2
3754
3755 \change_inserted 0 1283337235
3756 a2147 2
3757 \change_unchanged
3758
3759 d2251 1
3760 a2251 7
3761 Proposed Solution
3762 \change_deleted 0 1284423472
3763
3764 \end_layout
3765
3766 \begin_layout Standard
3767 None.
3768 d2261 1
3769 a2261 1
3770 \change_inserted 0 1284423891
3771 d2263 1
3772 a2263 4
3773 \change_deleted 0 1284423891
3774 .
3775
3776 \change_inserted 0 1284423901
3777 a2271 2
3778 \change_unchanged
3779
3780 a2293 2
3781 \change_inserted 0 1284423495
3782
3783 a2312 2
3784
3785 \change_inserted 0 1284424201
3786 d2321 1
3787 a2321 3
3788  
3789 \change_unchanged
3790 We could solve a small part of the problem by providing read-only transactions.
3791 a2505 2
3792 \change_inserted 0 1284423555
3793
3794 a2508 2
3795
3796 \change_inserted 0 1284423617
3797 a2512 2
3798
3799 \change_inserted 0 1284423719
3800 a2519 2
3801
3802 \change_inserted 0 1284423864
3803 a2530 2
3804
3805 \change_inserted 0 1284423850
3806 a2540 2
3807 \change_unchanged
3808
3809 @
3810
3811
3812 1.9
3813 log
3814 @Extension mechanism.
3815 @
3816 text
3817 @d56 2
3818 a57 2
3819 \change_inserted 0 1284016854
3820 9-September
3821 d479 11
3822 d1303 1
3823 a1303 1
3824 \change_inserted 0 1284016847
3825 d1310 56
3826 d1945 1
3827 a1945 1
3828 \change_inserted 0 1283310945
3829 d1956 2
3830 d2402 2
3831 d2416 4
3832 d2421 12
3833 d2455 2
3834 d2476 12
3835 d2673 47
3836 @
3837
3838
3839 1.8
3840 log
3841 @Remove bogus footnote
3842 @
3843 text
3844 @d56 2
3845 a57 2
3846 \change_inserted 0 1283307544
3847 1-September
3848 d838 12
3849 d1198 103
3850 @
3851
3852
3853 1.7
3854 log
3855 @Moving hash table does not work.
3856 @
3857 text
3858 @a1436 12
3859 \begin_inset Foot
3860 status collapsed
3861
3862 \begin_layout Plain Layout
3863
3864 \change_inserted 0 1283336450
3865 If we make the hash offsets zone-relative, then this only restricts the
3866  zone size, not the overall database size.
3867 \end_layout
3868
3869 \end_inset
3870
3871 @
3872
3873
3874 1.6
3875 log
3876 @Commit changes
3877 @
3878 text
3879 @d38 1
3880 a38 1
3881 \author "" 
3882 d53 7
3883 a59 1
3884 26-July-2010
3885 d1333 10
3886 d1361 3
3887 a1363 1
3888  There are three details which become important:
3889 d1367 2
3890 d1373 2
3891 d1379 2
3892 d1385 2
3893 d1397 2
3894 d1407 2
3895 d1411 45
3896 d1582 2
3897 d1598 14
3898 d1733 62
3899 d1996 13
3900 d2086 10
3901 d2110 15
3902 a2124 1
3903 \begin_layout LyX-Code
3904 @
3905
3906
3907 1.5
3908 log
3909 @Soft transaction commit
3910 @
3911 text
3912 @d38 1
3913 a38 1
3914 \author "Rusty Russell,,," 
3915 a52 4
3916
3917 \change_deleted 0 1280141199
3918 10-May-2010
3919 \change_inserted 0 1280141202
3920 a53 2
3921 \change_unchanged
3922
3923 a2028 2
3924
3925 \change_inserted 0 1280140902
3926 a2034 2
3927
3928 \change_unchanged
3929 a2212 2
3930 \change_inserted 0 1280140661
3931
3932 a2215 2
3933
3934 \change_inserted 0 1280140703
3935 a2219 2
3936
3937 \change_inserted 0 1280708312
3938 a2226 2
3939
3940 \change_inserted 0 1280708400
3941 a2239 2
3942
3943 \change_inserted 0 1280140836
3944 a2243 2
3945
3946 \change_inserted 0 1280708255
3947 a2247 2
3948
3949 \change_inserted 0 1280708374
3950 a2252 2
3951
3952 \change_inserted 0 1280141181
3953 a2274 2
3954
3955 \change_inserted 0 1280141345
3956 @
3957
3958
3959 1.4
3960 log
3961 @Merge changes
3962 @
3963 text
3964 @d38 1
3965 a38 1
3966 \author "" 
3967 d53 2
3968 d56 4
3969 d2035 10
3970 d2223 84
3971 @
3972
3973
3974 1.3
3975 log
3976 @Transaction and freelist rethink.
3977 @
3978 text
3979 @d38 1
3980 a38 1
3981 \author "Rusty Russell,,," 
3982 d53 1
3983 a53 1
3984 27-April-2010
3985 d662 1
3986 a662 5
3987  behavior of disallowing 
3988 \change_inserted 0 1272940179
3989 nested 
3990 \change_unchanged
3991 transactions should become the default.
3992 a1210 2
3993 \change_inserted 0 1272944650
3994
3995 a1214 2
3996
3997 \change_inserted 0 1272944763
3998 a1218 2
3999 \change_unchanged
4000
4001 a1223 2
4002 \change_unchanged
4003
4004 a1301 2
4005
4006 \change_inserted 0 1273478114
4007 a1310 2
4008 \change_unchanged
4009
4010 d1515 1
4011 a1515 11
4012 The free list 
4013 \change_deleted 0 1273469807
4014 should
4015 \change_inserted 0 1273469810
4016 must
4017 \change_unchanged
4018  be split 
4019 \change_deleted 0 1273469815
4020 into multiple lists 
4021 \change_unchanged
4022 to reduce contention.
4023 a1520 2
4024 \change_inserted 0 1273470006
4025
4026 a1523 2
4027
4028 \change_inserted 0 1273492055
4029 a1539 2
4030
4031 \change_inserted 0 1273483888
4032 a1551 2
4033 \change_unchanged
4034
4035 a1554 8
4036
4037 \change_deleted 0 1272942055
4038 There are various ways to organize these lisys, but because we want to be
4039  able to quickly identify which free list an entry is in, and reduce the
4040  number of locks required for merging, we will use zoning (eg.
4041  each free list covers some fixed fraction of the file).
4042  
4043 \change_inserted 0 1273484187
4044 d1556 1
4045 a1556 7
4046  
4047 \change_deleted 0 1273484194
4048 The algorithm for f
4049 \change_inserted 0 1273484194
4050 F
4051 \change_unchanged
4052 reeing is simple:
4053 d1560 1
4054 a1560 7
4055 Identify the correct 
4056 \change_deleted 0 1273482856
4057 free list
4058 \change_inserted 0 1273482857
4059 zone
4060 \change_unchanged
4061 .
4062 d1564 1
4063 a1564 7
4064 Lock the 
4065 \change_inserted 0 1273482895
4066 corresponding 
4067 \change_unchanged
4068 list
4069 \change_inserted 0 1273482863
4070 .
4071 a1567 2
4072
4073 \change_inserted 0 1273482909
4074 d1573 1
4075 a1573 13
4076
4077 \change_deleted 0 1273482885
4078 , and p
4079 \change_inserted 0 1273482888
4080 P
4081 \change_unchanged
4082 lace the freed entry 
4083 \change_deleted 0 1273492415
4084 at the head
4085 \change_inserted 0 1273492415
4086 in the list for that zone
4087 \change_unchanged
4088 .
4089 d1577 2
4090 a1578 7
4091 Allocation is a little more complicated, as we 
4092 \change_deleted 0 1273483240
4093 merge entries as we walk the list:
4094 \change_inserted 0 1273484250
4095 perform delayed coalescing at this point:
4096 \change_unchanged
4097
4098 d1582 1
4099 a1582 19
4100 Pick a 
4101 \change_deleted 0 1273482955
4102 free list;
4103 \change_inserted 0 1273482957
4104 zone
4105 \change_unchanged
4106  either the 
4107 \change_deleted 0 1273482962
4108 list
4109 \change_inserted 0 1273482962
4110 zone
4111 \change_unchanged
4112  we last freed 
4113 \change_deleted 0 1273482966
4114 o
4115 \change_inserted 0 1273482966
4116 i
4117 \change_unchanged
4118 nto, or based on a 
4119 d1594 1
4120 a1594 9
4121 Lock th
4122 \change_inserted 0 1273482980
4123 e corresponding
4124 \change_deleted 0 1273482973
4125 at
4126 \change_unchanged
4127  list.
4128 \change_inserted 0 1273482982
4129
4130 a1597 2
4131
4132 \change_inserted 0 1273483084
4133 a1598 53
4134 \change_unchanged
4135
4136 \end_layout
4137
4138 \begin_layout Enumerate
4139 If the top entry is 
4140 \change_deleted 0 1273492155
4141 well-sized, 
4142 \change_inserted 0 1273492159
4143 -large enough, 
4144 \change_unchanged
4145 remove it from the list and return it.
4146 \end_layout
4147
4148 \begin_layout Enumerate
4149 Otherwise, 
4150 \change_inserted 0 1273492206
4151 coalesce entries in the list.
4152 \change_deleted 0 1273492200
4153 examine the entry to the right of it in the file.
4154  If it is free:
4155 \end_layout
4156
4157 \begin_deeper
4158 \begin_layout Enumerate
4159
4160 \change_deleted 0 1273492200
4161 If that entry is in a different list, lock that list too.
4162 \end_layout
4163
4164 \begin_layout Enumerate
4165
4166 \change_deleted 0 1273492200
4167 If we had to place a new lock, re-check that the entry is free.
4168 \end_layout
4169
4170 \begin_layout Enumerate
4171
4172 \change_deleted 0 1273492200
4173 Remove that entry from its free list and expand this entry to cover it.
4174 \end_layout
4175
4176 \begin_layout Enumerate
4177
4178 \change_deleted 0 1273485554
4179 Goto step 3.
4180 \end_layout
4181
4182 \end_deeper
4183 \begin_layout Enumerate
4184
4185 \change_inserted 0 1273485311
4186 If there was no entry large enough, unlock the list and try the next zone.
4187 d1602 1
4188 a1602 5
4189
4190 \change_deleted 0 1273483646
4191 Repeat step 3 with each entry in the list.
4192 \change_unchanged
4193
4194 d1606 2
4195 a1607 5
4196
4197 \change_deleted 0 1273483668
4198 Unlock the list and repeat step 2 with the next list.
4199 \change_unchanged
4200
4201 d1611 1
4202 a1611 7
4203 If no 
4204 \change_deleted 0 1273483671
4205 list
4206 \change_inserted 0 1273483671
4207 zone
4208 \change_unchanged
4209  satisfies, expand the file.
4210 d1615 2
4211 a1616 9
4212 This optimizes rapid insert/delete of free list entries
4213 \change_inserted 0 1273485794
4214  by not coalescing them all the time.
4215 \change_deleted 0 1273483685
4216 , and allows us to get rid of the tailer altogether
4217 \change_unchanged
4218 .
4219
4220 \change_inserted 0 1273492299
4221 a1638 39
4222
4223 \change_deleted 0 1273476840
4224 The question of 
4225 \begin_inset Quotes eld
4226 \end_inset
4227
4228 well-sized
4229 \begin_inset Quotes erd
4230 \end_inset
4231
4232  free entries is more difficult: the 25% overhead works in practice for
4233  ldb because indexes tend to expand by one record at a time.
4234  This can be resolved by having an 
4235 \begin_inset Quotes eld
4236 \end_inset
4237
4238 expanded
4239 \begin_inset Quotes erd
4240 \end_inset
4241
4242  bit in the header to note entries that have previously expanded, and allocating
4243  more space for them.
4244  Whether the 
4245 \begin_inset Quotes eld
4246 \end_inset
4247
4248 increasing slack
4249 \begin_inset Quotes erd
4250 \end_inset
4251
4252  algorithm should be implemented or first-fit used is still unknown: we
4253  will determine this once these other ideas are implemented.
4254 \change_inserted 0 1273483750
4255
4256 \end_layout
4257
4258 \begin_layout Standard
4259
4260 \change_inserted 0 1273492450
4261 a1644 2
4262
4263 \change_inserted 0 1273470441
4264 a1654 2
4265
4266 \change_inserted 0 1273476556
4267 a1659 2
4268
4269 \change_inserted 0 1273470423
4270 a1661 2
4271 \change_unchanged
4272
4273 a1672 2
4274
4275 \change_inserted 0 1273476847
4276 a1676 2
4277
4278 \change_inserted 0 1273476886
4279 a1691 2
4280
4281 \change_inserted 0 1273477233
4282 a1699 2
4283
4284 \change_inserted 0 1273477534
4285 a1706 2
4286
4287 \change_inserted 0 1273482700
4288 a1712 2
4289
4290 \change_inserted 0 1273478079
4291 a1722 2
4292
4293 \change_inserted 0 1273477839
4294 a1726 2
4295
4296 \change_inserted 0 1273477925
4297 a1730 2
4298
4299 \change_inserted 0 1273477925
4300 a1734 2
4301
4302 \change_inserted 0 1273477925
4303 a1738 2
4304
4305 \change_inserted 0 1273477925
4306 a1742 2
4307
4308 \change_inserted 0 1273477925
4309 a1746 2
4310
4311 \change_inserted 0 1273477925
4312 a1750 2
4313
4314 \change_inserted 0 1273477925
4315 a1754 2
4316
4317 \change_inserted 0 1273477925
4318 a1758 2
4319
4320 \change_inserted 0 1273477925
4321 a1762 2
4322
4323 \change_inserted 0 1273477925
4324 a1766 2
4325
4326 \change_inserted 0 1273477925
4327 a1770 2
4328
4329 \change_inserted 0 1273477925
4330 a1774 2