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