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