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