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