9 date 2010.09.14.00.33.57; author rusty; state Exp;
14 date 2010.09.09.07.25.12; author rusty; state Exp;
19 date 2010.09.02.02.29.05; author rusty; state Exp;
24 date 2010.09.01.10.58.12; author rusty; state Exp;
29 date 2010.08.02.00.21.43; author rusty; state Exp;
34 date 2010.08.02.00.21.16; author rusty; state Exp;
39 date 2010.05.10.13.09.11; author rusty; state Exp;
44 date 2010.05.10.11.58.37; author rusty; state Exp;
49 date 2010.05.10.05.35.13; author rusty; state Exp;
54 date 2010.05.04.02.29.16; author rusty; state Exp;
66 @Tracing attribute, talloc support.
69 @#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
74 \use_default_options true
79 \font_typewriter default
80 \font_default_family default
87 \paperfontsize default
95 \paperorientation portrait
98 \paragraph_separation indent
100 \quotes_language english
103 \paperpagestyle default
104 \tracking_changes true
106 \author "Rusty Russell,,,"
113 TDB2: A Redesigning The Trivial DataBase
117 Rusty Russell, IBM Corporation
122 \change_deleted 0 1283307542
124 \change_inserted 0 1284423485
130 \begin_layout Abstract
131 The Trivial DataBase on-disk format is 32 bits; with usage cases heading
132 towards the 4G limit, that must change.
133 This required breakage provides an opportunity to revisit TDB's other design
134 decisions and reassess them.
137 \begin_layout Section
141 \begin_layout Standard
142 The Trivial DataBase was originally written by Andrew Tridgell as a simple
143 key/data pair storage system with the same API as dbm, but allowing multiple
144 readers and writers while being small enough (< 1000 lines of C) to include
146 The simple design created in 1999 has proven surprisingly robust and performant
147 , used in Samba versions 3 and 4 as well as numerous other projects.
148 Its useful life was greatly increased by the (backwards-compatible!) addition
149 of transaction support in 2005.
152 \begin_layout Standard
153 The wider variety and greater demands of TDB-using code has lead to some
154 organic growth of the API, as well as some compromises on the implementation.
155 None of these, by themselves, are seen as show-stoppers, but the cumulative
156 effect is to a loss of elegance over the initial, simple TDB implementation.
157 Here is a table of the approximate number of lines of implementation code
158 and number of API functions at the end of each year:
161 \begin_layout Standard
163 <lyxtabular version="3" rows="12" columns="3">
165 <column alignment="center" valignment="top" width="0">
166 <column alignment="center" valignment="top" width="0">
167 <column alignment="center" valignment="top" width="0">
169 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
172 \begin_layout Plain Layout
178 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
181 \begin_layout Plain Layout
187 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
190 \begin_layout Plain Layout
191 Lines of C Code Implementation
198 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
201 \begin_layout Plain Layout
207 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
210 \begin_layout Plain Layout
216 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
219 \begin_layout Plain Layout
227 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
230 \begin_layout Plain Layout
236 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
239 \begin_layout Plain Layout
245 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
248 \begin_layout Plain Layout
256 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
259 \begin_layout Plain Layout
265 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
268 \begin_layout Plain Layout
274 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
277 \begin_layout Plain Layout
285 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
288 \begin_layout Plain Layout
294 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
297 \begin_layout Plain Layout
303 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
306 \begin_layout Plain Layout
314 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
317 \begin_layout Plain Layout
323 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
326 \begin_layout Plain Layout
332 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
335 \begin_layout Plain Layout
343 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
346 \begin_layout Plain Layout
352 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
355 \begin_layout Plain Layout
361 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
364 \begin_layout Plain Layout
372 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
375 \begin_layout Plain Layout
381 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
384 \begin_layout Plain Layout
390 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
393 \begin_layout Plain Layout
401 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
404 \begin_layout Plain Layout
410 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
413 \begin_layout Plain Layout
419 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
422 \begin_layout Plain Layout
430 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
433 \begin_layout Plain Layout
439 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
442 \begin_layout Plain Layout
448 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
451 \begin_layout Plain Layout
459 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
462 \begin_layout Plain Layout
468 <cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
471 \begin_layout Plain Layout
477 <cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
480 \begin_layout Plain Layout
488 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
491 \begin_layout Plain Layout
497 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
500 \begin_layout Plain Layout
506 <cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
509 \begin_layout Plain Layout
523 \begin_layout Standard
524 This review is an attempt to catalog and address all the known issues with
525 TDB and create solutions which address the problems without significantly
526 increasing complexity; all involved are far too aware of the dangers of
527 second system syndrome in rewriting a successful project like this.
530 \begin_layout Section
534 \begin_layout Subsection
535 tdb_open_ex Is Not Expandable
538 \begin_layout Standard
539 The tdb_open() call was expanded to tdb_open_ex(), which added an optional
540 hashing function and an optional logging function argument.
541 Additional arguments to open would require the introduction of a tdb_open_ex2
545 \begin_layout Subsubsection
547 \change_inserted 0 1284422789
549 \begin_inset CommandInset label
560 \begin_layout Standard
561 tdb_open() will take a linked-list of attributes:
564 \begin_layout LyX-Code
568 \begin_layout LyX-Code
569 TDB_ATTRIBUTE_LOG = 0,
572 \begin_layout LyX-Code
573 TDB_ATTRIBUTE_HASH = 1
576 \begin_layout LyX-Code
580 \begin_layout LyX-Code
581 struct tdb_attribute_base {
584 \begin_layout LyX-Code
585 enum tdb_attribute attr;
588 \begin_layout LyX-Code
589 union tdb_attribute *next;
592 \begin_layout LyX-Code
596 \begin_layout LyX-Code
597 struct tdb_attribute_log {
600 \begin_layout LyX-Code
601 struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_LOG */
604 \begin_layout LyX-Code
608 \begin_layout LyX-Code
612 \begin_layout LyX-Code
616 \begin_layout LyX-Code
617 struct tdb_attribute_hash {
620 \begin_layout LyX-Code
621 struct tdb_attribute_base base; /* .attr = TDB_ATTRIBUTE_HASH */
624 \begin_layout LyX-Code
625 tdb_hash_func hash_fn;
628 \begin_layout LyX-Code
632 \begin_layout LyX-Code
636 \begin_layout LyX-Code
637 union tdb_attribute {
640 \begin_layout LyX-Code
641 struct tdb_attribute_base base;
644 \begin_layout LyX-Code
645 struct tdb_attribute_log log;
648 \begin_layout LyX-Code
649 struct tdb_attribute_hash hash;
652 \begin_layout LyX-Code
656 \begin_layout Standard
657 This allows future attributes to be added, even if this expands the size
661 \begin_layout Subsection
662 tdb_traverse Makes Impossible Guarantees
665 \begin_layout Standard
666 tdb_traverse (and tdb_firstkey/tdb_nextkey) predate transactions, and it
667 was thought that it was important to guarantee that all records which exist
668 at the start and end of the traversal would be included, and no record
669 would be included twice.
672 \begin_layout Standard
673 This adds complexity (see
674 \begin_inset CommandInset ref
676 reference "Reliable-Traversal-Adds"
680 ) and does not work anyway for records which are altered (in particular,
681 those which are expanded may be effectively deleted and re-added behind
685 \begin_layout Subsubsection
686 \begin_inset CommandInset label
688 name "traverse-Proposed-Solution"
695 \begin_layout Standard
696 Abandon the guarantee.
697 You will see every record if no changes occur during your traversal, otherwise
698 you will see some subset.
699 You can prevent changes by using a transaction or the locking API.
702 \begin_layout Subsection
703 Nesting of Transactions Is Fraught
706 \begin_layout Standard
707 TDB has alternated between allowing nested transactions and not allowing
709 Various paths in the Samba codebase assume that transactions will nest,
710 and in a sense they can: the operation is only committed to disk when the
711 outer transaction is committed.
712 There are two problems, however:
715 \begin_layout Enumerate
716 Canceling the inner transaction will cause the outer transaction commit
717 to fail, and will not undo any operations since the inner transaction began.
718 This problem is soluble with some additional internal code.
721 \begin_layout Enumerate
722 An inner transaction commit can be cancelled by the outer transaction.
723 This is desirable in the way which Samba's database initialization code
724 uses transactions, but could be a surprise to any users expecting a successful
725 transaction commit to expose changes to others.
728 \begin_layout Standard
729 The current solution is to specify the behavior at tdb_open(), with the
730 default currently that nested transactions are allowed.
731 This flag can also be changed at runtime.
734 \begin_layout Subsubsection
738 \begin_layout Standard
739 Given the usage patterns, it seems that the
740 \begin_inset Quotes eld
744 \begin_inset Quotes erd
747 behavior of disallowing nested transactions should become the default.
748 Additionally, it seems the outer transaction is the only code which knows
749 whether inner transactions should be allowed, so a flag to indicate this
750 could be added to tdb_transaction_start.
751 However, this behavior can be simulated with a wrapper which uses tdb_add_flags
752 () and tdb_remove_flags(), so the API should not be expanded for this relatively
756 \begin_layout Subsection
757 Incorrect Hash Function is Not Detected
760 \begin_layout Standard
761 tdb_open_ex() allows the calling code to specify a different hash function
762 to use, but does not check that all other processes accessing this tdb
763 are using the same hash function.
764 The result is that records are missing from tdb_fetch().
767 \begin_layout Subsubsection
771 \begin_layout Standard
772 The header should contain an example hash result (eg.
773 the hash of 0xdeadbeef), and tdb_open_ex() should check that the given
774 hash function produces the same answer, or fail the tdb_open call.
777 \begin_layout Subsection
778 tdb_set_max_dead/TDB_VOLATILE Expose Implementation
781 \begin_layout Standard
782 In response to scalability issues with the free list (
783 \begin_inset CommandInset ref
785 reference "TDB-Freelist-Is"
789 ) two API workarounds have been incorporated in TDB: tdb_set_max_dead()
790 and the TDB_VOLATILE flag to tdb_open.
791 The latter actually calls the former with an argument of
792 \begin_inset Quotes eld
796 \begin_inset Quotes erd
802 \begin_layout Standard
803 This code allows deleted records to accumulate without putting them in the
805 On delete we iterate through each chain and free them in a batch if there
806 are more than max_dead entries.
807 These are never otherwise recycled except as a side-effect of a tdb_repack.
810 \begin_layout Subsubsection
814 \begin_layout Standard
815 With the scalability problems of the freelist solved, this API can be removed.
816 The TDB_VOLATILE flag may still be useful as a hint that store and delete
817 of records will be at least as common as fetch in order to allow some internal
818 tuning, but initially will become a no-op.
821 \begin_layout Subsection
822 \begin_inset CommandInset label
824 name "TDB-Files-Cannot"
828 TDB Files Cannot Be Opened Multiple Times In The Same Process
831 \begin_layout Standard
832 No process can open the same TDB twice; we check and disallow it.
833 This is an unfortunate side-effect of fcntl locks, which operate on a per-file
834 rather than per-file-descriptor basis, and do not nest.
835 Thus, closing any file descriptor on a file clears all the locks obtained
836 by this process, even if they were placed using a different file descriptor!
839 \begin_layout Standard
840 Note that even if this were solved, deadlock could occur if operations were
841 nested: this is a more manageable programming error in most cases.
844 \begin_layout Subsubsection
848 \begin_layout Standard
849 We could lobby POSIX to fix the perverse rules, or at least lobby Linux
850 to violate them so that the most common implementation does not have this
852 This would be a generally good idea for other fcntl lock users.
855 \begin_layout Standard
856 Samba uses a wrapper which hands out the same tdb_context to multiple callers
857 if this happens, and does simple reference counting.
858 We should do this inside the tdb library, which already emulates lock nesting
859 internally; it would need to recognize when deadlock occurs within a single
861 This would create a new failure mode for tdb operations (while we currently
862 handle locking failures, they are impossible in normal use and a process
863 encountering them can do little but give up).
866 \begin_layout Standard
867 I do not see benefit in an additional tdb_open flag to indicate whether
868 re-opening is allowed, as though there may be some benefit to adding a
869 call to detect when a tdb_context is shared, to allow other to create such
873 \begin_layout Subsection
874 TDB API Is Not POSIX Thread-safe
877 \begin_layout Standard
878 The TDB API uses an error code which can be queried after an operation to
879 determine what went wrong.
880 This programming model does not work with threads, unless specific additional
881 guarantees are given by the implementation.
882 In addition, even otherwise-independent threads cannot open the same TDB
884 \begin_inset CommandInset ref
886 reference "TDB-Files-Cannot"
893 \begin_layout Subsubsection
897 \begin_layout Standard
898 Reachitecting the API to include a tdb_errcode pointer would be a great
899 deal of churn; we are better to guarantee that the tdb_errcode is per-thread
900 so the current programming model can be maintained.
903 \begin_layout Standard
904 This requires dynamic per-thread allocations, which is awkward with POSIX
905 threads (pthread_key_create space is limited and we cannot simply allocate
906 a key for every TDB).
909 \begin_layout Standard
910 Internal locking is required to make sure that fcntl locks do not overlap
911 between threads, and also that the global list of tdbs is maintained.
914 \begin_layout Standard
915 The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe
916 version of the library, and otherwise no overhead will exist.
918 \change_inserted 0 1284016998
919 Alternatively, a hooking mechanism similar to that proposed for
920 \begin_inset CommandInset ref
922 reference "Proposed-Solution-locking-hook"
926 could be used to enable pthread locking at runtime.
931 \begin_layout Subsection
932 *_nonblock Functions And *_mark Functions Expose Implementation
935 \begin_layout Standard
940 \begin_layout Plain Layout
941 Clustered TDB, see http://ctdb.samba.org
946 wishes to operate on TDB in a non-blocking manner.
947 This is currently done as follows:
950 \begin_layout Enumerate
951 Call the _nonblock variant of an API function (eg.
952 tdb_lockall_nonblock).
956 \begin_layout Enumerate
957 Fork a child process, and wait for it to call the normal variant (eg.
961 \begin_layout Enumerate
962 If the child succeeds, call the _mark variant to indicate we already have
967 \begin_layout Enumerate
968 Upon completion, tell the child to release the locks (eg.
972 \begin_layout Enumerate
973 Indicate to tdb that it should consider the locks removed (eg.
977 \begin_layout Standard
978 There are several issues with this approach.
979 Firstly, adding two new variants of each function clutters the API for
980 an obscure use, and so not all functions have three variants.
981 Secondly, it assumes that all paths of the functions ask for the same locks,
982 otherwise the parent process will have to get a lock which the child doesn't
983 have under some circumstances.
984 I don't believe this is currently the case, but it constrains the implementatio
989 \begin_layout Subsubsection
990 \begin_inset CommandInset label
992 name "Proposed-Solution-locking-hook"
999 \begin_layout Standard
1000 Implement a hook for locking methods, so that the caller can control the
1001 calls to create and remove fcntl locks.
1002 In this scenario, ctdbd would operate as follows:
1005 \begin_layout Enumerate
1006 Call the normal API function, eg tdb_lockall().
1009 \begin_layout Enumerate
1010 When the lock callback comes in, check if the child has the lock.
1011 Initially, this is always false.
1013 Otherwise, try to obtain it in non-blocking mode.
1014 If that fails, return EWOULDBLOCK.
1017 \begin_layout Enumerate
1018 Release locks in the unlock callback as normal.
1021 \begin_layout Enumerate
1022 If tdb_lockall() fails, see if we recorded a lock failure; if so, call the
1023 child to repeat the operation.
1026 \begin_layout Enumerate
1027 The child records what locks it obtains, and returns that information to
1031 \begin_layout Enumerate
1032 When the child has succeeded, goto 1.
1035 \begin_layout Standard
1036 This is flexible enough to handle any potential locking scenario, even when
1037 lock requirements change.
1038 It can be optimized so that the parent does not release locks, just tells
1039 the child which locks it doesn't need to obtain.
1042 \begin_layout Standard
1043 It also keeps the complexity out of the API, and in ctdbd where it is needed.
1046 \begin_layout Subsection
1047 tdb_chainlock Functions Expose Implementation
1050 \begin_layout Standard
1051 tdb_chainlock locks some number of records, including the record indicated
1053 This gave atomicity guarantees; no-one can start a transaction, alter,
1054 read or delete that key while the lock is held.
1057 \begin_layout Standard
1058 It also makes the same guarantee for any other key in the chain, which is
1059 an internal implementation detail and potentially a cause for deadlock.
1062 \begin_layout Subsubsection
1066 \begin_layout Standard
1068 It would be nice to have an explicit single entry lock which effected no
1070 Unfortunately, this won't work for an entry which doesn't exist.
1071 Thus while chainlock may be implemented more efficiently for the existing
1072 case, it will still have overlap issues with the non-existing case.
1073 So it is best to keep the current (lack of) guarantee about which records
1074 will be effected to avoid constraining our implementation.
1077 \begin_layout Subsection
1078 Signal Handling is Not Race-Free
1081 \begin_layout Standard
1082 The tdb_setalarm_sigptr() call allows the caller's signal handler to indicate
1083 that the tdb locking code should return with a failure, rather than trying
1084 again when a signal is received (and errno == EAGAIN).
1085 This is usually used to implement timeouts.
1088 \begin_layout Standard
1089 Unfortunately, this does not work in the case where the signal is received
1090 before the tdb code enters the fcntl() call to place the lock: the code
1091 will sleep within the fcntl() code, unaware that the signal wants it to
1093 In the case of long timeouts, this does not happen in practice.
1096 \begin_layout Subsubsection
1100 \begin_layout Standard
1101 The locking hooks proposed in
1102 \begin_inset CommandInset ref
1104 reference "Proposed-Solution-locking-hook"
1108 would allow the user to decide on whether to fail the lock acquisition
1110 This allows the caller to choose their own compromise: they could narrow
1111 the race by checking immediately before the fcntl call.
1115 \begin_layout Plain Layout
1116 It may be possible to make this race-free in some implementations by having
1117 the signal handler alter the struct flock to make it invalid.
1118 This will cause the fcntl() lock call to fail with EINVAL if the signal
1119 occurs before the kernel is entered, otherwise EAGAIN.
1127 \begin_layout Subsection
1128 The API Uses Gratuitous Typedefs, Capitals
1131 \begin_layout Standard
1132 typedefs are useful for providing source compatibility when types can differ
1133 across implementations, or arguably in the case of function pointer definitions
1134 which are hard for humans to parse.
1135 Otherwise it is simply obfuscation and pollutes the namespace.
1138 \begin_layout Standard
1139 Capitalization is usually reserved for compile-time constants and macros.
1142 \begin_layout Description
1143 TDB_CONTEXT There is no reason to use this over 'struct tdb_context'; the
1144 definition isn't visible to the API user anyway.
1147 \begin_layout Description
1148 TDB_DATA There is no reason to use this over struct TDB_DATA; the struct
1149 needs to be understood by the API user.
1152 \begin_layout Description
1154 \begin_inset space ~
1157 TDB_DATA This would normally be called 'struct tdb_data'.
1160 \begin_layout Description
1162 \begin_inset space ~
1165 TDB_ERROR Similarly, this would normally be enum tdb_error.
1168 \begin_layout Subsubsection
1172 \begin_layout Standard
1174 Introducing lower case variants would please pedants like myself, but if
1175 it were done the existing ones should be kept.
1176 There is little point forcing a purely cosmetic change upon tdb users.
1179 \begin_layout Subsection
1180 \begin_inset CommandInset label
1182 name "tdb_log_func-Doesnt-Take"
1186 tdb_log_func Doesn't Take The Private Pointer
1189 \begin_layout Standard
1190 For API compatibility reasons, the logging function needs to call tdb_get_loggin
1191 g_private() to retrieve the pointer registered by the tdb_open_ex for logging.
1194 \begin_layout Subsubsection
1198 \begin_layout Standard
1199 It should simply take an extra argument, since we are prepared to break
1203 \begin_layout Subsection
1204 Various Callback Functions Are Not Typesafe
1207 \begin_layout Standard
1208 The callback functions in tdb_set_logging_function (after
1209 \begin_inset CommandInset ref
1211 reference "tdb_log_func-Doesnt-Take"
1215 is resolved), tdb_parse_record, tdb_traverse, tdb_traverse_read and tdb_check
1216 all take void * and must internally convert it to the argument type they
1220 \begin_layout Standard
1221 If this type changes, the compiler will not produce warnings on the callers,
1222 since it only sees void *.
1225 \begin_layout Subsubsection
1229 \begin_layout Standard
1230 With careful use of macros, we can create callback functions which give
1231 a warning when used on gcc and the types of the callback and its private
1233 Unsupported compilers will not give a warning, which is no worse than now.
1234 In addition, the callbacks become clearer, as they need not use void *
1235 for their parameter.
1238 \begin_layout Standard
1239 See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html
1242 \begin_layout Subsection
1243 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic
1246 \begin_layout Standard
1247 The TDB_CLEAR_IF_FIRST flag to tdb_open indicates that the TDB file should
1248 be cleared if the caller discovers it is the only process with the TDB
1250 However, if any caller does not specify TDB_CLEAR_IF_FIRST it will not
1251 be detected, so will have the TDB erased underneath them (usually resulting
1255 \begin_layout Standard
1256 There is a similar issue on fork(); if the parent exits (or otherwise closes
1257 the tdb) before the child calls tdb_reopen_all() to establish the lock
1258 used to indicate the TDB is opened by someone, a TDB_CLEAR_IF_FIRST opener
1259 at that moment will believe it alone has opened the TDB and will erase
1263 \begin_layout Subsubsection
1267 \begin_layout Standard
1268 Remove TDB_CLEAR_IF_FIRST.
1269 Other workarounds are possible, but see
1270 \begin_inset CommandInset ref
1272 reference "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1277 \change_inserted 0 1284015637
1281 \begin_layout Subsection
1283 \change_inserted 0 1284015716
1284 Extending The Header Is Difficult
1287 \begin_layout Standard
1289 \change_inserted 0 1284015906
1290 We have reserved (zeroed) words in the TDB header, which can be used for
1292 If the future features are compulsory, the version number must be updated
1293 to prevent old code from accessing the database.
1294 But if the future feature is optional, we have no way of telling if older
1295 code is accessing the database or not.
1298 \begin_layout Subsubsection
1300 \change_inserted 0 1284015637
1304 \begin_layout Standard
1306 \change_inserted 0 1284016114
1307 The header should contain a
1308 \begin_inset Quotes eld
1312 \begin_inset Quotes erd
1316 This is divided into two 32-bit parts:
1319 \begin_layout Enumerate
1321 \change_inserted 0 1284016149
1322 The lower part reflects the format variant understood by code accessing
1326 \begin_layout Enumerate
1328 \change_inserted 0 1284016639
1329 The upper part reflects the format variant you must understand to write
1330 to the database (otherwise you can only open for reading).
1333 \begin_layout Standard
1335 \change_inserted 0 1284016821
1336 The latter field can only be written at creation time, the former should
1337 be written under the OPEN_LOCK when opening the database for writing, if
1338 the variant of the code is lower than the current lowest variant.
1341 \begin_layout Standard
1343 \change_inserted 0 1284016803
1344 This should allow backwards-compatible features to be added, and detection
1345 if older code (which doesn't understand the feature) writes to the database.
1346 \change_deleted 0 1284016101
1350 \begin_layout Subsection
1352 \change_inserted 0 1284015634
1353 Record Headers Are Not Expandible
1356 \begin_layout Standard
1358 \change_inserted 0 1284015634
1359 If we later want to add (say) checksums on keys and data, it would require
1360 another format change, which we'd like to avoid.
1363 \begin_layout Subsubsection
1365 \change_inserted 0 1284015634
1369 \begin_layout Standard
1371 \change_inserted 0 1284422552
1372 We often have extra padding at the tail of a record.
1373 If we ensure that the first byte (if any) of this padding is zero, we will
1374 have a way for future changes to detect code which doesn't understand a
1375 new format: the new code would write (say) a 1 at the tail, and thus if
1376 there is no tail or the first byte is 0, we would know the extension is
1377 not present on that record.
1380 \begin_layout Subsection
1382 \change_inserted 0 1284422568
1383 TDB Does Not Use Talloc
1386 \begin_layout Standard
1388 \change_inserted 0 1284422646
1389 Many users of TDB (particularly Samba) use the talloc allocator, and thus
1390 have to wrap TDB in a talloc context to use it conveniently.
1393 \begin_layout Subsubsection
1395 \change_inserted 0 1284422656
1399 \begin_layout Standard
1401 \change_inserted 0 1284423065
1402 The allocation within TDB is not complicated enough to justify the use of
1403 talloc, and I am reluctant to force another (excellent) library on TDB
1405 Nonetheless a compromise is possible.
1407 \begin_inset CommandInset ref
1409 reference "attributes"
1413 ) can be added later to tdb_open() to provide an alternate allocation mechanism,
1414 specifically for talloc but usable by any other allocator (which would
1416 \begin_inset Quotes eld
1420 \begin_inset Quotes erd
1426 \begin_layout Standard
1428 \change_inserted 0 1284423042
1429 This would form a talloc heirarchy as expected, but the caller would still
1430 have to attach a destructor to the tdb context returned from tdb_open to
1432 All TDB_DATA fields would be children of the tdb_context, and the caller
1433 would still have to manage them (using talloc_free() or talloc_steal()).
1438 \begin_layout Section
1439 Performance And Scalability Issues
1442 \begin_layout Subsection
1443 \begin_inset CommandInset label
1445 name "TDB_CLEAR_IF_FIRST-Imposes-Performance"
1449 TDB_CLEAR_IF_FIRST Imposes Performance Penalty
1452 \begin_layout Standard
1453 When TDB_CLEAR_IF_FIRST is specified, a 1-byte read lock is placed at offset
1456 While these locks never conflict in normal tdb usage, they do add substantial
1457 overhead for most fcntl lock implementations when the kernel scans to detect
1458 if a lock conflict exists.
1459 This is often a single linked list, making the time to acquire and release
1460 a fcntl lock O(N) where N is the number of processes with the TDB open,
1461 not the number actually doing work.
1464 \begin_layout Standard
1465 In a Samba server it is common to have huge numbers of clients sitting idle,
1466 and thus they have weaned themselves off the TDB_CLEAR_IF_FIRST flag.
1470 \begin_layout Plain Layout
1471 There is a flag to tdb_reopen_all() which is used for this optimization:
1472 if the parent process will outlive the child, the child does not need the
1474 This is a workaround for this very performance issue.
1482 \begin_layout Subsubsection
1486 \begin_layout Standard
1488 It was a neat idea, but even trivial servers tend to know when they are
1489 initializing for the first time and can simply unlink the old tdb at that
1493 \begin_layout Subsection
1494 TDB Files Have a 4G Limit
1497 \begin_layout Standard
1498 This seems to be becoming an issue (so much for
1499 \begin_inset Quotes eld
1503 \begin_inset Quotes erd
1506 !), particularly for ldb.
1509 \begin_layout Subsubsection
1513 \begin_layout Standard
1514 A new, incompatible TDB format which uses 64 bit offsets internally rather
1516 For simplicity of endian conversion (which TDB does on the fly if required),
1517 all values will be 64 bit on disk.
1518 In practice, some upper bits may be used for other purposes, but at least
1519 56 bits will be available for file offsets.
1522 \begin_layout Standard
1523 tdb_open() will automatically detect the old version, and even create them
1524 if TDB_VERSION6 is specified to tdb_open.
1527 \begin_layout Standard
1528 32 bit processes will still be able to access TDBs larger than 4G (assuming
1529 that their off_t allows them to seek to 64 bits), they will gracefully
1530 fall back as they fail to mmap.
1531 This can happen already with large TDBs.
1534 \begin_layout Standard
1535 Old versions of tdb will fail to open the new TDB files (since 28 August
1536 2009, commit 398d0c29290: prior to that any unrecognized file format would
1537 be erased and initialized as a fresh tdb!)
1540 \begin_layout Subsection
1541 TDB Records Have a 4G Limit
1544 \begin_layout Standard
1545 This has not been a reported problem, and the API uses size_t which can
1546 be 64 bit on 64 bit platforms.
1547 However, other limits may have made such an issue moot.
1550 \begin_layout Subsubsection
1554 \begin_layout Standard
1555 Record sizes will be 64 bit, with an error returned on 32 bit platforms
1556 which try to access such records (the current implementation would return
1557 TDB_ERR_OOM in a similar case).
1558 It seems unlikely that 32 bit keys will be a limitation, so the implementation
1559 may not support this (see
1560 \begin_inset CommandInset ref
1562 reference "sub:Records-Incur-A"
1569 \begin_layout Subsection
1570 Hash Size Is Determined At TDB Creation Time
1573 \begin_layout Standard
1574 TDB contains a number of hash chains in the header; the number is specified
1575 at creation time, and defaults to 131.
1576 This is such a bottleneck on large databases (as each hash chain gets quite
1577 long), that LDB uses 10,000 for this hash.
1578 In general it is impossible to know what the 'right' answer is at database
1582 \begin_layout Subsubsection
1584 \change_inserted 0 1283336713
1585 \begin_inset CommandInset label
1587 name "sub:Hash-Size-Solution"
1596 \begin_layout Standard
1597 After comprehensive performance testing on various scalable hash variants
1601 \begin_layout Plain Layout
1602 http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoying
1603 because I was previously convinced that an expanding tree of hashes would
1604 be very close to optimal.
1609 , it became clear that it is hard to beat a straight linear hash table which
1610 doubles in size when it reaches saturation.
1612 \change_deleted 0 1283307675
1613 There are three details which become important:
1616 \begin_layout Enumerate
1618 \change_deleted 0 1283307675
1619 On encountering a full bucket, we use the next bucket.
1622 \begin_layout Enumerate
1624 \change_deleted 0 1283307675
1625 Extra hash bits are stored with the offset, to reduce comparisons.
1628 \begin_layout Enumerate
1630 \change_deleted 0 1283307675
1631 A marker entry is used on deleting an entry.
1634 \begin_layout Standard
1636 \change_deleted 0 1283307675
1637 The doubling of the table must be done under a transaction; we will not
1638 reduce it on deletion, so it will be an unusual case.
1639 It will either be placed at the head (other entries will be moved out the
1640 way so we can expand).
1641 We could have a pointer in the header to the current hashtable location,
1642 but that pointer would have to be read frequently to check for hashtable
1646 \begin_layout Standard
1648 \change_deleted 0 1283307675
1649 The locking for this is slightly more complex than the chained case; we
1650 currently have one lock per bucket, and that means we would need to expand
1651 the lock if we overflow to the next bucket.
1652 The frequency of such collisions will effect our locking heuristics: we
1653 can always lock more buckets than we need.
1656 \begin_layout Standard
1658 \change_deleted 0 1283307675
1659 One possible optimization is to only re-check the hash size on an insert
1662 \change_inserted 0 1283307770
1663 Unfortunately, altering the hash table introduces serious locking complications
1664 : the entire hash table needs to be locked to enlarge the hash table, and
1665 others might be holding locks.
1666 Particularly insidious are insertions done under tdb_chainlock.
1669 \begin_layout Standard
1671 \change_inserted 0 1283336187
1672 Thus an expanding layered hash will be used: an array of hash groups, with
1673 each hash group exploding into pointers to lower hash groups once it fills,
1674 turning into a hash tree.
1675 This has implications for locking: we must lock the entire group in case
1676 we need to expand it, yet we don't know how deep the tree is at that point.
1679 \begin_layout Standard
1681 \change_inserted 0 1283336586
1682 Note that bits from the hash table entries should be stolen to hold more
1683 hash bits to reduce the penalty of collisions.
1684 We can use the otherwise-unused lower 3 bits.
1685 If we limit the size of the database to 64 exabytes, we can use the top
1686 8 bits of the hash entry as well.
1687 These 11 bits would reduce false positives down to 1 in 2000 which is more
1688 than we need: we can use one of the bits to indicate that the extra hash
1690 This means we can choose not to re-hash all entries when we expand a hash
1691 group; simply use the next bits we need and mark them invalid.
1696 \begin_layout Subsection
1697 \begin_inset CommandInset label
1699 name "TDB-Freelist-Is"
1703 TDB Freelist Is Highly Contended
1706 \begin_layout Standard
1707 TDB uses a single linked list for the free list.
1708 Allocation occurs as follows, using heuristics which have evolved over
1712 \begin_layout Enumerate
1713 Get the free list lock for this whole operation.
1716 \begin_layout Enumerate
1717 Multiply length by 1.25, so we always over-allocate by 25%.
1720 \begin_layout Enumerate
1721 Set the slack multiplier to 1.
1724 \begin_layout Enumerate
1725 Examine the current freelist entry: if it is > length but < the current
1726 best case, remember it as the best case.
1729 \begin_layout Enumerate
1730 Multiply the slack multiplier by 1.05.
1733 \begin_layout Enumerate
1734 If our best fit so far is less than length * slack multiplier, return it.
1735 The slack will be turned into a new free record if it's large enough.
1738 \begin_layout Enumerate
1739 Otherwise, go onto the next freelist entry.
1742 \begin_layout Standard
1743 Deleting a record occurs as follows:
1746 \begin_layout Enumerate
1747 Lock the hash chain for this whole operation.
1750 \begin_layout Enumerate
1751 Walk the chain to find the record, keeping the prev pointer offset.
1754 \begin_layout Enumerate
1755 If max_dead is non-zero:
1759 \begin_layout Enumerate
1760 Walk the hash chain again and count the dead records.
1763 \begin_layout Enumerate
1764 If it's more than max_dead, bulk free all the dead ones (similar to steps
1765 4 and below, but the lock is only obtained once).
1768 \begin_layout Enumerate
1769 Simply mark this record as dead and return.
1774 \begin_layout Enumerate
1775 Get the free list lock for the remainder of this operation.
1778 \begin_layout Enumerate
1779 \begin_inset CommandInset label
1781 name "right-merging"
1785 Examine the following block to see if it is free; if so, enlarge the current
1786 block and remove that block from the free list.
1787 This was disabled, as removal from the free list was O(entries-in-free-list).
1790 \begin_layout Enumerate
1791 Examine the preceeding block to see if it is free: for this reason, each
1792 block has a 32-bit tailer which indicates its length.
1793 If it is free, expand it to cover our new block and return.
1796 \begin_layout Enumerate
1797 Otherwise, prepend ourselves to the free list.
1800 \begin_layout Standard
1801 Disabling right-merging (step
1802 \begin_inset CommandInset ref
1804 reference "right-merging"
1808 ) causes fragmentation; the other heuristics proved insufficient to address
1809 this, so the final answer to this was that when we expand the TDB file
1810 inside a transaction commit, we repack the entire tdb.
1813 \begin_layout Standard
1814 The single list lock limits our allocation rate; due to the other issues
1815 this is not currently seen as a bottleneck.
1818 \begin_layout Subsubsection
1820 \change_deleted 0 1283336858
1824 \begin_layout Standard
1825 The first step is to remove all the current heuristics, as they obviously
1826 interact, then examine them once the lock contention is addressed.
1829 \begin_layout Standard
1830 The free list must be split to reduce contention.
1831 Assuming perfect free merging, we can at most have 1 free list entry for
1833 This implies that the number of free lists is related to the size of the
1834 hash table, but as it is rare to walk a large number of free list entries
1835 we can use far fewer, say 1/32 of the number of hash buckets.
1836 \change_inserted 0 1283336910
1840 \begin_layout Standard
1842 \change_inserted 0 1283337052
1843 It seems tempting to try to reuse the hash implementation which we use for
1844 records here, but we have two ways of searching for free entries: for allocatio
1845 n we search by size (and possibly zone) which produces too many clashes
1846 for our hash table to handle well, and for coalescing we search by address.
1847 Thus an array of doubly-linked free lists seems preferable.
1852 \begin_layout Standard
1853 There are various benefits in using per-size free lists (see
1854 \begin_inset CommandInset ref
1856 reference "sub:TDB-Becomes-Fragmented"
1860 ) but it's not clear this would reduce contention in the common case where
1861 all processes are allocating/freeing the same size.
1862 Thus we almost certainly need to divide in other ways: the most obvious
1863 is to divide the file into zones, and using a free list (or set of free
1865 This approximates address ordering.
1868 \begin_layout Standard
1869 Note that this means we need to split the free lists when we expand the
1870 file; this is probably acceptable when we double the hash table size, since
1871 that is such an expensive operation already.
1872 In the case of increasing the file size, there is an optimization we can
1873 use: if we use M in the formula above as the file size rounded up to the
1874 next power of 2, we only need reshuffle free lists when the file size crosses
1875 a power of 2 boundary,
1879 reshuffling the free lists is trivial: we simply merge every consecutive
1883 \begin_layout Standard
1884 The basic algorithm is as follows.
1888 \begin_layout Enumerate
1889 Identify the correct zone.
1892 \begin_layout Enumerate
1893 Lock the corresponding list.
1896 \begin_layout Enumerate
1897 Re-check the zone (we didn't have a lock, sizes could have changed): relock
1901 \begin_layout Enumerate
1902 Place the freed entry in the list for that zone.
1905 \begin_layout Standard
1906 Allocation is a little more complicated, as we perform delayed coalescing
1910 \begin_layout Enumerate
1911 Pick a zone either the zone we last freed into, or based on a
1912 \begin_inset Quotes eld
1916 \begin_inset Quotes erd
1922 \begin_layout Enumerate
1923 Lock the corresponding list.
1926 \begin_layout Enumerate
1927 Re-check the zone: relock if necessary.
1930 \begin_layout Enumerate
1931 If the top entry is -large enough, remove it from the list and return it.
1934 \begin_layout Enumerate
1935 Otherwise, coalesce entries in the list.If there was no entry large enough,
1936 unlock the list and try the next zone.
1939 \begin_layout Enumerate
1940 If no zone satisfies, expand the file.
1943 \begin_layout Standard
1944 This optimizes rapid insert/delete of free list entries by not coalescing
1946 First-fit address ordering ordering seems to be fairly good for keeping
1947 fragmentation low (see
1948 \begin_inset CommandInset ref
1950 reference "sub:TDB-Becomes-Fragmented"
1955 Note that address ordering does not need a tailer to coalesce, though if
1956 we needed one we could have one cheaply: see
1957 \begin_inset CommandInset ref
1959 reference "sub:Records-Incur-A"
1967 \begin_layout Standard
1968 I anticipate that the number of entries in each free zone would be small,
1969 but it might be worth using one free entry to hold pointers to the others
1970 for cache efficiency.
1971 \change_inserted 0 1283309850
1975 \begin_layout Standard
1977 \change_inserted 0 1283337216
1978 \begin_inset CommandInset label
1980 name "freelist-in-zone"
1984 If we want to avoid locking complexity (enlarging the free lists when we
1985 enlarge the file) we could place the array of free lists at the beginning
1987 This means existing array lists never move, but means that a record cannot
1988 be larger than a zone.
1989 That in turn implies that zones should be variable sized (say, power of
1990 2), which makes the question
1991 \begin_inset Quotes eld
1994 what zone is this record in?
1995 \begin_inset Quotes erd
1999 \begin_inset Quotes eld
2003 \begin_inset Quotes erd
2006 , but that's less common).
2007 It could be done with as few as 4 bits from the record header.
2011 \begin_layout Plain Layout
2013 \change_inserted 0 1284424151
2015 \begin_inset Formula $2^{16+N*3}$
2018 means 0 gives a minimal 65536-byte zone, 15 gives the maximal
2019 \begin_inset Formula $2^{61}$
2023 Zones range in factor of 8 steps.
2024 Given the zone size for the zone the current record is in, we can determine
2025 the start of the zone.
2037 \begin_layout Subsection
2038 \begin_inset CommandInset label
2040 name "sub:TDB-Becomes-Fragmented"
2044 TDB Becomes Fragmented
2047 \begin_layout Standard
2048 Much of this is a result of allocation strategy
2052 \begin_layout Plain Layout
2053 The Memory Fragmentation Problem: Solved? Johnstone & Wilson 1995 ftp://ftp.cs.ute
2054 xas.edu/pub/garbage/malloc/ismm98.ps
2059 and deliberate hobbling of coalescing; internal fragmentation (aka overallocati
2060 on) is deliberately set at 25%, and external fragmentation is only cured
2061 by the decision to repack the entire db when a transaction commit needs
2062 to enlarge the file.
2065 \begin_layout Subsubsection
2069 \begin_layout Standard
2070 The 25% overhead on allocation works in practice for ldb because indexes
2071 tend to expand by one record at a time.
2072 This internal fragmentation can be resolved by having an
2073 \begin_inset Quotes eld
2077 \begin_inset Quotes erd
2080 bit in the header to note entries that have previously expanded, and allocating
2081 more space for them.
2084 \begin_layout Standard
2085 There are is a spectrum of possible solutions for external fragmentation:
2086 one is to use a fragmentation-avoiding allocation strategy such as best-fit
2087 address-order allocator.
2088 The other end of the spectrum would be to use a bump allocator (very fast
2089 and simple) and simply repack the file when we reach the end.
2092 \begin_layout Standard
2093 There are three problems with efficient fragmentation-avoiding allocators:
2094 they are non-trivial, they tend to use a single free list for each size,
2095 and there's no evidence that tdb allocation patterns will match those recorded
2096 for general allocators (though it seems likely).
2099 \begin_layout Standard
2100 Thus we don't spend too much effort on external fragmentation; we will be
2101 no worse than the current code if we need to repack on occasion.
2102 More effort is spent on reducing freelist contention, and reducing overhead.
2105 \begin_layout Subsection
2106 \begin_inset CommandInset label
2108 name "sub:Records-Incur-A"
2112 Records Incur A 28-Byte Overhead
2115 \begin_layout Standard
2116 Each TDB record has a header as follows:
2119 \begin_layout LyX-Code
2123 \begin_layout LyX-Code
2124 tdb_off_t next; /* offset of the next record in the list */
2127 \begin_layout LyX-Code
2128 tdb_len_t rec_len; /* total byte length of record */
2131 \begin_layout LyX-Code
2132 tdb_len_t key_len; /* byte length of key */
2135 \begin_layout LyX-Code
2136 tdb_len_t data_len; /* byte length of data */
2139 \begin_layout LyX-Code
2140 uint32_t full_hash; /* the full 32 bit hash of the key */
2143 \begin_layout LyX-Code
2144 uint32_t magic; /* try to catch errors */
2147 \begin_layout LyX-Code
2148 /* the following union is implied:
2151 \begin_layout LyX-Code
2155 \begin_layout LyX-Code
2156 char record[rec_len];
2159 \begin_layout LyX-Code
2163 \begin_layout LyX-Code
2167 \begin_layout LyX-Code
2168 char data[data_len];
2171 \begin_layout LyX-Code
2175 \begin_layout LyX-Code
2176 uint32_t totalsize; (tailer)
2179 \begin_layout LyX-Code
2183 \begin_layout LyX-Code
2187 \begin_layout LyX-Code
2191 \begin_layout Standard
2192 Naively, this would double to a 56-byte overhead on a 64 bit implementation.
2195 \begin_layout Subsubsection
2199 \begin_layout Standard
2200 We can use various techniques to reduce this for an allocated block:
2203 \begin_layout Enumerate
2204 The 'next' pointer is not required, as we are using a flat hash table.
2207 \begin_layout Enumerate
2208 'rec_len' can instead be expressed as an addition to key_len and data_len
2209 (it accounts for wasted or overallocated length in the record).
2210 Since the record length is always a multiple of 8, we can conveniently
2211 fit it in 32 bits (representing up to 35 bits).
2214 \begin_layout Enumerate
2215 'key_len' and 'data_len' can be reduced.
2216 I'm unwilling to restrict 'data_len' to 32 bits, but instead we can combine
2217 the two into one 64-bit field and using a 5 bit value which indicates at
2218 what bit to divide the two.
2219 Keys are unlikely to scale as fast as data, so I'm assuming a maximum key
2223 \begin_layout Enumerate
2224 'full_hash' is used to avoid a memcmp on the
2225 \begin_inset Quotes eld
2229 \begin_inset Quotes erd
2232 case, but this is diminishing returns after a handful of bits (at 10 bits,
2233 it reduces 99.9% of false memcmp).
2234 As an aside, as the lower bits are already incorporated in the hash table
2235 resolution, the upper bits should be used here.
2237 \change_inserted 0 1283336739
2238 Note that it's not clear that these bits will be a win, given the extra
2239 bits in the hash table itself (see
2240 \begin_inset CommandInset ref
2242 reference "sub:Hash-Size-Solution"
2251 \begin_layout Enumerate
2252 'magic' does not need to be enlarged: it currently reflects one of 5 values
2253 (used, free, dead, recovery, and unused_recovery).
2254 It is useful for quick sanity checking however, and should not be eliminated.
2257 \begin_layout Enumerate
2258 'tailer' is only used to coalesce free blocks (so a block to the right can
2259 find the header to check if this block is free).
2260 This can be replaced by a single 'free' bit in the header of the following
2261 block (and the tailer only exists in free blocks).
2265 \begin_layout Plain Layout
2266 This technique from Thomas Standish.
2267 Data Structure Techniques.
2268 Addison-Wesley, Reading, Massachusetts, 1980.
2273 The current proposed coalescing algorithm doesn't need this, however.
2276 \begin_layout Standard
2277 This produces a 16 byte used header like this:
2280 \begin_layout LyX-Code
2281 struct tdb_used_record {
2284 \begin_layout LyX-Code
2285 uint32_t magic : 16,
2288 \begin_layout LyX-Code
2292 \begin_layout LyX-Code
2296 \begin_layout LyX-Code
2300 \begin_layout LyX-Code
2301 uint32_t extra_octets;
2304 \begin_layout LyX-Code
2305 uint64_t key_and_data_len;
2308 \begin_layout LyX-Code
2312 \begin_layout Standard
2313 And a free record like this:
2316 \begin_layout LyX-Code
2317 struct tdb_free_record {
2320 \begin_layout LyX-Code
2321 uint32_t free_magic;
2324 \begin_layout LyX-Code
2325 uint64_t total_length;
2326 \change_inserted 0 1283337133
2330 \begin_layout LyX-Code
2332 \change_inserted 0 1283337139
2333 uint64_t prev, next;
2338 \begin_layout LyX-Code
2342 \begin_layout LyX-Code
2346 \begin_layout LyX-Code
2350 \begin_layout Standard
2352 \change_inserted 0 1283337235
2353 We might want to take some bits from the used record's top_hash (and the
2354 free record which has 32 bits of padding to spare anyway) if we use variable
2357 \begin_inset CommandInset ref
2359 reference "freelist-in-zone"
2368 \begin_layout Subsection
2369 Transaction Commit Requires 4 fdatasync
2372 \begin_layout Standard
2373 The current transaction algorithm is:
2376 \begin_layout Enumerate
2377 write_recovery_data();
2380 \begin_layout Enumerate
2384 \begin_layout Enumerate
2385 write_recovery_header();
2388 \begin_layout Enumerate
2392 \begin_layout Enumerate
2393 overwrite_with_new_data();
2396 \begin_layout Enumerate
2400 \begin_layout Enumerate
2401 remove_recovery_header();
2404 \begin_layout Enumerate
2408 \begin_layout Standard
2409 On current ext3, each sync flushes all data to disk, so the next 3 syncs
2410 are relatively expensive.
2411 But this could become a performance bottleneck on other filesystems such
2415 \begin_layout Subsubsection
2419 \begin_layout Standard
2420 Neil Brown points out that this is overzealous, and only one sync is needed:
2423 \begin_layout Enumerate
2424 Bundle the recovery data, a transaction counter and a strong checksum of
2428 \begin_layout Enumerate
2429 Strong checksum that whole bundle.
2432 \begin_layout Enumerate
2433 Store the bundle in the database.
2436 \begin_layout Enumerate
2437 Overwrite the oldest of the two recovery pointers in the header (identified
2438 using the transaction counter) with the offset of this bundle.
2441 \begin_layout Enumerate
2445 \begin_layout Enumerate
2446 Write the new data to the file.
2449 \begin_layout Standard
2450 Checking for recovery means identifying the latest bundle with a valid checksum
2451 and using the new data checksum to ensure that it has been applied.
2452 This is more expensive than the current check, but need only be done at
2454 For running databases, a separate header field can be used to indicate
2455 a transaction in progress; we need only check for recovery if this is set.
2458 \begin_layout Subsection
2459 \begin_inset CommandInset label
2461 name "sub:TDB-Does-Not"
2465 TDB Does Not Have Snapshot Support
2468 \begin_layout Subsubsection
2470 \change_deleted 0 1284423472
2474 \begin_layout Standard
2476 At some point you say
2477 \begin_inset Quotes eld
2481 \begin_inset Quotes erd
2485 \change_inserted 0 1284423891
2487 \change_deleted 0 1284423891
2490 \change_inserted 0 1284423901
2492 \begin_inset CommandInset ref
2494 reference "replay-attribute"
2503 \begin_layout Standard
2504 But as a thought experiment, if we implemented transactions to only overwrite
2505 free entries (this is tricky: there must not be a header in each entry
2506 which indicates whether it is free, but use of presence in metadata elsewhere),
2507 and a pointer to the hash table, we could create an entirely new commit
2508 without destroying existing data.
2509 Then it would be easy to implement snapshots in a similar way.
2512 \begin_layout Standard
2513 This would not allow arbitrary changes to the database, such as tdb_repack
2514 does, and would require more space (since we have to preserve the current
2515 and future entries at once).
2516 If we used hash trees rather than one big hash table, we might only have
2517 to rewrite some sections of the hash, too.
2520 \begin_layout Standard
2521 We could then implement snapshots using a similar method, using multiple
2522 different hash tables/free tables.
2523 \change_inserted 0 1284423495
2527 \begin_layout Subsection
2528 Transactions Cannot Operate in Parallel
2531 \begin_layout Standard
2532 This would be useless for ldb, as it hits the index records with just about
2534 It would add significant complexity in resolving clashes, and cause the
2535 all transaction callers to write their code to loop in the case where the
2536 transactions spuriously failed.
2539 \begin_layout Subsubsection
2543 \begin_layout Standard
2545 \change_inserted 0 1284424201
2547 \begin_inset CommandInset ref
2549 reference "replay-attribute"
2556 We could solve a small part of the problem by providing read-only transactions.
2557 These would allow one write transaction to begin, but it could not commit
2558 until all r/o transactions are done.
2559 This would require a new RO_TRANSACTION_LOCK, which would be upgraded on
2563 \begin_layout Subsection
2564 Default Hash Function Is Suboptimal
2567 \begin_layout Standard
2568 The Knuth-inspired multiplicative hash used by tdb is fairly slow (especially
2569 if we expand it to 64 bits), and works best when the hash bucket size is
2570 a prime number (which also means a slow modulus).
2571 In addition, it is highly predictable which could potentially lead to a
2572 Denial of Service attack in some TDB uses.
2575 \begin_layout Subsubsection
2579 \begin_layout Standard
2580 The Jenkins lookup3 hash
2584 \begin_layout Plain Layout
2585 http://burtleburtle.net/bob/c/lookup3.c
2590 is a fast and superbly-mixing hash.
2591 It's used by the Linux kernel and almost everything else.
2592 This has the particular properties that it takes an initial seed, and produces
2593 two 32 bit hash numbers, which we can combine into a 64-bit hash.
2596 \begin_layout Standard
2597 The seed should be created at tdb-creation time from some random source,
2598 and placed in the header.
2599 This is far from foolproof, but adds a little bit of protection against
2603 \begin_layout Subsection
2604 \begin_inset CommandInset label
2606 name "Reliable-Traversal-Adds"
2610 Reliable Traversal Adds Complexity
2613 \begin_layout Standard
2614 We lock a record during traversal iteration, and try to grab that lock in
2616 If that grab on delete fails, we simply mark it deleted and continue onwards;
2617 traversal checks for this condition and does the delete when it moves off
2621 \begin_layout Standard
2622 If traversal terminates, the dead record may be left indefinitely.
2625 \begin_layout Subsubsection
2629 \begin_layout Standard
2630 Remove reliability guarantees; see
2631 \begin_inset CommandInset ref
2633 reference "traverse-Proposed-Solution"
2640 \begin_layout Subsection
2641 Fcntl Locking Adds Overhead
2644 \begin_layout Standard
2645 Placing a fcntl lock means a system call, as does removing one.
2646 This is actually one reason why transactions can be faster (everything
2647 is locked once at transaction start).
2648 In the uncontended case, this overhead can theoretically be eliminated.
2651 \begin_layout Subsubsection
2655 \begin_layout Standard
2659 \begin_layout Standard
2660 We tried this before with spinlock support, in the early days of TDB, and
2661 it didn't make much difference except in manufactured benchmarks.
2664 \begin_layout Standard
2665 We could use spinlocks (with futex kernel support under Linux), but it means
2666 that we lose automatic cleanup when a process dies with a lock.
2667 There is a method of auto-cleanup under Linux, but it's not supported by
2668 other operating systems.
2669 We could reintroduce a clear-if-first-style lock and sweep for dead futexes
2670 on open, but that wouldn't help the normal case of one concurrent opener
2672 Increasingly elaborate repair schemes could be considered, but they require
2673 an ABI change (everyone must use them) anyway, so there's no need to do
2674 this at the same time as everything else.
2677 \begin_layout Subsection
2678 Some Transactions Don't Require Durability
2681 \begin_layout Standard
2682 Volker points out that gencache uses a CLEAR_IF_FIRST tdb for normal (fast)
2683 usage, and occasionally empties the results into a transactional TDB.
2684 This kind of usage prioritizes performance over durability: as long as
2685 we are consistent, data can be lost.
2688 \begin_layout Standard
2689 This would be more neatly implemented inside tdb: a
2690 \begin_inset Quotes eld
2694 \begin_inset Quotes erd
2697 transaction commit (ie.
2698 syncless) which meant that data may be reverted on a crash.
2701 \begin_layout Subsubsection
2705 \begin_layout Standard
2709 \begin_layout Standard
2710 Unfortunately any transaction scheme which overwrites old data requires
2711 a sync before that overwrite to avoid the possibility of corruption.
2714 \begin_layout Standard
2715 It seems possible to use a scheme similar to that described in
2716 \begin_inset CommandInset ref
2718 reference "sub:TDB-Does-Not"
2722 ,where transactions are committed without overwriting existing data, and
2723 an array of top-level pointers were available in the header.
2724 If the transaction is
2725 \begin_inset Quotes eld
2729 \begin_inset Quotes erd
2732 then we would not need a sync at all: existing processes would pick up
2733 the new hash table and free list and work with that.
2736 \begin_layout Standard
2737 At some later point, a sync would allow recovery of the old data into the
2738 free lists (perhaps when the array of top-level pointers filled).
2739 On crash, tdb_open() would examine the array of top levels, and apply the
2740 transactions until it encountered an invalid checksum.
2741 \change_inserted 0 1284423555
2745 \begin_layout Subsection
2747 \change_inserted 0 1284423617
2748 Tracing Is Fragile, Replay Is External
2751 \begin_layout Standard
2753 \change_inserted 0 1284423719
2754 The current TDB has compile-time-enabled tracing code, but it often breaks
2755 as it is not enabled by default.
2756 In a similar way, the ctdb code has an external wrapper which does replay
2757 tracing so it can coordinate cluster-wide transactions.
2760 \begin_layout Subsubsection
2762 \change_inserted 0 1284423864
2764 \begin_inset CommandInset label
2766 name "replay-attribute"
2773 \begin_layout Standard
2775 \change_inserted 0 1284423850
2776 Tridge points out that an attribute can be later added to tdb_open (see
2778 \begin_inset CommandInset ref
2780 reference "attributes"
2784 ) to provide replay/trace hooks, which could become the basis for this and
2785 future parallel transactions and snapshot support.
2797 @Extension mechanism.
2802 \change_inserted 0 1284016854
2807 \change_inserted 0 1284016847
2811 \change_inserted 0 1283310945
2824 @Remove bogus footnote
2829 \change_inserted 0 1283307544
2838 @Moving hash table does not work.
2845 \begin_layout Plain Layout
2847 \change_inserted 0 1283336450
2848 If we make the hash offsets zone-relative, then this only restricts the
2849 zone size, not the overall database size.
2871 There are three details which become important:
2886 \begin_layout LyX-Code
2892 @Soft transaction commit
2897 \author "Rusty Russell,,,"
2900 \change_deleted 0 1280141199
2902 \change_inserted 0 1280141202
2908 \change_inserted 0 1280140902
2913 \change_inserted 0 1280140661
2917 \change_inserted 0 1280140703
2920 \change_inserted 0 1280708312
2923 \change_inserted 0 1280708400
2926 \change_inserted 0 1280140836
2929 \change_inserted 0 1280708255
2932 \change_inserted 0 1280708374
2935 \change_inserted 0 1280141181
2938 \change_inserted 0 1280141345
2959 @Transaction and freelist rethink.
2964 \author "Rusty Russell,,,"
2970 behavior of disallowing
2971 \change_inserted 0 1272940179
2974 transactions should become the default.
2976 \change_inserted 0 1272944650
2980 \change_inserted 0 1272944763
2989 \change_inserted 0 1273478114
2996 \change_deleted 0 1273469807
2998 \change_inserted 0 1273469810
3002 \change_deleted 0 1273469815
3005 to reduce contention.
3007 \change_inserted 0 1273470006
3011 \change_inserted 0 1273492055
3014 \change_inserted 0 1273483888
3020 \change_deleted 0 1272942055
3021 There are various ways to organize these lisys, but because we want to be
3022 able to quickly identify which free list an entry is in, and reduce the
3023 number of locks required for merging, we will use zoning (eg.
3024 each free list covers some fixed fraction of the file).
3026 \change_inserted 0 1273484187
3030 \change_deleted 0 1273484194
3032 \change_inserted 0 1273484194
3038 Identify the correct
3039 \change_deleted 0 1273482856
3041 \change_inserted 0 1273482857
3048 \change_inserted 0 1273482895
3052 \change_inserted 0 1273482863
3056 \change_inserted 0 1273482909
3060 \change_deleted 0 1273482885
3062 \change_inserted 0 1273482888
3065 lace the freed entry
3066 \change_deleted 0 1273492415
3068 \change_inserted 0 1273492415
3069 in the list for that zone
3074 Allocation is a little more complicated, as we
3075 \change_deleted 0 1273483240
3076 merge entries as we walk the list:
3077 \change_inserted 0 1273484250
3078 perform delayed coalescing at this point:
3084 \change_deleted 0 1273482955
3086 \change_inserted 0 1273482957
3090 \change_deleted 0 1273482962
3092 \change_inserted 0 1273482962
3096 \change_deleted 0 1273482966
3098 \change_inserted 0 1273482966
3105 \change_inserted 0 1273482980
3107 \change_deleted 0 1273482973
3111 \change_inserted 0 1273482982
3115 \change_inserted 0 1273483084
3121 \begin_layout Enumerate
3123 \change_deleted 0 1273492155
3125 \change_inserted 0 1273492159
3128 remove it from the list and return it.
3131 \begin_layout Enumerate
3133 \change_inserted 0 1273492206
3134 coalesce entries in the list.
3135 \change_deleted 0 1273492200
3136 examine the entry to the right of it in the file.
3141 \begin_layout Enumerate
3143 \change_deleted 0 1273492200
3144 If that entry is in a different list, lock that list too.
3147 \begin_layout Enumerate
3149 \change_deleted 0 1273492200
3150 If we had to place a new lock, re-check that the entry is free.
3153 \begin_layout Enumerate
3155 \change_deleted 0 1273492200
3156 Remove that entry from its free list and expand this entry to cover it.
3159 \begin_layout Enumerate
3161 \change_deleted 0 1273485554
3166 \begin_layout Enumerate
3168 \change_inserted 0 1273485311
3169 If there was no entry large enough, unlock the list and try the next zone.
3173 \change_deleted 0 1273483646
3174 Repeat step 3 with each entry in the list.
3180 \change_deleted 0 1273483668
3181 Unlock the list and repeat step 2 with the next list.
3187 \change_deleted 0 1273483671
3189 \change_inserted 0 1273483671
3192 satisfies, expand the file.
3195 This optimizes rapid insert/delete of free list entries
3196 \change_inserted 0 1273485794
3197 by not coalescing them all the time.
3198 \change_deleted 0 1273483685
3199 , and allows us to get rid of the tailer altogether
3203 \change_inserted 0 1273492299
3206 \change_deleted 0 1273476840
3208 \begin_inset Quotes eld
3212 \begin_inset Quotes erd
3215 free entries is more difficult: the 25% overhead works in practice for
3216 ldb because indexes tend to expand by one record at a time.
3217 This can be resolved by having an
3218 \begin_inset Quotes eld
3222 \begin_inset Quotes erd
3225 bit in the header to note entries that have previously expanded, and allocating
3226 more space for them.
3228 \begin_inset Quotes eld
3232 \begin_inset Quotes erd
3235 algorithm should be implemented or first-fit used is still unknown: we
3236 will determine this once these other ideas are implemented.
3237 \change_inserted 0 1273483750
3241 \begin_layout Standard
3243 \change_inserted 0 1273492450
3246 \change_inserted 0 1273470441
3249 \change_inserted 0 1273476556
3252 \change_inserted 0 1273470423
3258 \change_inserted 0 1273476847
3261 \change_inserted 0 1273476886
3264 \change_inserted 0 1273477233
3267 \change_inserted 0 1273477534
3270 \change_inserted 0 1273482700
3273 \change_inserted 0 1273478079
3276 \change_inserted 0 1273477839
3279 \change_inserted 0 1273477925
3282 \change_inserted 0 1273477925
3285 \change_inserted 0 1273477925
3288 \change_inserted 0 1273477925
3291 \change_inserted 0 1273477925
3294 \change_inserted 0 1273477925
3297 \change_inserted 0 1273477925
3300 \change_inserted 0 1273477925
3303 \change_inserted 0 1273477925
3306 \change_inserted 0 1273477925
3309 \change_inserted 0 1273477925
3312 \change_inserted 0 1273477925
3315 \change_inserted 0 1273477925
3318 \change_inserted 0 1273477925
3321 \change_inserted 0 1273477925
3324 \change_inserted 0 1273477925
3327 \change_inserted 0 1273477925
3330 \change_inserted 0 1273477925
3333 \change_inserted 0 1273492522
3336 \change_inserted 0 1273492530
3339 \change_inserted 0 1273492546
3342 \change_inserted 0 1273478239
3345 \change_inserted 0 1273479960
3348 \change_inserted 0 1273480265
3351 \change_inserted 0 1273480354
3354 \change_inserted 0 1273478968
3357 \change_inserted 0 1273492604
3360 \change_inserted 0 1273479572
3366 \change_inserted 0 1273480282
3369 \change_inserted 0 1273478931
3372 \change_inserted 0 1273481549
3375 \change_inserted 0 1273481557
3378 \change_inserted 0 1273480307
3381 \change_inserted 0 1273480335
3384 \change_inserted 0 1273479897
3387 \change_inserted 0 1273479653
3390 \change_inserted 0 1273480371
3393 \change_inserted 0 1273480464
3396 \change_inserted 0 1273480399
3399 \change_inserted 0 1273480425
3402 \change_inserted 0 1273480453
3405 \change_inserted 0 1273480455
3408 \change_inserted 0 1273480450
3411 \change_inserted 0 1273480452
3413 \change_inserted 0 1273478830
3417 \change_deleted 0 1273481604
3418 In theory, we could get away with 2: one after we write the new data, and
3419 one to somehow atomically change over to it.
3420 \change_inserted 0 1273481632
3423 \change_inserted 0 1273481724
3426 \change_inserted 0 1273481713
3429 \change_inserted 0 1273481717
3432 \change_inserted 0 1273481730
3435 \change_inserted 0 1273481736
3438 \change_inserted 0 1273481744
3441 \change_inserted 0 1273481748
3444 \change_inserted 0 1273482185
3447 \change_inserted 0 1273482259
3450 \change_deleted 0 1273481848
3452 Trying to rewrite the transaction code is a separate experiment, which
3453 I encourage someone else to do.
3454 At some point you say
3455 \begin_inset Quotes eld
3459 \begin_inset Quotes erd
3465 \begin_layout Standard
3467 \change_deleted 0 1273481848
3468 But as a thought experiment:
3473 \begin_layout Standard
3475 \change_deleted 0 1273481788
3476 Say there was a pointer in the header which said where the hash table and
3477 free list tables were, and that no blocks were labeled with whether they
3478 were free or not (it had to be derived from what list they were in).
3479 We could create new hash table and free list in some free space, and populate
3480 it as we want the post-committed state to look.
3481 Then we sync, then we switch the offset in the header, then we sync again.
3484 \begin_layout Standard
3486 \change_deleted 0 1273481788
3487 This would not allow arbitrary changes to the database, such as tdb_repack
3488 does, and would require more space (since we have to preserve the current
3489 and future entries at once).
3490 If we used hash trees rather than one big hash table, we might only have
3491 to rewrite some sections of the hash, too.
3492 \change_inserted 0 1273481854
3496 \begin_layout Standard
3498 \change_inserted 0 1273482102
3501 \change_inserted 0 1273482061
3504 \change_inserted 0 1273482063
3507 \change_inserted 0 1273482072
3510 \change_inserted 0 1273482139
3513 \change_inserted 0 1273482364
3516 \change_inserted 0 1273482163
3519 \change_inserted 0 1273482493
3522 \change_inserted 0 1273482536
3528 \change_inserted 0 1273482641
3531 \change_inserted 0 1273481827
3535 \change_inserted 0 1273481829
3538 implement snapshots using a similar method
3539 \change_deleted 0 1273481838
3541 \change_inserted 0 1273481840
3544 using multiple different hash tables/free tables.
3550 @After first feedback (Ronnie & Volker)
3556 The free list should be split into multiple lists to reduce contention.
3561 The algorithm for freeing is simple:
3564 Identify the correct free list.
3567 Lock the list, and place the freed entry at the head.
3570 Allocation is a little more complicated, as we merge entries as we walk
3574 Pick a free list; either the list we last freed onto, or based on a
3580 If the top entry is well-sized, remove it from the list and return it.
3583 Otherwise, examine the entry to the right of it in the file.
3594 If no list satisfies, expand the file.
3597 This optimizes rapid insert/delete of free list entries, and allows us to
3598 get rid of the tailer altogether.
3602 \change_inserted 0 1272941474
3605 \change_inserted 0 1272942759
3606 There are various ways to organize these lists, but because we want to be
3607 able to quickly identify which free list an entry is in, and reduce the
3608 number of locks required for merging, we will use zoning (eg.
3609 each of the N free lists in a tdb file of size M covers a fixed fraction
3611 Note that this means we need to reshuffle the free lists when we expand
3612 the file; this is probably acceptable when we double the hash table size,
3613 since that is such an expensive operation already.
3614 In the case of increasing the file size, there is an optimization we can
3615 use: if we use M in the formula above as the file size rounded up to the
3616 next power of 2, we only need reshuffle free lists when the file size crosses
3617 a power of 2 boundary,
3621 reshuffling the free lists is trivial: we simply merge every consecutive
3635 We could implement snapshots using a similar method to the above, only using
3636 multiple different hash tables/free tables.
3647 #LyX 1.6.4 created this file. For more info see http://www.lyx.org/
3650 \tracking_changes false
3651 \output_changes false
3655 behavior of disallowing transactions should become the default.
3660 The algorithm for freeing is simple:
projects / ccan / blob