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