tdb2: document problems with moving or enlarging hash table.
[ccan] / ccan / tdb2 / doc / design.lyx,v
1 head    1.8;
2 access;
3 symbols;
4 locks; strict;
5 comment @# @;
6
7
8 1.8
9 date    2010.09.02.02.29.05;    author rusty;   state Exp;
10 branches;
11 next    1.7;
12
13 1.7
14 date    2010.09.01.10.58.12;    author rusty;   state Exp;
15 branches;
16 next    1.6;
17
18 1.6
19 date    2010.08.02.00.21.43;    author rusty;   state Exp;
20 branches;
21 next    1.5;
22
23 1.5
24 date    2010.08.02.00.21.16;    author rusty;   state Exp;
25 branches;
26 next    1.4;
27
28 1.4
29 date    2010.05.10.13.09.11;    author rusty;   state Exp;
30 branches;
31 next    1.3;
32
33 1.3
34 date    2010.05.10.11.58.37;    author rusty;   state Exp;
35 branches;
36 next    1.2;
37
38 1.2
39 date    2010.05.10.05.35.13;    author rusty;   state Exp;
40 branches;
41 next    1.1;
42
43 1.1
44 date    2010.05.04.02.29.16;    author rusty;   state Exp;
45 branches;
46 next    ;
47
48
49 desc
50 @First draft
51 @
52
53
54 1.8
55 log
56 @Remove bogus footnote
57 @
58 text
59 @#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
60 \lyxformat 345
61 \begin_document
62 \begin_header
63 \textclass article
64 \use_default_options true
65 \language english
66 \inputencoding auto
67 \font_roman default
68 \font_sans default
69 \font_typewriter default
70 \font_default_family default
71 \font_sc false
72 \font_osf false
73 \font_sf_scale 100
74 \font_tt_scale 100
75
76 \graphics default
77 \paperfontsize default
78 \use_hyperref false
79 \papersize default
80 \use_geometry false
81 \use_amsmath 1
82 \use_esint 1
83 \cite_engine basic
84 \use_bibtopic false
85 \paperorientation portrait
86 \secnumdepth 3
87 \tocdepth 3
88 \paragraph_separation indent
89 \defskip medskip
90 \quotes_language english
91 \papercolumns 1
92 \papersides 1
93 \paperpagestyle default
94 \tracking_changes true
95 \output_changes true
96 \author "Rusty Russell,,," 
97 \author "" 
98 \end_header
99
100 \begin_body
101
102 \begin_layout Title
103 TDB2: A Redesigning The Trivial DataBase
104 \end_layout
105
106 \begin_layout Author
107 Rusty Russell, IBM Corporation
108 \end_layout
109
110 \begin_layout Date
111
112 \change_deleted 0 1283307542
113 26-July
114 \change_inserted 0 1283307544
115 1-September
116 \change_unchanged
117 -2010
118 \end_layout
119
120 \begin_layout Abstract
121 The Trivial DataBase on-disk format is 32 bits; with usage cases heading
122  towards the 4G limit, that must change.
123  This required breakage provides an opportunity to revisit TDB's other design
124  decisions and reassess them.
125 \end_layout
126
127 \begin_layout Section
128 Introduction
129 \end_layout
130
131 \begin_layout Standard
132 The Trivial DataBase was originally written by Andrew Tridgell as a simple
133  key/data pair storage system with the same API as dbm, but allowing multiple
134  readers and writers while being small enough (< 1000 lines of C) to include
135  in SAMBA.
136  The simple design created in 1999 has proven surprisingly robust and performant
137 , used in Samba versions 3 and 4 as well as numerous other projects.
138  Its useful life was greatly increased by the (backwards-compatible!) addition
139  of transaction support in 2005.
140 \end_layout
141
142 \begin_layout Standard
143 The wider variety and greater demands of TDB-using code has lead to some
144  organic growth of the API, as well as some compromises on the implementation.
145  None of these, by themselves, are seen as show-stoppers, but the cumulative
146  effect is to a loss of elegance over the initial, simple TDB implementation.
147  Here is a table of the approximate number of lines of implementation code
148  and number of API functions at the end of each year:
149 \end_layout
150
151 \begin_layout Standard
152 \begin_inset Tabular
153 <lyxtabular version="3" rows="12" columns="3">
154 <features>
155 <column alignment="center" valignment="top" width="0">
156 <column alignment="center" valignment="top" width="0">
157 <column alignment="center" valignment="top" width="0">
158 <row>
159 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
160 \begin_inset Text
161
162 \begin_layout Plain Layout
163 Year End
164 \end_layout
165
166 \end_inset
167 </cell>
168 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
169 \begin_inset Text
170
171 \begin_layout Plain Layout
172 API Functions
173 \end_layout
174
175 \end_inset
176 </cell>
177 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
178 \begin_inset Text
179
180 \begin_layout Plain Layout
181 Lines of C Code Implementation
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 1999
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 13
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 1195
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 2000
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 24
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 1725
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 2001
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 32
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 2228
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 2002
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 35
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 2481
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 2003
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 35
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 2552
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 2004
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 40
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 2584
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 2005
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 38
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 2647
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 2006
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 52
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 3754
414 \end_layout
415
416 \end_inset
417 </cell>
418 </row>
419 <row>
420 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
421 \begin_inset Text
422
423 \begin_layout Plain Layout
424 2007
425 \end_layout
426
427 \end_inset
428 </cell>
429 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
430 \begin_inset Text
431
432 \begin_layout Plain Layout
433 66
434 \end_layout
435
436 \end_inset
437 </cell>
438 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
439 \begin_inset Text
440
441 \begin_layout Plain Layout
442 4398
443 \end_layout
444
445 \end_inset
446 </cell>
447 </row>
448 <row>
449 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
450 \begin_inset Text
451
452 \begin_layout Plain Layout
453 2008
454 \end_layout
455
456 \end_inset
457 </cell>
458 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
459 \begin_inset Text
460
461 \begin_layout Plain Layout
462 71
463 \end_layout
464
465 \end_inset
466 </cell>
467 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
468 \begin_inset Text
469
470 \begin_layout Plain Layout
471 4768
472 \end_layout
473
474 \end_inset
475 </cell>
476 </row>
477 <row>
478 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
479 \begin_inset Text
480
481 \begin_layout Plain Layout
482 2009
483 \end_layout
484
485 \end_inset
486 </cell>
487 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
488 \begin_inset Text
489
490 \begin_layout Plain Layout
491 73
492 \end_layout
493
494 \end_inset
495 </cell>
496 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
497 \begin_inset Text
498
499 \begin_layout Plain Layout
500 5715
501 \end_layout
502
503 \end_inset
504 </cell>
505 </row>
506 </lyxtabular>
507
508 \end_inset
509
510
511 \end_layout
512
513 \begin_layout Standard
514 This review is an attempt to catalog and address all the known issues with
515  TDB and create solutions which address the problems without significantly
516  increasing complexity; all involved are far too aware of the dangers of
517  second system syndrome in rewriting a successful project like this.
518 \end_layout
519
520 \begin_layout Section
521 API Issues
522 \end_layout
523
524 \begin_layout Subsection
525 tdb_open_ex Is Not Expandable
526 \end_layout
527
528 \begin_layout Standard
529 The tdb_open() call was expanded to tdb_open_ex(), which added an optional
530  hashing function and an optional logging function argument.
531  Additional arguments to open would require the introduction of a tdb_open_ex2
532  call etc.
533 \end_layout
534
535 \begin_layout Subsubsection
536 Proposed Solution
537 \end_layout
538
539 \begin_layout Standard
540 tdb_open() will take a linked-list of attributes:
541 \end_layout
542
543 \begin_layout LyX-Code
544 enum tdb_attribute {
545 \end_layout
546
547 \begin_layout LyX-Code
548     TDB_ATTRIBUTE_LOG = 0,
549 \end_layout
550
551 \begin_layout LyX-Code
552     TDB_ATTRIBUTE_HASH = 1
553 \end_layout
554
555 \begin_layout LyX-Code
556 };
557 \end_layout
558
559 \begin_layout LyX-Code
560 struct tdb_attribute_base {
561 \end_layout
562
563 \begin_layout LyX-Code
564     enum tdb_attribute attr;
565 \end_layout
566
567 \begin_layout LyX-Code
568     union tdb_attribute *next;
569 \end_layout
570
571 \begin_layout LyX-Code
572 };
573 \end_layout
574
575 \begin_layout LyX-Code
576 struct tdb_attribute_log {
577 \end_layout
578
579 \begin_layout LyX-Code
580     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_LOG */
581 \end_layout
582
583 \begin_layout LyX-Code
584     tdb_log_func log_fn;
585 \end_layout
586
587 \begin_layout LyX-Code
588     void *log_private;
589 \end_layout
590
591 \begin_layout LyX-Code
592 };
593 \end_layout
594
595 \begin_layout LyX-Code
596 struct tdb_attribute_hash {
597 \end_layout
598
599 \begin_layout LyX-Code
600     struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_HASH */
601 \end_layout
602
603 \begin_layout LyX-Code
604     tdb_hash_func hash_fn;
605 \end_layout
606
607 \begin_layout LyX-Code
608     void *hash_private;
609 \end_layout
610
611 \begin_layout LyX-Code
612 };
613 \end_layout
614
615 \begin_layout LyX-Code
616 union tdb_attribute {
617 \end_layout
618
619 \begin_layout LyX-Code
620     struct tdb_attribute_base base;
621 \end_layout
622
623 \begin_layout LyX-Code
624     struct tdb_attribute_log log;
625 \end_layout
626
627 \begin_layout LyX-Code
628     struct tdb_attribute_hash hash;
629 \end_layout
630
631 \begin_layout LyX-Code
632 };
633 \end_layout
634
635 \begin_layout Standard
636 This allows future attributes to be added, even if this expands the size
637  of the union.
638 \end_layout
639
640 \begin_layout Subsection
641 tdb_traverse Makes Impossible Guarantees
642 \end_layout
643
644 \begin_layout Standard
645 tdb_traverse (and tdb_firstkey/tdb_nextkey) predate transactions, and it
646  was thought that it was important to guarantee that all records which exist
647  at the start and end of the traversal would be included, and no record
648  would be included twice.
649 \end_layout
650
651 \begin_layout Standard
652 This adds complexity (see
653 \begin_inset CommandInset ref
654 LatexCommand ref
655 reference "Reliable-Traversal-Adds"
656
657 \end_inset
658
659 ) and does not work anyway for records which are altered (in particular,
660  those which are expanded may be effectively deleted and re-added behind
661  the traversal).
662 \end_layout
663
664 \begin_layout Subsubsection
665 \begin_inset CommandInset label
666 LatexCommand label
667 name "traverse-Proposed-Solution"
668
669 \end_inset
670
671 Proposed Solution
672 \end_layout
673
674 \begin_layout Standard
675 Abandon the guarantee.
676  You will see every record if no changes occur during your traversal, otherwise
677  you will see some subset.
678  You can prevent changes by using a transaction or the locking API.
679 \end_layout
680
681 \begin_layout Subsection
682 Nesting of Transactions Is Fraught
683 \end_layout
684
685 \begin_layout Standard
686 TDB has alternated between allowing nested transactions and not allowing
687  them.
688  Various paths in the Samba codebase assume that transactions will nest,
689  and in a sense they can: the operation is only committed to disk when the
690  outer transaction is committed.
691  There are two problems, however:
692 \end_layout
693
694 \begin_layout Enumerate
695 Canceling the inner transaction will cause the outer transaction commit
696  to fail, and will not undo any operations since the inner transaction began.
697  This problem is soluble with some additional internal code.
698 \end_layout
699
700 \begin_layout Enumerate
701 An inner transaction commit can be cancelled by the outer transaction.
702  This is desirable in the way which Samba's database initialization code
703  uses transactions, but could be a surprise to any users expecting a successful
704  transaction commit to expose changes to others.
705 \end_layout
706
707 \begin_layout Standard
708 The current solution is to specify the behavior at tdb_open(), with the
709  default currently that nested transactions are allowed.
710  This flag can also be changed at runtime.
711 \end_layout
712
713 \begin_layout Subsubsection
714 Proposed Solution
715 \end_layout
716
717 \begin_layout Standard
718 Given the usage patterns, it seems that the 
719 \begin_inset Quotes eld
720 \end_inset
721
722 least-surprise
723 \begin_inset Quotes erd
724 \end_inset
725
726  behavior of disallowing nested transactions should become the default.
727  Additionally, it seems the outer transaction is the only code which knows
728  whether inner transactions should be allowed, so a flag to indicate this
729  could be added to tdb_transaction_start.
730  However, this behavior can be simulated with a wrapper which uses tdb_add_flags
731 () and tdb_remove_flags(), so the API should not be expanded for this relatively
732 -obscure case.
733 \end_layout
734
735 \begin_layout Subsection
736 Incorrect Hash Function is Not Detected
737 \end_layout
738
739 \begin_layout Standard
740 tdb_open_ex() allows the calling code to specify a different hash function
741  to use, but does not check that all other processes accessing this tdb
742  are using the same hash function.
743  The result is that records are missing from tdb_fetch().
744 \end_layout
745
746 \begin_layout Subsubsection
747 Proposed Solution
748 \end_layout
749
750 \begin_layout Standard
751 The header should contain an example hash result (eg.
752  the hash of 0xdeadbeef), and tdb_open_ex() should check that the given
753  hash function produces the same answer, or fail the tdb_open call.
754 \end_layout
755
756 \begin_layout Subsection
757 tdb_set_max_dead/TDB_VOLATILE Expose Implementation
758 \end_layout
759
760 \begin_layout Standard
761 In response to scalability issues with the free list (
762 \begin_inset CommandInset ref
763 LatexCommand ref
764 reference "TDB-Freelist-Is"
765
766 \end_inset
767
768 ) two API workarounds have been incorporated in TDB: tdb_set_max_dead()
769  and the TDB_VOLATILE flag to tdb_open.
770  The latter actually calls the former with an argument of 
771 \begin_inset Quotes eld
772 \end_inset
773
774 5
775 \begin_inset Quotes erd
776 \end_inset
777
778 .
779 \end_layout
780
781 \begin_layout Standard
782 This code allows deleted records to accumulate without putting them in the
783  free list.
784  On delete we iterate through each chain and free them in a batch if there
785  are more than max_dead entries.
786  These are never otherwise recycled except as a side-effect of a tdb_repack.
787 \end_layout
788
789 \begin_layout Subsubsection
790 Proposed Solution
791 \end_layout
792
793 \begin_layout Standard
794 With the scalability problems of the freelist solved, this API can be removed.
795  The TDB_VOLATILE flag may still be useful as a hint that store and delete
796  of records will be at least as common as fetch in order to allow some internal
797  tuning, but initially will become a no-op.
798 \end_layout
799
800 \begin_layout Subsection
801 \begin_inset CommandInset label
802 LatexCommand label
803 name "TDB-Files-Cannot"
804
805 \end_inset
806
807 TDB Files Cannot Be Opened Multiple Times In The Same Process
808 \end_layout
809
810 \begin_layout Standard
811 No process can open the same TDB twice; we check and disallow it.
812  This is an unfortunate side-effect of fcntl locks, which operate on a per-file
813  rather than per-file-descriptor basis, and do not nest.
814  Thus, closing any file descriptor on a file clears all the locks obtained
815  by this process, even if they were placed using a different file descriptor!
816 \end_layout
817
818 \begin_layout Standard
819 Note that even if this were solved, deadlock could occur if operations were
820  nested: this is a more manageable programming error in most cases.
821 \end_layout
822
823 \begin_layout Subsubsection
824 Proposed Solution
825 \end_layout
826
827 \begin_layout Standard
828 We could lobby POSIX to fix the perverse rules, or at least lobby Linux
829  to violate them so that the most common implementation does not have this
830  restriction.
831  This would be a generally good idea for other fcntl lock users.
832 \end_layout
833
834 \begin_layout Standard
835 Samba uses a wrapper which hands out the same tdb_context to multiple callers
836  if this happens, and does simple reference counting.
837  We should do this inside the tdb library, which already emulates lock nesting
838  internally; it would need to recognize when deadlock occurs within a single
839  process.
840  This would create a new failure mode for tdb operations (while we currently
841  handle locking failures, they are impossible in normal use and a process
842  encountering them can do little but give up).
843 \end_layout
844
845 \begin_layout Standard
846 I do not see benefit in an additional tdb_open flag to indicate whether
847  re-opening is allowed, as though there may be some benefit to adding a
848  call to detect when a tdb_context is shared, to allow other to create such
849  an API.
850 \end_layout
851
852 \begin_layout Subsection
853 TDB API Is Not POSIX Thread-safe
854 \end_layout
855
856 \begin_layout Standard
857 The TDB API uses an error code which can be queried after an operation to
858  determine what went wrong.
859  This programming model does not work with threads, unless specific additional
860  guarantees are given by the implementation.
861  In addition, even otherwise-independent threads cannot open the same TDB
862  (as in 
863 \begin_inset CommandInset ref
864 LatexCommand ref
865 reference "TDB-Files-Cannot"
866
867 \end_inset
868
869 ).
870 \end_layout
871
872 \begin_layout Subsubsection
873 Proposed Solution
874 \end_layout
875
876 \begin_layout Standard
877 Reachitecting the API to include a tdb_errcode pointer would be a great
878  deal of churn; we are better to guarantee that the tdb_errcode is per-thread
879  so the current programming model can be maintained.
880 \end_layout
881
882 \begin_layout Standard
883 This requires dynamic per-thread allocations, which is awkward with POSIX
884  threads (pthread_key_create space is limited and we cannot simply allocate
885  a key for every TDB).
886 \end_layout
887
888 \begin_layout Standard
889 Internal locking is required to make sure that fcntl locks do not overlap
890  between threads, and also that the global list of tdbs is maintained.
891 \end_layout
892
893 \begin_layout Standard
894 The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe
895  version of the library, and otherwise no overhead will exist.
896 \end_layout
897
898 \begin_layout Subsection
899 *_nonblock Functions And *_mark Functions Expose Implementation
900 \end_layout
901
902 \begin_layout Standard
903 CTDB
904 \begin_inset Foot
905 status collapsed
906
907 \begin_layout Plain Layout
908 Clustered TDB, see http://ctdb.samba.org
909 \end_layout
910
911 \end_inset
912
913  wishes to operate on TDB in a non-blocking manner.
914  This is currently done as follows:
915 \end_layout
916
917 \begin_layout Enumerate
918 Call the _nonblock variant of an API function (eg.
919  tdb_lockall_nonblock).
920  If this fails:
921 \end_layout
922
923 \begin_layout Enumerate
924 Fork a child process, and wait for it to call the normal variant (eg.
925  tdb_lockall).
926 \end_layout
927
928 \begin_layout Enumerate
929 If the child succeeds, call the _mark variant to indicate we already have
930  the locks (eg.
931  tdb_lockall_mark).
932 \end_layout
933
934 \begin_layout Enumerate
935 Upon completion, tell the child to release the locks (eg.
936  tdb_unlockall).
937 \end_layout
938
939 \begin_layout Enumerate
940 Indicate to tdb that it should consider the locks removed (eg.
941  tdb_unlockall_mark).
942 \end_layout
943
944 \begin_layout Standard
945 There are several issues with this approach.
946  Firstly, adding two new variants of each function clutters the API for
947  an obscure use, and so not all functions have three variants.
948  Secondly, it assumes that all paths of the functions ask for the same locks,
949  otherwise the parent process will have to get a lock which the child doesn't
950  have under some circumstances.
951  I don't believe this is currently the case, but it constrains the implementatio
952 n.
953  
954 \end_layout
955
956 \begin_layout Subsubsection
957 \begin_inset CommandInset label
958 LatexCommand label
959 name "Proposed-Solution-locking-hook"
960
961 \end_inset
962
963 Proposed Solution
964 \end_layout
965
966 \begin_layout Standard
967 Implement a hook for locking methods, so that the caller can control the
968  calls to create and remove fcntl locks.
969  In this scenario, ctdbd would operate as follows:
970 \end_layout
971
972 \begin_layout Enumerate
973 Call the normal API function, eg tdb_lockall().
974 \end_layout
975
976 \begin_layout Enumerate
977 When the lock callback comes in, check if the child has the lock.
978  Initially, this is always false.
979  If so, return 0.
980  Otherwise, try to obtain it in non-blocking mode.
981  If that fails, return EWOULDBLOCK.
982 \end_layout
983
984 \begin_layout Enumerate
985 Release locks in the unlock callback as normal.
986 \end_layout
987
988 \begin_layout Enumerate
989 If tdb_lockall() fails, see if we recorded a lock failure; if so, call the
990  child to repeat the operation.
991 \end_layout
992
993 \begin_layout Enumerate
994 The child records what locks it obtains, and returns that information to
995  the parent.
996 \end_layout
997
998 \begin_layout Enumerate
999 When the child has succeeded, goto 1.
1000 \end_layout
1001
1002 \begin_layout Standard
1003 This is flexible enough to handle any potential locking scenario, even when
1004  lock requirements change.
1005  It can be optimized so that the parent does not release locks, just tells
1006  the child which locks it doesn't need to obtain.
1007 \end_layout
1008
1009 \begin_layout Standard
1010 It also keeps the complexity out of the API, and in ctdbd where it is needed.
1011 \end_layout
1012
1013 \begin_layout Subsection
1014 tdb_chainlock Functions Expose Implementation
1015 \end_layout
1016
1017 \begin_layout Standard
1018 tdb_chainlock locks some number of records, including the record indicated
1019  by the given key.
1020  This gave atomicity guarantees; no-one can start a transaction, alter,
1021  read or delete that key while the lock is held.
1022 \end_layout
1023
1024 \begin_layout Standard
1025 It also makes the same guarantee for any other key in the chain, which is
1026  an internal implementation detail and potentially a cause for deadlock.
1027 \end_layout
1028
1029 \begin_layout Subsubsection
1030 Proposed Solution
1031 \end_layout
1032
1033 \begin_layout Standard
1034 None.
1035  It would be nice to have an explicit single entry lock which effected no
1036  other keys.
1037  Unfortunately, this won't work for an entry which doesn't exist.
1038  Thus while chainlock may be implemented more efficiently for the existing
1039  case, it will still have overlap issues with the non-existing case.
1040  So it is best to keep the current (lack of) guarantee about which records
1041  will be effected to avoid constraining our implementation.
1042 \end_layout
1043
1044 \begin_layout Subsection
1045 Signal Handling is Not Race-Free
1046 \end_layout
1047
1048 \begin_layout Standard
1049 The tdb_setalarm_sigptr() call allows the caller's signal handler to indicate
1050  that the tdb locking code should return with a failure, rather than trying
1051  again when a signal is received (and errno == EAGAIN).
1052  This is usually used to implement timeouts.
1053 \end_layout
1054
1055 \begin_layout Standard
1056 Unfortunately, this does not work in the case where the signal is received
1057  before the tdb code enters the fcntl() call to place the lock: the code
1058  will sleep within the fcntl() code, unaware that the signal wants it to
1059  exit.
1060  In the case of long timeouts, this does not happen in practice.
1061 \end_layout
1062
1063 \begin_layout Subsubsection
1064 Proposed Solution
1065 \end_layout
1066
1067 \begin_layout Standard
1068 The locking hooks proposed in
1069 \begin_inset CommandInset ref
1070 LatexCommand ref
1071 reference "Proposed-Solution-locking-hook"
1072
1073 \end_inset
1074
1075  would allow the user to decide on whether to fail the lock acquisition
1076  on a signal.
1077  This allows the caller to choose their own compromise: they could narrow
1078  the race by checking immediately before the fcntl call.
1079 \begin_inset Foot
1080 status collapsed
1081
1082 \begin_layout Plain Layout
1083 It may be possible to make this race-free in some implementations by having
1084  the signal handler alter the struct flock to make it invalid.
1085  This will cause the fcntl() lock call to fail with EINVAL if the signal
1086  occurs before the kernel is entered, otherwise EAGAIN.
1087 \end_layout
1088
1089 \end_inset
1090
1091
1092 \end_layout
1093
1094 \begin_layout Subsection
1095 The API Uses Gratuitous Typedefs, Capitals
1096 \end_layout
1097
1098 \begin_layout Standard
1099 typedefs are useful for providing source compatibility when types can differ
1100  across implementations, or arguably in the case of function pointer definitions
1101  which are hard for humans to parse.
1102  Otherwise it is simply obfuscation and pollutes the namespace.
1103 \end_layout
1104
1105 \begin_layout Standard
1106 Capitalization is usually reserved for compile-time constants and macros.
1107 \end_layout
1108
1109 \begin_layout Description
1110 TDB_CONTEXT There is no reason to use this over 'struct tdb_context'; the
1111  definition isn't visible to the API user anyway.
1112 \end_layout
1113
1114 \begin_layout Description
1115 TDB_DATA There is no reason to use this over struct TDB_DATA; the struct
1116  needs to be understood by the API user.
1117 \end_layout
1118
1119 \begin_layout Description
1120 struct
1121 \begin_inset space ~
1122 \end_inset
1123
1124 TDB_DATA This would normally be called 'struct tdb_data'.
1125 \end_layout
1126
1127 \begin_layout Description
1128 enum
1129 \begin_inset space ~
1130 \end_inset
1131
1132 TDB_ERROR Similarly, this would normally be enum tdb_error.
1133 \end_layout
1134
1135 \begin_layout Subsubsection
1136 Proposed Solution
1137 \end_layout
1138
1139 \begin_layout Standard
1140 None.
1141  Introducing lower case variants would please pedants like myself, but if
1142  it were done the existing ones should be kept.
1143  There is little point forcing a purely cosmetic change upon tdb users.
1144 \end_layout
1145
1146 \begin_layout Subsection
1147 \begin_inset CommandInset label
1148 LatexCommand label
1149 name "tdb_log_func-Doesnt-Take"
1150
1151 \end_inset
1152
1153 tdb_log_func Doesn't Take The Private Pointer
1154 \end_layout
1155
1156 \begin_layout Standard
1157 For API compatibility reasons, the logging function needs to call tdb_get_loggin
1158 g_private() to retrieve the pointer registered by the tdb_open_ex for logging.
1159 \end_layout
1160
1161 \begin_layout Subsubsection
1162 Proposed Solution
1163 \end_layout
1164
1165 \begin_layout Standard
1166 It should simply take an extra argument, since we are prepared to break
1167  the API/ABI.
1168 \end_layout
1169
1170 \begin_layout Subsection
1171 Various Callback Functions Are Not Typesafe
1172 \end_layout
1173
1174 \begin_layout Standard
1175 The callback functions in tdb_set_logging_function (after 
1176 \begin_inset CommandInset ref
1177 LatexCommand ref
1178 reference "tdb_log_func-Doesnt-Take"
1179
1180 \end_inset
1181
1182  is resolved), tdb_parse_record, tdb_traverse, tdb_traverse_read and tdb_check
1183  all take void * and must internally convert it to the argument type they
1184  were expecting.
1185 \end_layout
1186
1187 \begin_layout Standard
1188 If this type changes, the compiler will not produce warnings on the callers,
1189  since it only sees void *.
1190 \end_layout
1191
1192 \begin_layout Subsubsection
1193 Proposed Solution
1194 \end_layout
1195
1196 \begin_layout Standard
1197 With careful use of macros, we can create callback functions which give
1198  a warning when used on gcc and the types of the callback and its private
1199  argument differ.
1200  Unsupported compilers will not give a warning, which is no worse than now.
1201  In addition, the callbacks become clearer, as they need not use void *
1202  for their parameter.
1203 \end_layout
1204
1205 \begin_layout Standard
1206 See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html
1207 \end_layout
1208
1209 \begin_layout Subsection
1210 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic
1211 \end_layout
1212
1213 \begin_layout Standard
1214 The TDB_CLEAR_IF_FIRST flag to tdb_open indicates that the TDB file should
1215  be cleared if the caller discovers it is the only process with the TDB
1216  open.
1217  However, if any caller does not specify TDB_CLEAR_IF_FIRST it will not
1218  be detected, so will have the TDB erased underneath them (usually resulting
1219  in a crash).
1220 \end_layout
1221
1222 \begin_layout Standard
1223 There is a similar issue on fork(); if the parent exits (or otherwise closes
1224  the tdb) before the child calls tdb_reopen_all() to establish the lock
1225  used to indicate the TDB is opened by someone, a TDB_CLEAR_IF_FIRST opener
1226  at that moment will believe it alone has opened the TDB and will erase
1227  it.
1228 \end_layout
1229
1230 \begin_layout Subsubsection
1231 Proposed Solution
1232 \end_layout
1233
1234 \begin_layout Standard
1235 Remove TDB_CLEAR_IF_FIRST.
1236  Other workarounds are possible, but see 
1237 \begin_inset CommandInset ref
1238 LatexCommand ref
1239 reference "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1240
1241 \end_inset
1242
1243 .
1244 \end_layout
1245
1246 \begin_layout Section
1247 Performance And Scalability Issues
1248 \end_layout
1249
1250 \begin_layout Subsection
1251 \begin_inset CommandInset label
1252 LatexCommand label
1253 name "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1254
1255 \end_inset
1256
1257 TDB_CLEAR_IF_FIRST Imposes Performance Penalty
1258 \end_layout
1259
1260 \begin_layout Standard
1261 When TDB_CLEAR_IF_FIRST is specified, a 1-byte read lock is placed at offset
1262  4 (aka.
1263  the ACTIVE_LOCK).
1264  While these locks never conflict in normal tdb usage, they do add substantial
1265  overhead for most fcntl lock implementations when the kernel scans to detect
1266  if a lock conflict exists.
1267  This is often a single linked list, making the time to acquire and release
1268  a fcntl lock O(N) where N is the number of processes with the TDB open,
1269  not the number actually doing work.
1270 \end_layout
1271
1272 \begin_layout Standard
1273 In a Samba server it is common to have huge numbers of clients sitting idle,
1274  and thus they have weaned themselves off the TDB_CLEAR_IF_FIRST flag.
1275 \begin_inset Foot
1276 status collapsed
1277
1278 \begin_layout Plain Layout
1279 There is a flag to tdb_reopen_all() which is used for this optimization:
1280  if the parent process will outlive the child, the child does not need the
1281  ACTIVE_LOCK.
1282  This is a workaround for this very performance issue.
1283 \end_layout
1284
1285 \end_inset
1286
1287
1288 \end_layout
1289
1290 \begin_layout Subsubsection
1291 Proposed Solution
1292 \end_layout
1293
1294 \begin_layout Standard
1295 Remove the flag.
1296  It was a neat idea, but even trivial servers tend to know when they are
1297  initializing for the first time and can simply unlink the old tdb at that
1298  point.
1299 \end_layout
1300
1301 \begin_layout Subsection
1302 TDB Files Have a 4G Limit
1303 \end_layout
1304
1305 \begin_layout Standard
1306 This seems to be becoming an issue (so much for 
1307 \begin_inset Quotes eld
1308 \end_inset
1309
1310 trivial
1311 \begin_inset Quotes erd
1312 \end_inset
1313
1314 !), particularly for ldb.
1315 \end_layout
1316
1317 \begin_layout Subsubsection
1318 Proposed Solution
1319 \end_layout
1320
1321 \begin_layout Standard
1322 A new, incompatible TDB format which uses 64 bit offsets internally rather
1323  than 32 bit as now.
1324  For simplicity of endian conversion (which TDB does on the fly if required),
1325  all values will be 64 bit on disk.
1326  In practice, some upper bits may be used for other purposes, but at least
1327  56 bits will be available for file offsets.
1328 \end_layout
1329
1330 \begin_layout Standard
1331 tdb_open() will automatically detect the old version, and even create them
1332  if TDB_VERSION6 is specified to tdb_open.
1333 \end_layout
1334
1335 \begin_layout Standard
1336 32 bit processes will still be able to access TDBs larger than 4G (assuming
1337  that their off_t allows them to seek to 64 bits), they will gracefully
1338  fall back as they fail to mmap.
1339  This can happen already with large TDBs.
1340 \end_layout
1341
1342 \begin_layout Standard
1343 Old versions of tdb will fail to open the new TDB files (since 28 August
1344  2009, commit 398d0c29290: prior to that any unrecognized file format would
1345  be erased and initialized as a fresh tdb!)
1346 \end_layout
1347
1348 \begin_layout Subsection
1349 TDB Records Have a 4G Limit
1350 \end_layout
1351
1352 \begin_layout Standard
1353 This has not been a reported problem, and the API uses size_t which can
1354  be 64 bit on 64 bit platforms.
1355  However, other limits may have made such an issue moot.
1356 \end_layout
1357
1358 \begin_layout Subsubsection
1359 Proposed Solution
1360 \end_layout
1361
1362 \begin_layout Standard
1363 Record sizes will be 64 bit, with an error returned on 32 bit platforms
1364  which try to access such records (the current implementation would return
1365  TDB_ERR_OOM in a similar case).
1366  It seems unlikely that 32 bit keys will be a limitation, so the implementation
1367  may not support this (see 
1368 \begin_inset CommandInset ref
1369 LatexCommand ref
1370 reference "sub:Records-Incur-A"
1371
1372 \end_inset
1373
1374 ).
1375 \end_layout
1376
1377 \begin_layout Subsection
1378 Hash Size Is Determined At TDB Creation Time
1379 \end_layout
1380
1381 \begin_layout Standard
1382 TDB contains a number of hash chains in the header; the number is specified
1383  at creation time, and defaults to 131.
1384  This is such a bottleneck on large databases (as each hash chain gets quite
1385  long), that LDB uses 10,000 for this hash.
1386  In general it is impossible to know what the 'right' answer is at database
1387  creation time.
1388 \end_layout
1389
1390 \begin_layout Subsubsection
1391
1392 \change_inserted 0 1283336713
1393 \begin_inset CommandInset label
1394 LatexCommand label
1395 name "sub:Hash-Size-Solution"
1396
1397 \end_inset
1398
1399
1400 \change_unchanged
1401 Proposed Solution
1402 \end_layout
1403
1404 \begin_layout Standard
1405 After comprehensive performance testing on various scalable hash variants
1406 \begin_inset Foot
1407 status collapsed
1408
1409 \begin_layout Plain Layout
1410 http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoying
1411  because I was previously convinced that an expanding tree of hashes would
1412  be very close to optimal.
1413 \end_layout
1414
1415 \end_inset
1416
1417 , it became clear that it is hard to beat a straight linear hash table which
1418  doubles in size when it reaches saturation.
1419  
1420 \change_deleted 0 1283307675
1421 There are three details which become important:
1422 \end_layout
1423
1424 \begin_layout Enumerate
1425
1426 \change_deleted 0 1283307675
1427 On encountering a full bucket, we use the next bucket.
1428 \end_layout
1429
1430 \begin_layout Enumerate
1431
1432 \change_deleted 0 1283307675
1433 Extra hash bits are stored with the offset, to reduce comparisons.
1434 \end_layout
1435
1436 \begin_layout Enumerate
1437
1438 \change_deleted 0 1283307675
1439 A marker entry is used on deleting an entry.
1440 \end_layout
1441
1442 \begin_layout Standard
1443
1444 \change_deleted 0 1283307675
1445 The doubling of the table must be done under a transaction; we will not
1446  reduce it on deletion, so it will be an unusual case.
1447  It will either be placed at the head (other entries will be moved out the
1448  way so we can expand).
1449  We could have a pointer in the header to the current hashtable location,
1450  but that pointer would have to be read frequently to check for hashtable
1451  moves.
1452 \end_layout
1453
1454 \begin_layout Standard
1455
1456 \change_deleted 0 1283307675
1457 The locking for this is slightly more complex than the chained case; we
1458  currently have one lock per bucket, and that means we would need to expand
1459  the lock if we overflow to the next bucket.
1460  The frequency of such collisions will effect our locking heuristics: we
1461  can always lock more buckets than we need.
1462 \end_layout
1463
1464 \begin_layout Standard
1465
1466 \change_deleted 0 1283307675
1467 One possible optimization is to only re-check the hash size on an insert
1468  or a lookup miss.
1469
1470 \change_inserted 0 1283307770
1471  Unfortunately, altering the hash table introduces serious locking complications
1472 : the entire hash table needs to be locked to enlarge the hash table, and
1473  others might be holding locks.
1474  Particularly insidious are insertions done under tdb_chainlock.
1475 \end_layout
1476
1477 \begin_layout Standard
1478
1479 \change_inserted 0 1283336187
1480 Thus an expanding layered hash will be used: an array of hash groups, with
1481  each hash group exploding into pointers to lower hash groups once it fills,
1482  turning into a hash tree.
1483  This has implications for locking: we must lock the entire group in case
1484  we need to expand it, yet we don't know how deep the tree is at that point.
1485 \end_layout
1486
1487 \begin_layout Standard
1488
1489 \change_inserted 0 1283336586
1490 Note that bits from the hash table entries should be stolen to hold more
1491  hash bits to reduce the penalty of collisions.
1492  We can use the otherwise-unused lower 3 bits.
1493  If we limit the size of the database to 64 exabytes, we can use the top
1494  8 bits of the hash entry as well.
1495  These 11 bits would reduce false positives down to 1 in 2000 which is more
1496  than we need: we can use one of the bits to indicate that the extra hash
1497  bits are valid.
1498  This means we can choose not to re-hash all entries when we expand a hash
1499  group; simply use the next bits we need and mark them invalid.
1500 \change_unchanged
1501
1502 \end_layout
1503
1504 \begin_layout Subsection
1505 \begin_inset CommandInset label
1506 LatexCommand label
1507 name "TDB-Freelist-Is"
1508
1509 \end_inset
1510
1511 TDB Freelist Is Highly Contended
1512 \end_layout
1513
1514 \begin_layout Standard
1515 TDB uses a single linked list for the free list.
1516  Allocation occurs as follows, using heuristics which have evolved over
1517  time:
1518 \end_layout
1519
1520 \begin_layout Enumerate
1521 Get the free list lock for this whole operation.
1522 \end_layout
1523
1524 \begin_layout Enumerate
1525 Multiply length by 1.25, so we always over-allocate by 25%.
1526 \end_layout
1527
1528 \begin_layout Enumerate
1529 Set the slack multiplier to 1.
1530 \end_layout
1531
1532 \begin_layout Enumerate
1533 Examine the current freelist entry: if it is > length but < the current
1534  best case, remember it as the best case.
1535 \end_layout
1536
1537 \begin_layout Enumerate
1538 Multiply the slack multiplier by 1.05.
1539 \end_layout
1540
1541 \begin_layout Enumerate
1542 If our best fit so far is less than length * slack multiplier, return it.
1543  The slack will be turned into a new free record if it's large enough.
1544 \end_layout
1545
1546 \begin_layout Enumerate
1547 Otherwise, go onto the next freelist entry.
1548 \end_layout
1549
1550 \begin_layout Standard
1551 Deleting a record occurs as follows:
1552 \end_layout
1553
1554 \begin_layout Enumerate
1555 Lock the hash chain for this whole operation.
1556 \end_layout
1557
1558 \begin_layout Enumerate
1559 Walk the chain to find the record, keeping the prev pointer offset.
1560 \end_layout
1561
1562 \begin_layout Enumerate
1563 If max_dead is non-zero:
1564 \end_layout
1565
1566 \begin_deeper
1567 \begin_layout Enumerate
1568 Walk the hash chain again and count the dead records.
1569 \end_layout
1570
1571 \begin_layout Enumerate
1572 If it's more than max_dead, bulk free all the dead ones (similar to steps
1573  4 and below, but the lock is only obtained once).
1574 \end_layout
1575
1576 \begin_layout Enumerate
1577 Simply mark this record as dead and return.
1578  
1579 \end_layout
1580
1581 \end_deeper
1582 \begin_layout Enumerate
1583 Get the free list lock for the remainder of this operation.
1584 \end_layout
1585
1586 \begin_layout Enumerate
1587 \begin_inset CommandInset label
1588 LatexCommand label
1589 name "right-merging"
1590
1591 \end_inset
1592
1593 Examine the following block to see if it is free; if so, enlarge the current
1594  block and remove that block from the free list.
1595  This was disabled, as removal from the free list was O(entries-in-free-list).
1596 \end_layout
1597
1598 \begin_layout Enumerate
1599 Examine the preceeding block to see if it is free: for this reason, each
1600  block has a 32-bit tailer which indicates its length.
1601  If it is free, expand it to cover our new block and return.
1602 \end_layout
1603
1604 \begin_layout Enumerate
1605 Otherwise, prepend ourselves to the free list.
1606 \end_layout
1607
1608 \begin_layout Standard
1609 Disabling right-merging (step 
1610 \begin_inset CommandInset ref
1611 LatexCommand ref
1612 reference "right-merging"
1613
1614 \end_inset
1615
1616 ) causes fragmentation; the other heuristics proved insufficient to address
1617  this, so the final answer to this was that when we expand the TDB file
1618  inside a transaction commit, we repack the entire tdb.
1619 \end_layout
1620
1621 \begin_layout Standard
1622 The single list lock limits our allocation rate; due to the other issues
1623  this is not currently seen as a bottleneck.
1624 \end_layout
1625
1626 \begin_layout Subsubsection
1627 Proposed Solution
1628 \change_deleted 0 1283336858
1629
1630 \end_layout
1631
1632 \begin_layout Standard
1633 The first step is to remove all the current heuristics, as they obviously
1634  interact, then examine them once the lock contention is addressed.
1635 \end_layout
1636
1637 \begin_layout Standard
1638 The free list must be split to reduce contention.
1639  Assuming perfect free merging, we can at most have 1 free list entry for
1640  each entry.
1641  This implies that the number of free lists is related to the size of the
1642  hash table, but as it is rare to walk a large number of free list entries
1643  we can use far fewer, say 1/32 of the number of hash buckets.
1644 \change_inserted 0 1283336910
1645
1646 \end_layout
1647
1648 \begin_layout Standard
1649
1650 \change_inserted 0 1283337052
1651 It seems tempting to try to reuse the hash implementation which we use for
1652  records here, but we have two ways of searching for free entries: for allocatio
1653 n we search by size (and possibly zone) which produces too many clashes
1654  for our hash table to handle well, and for coalescing we search by address.
1655  Thus an array of doubly-linked free lists seems preferable.
1656 \change_unchanged
1657
1658 \end_layout
1659
1660 \begin_layout Standard
1661 There are various benefits in using per-size free lists (see 
1662 \begin_inset CommandInset ref
1663 LatexCommand ref
1664 reference "sub:TDB-Becomes-Fragmented"
1665
1666 \end_inset
1667
1668 ) but it's not clear this would reduce contention in the common case where
1669  all processes are allocating/freeing the same size.
1670  Thus we almost certainly need to divide in other ways: the most obvious
1671  is to divide the file into zones, and using a free list (or set of free
1672  lists) for each.
1673  This approximates address ordering.
1674 \end_layout
1675
1676 \begin_layout Standard
1677 Note that this means we need to split the free lists when we expand the
1678  file; this is probably acceptable when we double the hash table size, since
1679  that is such an expensive operation already.
1680  In the case of increasing the file size, there is an optimization we can
1681  use: if we use M in the formula above as the file size rounded up to the
1682  next power of 2, we only need reshuffle free lists when the file size crosses
1683  a power of 2 boundary, 
1684 \emph on
1685 and 
1686 \emph default
1687 reshuffling the free lists is trivial: we simply merge every consecutive
1688  pair of free lists.
1689 \end_layout
1690
1691 \begin_layout Standard
1692 The basic algorithm is as follows.
1693  Freeing is simple:
1694 \end_layout
1695
1696 \begin_layout Enumerate
1697 Identify the correct zone.
1698 \end_layout
1699
1700 \begin_layout Enumerate
1701 Lock the corresponding list.
1702 \end_layout
1703
1704 \begin_layout Enumerate
1705 Re-check the zone (we didn't have a lock, sizes could have changed): relock
1706  if necessary.
1707 \end_layout
1708
1709 \begin_layout Enumerate
1710 Place the freed entry in the list for that zone.
1711 \end_layout
1712
1713 \begin_layout Standard
1714 Allocation is a little more complicated, as we perform delayed coalescing
1715  at this point:
1716 \end_layout
1717
1718 \begin_layout Enumerate
1719 Pick a zone either the zone we last freed into, or based on a 
1720 \begin_inset Quotes eld
1721 \end_inset
1722
1723 random
1724 \begin_inset Quotes erd
1725 \end_inset
1726
1727  number.
1728 \end_layout
1729
1730 \begin_layout Enumerate
1731 Lock the corresponding list.
1732 \end_layout
1733
1734 \begin_layout Enumerate
1735 Re-check the zone: relock if necessary.
1736 \end_layout
1737
1738 \begin_layout Enumerate
1739 If the top entry is -large enough, remove it from the list and return it.
1740 \end_layout
1741
1742 \begin_layout Enumerate
1743 Otherwise, coalesce entries in the list.If there was no entry large enough,
1744  unlock the list and try the next zone.
1745 \end_layout
1746
1747 \begin_layout Enumerate
1748 If no zone satisfies, expand the file.
1749 \end_layout
1750
1751 \begin_layout Standard
1752 This optimizes rapid insert/delete of free list entries by not coalescing
1753  them all the time..
1754  First-fit address ordering ordering seems to be fairly good for keeping
1755  fragmentation low (see 
1756 \begin_inset CommandInset ref
1757 LatexCommand ref
1758 reference "sub:TDB-Becomes-Fragmented"
1759
1760 \end_inset
1761
1762 ).
1763  Note that address ordering does not need a tailer to coalesce, though if
1764  we needed one we could have one cheaply: see 
1765 \begin_inset CommandInset ref
1766 LatexCommand ref
1767 reference "sub:Records-Incur-A"
1768
1769 \end_inset
1770
1771 .
1772  
1773 \end_layout
1774
1775 \begin_layout Standard
1776 I anticipate that the number of entries in each free zone would be small,
1777  but it might be worth using one free entry to hold pointers to the others
1778  for cache efficiency.
1779 \change_inserted 0 1283309850
1780
1781 \end_layout
1782
1783 \begin_layout Standard
1784
1785 \change_inserted 0 1283337216
1786 \begin_inset CommandInset label
1787 LatexCommand label
1788 name "freelist-in-zone"
1789
1790 \end_inset
1791
1792 If we want to avoid locking complexity (enlarging the free lists when we
1793  enlarge the file) we could place the array of free lists at the beginning
1794  of each zone.
1795  This means existing array lists never move, but means that a record cannot
1796  be larger than a zone.
1797  That in turn implies that zones should be variable sized (say, power of
1798  2), which makes the question 
1799 \begin_inset Quotes eld
1800 \end_inset
1801
1802 what zone is this record in?
1803 \begin_inset Quotes erd
1804 \end_inset
1805
1806  much harder (and 
1807 \begin_inset Quotes eld
1808 \end_inset
1809
1810 pick a random zone
1811 \begin_inset Quotes erd
1812 \end_inset
1813
1814 , but that's less common).
1815  It could be done with as few as 4 bits from the record header.
1816 \begin_inset Foot
1817 status open
1818
1819 \begin_layout Plain Layout
1820
1821 \change_inserted 0 1283310945
1822 Using 
1823 \begin_inset Formula $2^{16+N*3}$
1824 \end_inset
1825
1826 means 0 gives a minimal 65536-byte zone, 15 gives the maximal 
1827 \begin_inset Formula $2^{61}$
1828 \end_inset
1829
1830  byte zone.
1831  Zones range in factor of 8 steps.
1832 \change_unchanged
1833
1834 \end_layout
1835
1836 \end_inset
1837
1838
1839 \change_unchanged
1840
1841 \end_layout
1842
1843 \begin_layout Subsection
1844 \begin_inset CommandInset label
1845 LatexCommand label
1846 name "sub:TDB-Becomes-Fragmented"
1847
1848 \end_inset
1849
1850 TDB Becomes Fragmented
1851 \end_layout
1852
1853 \begin_layout Standard
1854 Much of this is a result of allocation strategy
1855 \begin_inset Foot
1856 status collapsed
1857
1858 \begin_layout Plain Layout
1859 The Memory Fragmentation Problem: Solved? Johnstone & Wilson 1995 ftp://ftp.cs.ute
1860 xas.edu/pub/garbage/malloc/ismm98.ps
1861 \end_layout
1862
1863 \end_inset
1864
1865  and deliberate hobbling of coalescing; internal fragmentation (aka overallocati
1866 on) is deliberately set at 25%, and external fragmentation is only cured
1867  by the decision to repack the entire db when a transaction commit needs
1868  to enlarge the file.
1869 \end_layout
1870
1871 \begin_layout Subsubsection
1872 Proposed Solution
1873 \end_layout
1874
1875 \begin_layout Standard
1876 The 25% overhead on allocation works in practice for ldb because indexes
1877  tend to expand by one record at a time.
1878  This internal fragmentation can be resolved by having an 
1879 \begin_inset Quotes eld
1880 \end_inset
1881
1882 expanded
1883 \begin_inset Quotes erd
1884 \end_inset
1885
1886  bit in the header to note entries that have previously expanded, and allocating
1887  more space for them.
1888 \end_layout
1889
1890 \begin_layout Standard
1891 There are is a spectrum of possible solutions for external fragmentation:
1892  one is to use a fragmentation-avoiding allocation strategy such as best-fit
1893  address-order allocator.
1894  The other end of the spectrum would be to use a bump allocator (very fast
1895  and simple) and simply repack the file when we reach the end.
1896 \end_layout
1897
1898 \begin_layout Standard
1899 There are three problems with efficient fragmentation-avoiding allocators:
1900  they are non-trivial, they tend to use a single free list for each size,
1901  and there's no evidence that tdb allocation patterns will match those recorded
1902  for general allocators (though it seems likely).
1903 \end_layout
1904
1905 \begin_layout Standard
1906 Thus we don't spend too much effort on external fragmentation; we will be
1907  no worse than the current code if we need to repack on occasion.
1908  More effort is spent on reducing freelist contention, and reducing overhead.
1909 \end_layout
1910
1911 \begin_layout Subsection
1912 \begin_inset CommandInset label
1913 LatexCommand label
1914 name "sub:Records-Incur-A"
1915
1916 \end_inset
1917
1918 Records Incur A 28-Byte Overhead
1919 \end_layout
1920
1921 \begin_layout Standard
1922 Each TDB record has a header as follows:
1923 \end_layout
1924
1925 \begin_layout LyX-Code
1926 struct tdb_record {
1927 \end_layout
1928
1929 \begin_layout LyX-Code
1930         tdb_off_t next; /* offset of the next record in the list */
1931 \end_layout
1932
1933 \begin_layout LyX-Code
1934         tdb_len_t rec_len; /* total byte length of record */
1935 \end_layout
1936
1937 \begin_layout LyX-Code
1938         tdb_len_t key_len; /* byte length of key */
1939 \end_layout
1940
1941 \begin_layout LyX-Code
1942         tdb_len_t data_len; /* byte length of data */
1943 \end_layout
1944
1945 \begin_layout LyX-Code
1946         uint32_t full_hash; /* the full 32 bit hash of the key */
1947 \end_layout
1948
1949 \begin_layout LyX-Code
1950         uint32_t magic;   /* try to catch errors */
1951 \end_layout
1952
1953 \begin_layout LyX-Code
1954         /* the following union is implied:
1955 \end_layout
1956
1957 \begin_layout LyX-Code
1958                 union {
1959 \end_layout
1960
1961 \begin_layout LyX-Code
1962                         char record[rec_len];
1963 \end_layout
1964
1965 \begin_layout LyX-Code
1966                         struct {
1967 \end_layout
1968
1969 \begin_layout LyX-Code
1970                                 char key[key_len];
1971 \end_layout
1972
1973 \begin_layout LyX-Code
1974                                 char data[data_len];
1975 \end_layout
1976
1977 \begin_layout LyX-Code
1978                         }
1979 \end_layout
1980
1981 \begin_layout LyX-Code
1982                         uint32_t totalsize; (tailer)
1983 \end_layout
1984
1985 \begin_layout LyX-Code
1986                 }
1987 \end_layout
1988
1989 \begin_layout LyX-Code
1990         */
1991 \end_layout
1992
1993 \begin_layout LyX-Code
1994 };
1995 \end_layout
1996
1997 \begin_layout Standard
1998 Naively, this would double to a 56-byte overhead on a 64 bit implementation.
1999 \end_layout
2000
2001 \begin_layout Subsubsection
2002 Proposed Solution
2003 \end_layout
2004
2005 \begin_layout Standard
2006 We can use various techniques to reduce this for an allocated block:
2007 \end_layout
2008
2009 \begin_layout Enumerate
2010 The 'next' pointer is not required, as we are using a flat hash table.
2011 \end_layout
2012
2013 \begin_layout Enumerate
2014 'rec_len' can instead be expressed as an addition to key_len and data_len
2015  (it accounts for wasted or overallocated length in the record).
2016  Since the record length is always a multiple of 8, we can conveniently
2017  fit it in 32 bits (representing up to 35 bits).
2018 \end_layout
2019
2020 \begin_layout Enumerate
2021 'key_len' and 'data_len' can be reduced.
2022  I'm unwilling to restrict 'data_len' to 32 bits, but instead we can combine
2023  the two into one 64-bit field and using a 5 bit value which indicates at
2024  what bit to divide the two.
2025  Keys are unlikely to scale as fast as data, so I'm assuming a maximum key
2026  size of 32 bits.
2027 \end_layout
2028
2029 \begin_layout Enumerate
2030 'full_hash' is used to avoid a memcmp on the 
2031 \begin_inset Quotes eld
2032 \end_inset
2033
2034 miss
2035 \begin_inset Quotes erd
2036 \end_inset
2037
2038  case, but this is diminishing returns after a handful of bits (at 10 bits,
2039  it reduces 99.9% of false memcmp).
2040  As an aside, as the lower bits are already incorporated in the hash table
2041  resolution, the upper bits should be used here.
2042
2043 \change_inserted 0 1283336739
2044  Note that it's not clear that these bits will be a win, given the extra
2045  bits in the hash table itself (see 
2046 \begin_inset CommandInset ref
2047 LatexCommand ref
2048 reference "sub:Hash-Size-Solution"
2049
2050 \end_inset
2051
2052 ).
2053 \change_unchanged
2054
2055 \end_layout
2056
2057 \begin_layout Enumerate
2058 'magic' does not need to be enlarged: it currently reflects one of 5 values
2059  (used, free, dead, recovery, and unused_recovery).
2060  It is useful for quick sanity checking however, and should not be eliminated.
2061 \end_layout
2062
2063 \begin_layout Enumerate
2064 'tailer' is only used to coalesce free blocks (so a block to the right can
2065  find the header to check if this block is free).
2066  This can be replaced by a single 'free' bit in the header of the following
2067  block (and the tailer only exists in free blocks).
2068 \begin_inset Foot
2069 status collapsed
2070
2071 \begin_layout Plain Layout
2072 This technique from Thomas Standish.
2073  Data Structure Techniques.
2074  Addison-Wesley, Reading, Massachusetts, 1980.
2075 \end_layout
2076
2077 \end_inset
2078
2079  The current proposed coalescing algorithm doesn't need this, however.
2080 \end_layout
2081
2082 \begin_layout Standard
2083 This produces a 16 byte used header like this:
2084 \end_layout
2085
2086 \begin_layout LyX-Code
2087 struct tdb_used_record {
2088 \end_layout
2089
2090 \begin_layout LyX-Code
2091         uint32_t magic : 16,
2092 \end_layout
2093
2094 \begin_layout LyX-Code
2095                  prev_is_free: 1,
2096 \end_layout
2097
2098 \begin_layout LyX-Code
2099                  key_data_divide: 5,
2100 \end_layout
2101
2102 \begin_layout LyX-Code
2103                  top_hash: 10;
2104 \end_layout
2105
2106 \begin_layout LyX-Code
2107         uint32_t extra_octets;
2108 \end_layout
2109
2110 \begin_layout LyX-Code
2111         uint64_t key_and_data_len;
2112 \end_layout
2113
2114 \begin_layout LyX-Code
2115 };
2116 \end_layout
2117
2118 \begin_layout Standard
2119 And a free record like this:
2120 \end_layout
2121
2122 \begin_layout LyX-Code
2123 struct tdb_free_record {
2124 \end_layout
2125
2126 \begin_layout LyX-Code
2127         uint32_t free_magic;
2128 \end_layout
2129
2130 \begin_layout LyX-Code
2131         uint64_t total_length;
2132 \change_inserted 0 1283337133
2133
2134 \end_layout
2135
2136 \begin_layout LyX-Code
2137
2138 \change_inserted 0 1283337139
2139         uint64_t prev, next;
2140 \change_unchanged
2141
2142 \end_layout
2143
2144 \begin_layout LyX-Code
2145         ...
2146 \end_layout
2147
2148 \begin_layout LyX-Code
2149         uint64_t tailer;
2150 \end_layout
2151
2152 \begin_layout LyX-Code
2153 };
2154 \end_layout
2155
2156 \begin_layout Standard
2157
2158 \change_inserted 0 1283337235
2159 We might want to take some bits from the used record's top_hash (and the
2160  free record which has 32 bits of padding to spare anyway) if we use variable
2161  sized zones.
2162  See 
2163 \begin_inset CommandInset ref
2164 LatexCommand ref
2165 reference "freelist-in-zone"
2166
2167 \end_inset
2168
2169 .
2170 \change_unchanged
2171
2172 \end_layout
2173
2174 \begin_layout Subsection
2175 Transaction Commit Requires 4 fdatasync
2176 \end_layout
2177
2178 \begin_layout Standard
2179 The current transaction algorithm is:
2180 \end_layout
2181
2182 \begin_layout Enumerate
2183 write_recovery_data();
2184 \end_layout
2185
2186 \begin_layout Enumerate
2187 sync();
2188 \end_layout
2189
2190 \begin_layout Enumerate
2191 write_recovery_header();
2192 \end_layout
2193
2194 \begin_layout Enumerate
2195 sync();
2196 \end_layout
2197
2198 \begin_layout Enumerate
2199 overwrite_with_new_data();
2200 \end_layout
2201
2202 \begin_layout Enumerate
2203 sync();
2204 \end_layout
2205
2206 \begin_layout Enumerate
2207 remove_recovery_header();
2208 \end_layout
2209
2210 \begin_layout Enumerate
2211 sync(); 
2212 \end_layout
2213
2214 \begin_layout Standard
2215 On current ext3, each sync flushes all data to disk, so the next 3 syncs
2216  are relatively expensive.
2217  But this could become a performance bottleneck on other filesystems such
2218  as ext4.
2219 \end_layout
2220
2221 \begin_layout Subsubsection
2222 Proposed Solution
2223 \end_layout
2224
2225 \begin_layout Standard
2226 Neil Brown points out that this is overzealous, and only one sync is needed:
2227 \end_layout
2228
2229 \begin_layout Enumerate
2230 Bundle the recovery data, a transaction counter and a strong checksum of
2231  the new data.
2232 \end_layout
2233
2234 \begin_layout Enumerate
2235 Strong checksum that whole bundle.
2236 \end_layout
2237
2238 \begin_layout Enumerate
2239 Store the bundle in the database.
2240 \end_layout
2241
2242 \begin_layout Enumerate
2243 Overwrite the oldest of the two recovery pointers in the header (identified
2244  using the transaction counter) with the offset of this bundle.
2245 \end_layout
2246
2247 \begin_layout Enumerate
2248 sync.
2249 \end_layout
2250
2251 \begin_layout Enumerate
2252 Write the new data to the file.
2253 \end_layout
2254
2255 \begin_layout Standard
2256 Checking for recovery means identifying the latest bundle with a valid checksum
2257  and using the new data checksum to ensure that it has been applied.
2258  This is more expensive than the current check, but need only be done at
2259  open.
2260  For running databases, a separate header field can be used to indicate
2261  a transaction in progress; we need only check for recovery if this is set.
2262 \end_layout
2263
2264 \begin_layout Subsection
2265 \begin_inset CommandInset label
2266 LatexCommand label
2267 name "sub:TDB-Does-Not"
2268
2269 \end_inset
2270
2271 TDB Does Not Have Snapshot Support
2272 \end_layout
2273
2274 \begin_layout Subsubsection
2275 Proposed Solution
2276 \end_layout
2277
2278 \begin_layout Standard
2279 None.
2280  At some point you say 
2281 \begin_inset Quotes eld
2282 \end_inset
2283
2284 use a real database
2285 \begin_inset Quotes erd
2286 \end_inset
2287
2288 .
2289 \end_layout
2290
2291 \begin_layout Standard
2292 But as a thought experiment, if we implemented transactions to only overwrite
2293  free entries (this is tricky: there must not be a header in each entry
2294  which indicates whether it is free, but use of presence in metadata elsewhere),
2295  and a pointer to the hash table, we could create an entirely new commit
2296  without destroying existing data.
2297  Then it would be easy to implement snapshots in a similar way.
2298 \end_layout
2299
2300 \begin_layout Standard
2301 This would not allow arbitrary changes to the database, such as tdb_repack
2302  does, and would require more space (since we have to preserve the current
2303  and future entries at once).
2304  If we used hash trees rather than one big hash table, we might only have
2305  to rewrite some sections of the hash, too.
2306 \end_layout
2307
2308 \begin_layout Standard
2309 We could then implement snapshots using a similar method, using multiple
2310  different hash tables/free tables.
2311 \end_layout
2312
2313 \begin_layout Subsection
2314 Transactions Cannot Operate in Parallel
2315 \end_layout
2316
2317 \begin_layout Standard
2318 This would be useless for ldb, as it hits the index records with just about
2319  every update.
2320  It would add significant complexity in resolving clashes, and cause the
2321  all transaction callers to write their code to loop in the case where the
2322  transactions spuriously failed.
2323 \end_layout
2324
2325 \begin_layout Subsubsection
2326 Proposed Solution
2327 \end_layout
2328
2329 \begin_layout Standard
2330 We could solve a small part of the problem by providing read-only transactions.
2331  These would allow one write transaction to begin, but it could not commit
2332  until all r/o transactions are done.
2333  This would require a new RO_TRANSACTION_LOCK, which would be upgraded on
2334  commit.
2335 \end_layout
2336
2337 \begin_layout Subsection
2338 Default Hash Function Is Suboptimal
2339 \end_layout
2340
2341 \begin_layout Standard
2342 The Knuth-inspired multiplicative hash used by tdb is fairly slow (especially
2343  if we expand it to 64 bits), and works best when the hash bucket size is
2344  a prime number (which also means a slow modulus).
2345  In addition, it is highly predictable which could potentially lead to a
2346  Denial of Service attack in some TDB uses.
2347 \end_layout
2348
2349 \begin_layout Subsubsection
2350 Proposed Solution
2351 \end_layout
2352
2353 \begin_layout Standard
2354 The Jenkins lookup3 hash
2355 \begin_inset Foot
2356 status open
2357
2358 \begin_layout Plain Layout
2359 http://burtleburtle.net/bob/c/lookup3.c
2360 \end_layout
2361
2362 \end_inset
2363
2364  is a fast and superbly-mixing hash.
2365  It's used by the Linux kernel and almost everything else.
2366  This has the particular properties that it takes an initial seed, and produces
2367  two 32 bit hash numbers, which we can combine into a 64-bit hash.
2368 \end_layout
2369
2370 \begin_layout Standard
2371 The seed should be created at tdb-creation time from some random source,
2372  and placed in the header.
2373  This is far from foolproof, but adds a little bit of protection against
2374  hash bombing.
2375 \end_layout
2376
2377 \begin_layout Subsection
2378 \begin_inset CommandInset label
2379 LatexCommand label
2380 name "Reliable-Traversal-Adds"
2381
2382 \end_inset
2383
2384 Reliable Traversal Adds Complexity
2385 \end_layout
2386
2387 \begin_layout Standard
2388 We lock a record during traversal iteration, and try to grab that lock in
2389  the delete code.
2390  If that grab on delete fails, we simply mark it deleted and continue onwards;
2391  traversal checks for this condition and does the delete when it moves off
2392  the record.
2393 \end_layout
2394
2395 \begin_layout Standard
2396 If traversal terminates, the dead record may be left indefinitely.
2397 \end_layout
2398
2399 \begin_layout Subsubsection
2400 Proposed Solution
2401 \end_layout
2402
2403 \begin_layout Standard
2404 Remove reliability guarantees; see 
2405 \begin_inset CommandInset ref
2406 LatexCommand ref
2407 reference "traverse-Proposed-Solution"
2408
2409 \end_inset
2410
2411 .
2412 \end_layout
2413
2414 \begin_layout Subsection
2415 Fcntl Locking Adds Overhead
2416 \end_layout
2417
2418 \begin_layout Standard
2419 Placing a fcntl lock means a system call, as does removing one.
2420  This is actually one reason why transactions can be faster (everything
2421  is locked once at transaction start).
2422  In the uncontended case, this overhead can theoretically be eliminated.
2423 \end_layout
2424
2425 \begin_layout Subsubsection
2426 Proposed Solution
2427 \end_layout
2428
2429 \begin_layout Standard
2430 None.
2431 \end_layout
2432
2433 \begin_layout Standard
2434 We tried this before with spinlock support, in the early days of TDB, and
2435  it didn't make much difference except in manufactured benchmarks.
2436 \end_layout
2437
2438 \begin_layout Standard
2439 We could use spinlocks (with futex kernel support under Linux), but it means
2440  that we lose automatic cleanup when a process dies with a lock.
2441  There is a method of auto-cleanup under Linux, but it's not supported by
2442  other operating systems.
2443  We could reintroduce a clear-if-first-style lock and sweep for dead futexes
2444  on open, but that wouldn't help the normal case of one concurrent opener
2445  dying.
2446  Increasingly elaborate repair schemes could be considered, but they require
2447  an ABI change (everyone must use them) anyway, so there's no need to do
2448  this at the same time as everything else.
2449 \end_layout
2450
2451 \begin_layout Subsection
2452 Some Transactions Don't Require Durability
2453 \end_layout
2454
2455 \begin_layout Standard
2456 Volker points out that gencache uses a CLEAR_IF_FIRST tdb for normal (fast)
2457  usage, and occasionally empties the results into a transactional TDB.
2458  This kind of usage prioritizes performance over durability: as long as
2459  we are consistent, data can be lost.
2460 \end_layout
2461
2462 \begin_layout Standard
2463 This would be more neatly implemented inside tdb: a 
2464 \begin_inset Quotes eld
2465 \end_inset
2466
2467 soft
2468 \begin_inset Quotes erd
2469 \end_inset
2470
2471  transaction commit (ie.
2472  syncless) which meant that data may be reverted on a crash.
2473 \end_layout
2474
2475 \begin_layout Subsubsection
2476 Proposed Solution
2477 \end_layout
2478
2479 \begin_layout Standard
2480 None.
2481 \end_layout
2482
2483 \begin_layout Standard
2484 Unfortunately any transaction scheme which overwrites old data requires
2485  a sync before that overwrite to avoid the possibility of corruption.
2486 \end_layout
2487
2488 \begin_layout Standard
2489 It seems possible to use a scheme similar to that described in 
2490 \begin_inset CommandInset ref
2491 LatexCommand ref
2492 reference "sub:TDB-Does-Not"
2493
2494 \end_inset
2495
2496 ,where transactions are committed without overwriting existing data, and
2497  an array of top-level pointers were available in the header.
2498  If the transaction is 
2499 \begin_inset Quotes eld
2500 \end_inset
2501
2502 soft
2503 \begin_inset Quotes erd
2504 \end_inset
2505
2506  then we would not need a sync at all: existing processes would pick up
2507  the new hash table and free list and work with that.
2508 \end_layout
2509
2510 \begin_layout Standard
2511 At some later point, a sync would allow recovery of the old data into the
2512  free lists (perhaps when the array of top-level pointers filled).
2513  On crash, tdb_open() would examine the array of top levels, and apply the
2514  transactions until it encountered an invalid checksum.
2515 \end_layout
2516
2517 \end_body
2518 \end_document
2519 @
2520
2521
2522 1.7
2523 log
2524 @Moving hash table does not work.
2525 @
2526 text
2527 @a1436 12
2528 \begin_inset Foot
2529 status collapsed
2530
2531 \begin_layout Plain Layout
2532
2533 \change_inserted 0 1283336450
2534 If we make the hash offsets zone-relative, then this only restricts the
2535  zone size, not the overall database size.
2536 \end_layout
2537
2538 \end_inset
2539
2540 @
2541
2542
2543 1.6
2544 log
2545 @Commit changes
2546 @
2547 text
2548 @d38 1
2549 a38 1
2550 \author "" 
2551 d53 7
2552 a59 1
2553 26-July-2010
2554 d1333 10
2555 d1361 3
2556 a1363 1
2557  There are three details which become important:
2558 d1367 2
2559 d1373 2
2560 d1379 2
2561 d1385 2
2562 d1397 2
2563 d1407 2
2564 d1411 45
2565 d1582 2
2566 d1598 14
2567 d1733 62
2568 d1996 13
2569 d2086 10
2570 d2110 15
2571 a2124 1
2572 \begin_layout LyX-Code
2573 @
2574
2575
2576 1.5
2577 log
2578 @Soft transaction commit
2579 @
2580 text
2581 @d38 1
2582 a38 1
2583 \author "Rusty Russell,,," 
2584 a52 4
2585
2586 \change_deleted 0 1280141199
2587 10-May-2010
2588 \change_inserted 0 1280141202
2589 a53 2
2590 \change_unchanged
2591
2592 a2028 2
2593
2594 \change_inserted 0 1280140902
2595 a2034 2
2596
2597 \change_unchanged
2598 a2212 2
2599 \change_inserted 0 1280140661
2600
2601 a2215 2
2602
2603 \change_inserted 0 1280140703
2604 a2219 2
2605
2606 \change_inserted 0 1280708312
2607 a2226 2
2608
2609 \change_inserted 0 1280708400
2610 a2239 2
2611
2612 \change_inserted 0 1280140836
2613 a2243 2
2614
2615 \change_inserted 0 1280708255
2616 a2247 2
2617
2618 \change_inserted 0 1280708374
2619 a2252 2
2620
2621 \change_inserted 0 1280141181
2622 a2274 2
2623
2624 \change_inserted 0 1280141345
2625 @
2626
2627
2628 1.4
2629 log
2630 @Merge changes
2631 @
2632 text
2633 @d38 1
2634 a38 1
2635 \author "" 
2636 d53 2
2637 d56 4
2638 d2035 10
2639 d2223 84
2640 @
2641
2642
2643 1.3
2644 log
2645 @Transaction and freelist rethink.
2646 @
2647 text
2648 @d38 1
2649 a38 1
2650 \author "Rusty Russell,,," 
2651 d53 1
2652 a53 1
2653 27-April-2010
2654 d662 1
2655 a662 5
2656  behavior of disallowing 
2657 \change_inserted 0 1272940179
2658 nested 
2659 \change_unchanged
2660 transactions should become the default.
2661 a1210 2
2662 \change_inserted 0 1272944650
2663
2664 a1214 2
2665
2666 \change_inserted 0 1272944763
2667 a1218 2
2668 \change_unchanged
2669
2670 a1223 2
2671 \change_unchanged
2672
2673 a1301 2
2674
2675 \change_inserted 0 1273478114
2676 a1310 2
2677 \change_unchanged
2678
2679 d1515 1
2680 a1515 11
2681 The free list 
2682 \change_deleted 0 1273469807
2683 should
2684 \change_inserted 0 1273469810
2685 must
2686 \change_unchanged
2687  be split 
2688 \change_deleted 0 1273469815
2689 into multiple lists 
2690 \change_unchanged
2691 to reduce contention.
2692 a1520 2
2693 \change_inserted 0 1273470006
2694
2695 a1523 2
2696
2697 \change_inserted 0 1273492055
2698 a1539 2
2699
2700 \change_inserted 0 1273483888
2701 a1551 2
2702 \change_unchanged
2703
2704 a1554 8
2705
2706 \change_deleted 0 1272942055
2707 There are various ways to organize these lisys, but because we want to be
2708  able to quickly identify which free list an entry is in, and reduce the
2709  number of locks required for merging, we will use zoning (eg.
2710  each free list covers some fixed fraction of the file).
2711  
2712 \change_inserted 0 1273484187
2713 d1556 1
2714 a1556 7
2715  
2716 \change_deleted 0 1273484194
2717 The algorithm for f
2718 \change_inserted 0 1273484194
2719 F
2720 \change_unchanged
2721 reeing is simple:
2722 d1560 1
2723 a1560 7
2724 Identify the correct 
2725 \change_deleted 0 1273482856
2726 free list
2727 \change_inserted 0 1273482857
2728 zone
2729 \change_unchanged
2730 .
2731 d1564 1
2732 a1564 7
2733 Lock the 
2734 \change_inserted 0 1273482895
2735 corresponding 
2736 \change_unchanged
2737 list
2738 \change_inserted 0 1273482863
2739 .
2740 a1567 2
2741
2742 \change_inserted 0 1273482909
2743 d1573 1
2744 a1573 13
2745
2746 \change_deleted 0 1273482885
2747 , and p
2748 \change_inserted 0 1273482888
2749 P
2750 \change_unchanged
2751 lace the freed entry 
2752 \change_deleted 0 1273492415
2753 at the head
2754 \change_inserted 0 1273492415
2755 in the list for that zone
2756 \change_unchanged
2757 .
2758 d1577 2
2759 a1578 7
2760 Allocation is a little more complicated, as we 
2761 \change_deleted 0 1273483240
2762 merge entries as we walk the list:
2763 \change_inserted 0 1273484250
2764 perform delayed coalescing at this point:
2765 \change_unchanged
2766
2767 d1582 1
2768 a1582 19
2769 Pick a 
2770 \change_deleted 0 1273482955
2771 free list;
2772 \change_inserted 0 1273482957
2773 zone
2774 \change_unchanged
2775  either the 
2776 \change_deleted 0 1273482962
2777 list
2778 \change_inserted 0 1273482962
2779 zone
2780 \change_unchanged
2781  we last freed 
2782 \change_deleted 0 1273482966
2783 o
2784 \change_inserted 0 1273482966
2785 i
2786 \change_unchanged
2787 nto, or based on a 
2788 d1594 1
2789 a1594 9
2790 Lock th
2791 \change_inserted 0 1273482980
2792 e corresponding
2793 \change_deleted 0 1273482973
2794 at
2795 \change_unchanged
2796  list.
2797 \change_inserted 0 1273482982
2798
2799 a1597 2
2800
2801 \change_inserted 0 1273483084
2802 a1598 53
2803 \change_unchanged
2804
2805 \end_layout
2806
2807 \begin_layout Enumerate
2808 If the top entry is 
2809 \change_deleted 0 1273492155
2810 well-sized, 
2811 \change_inserted 0 1273492159
2812 -large enough, 
2813 \change_unchanged
2814 remove it from the list and return it.
2815 \end_layout
2816
2817 \begin_layout Enumerate
2818 Otherwise, 
2819 \change_inserted 0 1273492206
2820 coalesce entries in the list.
2821 \change_deleted 0 1273492200
2822 examine the entry to the right of it in the file.
2823  If it is free:
2824 \end_layout
2825
2826 \begin_deeper
2827 \begin_layout Enumerate
2828
2829 \change_deleted 0 1273492200
2830 If that entry is in a different list, lock that list too.
2831 \end_layout
2832
2833 \begin_layout Enumerate
2834
2835 \change_deleted 0 1273492200
2836 If we had to place a new lock, re-check that the entry is free.
2837 \end_layout
2838
2839 \begin_layout Enumerate
2840
2841 \change_deleted 0 1273492200
2842 Remove that entry from its free list and expand this entry to cover it.
2843 \end_layout
2844
2845 \begin_layout Enumerate
2846
2847 \change_deleted 0 1273485554
2848 Goto step 3.
2849 \end_layout
2850
2851 \end_deeper
2852 \begin_layout Enumerate
2853
2854 \change_inserted 0 1273485311
2855 If there was no entry large enough, unlock the list and try the next zone.
2856 d1602 1
2857 a1602 5
2858
2859 \change_deleted 0 1273483646
2860 Repeat step 3 with each entry in the list.
2861 \change_unchanged
2862
2863 d1606 2
2864 a1607 5
2865
2866 \change_deleted 0 1273483668
2867 Unlock the list and repeat step 2 with the next list.
2868 \change_unchanged
2869
2870 d1611 1
2871 a1611 7
2872 If no 
2873 \change_deleted 0 1273483671
2874 list
2875 \change_inserted 0 1273483671
2876 zone
2877 \change_unchanged
2878  satisfies, expand the file.
2879 d1615 2
2880 a1616 9
2881 This optimizes rapid insert/delete of free list entries
2882 \change_inserted 0 1273485794
2883  by not coalescing them all the time.
2884 \change_deleted 0 1273483685
2885 , and allows us to get rid of the tailer altogether
2886 \change_unchanged
2887 .
2888
2889 \change_inserted 0 1273492299
2890 a1638 39
2891
2892 \change_deleted 0 1273476840
2893 The question of 
2894 \begin_inset Quotes eld
2895 \end_inset
2896
2897 well-sized
2898 \begin_inset Quotes erd
2899 \end_inset
2900
2901  free entries is more difficult: the 25% overhead works in practice for
2902  ldb because indexes tend to expand by one record at a time.
2903  This can be resolved by having an 
2904 \begin_inset Quotes eld
2905 \end_inset
2906
2907 expanded
2908 \begin_inset Quotes erd
2909 \end_inset
2910
2911  bit in the header to note entries that have previously expanded, and allocating
2912  more space for them.
2913  Whether the 
2914 \begin_inset Quotes eld
2915 \end_inset
2916
2917 increasing slack
2918 \begin_inset Quotes erd
2919 \end_inset
2920
2921  algorithm should be implemented or first-fit used is still unknown: we
2922  will determine this once these other ideas are implemented.
2923 \change_inserted 0 1273483750
2924
2925 \end_layout
2926
2927 \begin_layout Standard
2928
2929 \change_inserted 0 1273492450
2930 a1644 2
2931
2932 \change_inserted 0 1273470441
2933 a1654 2
2934
2935 \change_inserted 0 1273476556
2936 a1659 2
2937
2938 \change_inserted 0 1273470423
2939 a1661 2
2940 \change_unchanged
2941
2942 a1672 2
2943
2944 \change_inserted 0 1273476847
2945 a1676 2
2946
2947 \change_inserted 0 1273476886
2948 a1691 2
2949
2950 \change_inserted 0 1273477233
2951 a1699 2
2952
2953 \change_inserted 0 1273477534
2954 a1706 2
2955
2956 \change_inserted 0 1273482700
2957 a1712 2
2958
2959 \change_inserted 0 1273478079
2960 a1722 2
2961
2962 \change_inserted 0 1273477839
2963 a1726 2
2964
2965 \change_inserted 0 1273477925
2966 a1730 2
2967
2968 \change_inserted 0 1273477925
2969 a1734 2
2970
2971 \change_inserted 0 1273477925
2972 a1738 2
2973
2974 \change_inserted 0 1273477925
2975 a1742 2
2976
2977 \change_inserted 0 1273477925
2978 a1746 2
2979
2980 \change_inserted 0 1273477925
2981 a1750 2
2982
2983 \change_inserted 0 1273477925
2984 a1754 2
2985
2986 \change_inserted 0 1273477925
2987 a1758 2
2988
2989 \change_inserted 0 1273477925
2990 a1762 2
2991
2992 \change_inserted 0 1273477925
2993 a1766 2
2994
2995 \change_inserted 0 1273477925
2996 a1770 2
2997
2998 \change_inserted 0 1273477925
2999 a1774 2
3000
3001 \change_inserted 0 1273477925
3002 a1778 2
3003
3004 \change_inserted 0 1273477925
3005 a1782 2
3006
3007 \change_inserted 0 1273477925
3008 a1786 2
3009
3010 \change_inserted 0 1273477925
3011 a1790 2
3012
3013 \change_inserted 0 1273477925
3014 a1794 2
3015
3016 \change_inserted 0 1273477925
3017 a1798 2
3018
3019 \change_inserted 0 1273492522
3020 a1802 2
3021
3022 \change_inserted 0 1273492530
3023 a1806 2
3024
3025 \change_inserted 0 1273492546
3026 a1810 2
3027
3028 \change_inserted 0 1273478239
3029 a1814 2
3030
3031 \change_inserted 0 1273479960
3032 a1821 2
3033
3034 \change_inserted 0 1273480265
3035 a1830 2
3036
3037 \change_inserted 0 1273480354
3038 a1845 2
3039
3040 \change_inserted 0 1273478968
3041 a1851 2
3042
3043 \change_inserted 0 1273492604
3044 a1859 2
3045
3046 \change_inserted 0 1273479572
3047 a1862 2
3048 \change_unchanged
3049
3050 a1870 2
3051
3052 \change_inserted 0 1273480282
3053 a1874 2
3054
3055 \change_inserted 0 1273478931
3056 a1878 2
3057
3058 \change_inserted 0 1273481549
3059 a1882 2
3060
3061 \change_inserted 0 1273481557
3062 a1886 2
3063
3064 \change_inserted 0 1273480307
3065 a1890 2
3066
3067 \change_inserted 0 1273480335
3068 a1894 2
3069
3070 \change_inserted 0 1273479897
3071 a1898 2
3072
3073 \change_inserted 0 1273479653
3074 a1902 2
3075
3076 \change_inserted 0 1273480371
3077 a1906 2
3078
3079 \change_inserted 0 1273480464
3080 a1910 2
3081
3082 \change_inserted 0 1273480399
3083 a1914 2
3084
3085 \change_inserted 0 1273480425
3086 a1918 2
3087
3088 \change_inserted 0 1273480453
3089 a1922 2
3090
3091 \change_inserted 0 1273480455
3092 a1926 2
3093
3094 \change_inserted 0 1273480450
3095 a1930 2
3096
3097 \change_inserted 0 1273480452
3098 a1935 2
3099 \change_inserted 0 1273478830
3100
3101 a1942 5
3102
3103 \change_deleted 0 1273481604
3104 In theory, we could get away with 2: one after we write the new data, and
3105  one to somehow atomically change over to it.
3106 \change_inserted 0 1273481632
3107 a1946 2
3108
3109 \change_inserted 0 1273481724
3110 a1950 2
3111
3112 \change_inserted 0 1273481713
3113 a1954 2
3114
3115 \change_inserted 0 1273481717
3116 a1958 2
3117
3118 \change_inserted 0 1273481730
3119 a1962 2
3120
3121 \change_inserted 0 1273481736
3122 a1966 2
3123
3124 \change_inserted 0 1273481744
3125 a1970 2
3126
3127 \change_inserted 0 1273481748
3128 a1974 2
3129
3130 \change_inserted 0 1273482185
3131 a1978 2
3132
3133 \change_inserted 0 1273482259
3134 a1989 50
3135
3136 \change_deleted 0 1273481848
3137 None.
3138  Trying to rewrite the transaction code is a separate experiment, which
3139  I encourage someone else to do.
3140  At some point you say 
3141 \begin_inset Quotes eld
3142 \end_inset
3143
3144 use a real database
3145 \begin_inset Quotes erd
3146 \end_inset
3147
3148 .
3149 \end_layout
3150
3151 \begin_layout Standard
3152
3153 \change_deleted 0 1273481848
3154 But as a thought experiment:
3155 \change_unchanged
3156
3157 \end_layout
3158
3159 \begin_layout Standard
3160
3161 \change_deleted 0 1273481788
3162 Say there was a pointer in the header which said where the hash table and
3163  free list tables were, and that no blocks were labeled with whether they
3164  were free or not (it had to be derived from what list they were in).
3165  We could create new hash table and free list in some free space, and populate
3166  it as we want the post-committed state to look.
3167  Then we sync, then we switch the offset in the header, then we sync again.
3168 \end_layout
3169
3170 \begin_layout Standard
3171
3172 \change_deleted 0 1273481788
3173 This would not allow arbitrary changes to the database, such as tdb_repack
3174  does, and would require more space (since we have to preserve the current
3175  and future entries at once).
3176  If we used hash trees rather than one big hash table, we might only have
3177  to rewrite some sections of the hash, too.
3178 \change_inserted 0 1273481854
3179
3180 \end_layout
3181
3182 \begin_layout Standard
3183
3184 \change_inserted 0 1273482102
3185 a1993 2
3186
3187 \change_inserted 0 1273482061
3188 a1998 2
3189
3190 \change_inserted 0 1273482063
3191 a2002 2
3192
3193 \change_inserted 0 1273482072
3194 a2006 2
3195
3196 \change_inserted 0 1273482139
3197 a2011 2
3198
3199 \change_inserted 0 1273482364
3200 a2015 2
3201
3202 \change_inserted 0 1273482163
3203 a2019 2
3204
3205 \change_inserted 0 1273482493
3206 a2037 2
3207
3208 \change_inserted 0 1273482536
3209 a2046 2
3210 \change_unchanged
3211
3212 a2049 2
3213
3214 \change_inserted 0 1273482641
3215 a2058 2
3216
3217 \change_inserted 0 1273481827
3218 d2067 2
3219 a2068 11
3220 We could 
3221 \change_inserted 0 1273481829
3222 then 
3223 \change_unchanged
3224 implement snapshots using a similar method
3225 \change_deleted 0 1273481838
3226  to the above, only
3227 \change_inserted 0 1273481840
3228 ,
3229 \change_unchanged
3230  using multiple different hash tables/free tables.
3231 @
3232
3233
3234 1.2
3235 log
3236 @After first feedback (Ronnie & Volker)
3237 @
3238 text
3239 @d1314 13
3240 d1531 11
3241 a1541 1
3242 The free list should be split into multiple lists to reduce contention.
3243 d1547 39
3244 d1596 7
3245 d1604 1
3246 a1604 1
3247 The algorithm for freeing is simple:
3248 d1608 7
3249 a1614 1
3250 Identify the correct free list.
3251 d1618 30
3252 a1647 1
3253 Lock the list, and place the freed entry at the head.
3254 d1651 7
3255 a1657 2
3256 Allocation is a little more complicated, as we merge entries as we walk
3257  the list:
3258 d1661 19
3259 a1679 1
3260 Pick a free list; either the list we last freed onto, or based on a 
3261 d1691 17
3262 a1707 1
3263 Lock that list.
3264 d1711 7
3265 a1717 1
3266 If the top entry is well-sized, remove it from the list and return it.
3267 d1721 5
3268 a1725 1
3269 Otherwise, examine the entry to the right of it in the file.
3270 d1731 2
3271 d1737 2
3272 d1743 2
3273 d1749 2
3274 d1756 8
3275 d1765 2
3276 d1770 2
3277 d1773 2
3278 d1778 7
3279 a1784 1
3280 If no list satisfies, expand the file.
3281 d1788 28
3282 a1815 2
3283 This optimizes rapid insert/delete of free list entries, and allows us to
3284  get rid of the tailer altogether.
3285 d1819 2
3286 d1851 1
3287 a1851 1
3288 \change_inserted 0 1272941474
3289 d1857 303
3290 a2159 18
3291 \change_inserted 0 1272942759
3292 There are various ways to organize these lists, but because we want to be
3293  able to quickly identify which free list an entry is in, and reduce the
3294  number of locks required for merging, we will use zoning (eg.
3295  each of the N free lists in a tdb file of size M covers a fixed fraction
3296  M/N).
3297  Note that this means we need to reshuffle the free lists when we expand
3298  the file; this is probably acceptable when we double the hash table size,
3299  since that is such an expensive operation already.
3300  In the case of increasing the file size, there is an optimization we can
3301  use: if we use M in the formula above as the file size rounded up to the
3302  next power of 2, we only need reshuffle free lists when the file size crosses
3303  a power of 2 boundary, 
3304 \emph on
3305 and 
3306 \emph default
3307 reshuffling the free lists is trivial: we simply merge every consecutive
3308  pair of free lists.
3309 d2164 107
3310 d2276 2
3311 d2280 59
3312 d2346 2
3313 d2363 2
3314 d2366 2
3315 d2371 2
3316 d2382 2
3317 d2389 57
3318 d2458 13
3319 d2474 32
3320 a2505 2
3321 We could implement snapshots using a similar method to the above, only using
3322  multiple different hash tables/free tables.
3323 @
3324
3325
3326 1.1
3327 log
3328 @Initial revision
3329 @
3330 text
3331 @d1 1
3332 a1 1
3333 #LyX 1.6.4 created this file. For more info see http://www.lyx.org/
3334 d36 3
3335 a38 3
3336 \tracking_changes false
3337 \output_changes false
3338 \author "" 
3339 d662 5
3340 a666 1
3341  behavior of disallowing transactions should become the default.
3342 d1215 21
3343 d1527 2
3344 d1533 3
3345 a1535 1
3346  The algorithm for freeing is simple:
3347 d1642 26
3348 @