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