tdb2: make tests work in parallel.
[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 "" 
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 17-March-2011
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 Complete; the nesting flag has been removed.
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 Complete.
783  Unknown flags cause tdb_open() to fail as well, so they can be detected
784  at runtime.
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 Complete.
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, but fortunately most functions return 0 on success and -1
874  on error: we can change these to return 0 on success and a negative error
875  code on error, and the API remains similar to previous.
876  The tdb_fetch, tdb_firstkey and tdb_nextkey functions need to take a TDB_DATA
877  pointer and return an error code.
878  It is also simpler to have tdb_nextkey replace its key argument in place,
879  freeing up any old .dptr.
880 \end_layout
881
882 \begin_layout Standard
883 Internal locking is required to make sure that fcntl locks do not overlap
884  between threads, and also that the global list of tdbs is maintained.
885 \end_layout
886
887 \begin_layout Standard
888 The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe
889  version of the library, and otherwise no overhead will exist.
890  Alternatively, a hooking mechanism similar to that proposed for 
891 \begin_inset CommandInset ref
892 LatexCommand ref
893 reference "Proposed-Solution-locking-hook"
894
895 \end_inset
896
897  could be used to enable pthread locking at runtime.
898 \end_layout
899
900 \begin_layout Subsubsection
901 Status
902 \end_layout
903
904 \begin_layout Standard
905 Incomplete; API has been changed but thread safety has not been implemented.
906 \end_layout
907
908 \begin_layout Subsection
909 *_nonblock Functions And *_mark Functions Expose Implementation
910 \end_layout
911
912 \begin_layout Standard
913 CTDB
914 \begin_inset Foot
915 status collapsed
916
917 \begin_layout Plain Layout
918 Clustered TDB, see http://ctdb.samba.org
919 \end_layout
920
921 \end_inset
922
923  wishes to operate on TDB in a non-blocking manner.
924  This is currently done as follows:
925 \end_layout
926
927 \begin_layout Enumerate
928 Call the _nonblock variant of an API function (eg.
929  tdb_lockall_nonblock).
930  If this fails:
931 \end_layout
932
933 \begin_layout Enumerate
934 Fork a child process, and wait for it to call the normal variant (eg.
935  tdb_lockall).
936 \end_layout
937
938 \begin_layout Enumerate
939 If the child succeeds, call the _mark variant to indicate we already have
940  the locks (eg.
941  tdb_lockall_mark).
942 \end_layout
943
944 \begin_layout Enumerate
945 Upon completion, tell the child to release the locks (eg.
946  tdb_unlockall).
947 \end_layout
948
949 \begin_layout Enumerate
950 Indicate to tdb that it should consider the locks removed (eg.
951  tdb_unlockall_mark).
952 \end_layout
953
954 \begin_layout Standard
955 There are several issues with this approach.
956  Firstly, adding two new variants of each function clutters the API for
957  an obscure use, and so not all functions have three variants.
958  Secondly, it assumes that all paths of the functions ask for the same locks,
959  otherwise the parent process will have to get a lock which the child doesn't
960  have under some circumstances.
961  I don't believe this is currently the case, but it constrains the implementatio
962 n.
963  
964 \end_layout
965
966 \begin_layout Subsubsection
967 \begin_inset CommandInset label
968 LatexCommand label
969 name "Proposed-Solution-locking-hook"
970
971 \end_inset
972
973 Proposed Solution
974 \end_layout
975
976 \begin_layout Standard
977 Implement a hook for locking methods, so that the caller can control the
978  calls to create and remove fcntl locks.
979  In this scenario, ctdbd would operate as follows:
980 \end_layout
981
982 \begin_layout Enumerate
983 Call the normal API function, eg tdb_lockall().
984 \end_layout
985
986 \begin_layout Enumerate
987 When the lock callback comes in, check if the child has the lock.
988  Initially, this is always false.
989  If so, return 0.
990  Otherwise, try to obtain it in non-blocking mode.
991  If that fails, return EWOULDBLOCK.
992 \end_layout
993
994 \begin_layout Enumerate
995 Release locks in the unlock callback as normal.
996 \end_layout
997
998 \begin_layout Enumerate
999 If tdb_lockall() fails, see if we recorded a lock failure; if so, call the
1000  child to repeat the operation.
1001 \end_layout
1002
1003 \begin_layout Enumerate
1004 The child records what locks it obtains, and returns that information to
1005  the parent.
1006 \end_layout
1007
1008 \begin_layout Enumerate
1009 When the child has succeeded, goto 1.
1010 \end_layout
1011
1012 \begin_layout Standard
1013 This is flexible enough to handle any potential locking scenario, even when
1014  lock requirements change.
1015  It can be optimized so that the parent does not release locks, just tells
1016  the child which locks it doesn't need to obtain.
1017 \end_layout
1018
1019 \begin_layout Standard
1020 It also keeps the complexity out of the API, and in ctdbd where it is needed.
1021 \end_layout
1022
1023 \begin_layout Subsubsection
1024 Status
1025 \end_layout
1026
1027 \begin_layout Standard
1028 Incomplete.
1029 \end_layout
1030
1031 \begin_layout Subsection
1032 tdb_chainlock Functions Expose Implementation
1033 \end_layout
1034
1035 \begin_layout Standard
1036 tdb_chainlock locks some number of records, including the record indicated
1037  by the given key.
1038  This gave atomicity guarantees; no-one can start a transaction, alter,
1039  read or delete that key while the lock is held.
1040 \end_layout
1041
1042 \begin_layout Standard
1043 It also makes the same guarantee for any other key in the chain, which is
1044  an internal implementation detail and potentially a cause for deadlock.
1045 \end_layout
1046
1047 \begin_layout Subsubsection
1048 Proposed Solution
1049 \end_layout
1050
1051 \begin_layout Standard
1052 None.
1053  It would be nice to have an explicit single entry lock which effected no
1054  other keys.
1055  Unfortunately, this won't work for an entry which doesn't exist.
1056  Thus while chainlock may be implemented more efficiently for the existing
1057  case, it will still have overlap issues with the non-existing case.
1058  So it is best to keep the current (lack of) guarantee about which records
1059  will be effected to avoid constraining our implementation.
1060 \end_layout
1061
1062 \begin_layout Subsection
1063 Signal Handling is Not Race-Free
1064 \end_layout
1065
1066 \begin_layout Standard
1067 The tdb_setalarm_sigptr() call allows the caller's signal handler to indicate
1068  that the tdb locking code should return with a failure, rather than trying
1069  again when a signal is received (and errno == EAGAIN).
1070  This is usually used to implement timeouts.
1071 \end_layout
1072
1073 \begin_layout Standard
1074 Unfortunately, this does not work in the case where the signal is received
1075  before the tdb code enters the fcntl() call to place the lock: the code
1076  will sleep within the fcntl() code, unaware that the signal wants it to
1077  exit.
1078  In the case of long timeouts, this does not happen in practice.
1079 \end_layout
1080
1081 \begin_layout Subsubsection
1082 Proposed Solution
1083 \end_layout
1084
1085 \begin_layout Standard
1086 The locking hooks proposed in
1087 \begin_inset CommandInset ref
1088 LatexCommand ref
1089 reference "Proposed-Solution-locking-hook"
1090
1091 \end_inset
1092
1093  would allow the user to decide on whether to fail the lock acquisition
1094  on a signal.
1095  This allows the caller to choose their own compromise: they could narrow
1096  the race by checking immediately before the fcntl call.
1097 \begin_inset Foot
1098 status collapsed
1099
1100 \begin_layout Plain Layout
1101 It may be possible to make this race-free in some implementations by having
1102  the signal handler alter the struct flock to make it invalid.
1103  This will cause the fcntl() lock call to fail with EINVAL if the signal
1104  occurs before the kernel is entered, otherwise EAGAIN.
1105 \end_layout
1106
1107 \end_inset
1108
1109
1110 \end_layout
1111
1112 \begin_layout Subsubsection
1113 Status
1114 \end_layout
1115
1116 \begin_layout Standard
1117 Incomplete.
1118 \end_layout
1119
1120 \begin_layout Subsection
1121 The API Uses Gratuitous Typedefs, Capitals
1122 \end_layout
1123
1124 \begin_layout Standard
1125 typedefs are useful for providing source compatibility when types can differ
1126  across implementations, or arguably in the case of function pointer definitions
1127  which are hard for humans to parse.
1128  Otherwise it is simply obfuscation and pollutes the namespace.
1129 \end_layout
1130
1131 \begin_layout Standard
1132 Capitalization is usually reserved for compile-time constants and macros.
1133 \end_layout
1134
1135 \begin_layout Description
1136 TDB_CONTEXT There is no reason to use this over 'struct tdb_context'; the
1137  definition isn't visible to the API user anyway.
1138 \end_layout
1139
1140 \begin_layout Description
1141 TDB_DATA There is no reason to use this over struct TDB_DATA; the struct
1142  needs to be understood by the API user.
1143 \end_layout
1144
1145 \begin_layout Description
1146 struct
1147 \begin_inset space ~
1148 \end_inset
1149
1150 TDB_DATA This would normally be called 'struct tdb_data'.
1151 \end_layout
1152
1153 \begin_layout Description
1154 enum
1155 \begin_inset space ~
1156 \end_inset
1157
1158 TDB_ERROR Similarly, this would normally be enum tdb_error.
1159 \end_layout
1160
1161 \begin_layout Subsubsection
1162 Proposed Solution
1163 \end_layout
1164
1165 \begin_layout Standard
1166 None.
1167  Introducing lower case variants would please pedants like myself, but if
1168  it were done the existing ones should be kept.
1169  There is little point forcing a purely cosmetic change upon tdb users.
1170 \end_layout
1171
1172 \begin_layout Subsection
1173 \begin_inset CommandInset label
1174 LatexCommand label
1175 name "tdb_log_func-Doesnt-Take"
1176
1177 \end_inset
1178
1179 tdb_log_func Doesn't Take The Private Pointer
1180 \end_layout
1181
1182 \begin_layout Standard
1183 For API compatibility reasons, the logging function needs to call tdb_get_loggin
1184 g_private() to retrieve the pointer registered by the tdb_open_ex for logging.
1185 \end_layout
1186
1187 \begin_layout Subsubsection
1188 Proposed Solution
1189 \end_layout
1190
1191 \begin_layout Standard
1192 It should simply take an extra argument, since we are prepared to break
1193  the API/ABI.
1194 \end_layout
1195
1196 \begin_layout Subsubsection
1197 Status
1198 \end_layout
1199
1200 \begin_layout Standard
1201 Complete.
1202 \end_layout
1203
1204 \begin_layout Subsection
1205 Various Callback Functions Are Not Typesafe
1206 \end_layout
1207
1208 \begin_layout Standard
1209 The callback functions in tdb_set_logging_function (after 
1210 \begin_inset CommandInset ref
1211 LatexCommand ref
1212 reference "tdb_log_func-Doesnt-Take"
1213
1214 \end_inset
1215
1216  is resolved), tdb_parse_record, tdb_traverse, tdb_traverse_read and tdb_check
1217  all take void * and must internally convert it to the argument type they
1218  were expecting.
1219 \end_layout
1220
1221 \begin_layout Standard
1222 If this type changes, the compiler will not produce warnings on the callers,
1223  since it only sees void *.
1224 \end_layout
1225
1226 \begin_layout Subsubsection
1227 Proposed Solution
1228 \end_layout
1229
1230 \begin_layout Standard
1231 With careful use of macros, we can create callback functions which give
1232  a warning when used on gcc and the types of the callback and its private
1233  argument differ.
1234  Unsupported compilers will not give a warning, which is no worse than now.
1235  In addition, the callbacks become clearer, as they need not use void *
1236  for their parameter.
1237 \end_layout
1238
1239 \begin_layout Standard
1240 See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html
1241 \end_layout
1242
1243 \begin_layout Subsubsection
1244 Status
1245 \end_layout
1246
1247 \begin_layout Standard
1248 Complete.
1249 \end_layout
1250
1251 \begin_layout Subsection
1252 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic
1253 \end_layout
1254
1255 \begin_layout Standard
1256 The TDB_CLEAR_IF_FIRST flag to tdb_open indicates that the TDB file should
1257  be cleared if the caller discovers it is the only process with the TDB
1258  open.
1259  However, if any caller does not specify TDB_CLEAR_IF_FIRST it will not
1260  be detected, so will have the TDB erased underneath them (usually resulting
1261  in a crash).
1262 \end_layout
1263
1264 \begin_layout Standard
1265 There is a similar issue on fork(); if the parent exits (or otherwise closes
1266  the tdb) before the child calls tdb_reopen_all() to establish the lock
1267  used to indicate the TDB is opened by someone, a TDB_CLEAR_IF_FIRST opener
1268  at that moment will believe it alone has opened the TDB and will erase
1269  it.
1270 \end_layout
1271
1272 \begin_layout Subsubsection
1273 Proposed Solution
1274 \end_layout
1275
1276 \begin_layout Standard
1277 Remove TDB_CLEAR_IF_FIRST.
1278  Other workarounds are possible, but see 
1279 \begin_inset CommandInset ref
1280 LatexCommand ref
1281 reference "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1282
1283 \end_inset
1284
1285 .
1286 \end_layout
1287
1288 \begin_layout Subsubsection
1289 Status
1290 \end_layout
1291
1292 \begin_layout Standard
1293 Complete.
1294 \end_layout
1295
1296 \begin_layout Subsection
1297 Extending The Header Is Difficult
1298 \end_layout
1299
1300 \begin_layout Standard
1301 We have reserved (zeroed) words in the TDB header, which can be used for
1302  future features.
1303  If the future features are compulsory, the version number must be updated
1304  to prevent old code from accessing the database.
1305  But if the future feature is optional, we have no way of telling if older
1306  code is accessing the database or not.
1307 \end_layout
1308
1309 \begin_layout Subsubsection
1310 Proposed Solution
1311 \end_layout
1312
1313 \begin_layout Standard
1314 The header should contain a 
1315 \begin_inset Quotes eld
1316 \end_inset
1317
1318 format variant
1319 \begin_inset Quotes erd
1320 \end_inset
1321
1322  value (64-bit).
1323  This is divided into two 32-bit parts:
1324 \end_layout
1325
1326 \begin_layout Enumerate
1327 The lower part reflects the format variant understood by code accessing
1328  the database.
1329 \end_layout
1330
1331 \begin_layout Enumerate
1332 The upper part reflects the format variant you must understand to write
1333  to the database (otherwise you can only open for reading).
1334 \end_layout
1335
1336 \begin_layout Standard
1337 The latter field can only be written at creation time, the former should
1338  be written under the OPEN_LOCK when opening the database for writing, if
1339  the variant of the code is lower than the current lowest variant.
1340 \end_layout
1341
1342 \begin_layout Standard
1343 This should allow backwards-compatible features to be added, and detection
1344  if older code (which doesn't understand the feature) writes to the database.
1345 \end_layout
1346
1347 \begin_layout Subsubsection
1348 Status
1349 \end_layout
1350
1351 \begin_layout Standard
1352 Complete.
1353 \end_layout
1354
1355 \begin_layout Subsection
1356 Record Headers Are Not Expandible
1357 \end_layout
1358
1359 \begin_layout Standard
1360 If we later want to add (say) checksums on keys and data, it would require
1361  another format change, which we'd like to avoid.
1362 \end_layout
1363
1364 \begin_layout Subsubsection
1365 Proposed Solution
1366 \end_layout
1367
1368 \begin_layout Standard
1369 We often have extra padding at the tail of a record.
1370  If we ensure that the first byte (if any) of this padding is zero, we will
1371  have a way for future changes to detect code which doesn't understand a
1372  new format: the new code would write (say) a 1 at the tail, and thus if
1373  there is no tail or the first byte is 0, we would know the extension is
1374  not present on that record.
1375 \end_layout
1376
1377 \begin_layout Subsubsection
1378 Status
1379 \end_layout
1380
1381 \begin_layout Standard
1382 Complete.
1383 \end_layout
1384
1385 \begin_layout Subsection
1386 TDB Does Not Use Talloc
1387 \end_layout
1388
1389 \begin_layout Standard
1390 Many users of TDB (particularly Samba) use the talloc allocator, and thus
1391  have to wrap TDB in a talloc context to use it conveniently.
1392 \end_layout
1393
1394 \begin_layout Subsubsection
1395 Proposed Solution
1396 \end_layout
1397
1398 \begin_layout Standard
1399 The allocation within TDB is not complicated enough to justify the use of
1400  talloc, and I am reluctant to force another (excellent) library on TDB
1401  users.
1402  Nonetheless a compromise is possible.
1403  An attribute (see 
1404 \begin_inset CommandInset ref
1405 LatexCommand ref
1406 reference "attributes"
1407
1408 \end_inset
1409
1410 ) can be added later to tdb_open() to provide an alternate allocation mechanism,
1411  specifically for talloc but usable by any other allocator (which would
1412  ignore the 
1413 \begin_inset Quotes eld
1414 \end_inset
1415
1416 context
1417 \begin_inset Quotes erd
1418 \end_inset
1419
1420  argument).
1421 \end_layout
1422
1423 \begin_layout Standard
1424 This would form a talloc heirarchy as expected, but the caller would still
1425  have to attach a destructor to the tdb context returned from tdb_open to
1426  close it.
1427  All TDB_DATA fields would be children of the tdb_context, and the caller
1428  would still have to manage them (using talloc_free() or talloc_steal()).
1429 \end_layout
1430
1431 \begin_layout Subsubsection
1432 Status
1433 \end_layout
1434
1435 \begin_layout Standard
1436 Deferred.
1437 \end_layout
1438
1439 \begin_layout Section
1440 Performance And Scalability Issues
1441 \end_layout
1442
1443 \begin_layout Subsection
1444 \begin_inset CommandInset label
1445 LatexCommand label
1446 name "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1447
1448 \end_inset
1449
1450 TDB_CLEAR_IF_FIRST Imposes Performance Penalty
1451 \end_layout
1452
1453 \begin_layout Standard
1454 When TDB_CLEAR_IF_FIRST is specified, a 1-byte read lock is placed at offset
1455  4 (aka.
1456  the ACTIVE_LOCK).
1457  While these locks never conflict in normal tdb usage, they do add substantial
1458  overhead for most fcntl lock implementations when the kernel scans to detect
1459  if a lock conflict exists.
1460  This is often a single linked list, making the time to acquire and release
1461  a fcntl lock O(N) where N is the number of processes with the TDB open,
1462  not the number actually doing work.
1463 \end_layout
1464
1465 \begin_layout Standard
1466 In a Samba server it is common to have huge numbers of clients sitting idle,
1467  and thus they have weaned themselves off the TDB_CLEAR_IF_FIRST flag.
1468 \begin_inset Foot
1469 status collapsed
1470
1471 \begin_layout Plain Layout
1472 There is a flag to tdb_reopen_all() which is used for this optimization:
1473  if the parent process will outlive the child, the child does not need the
1474  ACTIVE_LOCK.
1475  This is a workaround for this very performance issue.
1476 \end_layout
1477
1478 \end_inset
1479
1480
1481 \end_layout
1482
1483 \begin_layout Subsubsection
1484 Proposed Solution
1485 \end_layout
1486
1487 \begin_layout Standard
1488 Remove the flag.
1489  It was a neat idea, but even trivial servers tend to know when they are
1490  initializing for the first time and can simply unlink the old tdb at that
1491  point.
1492 \end_layout
1493
1494 \begin_layout Subsubsection
1495 Status
1496 \end_layout
1497
1498 \begin_layout Standard
1499 Complete.
1500 \end_layout
1501
1502 \begin_layout Subsection
1503 TDB Files Have a 4G Limit
1504 \end_layout
1505
1506 \begin_layout Standard
1507 This seems to be becoming an issue (so much for 
1508 \begin_inset Quotes eld
1509 \end_inset
1510
1511 trivial
1512 \begin_inset Quotes erd
1513 \end_inset
1514
1515 !), particularly for ldb.
1516 \end_layout
1517
1518 \begin_layout Subsubsection
1519 Proposed Solution
1520 \end_layout
1521
1522 \begin_layout Standard
1523 A new, incompatible TDB format which uses 64 bit offsets internally rather
1524  than 32 bit as now.
1525  For simplicity of endian conversion (which TDB does on the fly if required),
1526  all values will be 64 bit on disk.
1527  In practice, some upper bits may be used for other purposes, but at least
1528  56 bits will be available for file offsets.
1529 \end_layout
1530
1531 \begin_layout Standard
1532 tdb_open() will automatically detect the old version, and even create them
1533  if TDB_VERSION6 is specified to tdb_open.
1534 \end_layout
1535
1536 \begin_layout Standard
1537 32 bit processes will still be able to access TDBs larger than 4G (assuming
1538  that their off_t allows them to seek to 64 bits), they will gracefully
1539  fall back as they fail to mmap.
1540  This can happen already with large TDBs.
1541 \end_layout
1542
1543 \begin_layout Standard
1544 Old versions of tdb will fail to open the new TDB files (since 28 August
1545  2009, commit 398d0c29290: prior to that any unrecognized file format would
1546  be erased and initialized as a fresh tdb!)
1547 \end_layout
1548
1549 \begin_layout Subsubsection
1550 Status
1551 \end_layout
1552
1553 \begin_layout Standard
1554 Complete.
1555 \end_layout
1556
1557 \begin_layout Subsection
1558 TDB Records Have a 4G Limit
1559 \end_layout
1560
1561 \begin_layout Standard
1562 This has not been a reported problem, and the API uses size_t which can
1563  be 64 bit on 64 bit platforms.
1564  However, other limits may have made such an issue moot.
1565 \end_layout
1566
1567 \begin_layout Subsubsection
1568 Proposed Solution
1569 \end_layout
1570
1571 \begin_layout Standard
1572 Record sizes will be 64 bit, with an error returned on 32 bit platforms
1573  which try to access such records (the current implementation would return
1574  TDB_ERR_OOM in a similar case).
1575  It seems unlikely that 32 bit keys will be a limitation, so the implementation
1576  may not support this (see 
1577 \begin_inset CommandInset ref
1578 LatexCommand ref
1579 reference "sub:Records-Incur-A"
1580
1581 \end_inset
1582
1583 ).
1584 \end_layout
1585
1586 \begin_layout Subsubsection
1587 Status
1588 \end_layout
1589
1590 \begin_layout Standard
1591 Complete.
1592 \end_layout
1593
1594 \begin_layout Subsection
1595 Hash Size Is Determined At TDB Creation Time
1596 \end_layout
1597
1598 \begin_layout Standard
1599 TDB contains a number of hash chains in the header; the number is specified
1600  at creation time, and defaults to 131.
1601  This is such a bottleneck on large databases (as each hash chain gets quite
1602  long), that LDB uses 10,000 for this hash.
1603  In general it is impossible to know what the 'right' answer is at database
1604  creation time.
1605 \end_layout
1606
1607 \begin_layout Subsubsection
1608 \begin_inset CommandInset label
1609 LatexCommand label
1610 name "sub:Hash-Size-Solution"
1611
1612 \end_inset
1613
1614 Proposed Solution
1615 \end_layout
1616
1617 \begin_layout Standard
1618 After comprehensive performance testing on various scalable hash variants
1619 \begin_inset Foot
1620 status collapsed
1621
1622 \begin_layout Plain Layout
1623 http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoying
1624  because I was previously convinced that an expanding tree of hashes would
1625  be very close to optimal.
1626 \end_layout
1627
1628 \end_inset
1629
1630 , it became clear that it is hard to beat a straight linear hash table which
1631  doubles in size when it reaches saturation.
1632  Unfortunately, altering the hash table introduces serious locking complications
1633 : the entire hash table needs to be locked to enlarge the hash table, and
1634  others might be holding locks.
1635  Particularly insidious are insertions done under tdb_chainlock.
1636 \end_layout
1637
1638 \begin_layout Standard
1639 Thus an expanding layered hash will be used: an array of hash groups, with
1640  each hash group exploding into pointers to lower hash groups once it fills,
1641  turning into a hash tree.
1642  This has implications for locking: we must lock the entire group in case
1643  we need to expand it, yet we don't know how deep the tree is at that point.
1644 \end_layout
1645
1646 \begin_layout Standard
1647 Note that bits from the hash table entries should be stolen to hold more
1648  hash bits to reduce the penalty of collisions.
1649  We can use the otherwise-unused lower 3 bits.
1650  If we limit the size of the database to 64 exabytes, we can use the top
1651  8 bits of the hash entry as well.
1652  These 11 bits would reduce false positives down to 1 in 2000 which is more
1653  than we need: we can use one of the bits to indicate that the extra hash
1654  bits are valid.
1655  This means we can choose not to re-hash all entries when we expand a hash
1656  group; simply use the next bits we need and mark them invalid.
1657 \end_layout
1658
1659 \begin_layout Subsubsection
1660 Status
1661 \end_layout
1662
1663 \begin_layout Standard
1664 Complete.
1665 \end_layout
1666
1667 \begin_layout Subsection
1668 \begin_inset CommandInset label
1669 LatexCommand label
1670 name "TDB-Freelist-Is"
1671
1672 \end_inset
1673
1674 TDB Freelist Is Highly Contended
1675 \end_layout
1676
1677 \begin_layout Standard
1678 TDB uses a single linked list for the free list.
1679  Allocation occurs as follows, using heuristics which have evolved over
1680  time:
1681 \end_layout
1682
1683 \begin_layout Enumerate
1684 Get the free list lock for this whole operation.
1685 \end_layout
1686
1687 \begin_layout Enumerate
1688 Multiply length by 1.25, so we always over-allocate by 25%.
1689 \end_layout
1690
1691 \begin_layout Enumerate
1692 Set the slack multiplier to 1.
1693 \end_layout
1694
1695 \begin_layout Enumerate
1696 Examine the current freelist entry: if it is > length but < the current
1697  best case, remember it as the best case.
1698 \end_layout
1699
1700 \begin_layout Enumerate
1701 Multiply the slack multiplier by 1.05.
1702 \end_layout
1703
1704 \begin_layout Enumerate
1705 If our best fit so far is less than length * slack multiplier, return it.
1706  The slack will be turned into a new free record if it's large enough.
1707 \end_layout
1708
1709 \begin_layout Enumerate
1710 Otherwise, go onto the next freelist entry.
1711 \end_layout
1712
1713 \begin_layout Standard
1714 Deleting a record occurs as follows:
1715 \end_layout
1716
1717 \begin_layout Enumerate
1718 Lock the hash chain for this whole operation.
1719 \end_layout
1720
1721 \begin_layout Enumerate
1722 Walk the chain to find the record, keeping the prev pointer offset.
1723 \end_layout
1724
1725 \begin_layout Enumerate
1726 If max_dead is non-zero:
1727 \end_layout
1728
1729 \begin_deeper
1730 \begin_layout Enumerate
1731 Walk the hash chain again and count the dead records.
1732 \end_layout
1733
1734 \begin_layout Enumerate
1735 If it's more than max_dead, bulk free all the dead ones (similar to steps
1736  4 and below, but the lock is only obtained once).
1737 \end_layout
1738
1739 \begin_layout Enumerate
1740 Simply mark this record as dead and return.
1741  
1742 \end_layout
1743
1744 \end_deeper
1745 \begin_layout Enumerate
1746 Get the free list lock for the remainder of this operation.
1747 \end_layout
1748
1749 \begin_layout Enumerate
1750 \begin_inset CommandInset label
1751 LatexCommand label
1752 name "right-merging"
1753
1754 \end_inset
1755
1756 Examine the following block to see if it is free; if so, enlarge the current
1757  block and remove that block from the free list.
1758  This was disabled, as removal from the free list was O(entries-in-free-list).
1759 \end_layout
1760
1761 \begin_layout Enumerate
1762 Examine the preceeding block to see if it is free: for this reason, each
1763  block has a 32-bit tailer which indicates its length.
1764  If it is free, expand it to cover our new block and return.
1765 \end_layout
1766
1767 \begin_layout Enumerate
1768 Otherwise, prepend ourselves to the free list.
1769 \end_layout
1770
1771 \begin_layout Standard
1772 Disabling right-merging (step 
1773 \begin_inset CommandInset ref
1774 LatexCommand ref
1775 reference "right-merging"
1776
1777 \end_inset
1778
1779 ) causes fragmentation; the other heuristics proved insufficient to address
1780  this, so the final answer to this was that when we expand the TDB file
1781  inside a transaction commit, we repack the entire tdb.
1782 \end_layout
1783
1784 \begin_layout Standard
1785 The single list lock limits our allocation rate; due to the other issues
1786  this is not currently seen as a bottleneck.
1787 \end_layout
1788
1789 \begin_layout Subsubsection
1790 Proposed Solution
1791 \end_layout
1792
1793 \begin_layout Standard
1794 The first step is to remove all the current heuristics, as they obviously
1795  interact, then examine them once the lock contention is addressed.
1796 \end_layout
1797
1798 \begin_layout Standard
1799 The free list must be split to reduce contention.
1800  Assuming perfect free merging, we can at most have 1 free list entry for
1801  each entry.
1802  This implies that the number of free lists is related to the size of the
1803  hash table, but as it is rare to walk a large number of free list entries
1804  we can use far fewer, say 1/32 of the number of hash buckets.
1805 \end_layout
1806
1807 \begin_layout Standard
1808 It seems tempting to try to reuse the hash implementation which we use for
1809  records here, but we have two ways of searching for free entries: for allocatio
1810 n we search by size (and possibly zone) which produces too many clashes
1811  for our hash table to handle well, and for coalescing we search by address.
1812  Thus an array of doubly-linked free lists seems preferable.
1813 \end_layout
1814
1815 \begin_layout Standard
1816 There are various benefits in using per-size free lists (see 
1817 \begin_inset CommandInset ref
1818 LatexCommand ref
1819 reference "sub:TDB-Becomes-Fragmented"
1820
1821 \end_inset
1822
1823 ) but it's not clear this would reduce contention in the common case where
1824  all processes are allocating/freeing the same size.
1825  Thus we almost certainly need to divide in other ways: the most obvious
1826  is to divide the file into zones, and using a free list (or table of free
1827  lists) for each.
1828  This approximates address ordering.
1829 \end_layout
1830
1831 \begin_layout Standard
1832 Unfortunately it is difficult to know what heuristics should be used to
1833  determine zone sizes, and our transaction code relies on being able to
1834  create a 
1835 \begin_inset Quotes eld
1836 \end_inset
1837
1838 recovery area
1839 \begin_inset Quotes erd
1840 \end_inset
1841
1842  by simply appending to the file (difficult if it would need to create a
1843  new zone header).
1844  Thus we use a linked-list of free tables; currently we only ever create
1845  one, but if there is more than one we choose one at random to use.
1846  In future we may use heuristics to add new free tables on contention.
1847  We only expand the file when all free tables are exhausted.
1848 \end_layout
1849
1850 \begin_layout Standard
1851 The basic algorithm is as follows.
1852  Freeing is simple:
1853 \end_layout
1854
1855 \begin_layout Enumerate
1856 Identify the correct free list.
1857 \end_layout
1858
1859 \begin_layout Enumerate
1860 Lock the corresponding list.
1861 \end_layout
1862
1863 \begin_layout Enumerate
1864 Re-check the list (we didn't have a lock, sizes could have changed): relock
1865  if necessary.
1866 \end_layout
1867
1868 \begin_layout Enumerate
1869 Place the freed entry in the list.
1870 \end_layout
1871
1872 \begin_layout Standard
1873 Allocation is a little more complicated, as we perform delayed coalescing
1874  at this point:
1875 \end_layout
1876
1877 \begin_layout Enumerate
1878 Pick a free table; usually the previous one.
1879 \end_layout
1880
1881 \begin_layout Enumerate
1882 Lock the corresponding list.
1883 \end_layout
1884
1885 \begin_layout Enumerate
1886 If the top entry is -large enough, remove it from the list and return it.
1887 \end_layout
1888
1889 \begin_layout Enumerate
1890 Otherwise, coalesce entries in the list.If there was no entry large enough,
1891  unlock the list and try the next largest list
1892 \end_layout
1893
1894 \begin_layout Enumerate
1895 If no list has an entry which meets our needs, try the next free table.
1896 \end_layout
1897
1898 \begin_layout Enumerate
1899 If no zone satisfies, expand the file.
1900 \end_layout
1901
1902 \begin_layout Standard
1903 This optimizes rapid insert/delete of free list entries by not coalescing
1904  them all the time..
1905  First-fit address ordering ordering seems to be fairly good for keeping
1906  fragmentation low (see 
1907 \begin_inset CommandInset ref
1908 LatexCommand ref
1909 reference "sub:TDB-Becomes-Fragmented"
1910
1911 \end_inset
1912
1913 ).
1914  Note that address ordering does not need a tailer to coalesce, though if
1915  we needed one we could have one cheaply: see 
1916 \begin_inset CommandInset ref
1917 LatexCommand ref
1918 reference "sub:Records-Incur-A"
1919
1920 \end_inset
1921
1922 .
1923  
1924 \end_layout
1925
1926 \begin_layout Standard
1927 Each free entry has the free table number in the header: less than 255.
1928  It also contains a doubly-linked list for easy deletion.
1929 \end_layout
1930
1931 \begin_layout Subsection
1932 \begin_inset CommandInset label
1933 LatexCommand label
1934 name "sub:TDB-Becomes-Fragmented"
1935
1936 \end_inset
1937
1938 TDB Becomes Fragmented
1939 \end_layout
1940
1941 \begin_layout Standard
1942 Much of this is a result of allocation strategy
1943 \begin_inset Foot
1944 status collapsed
1945
1946 \begin_layout Plain Layout
1947 The Memory Fragmentation Problem: Solved? Johnstone & Wilson 1995 ftp://ftp.cs.ute
1948 xas.edu/pub/garbage/malloc/ismm98.ps
1949 \end_layout
1950
1951 \end_inset
1952
1953  and deliberate hobbling of coalescing; internal fragmentation (aka overallocati
1954 on) is deliberately set at 25%, and external fragmentation is only cured
1955  by the decision to repack the entire db when a transaction commit needs
1956  to enlarge the file.
1957 \end_layout
1958
1959 \begin_layout Subsubsection
1960 Proposed Solution
1961 \end_layout
1962
1963 \begin_layout Standard
1964 The 25% overhead on allocation works in practice for ldb because indexes
1965  tend to expand by one record at a time.
1966  This internal fragmentation can be resolved by having an 
1967 \begin_inset Quotes eld
1968 \end_inset
1969
1970 expanded
1971 \begin_inset Quotes erd
1972 \end_inset
1973
1974  bit in the header to note entries that have previously expanded, and allocating
1975  more space for them.
1976 \end_layout
1977
1978 \begin_layout Standard
1979 There are is a spectrum of possible solutions for external fragmentation:
1980  one is to use a fragmentation-avoiding allocation strategy such as best-fit
1981  address-order allocator.
1982  The other end of the spectrum would be to use a bump allocator (very fast
1983  and simple) and simply repack the file when we reach the end.
1984 \end_layout
1985
1986 \begin_layout Standard
1987 There are three problems with efficient fragmentation-avoiding allocators:
1988  they are non-trivial, they tend to use a single free list for each size,
1989  and there's no evidence that tdb allocation patterns will match those recorded
1990  for general allocators (though it seems likely).
1991 \end_layout
1992
1993 \begin_layout Standard
1994 Thus we don't spend too much effort on external fragmentation; we will be
1995  no worse than the current code if we need to repack on occasion.
1996  More effort is spent on reducing freelist contention, and reducing overhead.
1997 \end_layout
1998
1999 \begin_layout Subsection
2000 \begin_inset CommandInset label
2001 LatexCommand label
2002 name "sub:Records-Incur-A"
2003
2004 \end_inset
2005
2006 Records Incur A 28-Byte Overhead
2007 \end_layout
2008
2009 \begin_layout Standard
2010 Each TDB record has a header as follows:
2011 \end_layout
2012
2013 \begin_layout LyX-Code
2014 struct tdb_record {
2015 \end_layout
2016
2017 \begin_layout LyX-Code
2018         tdb_off_t next; /* offset of the next record in the list */
2019 \end_layout
2020
2021 \begin_layout LyX-Code
2022         tdb_len_t rec_len; /* total byte length of record */
2023 \end_layout
2024
2025 \begin_layout LyX-Code
2026         tdb_len_t key_len; /* byte length of key */
2027 \end_layout
2028
2029 \begin_layout LyX-Code
2030         tdb_len_t data_len; /* byte length of data */
2031 \end_layout
2032
2033 \begin_layout LyX-Code
2034         uint32_t full_hash; /* the full 32 bit hash of the key */
2035 \end_layout
2036
2037 \begin_layout LyX-Code
2038         uint32_t magic;   /* try to catch errors */
2039 \end_layout
2040
2041 \begin_layout LyX-Code
2042         /* the following union is implied:
2043 \end_layout
2044
2045 \begin_layout LyX-Code
2046                 union {
2047 \end_layout
2048
2049 \begin_layout LyX-Code
2050                         char record[rec_len];
2051 \end_layout
2052
2053 \begin_layout LyX-Code
2054                         struct {
2055 \end_layout
2056
2057 \begin_layout LyX-Code
2058                                 char key[key_len];
2059 \end_layout
2060
2061 \begin_layout LyX-Code
2062                                 char data[data_len];
2063 \end_layout
2064
2065 \begin_layout LyX-Code
2066                         }
2067 \end_layout
2068
2069 \begin_layout LyX-Code
2070                         uint32_t totalsize; (tailer)
2071 \end_layout
2072
2073 \begin_layout LyX-Code
2074                 }
2075 \end_layout
2076
2077 \begin_layout LyX-Code
2078         */
2079 \end_layout
2080
2081 \begin_layout LyX-Code
2082 };
2083 \end_layout
2084
2085 \begin_layout Standard
2086 Naively, this would double to a 56-byte overhead on a 64 bit implementation.
2087 \end_layout
2088
2089 \begin_layout Subsubsection
2090 Proposed Solution
2091 \end_layout
2092
2093 \begin_layout Standard
2094 We can use various techniques to reduce this for an allocated block:
2095 \end_layout
2096
2097 \begin_layout Enumerate
2098 The 'next' pointer is not required, as we are using a flat hash table.
2099 \end_layout
2100
2101 \begin_layout Enumerate
2102 'rec_len' can instead be expressed as an addition to key_len and data_len
2103  (it accounts for wasted or overallocated length in the record).
2104  Since the record length is always a multiple of 8, we can conveniently
2105  fit it in 32 bits (representing up to 35 bits).
2106 \end_layout
2107
2108 \begin_layout Enumerate
2109 'key_len' and 'data_len' can be reduced.
2110  I'm unwilling to restrict 'data_len' to 32 bits, but instead we can combine
2111  the two into one 64-bit field and using a 5 bit value which indicates at
2112  what bit to divide the two.
2113  Keys are unlikely to scale as fast as data, so I'm assuming a maximum key
2114  size of 32 bits.
2115 \end_layout
2116
2117 \begin_layout Enumerate
2118 'full_hash' is used to avoid a memcmp on the 
2119 \begin_inset Quotes eld
2120 \end_inset
2121
2122 miss
2123 \begin_inset Quotes erd
2124 \end_inset
2125
2126  case, but this is diminishing returns after a handful of bits (at 10 bits,
2127  it reduces 99.9% of false memcmp).
2128  As an aside, as the lower bits are already incorporated in the hash table
2129  resolution, the upper bits should be used here.
2130  Note that it's not clear that these bits will be a win, given the extra
2131  bits in the hash table itself (see 
2132 \begin_inset CommandInset ref
2133 LatexCommand ref
2134 reference "sub:Hash-Size-Solution"
2135
2136 \end_inset
2137
2138 ).
2139 \end_layout
2140
2141 \begin_layout Enumerate
2142 'magic' does not need to be enlarged: it currently reflects one of 5 values
2143  (used, free, dead, recovery, and unused_recovery).
2144  It is useful for quick sanity checking however, and should not be eliminated.
2145 \end_layout
2146
2147 \begin_layout Enumerate
2148 'tailer' is only used to coalesce free blocks (so a block to the right can
2149  find the header to check if this block is free).
2150  This can be replaced by a single 'free' bit in the header of the following
2151  block (and the tailer only exists in free blocks).
2152 \begin_inset Foot
2153 status collapsed
2154
2155 \begin_layout Plain Layout
2156 This technique from Thomas Standish.
2157  Data Structure Techniques.
2158  Addison-Wesley, Reading, Massachusetts, 1980.
2159 \end_layout
2160
2161 \end_inset
2162
2163  The current proposed coalescing algorithm doesn't need this, however.
2164 \end_layout
2165
2166 \begin_layout Standard
2167 This produces a 16 byte used header like this:
2168 \end_layout
2169
2170 \begin_layout LyX-Code
2171 struct tdb_used_record {
2172 \end_layout
2173
2174 \begin_layout LyX-Code
2175         uint32_t used_magic : 16,
2176 \end_layout
2177
2178 \begin_layout LyX-Code
2179
2180 \end_layout
2181
2182 \begin_layout LyX-Code
2183                  key_data_divide: 5,
2184 \end_layout
2185
2186 \begin_layout LyX-Code
2187                  top_hash: 11;
2188 \end_layout
2189
2190 \begin_layout LyX-Code
2191         uint32_t extra_octets;
2192 \end_layout
2193
2194 \begin_layout LyX-Code
2195         uint64_t key_and_data_len;
2196 \end_layout
2197
2198 \begin_layout LyX-Code
2199 };
2200 \end_layout
2201
2202 \begin_layout Standard
2203 And a free record like this:
2204 \end_layout
2205
2206 \begin_layout LyX-Code
2207 struct tdb_free_record {
2208 \end_layout
2209
2210 \begin_layout LyX-Code
2211         uint64_t free_magic: 8,
2212 \end_layout
2213
2214 \begin_layout LyX-Code
2215                    prev : 56;
2216 \end_layout
2217
2218 \begin_layout LyX-Code
2219
2220 \end_layout
2221
2222 \begin_layout LyX-Code
2223         uint64_t free_table: 8,
2224 \end_layout
2225
2226 \begin_layout LyX-Code
2227                  total_length : 56
2228 \end_layout
2229
2230 \begin_layout LyX-Code
2231         uint64_t next;;
2232 \end_layout
2233
2234 \begin_layout LyX-Code
2235 };
2236 \end_layout
2237
2238 \begin_layout Standard
2239 Note that by limiting valid offsets to 56 bits, we can pack everything we
2240  need into 3 64-byte words, meaning our minimum record size is 8 bytes.
2241 \end_layout
2242
2243 \begin_layout Subsubsection
2244 Status
2245 \end_layout
2246
2247 \begin_layout Standard
2248 Complete.
2249 \end_layout
2250
2251 \begin_layout Subsection
2252 Transaction Commit Requires 4 fdatasync
2253 \end_layout
2254
2255 \begin_layout Standard
2256 The current transaction algorithm is:
2257 \end_layout
2258
2259 \begin_layout Enumerate
2260 write_recovery_data();
2261 \end_layout
2262
2263 \begin_layout Enumerate
2264 sync();
2265 \end_layout
2266
2267 \begin_layout Enumerate
2268 write_recovery_header();
2269 \end_layout
2270
2271 \begin_layout Enumerate
2272 sync();
2273 \end_layout
2274
2275 \begin_layout Enumerate
2276 overwrite_with_new_data();
2277 \end_layout
2278
2279 \begin_layout Enumerate
2280 sync();
2281 \end_layout
2282
2283 \begin_layout Enumerate
2284 remove_recovery_header();
2285 \end_layout
2286
2287 \begin_layout Enumerate
2288 sync(); 
2289 \end_layout
2290
2291 \begin_layout Standard
2292 On current ext3, each sync flushes all data to disk, so the next 3 syncs
2293  are relatively expensive.
2294  But this could become a performance bottleneck on other filesystems such
2295  as ext4.
2296 \end_layout
2297
2298 \begin_layout Subsubsection
2299 Proposed Solution
2300 \end_layout
2301
2302 \begin_layout Standard
2303 Neil Brown points out that this is overzealous, and only one sync is needed:
2304 \end_layout
2305
2306 \begin_layout Enumerate
2307 Bundle the recovery data, a transaction counter and a strong checksum of
2308  the new data.
2309 \end_layout
2310
2311 \begin_layout Enumerate
2312 Strong checksum that whole bundle.
2313 \end_layout
2314
2315 \begin_layout Enumerate
2316 Store the bundle in the database.
2317 \end_layout
2318
2319 \begin_layout Enumerate
2320 Overwrite the oldest of the two recovery pointers in the header (identified
2321  using the transaction counter) with the offset of this bundle.
2322 \end_layout
2323
2324 \begin_layout Enumerate
2325 sync.
2326 \end_layout
2327
2328 \begin_layout Enumerate
2329 Write the new data to the file.
2330 \end_layout
2331
2332 \begin_layout Standard
2333 Checking for recovery means identifying the latest bundle with a valid checksum
2334  and using the new data checksum to ensure that it has been applied.
2335  This is more expensive than the current check, but need only be done at
2336  open.
2337  For running databases, a separate header field can be used to indicate
2338  a transaction in progress; we need only check for recovery if this is set.
2339 \end_layout
2340
2341 \begin_layout Subsubsection
2342 Status
2343 \end_layout
2344
2345 \begin_layout Standard
2346 Deferred.
2347 \end_layout
2348
2349 \begin_layout Subsection
2350 \begin_inset CommandInset label
2351 LatexCommand label
2352 name "sub:TDB-Does-Not"
2353
2354 \end_inset
2355
2356 TDB Does Not Have Snapshot Support
2357 \end_layout
2358
2359 \begin_layout Subsubsection
2360 Proposed SolutionNone.
2361  At some point you say 
2362 \begin_inset Quotes eld
2363 \end_inset
2364
2365 use a real database
2366 \begin_inset Quotes erd
2367 \end_inset
2368
2369  (but see 
2370 \begin_inset CommandInset ref
2371 LatexCommand ref
2372 reference "replay-attribute"
2373
2374 \end_inset
2375
2376 ).
2377 \end_layout
2378
2379 \begin_layout Standard
2380 But as a thought experiment, if we implemented transactions to only overwrite
2381  free entries (this is tricky: there must not be a header in each entry
2382  which indicates whether it is free, but use of presence in metadata elsewhere),
2383  and a pointer to the hash table, we could create an entirely new commit
2384  without destroying existing data.
2385  Then it would be easy to implement snapshots in a similar way.
2386 \end_layout
2387
2388 \begin_layout Standard
2389 This would not allow arbitrary changes to the database, such as tdb_repack
2390  does, and would require more space (since we have to preserve the current
2391  and future entries at once).
2392  If we used hash trees rather than one big hash table, we might only have
2393  to rewrite some sections of the hash, too.
2394 \end_layout
2395
2396 \begin_layout Standard
2397 We could then implement snapshots using a similar method, using multiple
2398  different hash tables/free tables.
2399 \end_layout
2400
2401 \begin_layout Subsubsection
2402 Status
2403 \end_layout
2404
2405 \begin_layout Standard
2406 Deferred.
2407 \end_layout
2408
2409 \begin_layout Subsection
2410 Transactions Cannot Operate in Parallel
2411 \end_layout
2412
2413 \begin_layout Standard
2414 This would be useless for ldb, as it hits the index records with just about
2415  every update.
2416  It would add significant complexity in resolving clashes, and cause the
2417  all transaction callers to write their code to loop in the case where the
2418  transactions spuriously failed.
2419 \end_layout
2420
2421 \begin_layout Subsubsection
2422 Proposed Solution
2423 \end_layout
2424
2425 \begin_layout Standard
2426 None (but see 
2427 \begin_inset CommandInset ref
2428 LatexCommand ref
2429 reference "replay-attribute"
2430
2431 \end_inset
2432
2433 ).
2434  We could solve a small part of the problem by providing read-only transactions.
2435  These would allow one write transaction to begin, but it could not commit
2436  until all r/o transactions are done.
2437  This would require a new RO_TRANSACTION_LOCK, which would be upgraded on
2438  commit.
2439 \end_layout
2440
2441 \begin_layout Subsubsection
2442 Status
2443 \end_layout
2444
2445 \begin_layout Standard
2446 Deferred.
2447 \end_layout
2448
2449 \begin_layout Subsection
2450 Default Hash Function Is Suboptimal
2451 \end_layout
2452
2453 \begin_layout Standard
2454 The Knuth-inspired multiplicative hash used by tdb is fairly slow (especially
2455  if we expand it to 64 bits), and works best when the hash bucket size is
2456  a prime number (which also means a slow modulus).
2457  In addition, it is highly predictable which could potentially lead to a
2458  Denial of Service attack in some TDB uses.
2459 \end_layout
2460
2461 \begin_layout Subsubsection
2462 Proposed Solution
2463 \end_layout
2464
2465 \begin_layout Standard
2466 The Jenkins lookup3 hash
2467 \begin_inset Foot
2468 status open
2469
2470 \begin_layout Plain Layout
2471 http://burtleburtle.net/bob/c/lookup3.c
2472 \end_layout
2473
2474 \end_inset
2475
2476  is a fast and superbly-mixing hash.
2477  It's used by the Linux kernel and almost everything else.
2478  This has the particular properties that it takes an initial seed, and produces
2479  two 32 bit hash numbers, which we can combine into a 64-bit hash.
2480 \end_layout
2481
2482 \begin_layout Standard
2483 The seed should be created at tdb-creation time from some random source,
2484  and placed in the header.
2485  This is far from foolproof, but adds a little bit of protection against
2486  hash bombing.
2487 \end_layout
2488
2489 \begin_layout Subsubsection
2490 Status
2491 \end_layout
2492
2493 \begin_layout Standard
2494 Complete.
2495 \end_layout
2496
2497 \begin_layout Subsection
2498 \begin_inset CommandInset label
2499 LatexCommand label
2500 name "Reliable-Traversal-Adds"
2501
2502 \end_inset
2503
2504 Reliable Traversal Adds Complexity
2505 \end_layout
2506
2507 \begin_layout Standard
2508 We lock a record during traversal iteration, and try to grab that lock in
2509  the delete code.
2510  If that grab on delete fails, we simply mark it deleted and continue onwards;
2511  traversal checks for this condition and does the delete when it moves off
2512  the record.
2513 \end_layout
2514
2515 \begin_layout Standard
2516 If traversal terminates, the dead record may be left indefinitely.
2517 \end_layout
2518
2519 \begin_layout Subsubsection
2520 Proposed Solution
2521 \end_layout
2522
2523 \begin_layout Standard
2524 Remove reliability guarantees; see 
2525 \begin_inset CommandInset ref
2526 LatexCommand ref
2527 reference "traverse-Proposed-Solution"
2528
2529 \end_inset
2530
2531 .
2532 \end_layout
2533
2534 \begin_layout Subsubsection
2535 Status
2536 \end_layout
2537
2538 \begin_layout Standard
2539 Complete.
2540 \end_layout
2541
2542 \begin_layout Subsection
2543 Fcntl Locking Adds Overhead
2544 \end_layout
2545
2546 \begin_layout Standard
2547 Placing a fcntl lock means a system call, as does removing one.
2548  This is actually one reason why transactions can be faster (everything
2549  is locked once at transaction start).
2550  In the uncontended case, this overhead can theoretically be eliminated.
2551 \end_layout
2552
2553 \begin_layout Subsubsection
2554 Proposed Solution
2555 \end_layout
2556
2557 \begin_layout Standard
2558 None.
2559 \end_layout
2560
2561 \begin_layout Standard
2562 We tried this before with spinlock support, in the early days of TDB, and
2563  it didn't make much difference except in manufactured benchmarks.
2564 \end_layout
2565
2566 \begin_layout Standard
2567 We could use spinlocks (with futex kernel support under Linux), but it means
2568  that we lose automatic cleanup when a process dies with a lock.
2569  There is a method of auto-cleanup under Linux, but it's not supported by
2570  other operating systems.
2571  We could reintroduce a clear-if-first-style lock and sweep for dead futexes
2572  on open, but that wouldn't help the normal case of one concurrent opener
2573  dying.
2574  Increasingly elaborate repair schemes could be considered, but they require
2575  an ABI change (everyone must use them) anyway, so there's no need to do
2576  this at the same time as everything else.
2577 \end_layout
2578
2579 \begin_layout Subsection
2580 Some Transactions Don't Require Durability
2581 \end_layout
2582
2583 \begin_layout Standard
2584 Volker points out that gencache uses a CLEAR_IF_FIRST tdb for normal (fast)
2585  usage, and occasionally empties the results into a transactional TDB.
2586  This kind of usage prioritizes performance over durability: as long as
2587  we are consistent, data can be lost.
2588 \end_layout
2589
2590 \begin_layout Standard
2591 This would be more neatly implemented inside tdb: a 
2592 \begin_inset Quotes eld
2593 \end_inset
2594
2595 soft
2596 \begin_inset Quotes erd
2597 \end_inset
2598
2599  transaction commit (ie.
2600  syncless) which meant that data may be reverted on a crash.
2601 \end_layout
2602
2603 \begin_layout Subsubsection
2604 Proposed Solution
2605 \end_layout
2606
2607 \begin_layout Standard
2608 None.
2609 \end_layout
2610
2611 \begin_layout Standard
2612 Unfortunately any transaction scheme which overwrites old data requires
2613  a sync before that overwrite to avoid the possibility of corruption.
2614 \end_layout
2615
2616 \begin_layout Standard
2617 It seems possible to use a scheme similar to that described in 
2618 \begin_inset CommandInset ref
2619 LatexCommand ref
2620 reference "sub:TDB-Does-Not"
2621
2622 \end_inset
2623
2624 ,where transactions are committed without overwriting existing data, and
2625  an array of top-level pointers were available in the header.
2626  If the transaction is 
2627 \begin_inset Quotes eld
2628 \end_inset
2629
2630 soft
2631 \begin_inset Quotes erd
2632 \end_inset
2633
2634  then we would not need a sync at all: existing processes would pick up
2635  the new hash table and free list and work with that.
2636 \end_layout
2637
2638 \begin_layout Standard
2639 At some later point, a sync would allow recovery of the old data into the
2640  free lists (perhaps when the array of top-level pointers filled).
2641  On crash, tdb_open() would examine the array of top levels, and apply the
2642  transactions until it encountered an invalid checksum.
2643 \end_layout
2644
2645 \begin_layout Subsection
2646 Tracing Is Fragile, Replay Is External
2647 \end_layout
2648
2649 \begin_layout Standard
2650 The current TDB has compile-time-enabled tracing code, but it often breaks
2651  as it is not enabled by default.
2652  In a similar way, the ctdb code has an external wrapper which does replay
2653  tracing so it can coordinate cluster-wide transactions.
2654 \end_layout
2655
2656 \begin_layout Subsubsection
2657 Proposed Solution
2658 \begin_inset CommandInset label
2659 LatexCommand label
2660 name "replay-attribute"
2661
2662 \end_inset
2663
2664
2665 \end_layout
2666
2667 \begin_layout Standard
2668 Tridge points out that an attribute can be later added to tdb_open (see
2669  
2670 \begin_inset CommandInset ref
2671 LatexCommand ref
2672 reference "attributes"
2673
2674 \end_inset
2675
2676 ) to provide replay/trace hooks, which could become the basis for this and
2677  future parallel transactions and snapshot support.
2678 \end_layout
2679
2680 \begin_layout Subsubsection
2681 Status
2682 \end_layout
2683
2684 \begin_layout Standard
2685 Deferred.
2686 \end_layout
2687
2688 \end_body
2689 \end_document