From: Rusty Russell Date: Wed, 1 Dec 2010 13:16:26 +0000 (+1030) Subject: tdb2: update documentation X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=a42bba8ec446284256a7c9146ba3525404de474c tdb2: update documentation Specifically the linked free tables, and reflect on the status of each point of the design document. --- diff --git a/ccan/tdb2/doc/design.lyx b/ccan/tdb2/doc/design.lyx index ca17f8fe..bb499482 100644 --- a/ccan/tdb2/doc/design.lyx +++ b/ccan/tdb2/doc/design.lyx @@ -1,4 +1,4 @@ -#LyX 1.6.5 created this file. For more info see http://www.lyx.org/ +#LyX 1.6.7 created this file. For more info see http://www.lyx.org/ \lyxformat 345 \begin_document \begin_header @@ -50,13 +50,7 @@ Rusty Russell, IBM Corporation \end_layout \begin_layout Date - -\change_deleted 0 1283307542 -26-July -\change_inserted 0 1284423485 -14-September -\change_unchanged --2010 +1-December-2010 \end_layout \begin_layout Abstract @@ -476,8 +470,6 @@ The tdb_open() call was expanded to tdb_open_ex(), which added an optional \begin_layout Subsubsection Proposed Solution -\change_inserted 0 1284422789 - \begin_inset CommandInset label LatexCommand label name "attributes" @@ -485,8 +477,6 @@ name "attributes" \end_inset -\change_unchanged - \end_layout \begin_layout Standard @@ -590,6 +580,14 @@ This allows future attributes to be added, even if this expands the size of the union. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection tdb_traverse Makes Impossible Guarantees \end_layout @@ -631,6 +629,16 @@ Abandon the guarantee. You can prevent changes by using a transaction or the locking API. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. + Delete-during-traverse will still delete every record, too (assuming no + other changes). +\end_layout + \begin_layout Subsection Nesting of Transactions Is Fraught \end_layout @@ -685,6 +693,14 @@ least-surprise -obscure case. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete; nesting flag is still defined as per tdb1. +\end_layout + \begin_layout Subsection Incorrect Hash Function is Not Detected \end_layout @@ -706,6 +722,14 @@ The header should contain an example hash result (eg. hash function produces the same answer, or fail the tdb_open call. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection tdb_set_max_dead/TDB_VOLATILE Expose Implementation \end_layout @@ -750,6 +774,16 @@ With the scalability problems of the freelist solved, this API can be removed. tuning, but initially will become a no-op. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. + TDB_VOLATILE still defined, but implementation should fail on unknown flags + to be future-proof. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -802,6 +836,14 @@ I do not see benefit in an additional tdb_open flag to indicate whether an API. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection TDB API Is Not POSIX Thread-safe \end_layout @@ -846,8 +888,6 @@ Internal locking is required to make sure that fcntl locks do not overlap \begin_layout Standard The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe version of the library, and otherwise no overhead will exist. - -\change_inserted 0 1284016998 Alternatively, a hooking mechanism similar to that proposed for \begin_inset CommandInset ref LatexCommand ref @@ -856,8 +896,14 @@ reference "Proposed-Solution-locking-hook" \end_inset could be used to enable pthread locking at runtime. -\change_unchanged +\end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. \end_layout \begin_layout Subsection @@ -975,6 +1021,14 @@ This is flexible enough to handle any potential locking scenario, even when It also keeps the complexity out of the API, and in ctdbd where it is needed. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection tdb_chainlock Functions Expose Implementation \end_layout @@ -1056,6 +1110,14 @@ It may be possible to make this race-free in some implementations by having \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection The API Uses Gratuitous Typedefs, Capitals \end_layout @@ -1132,6 +1194,14 @@ It should simply take an extra argument, since we are prepared to break the API/ABI. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Various Callback Functions Are Not Typesafe \end_layout @@ -1171,6 +1241,14 @@ With careful use of macros, we can create callback functions which give See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic \end_layout @@ -1206,19 +1284,21 @@ reference "TDB_CLEAR_IF_FIRST-Imposes-Performance" \end_inset . -\change_inserted 0 1284015637 +\end_layout +\begin_layout Subsubsection +Status \end_layout -\begin_layout Subsection +\begin_layout Standard +Incomplete, TDB_CLEAR_IF_FIRST still defined, but not implemented. +\end_layout -\change_inserted 0 1284015716 +\begin_layout Subsection Extending The Header Is Difficult \end_layout \begin_layout Standard - -\change_inserted 0 1284015906 We have reserved (zeroed) words in the TDB header, which can be used for future features. If the future features are compulsory, the version number must be updated @@ -1228,14 +1308,10 @@ We have reserved (zeroed) words in the TDB header, which can be used for \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284015637 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284016114 The header should contain a \begin_inset Quotes eld \end_inset @@ -1249,58 +1325,48 @@ format variant \end_layout \begin_layout Enumerate - -\change_inserted 0 1284016149 The lower part reflects the format variant understood by code accessing the database. \end_layout \begin_layout Enumerate - -\change_inserted 0 1284016639 The upper part reflects the format variant you must understand to write to the database (otherwise you can only open for reading). \end_layout \begin_layout Standard - -\change_inserted 0 1284016821 The latter field can only be written at creation time, the former should be written under the OPEN_LOCK when opening the database for writing, if the variant of the code is lower than the current lowest variant. \end_layout \begin_layout Standard - -\change_inserted 0 1284016803 This should allow backwards-compatible features to be added, and detection if older code (which doesn't understand the feature) writes to the database. -\change_deleted 0 1284016101 +\end_layout +\begin_layout Subsubsection +Status \end_layout -\begin_layout Subsection +\begin_layout Standard +Incomplete. +\end_layout -\change_inserted 0 1284015634 +\begin_layout Subsection Record Headers Are Not Expandible \end_layout \begin_layout Standard - -\change_inserted 0 1284015634 If we later want to add (say) checksums on keys and data, it would require another format change, which we'd like to avoid. \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284015634 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284422552 We often have extra padding at the tail of a record. If we ensure that the first byte (if any) of this padding is zero, we will have a way for future changes to detect code which doesn't understand a @@ -1309,28 +1375,28 @@ We often have extra padding at the tail of a record. not present on that record. \end_layout -\begin_layout Subsection +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout -\change_inserted 0 1284422568 +\begin_layout Subsection TDB Does Not Use Talloc \end_layout \begin_layout Standard - -\change_inserted 0 1284422646 Many users of TDB (particularly Samba) use the talloc allocator, and thus have to wrap TDB in a talloc context to use it conveniently. \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284422656 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284423065 The allocation within TDB is not complicated enough to justify the use of talloc, and I am reluctant to force another (excellent) library on TDB users. @@ -1356,15 +1422,19 @@ context \end_layout \begin_layout Standard - -\change_inserted 0 1284423042 This would form a talloc heirarchy as expected, but the caller would still have to attach a destructor to the tdb context returned from tdb_open to close it. All TDB_DATA fields would be children of the tdb_context, and the caller would still have to manage them (using talloc_free() or talloc_steal()). -\change_unchanged +\end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. \end_layout \begin_layout Section @@ -1422,6 +1492,14 @@ Remove the flag. point. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete; TDB_CLEAR_IF_FIRST still defined, but does nothing. +\end_layout + \begin_layout Subsection TDB Files Have a 4G Limit \end_layout @@ -1469,6 +1547,14 @@ Old versions of tdb will fail to open the new TDB files (since 28 August be erased and initialized as a fresh tdb!) \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection TDB Records Have a 4G Limit \end_layout @@ -1498,6 +1584,14 @@ reference "sub:Records-Incur-A" ). \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Hash Size Is Determined At TDB Creation Time \end_layout @@ -1512,16 +1606,12 @@ TDB contains a number of hash chains in the header; the number is specified \end_layout \begin_layout Subsubsection - -\change_inserted 0 1283336713 \begin_inset CommandInset label LatexCommand label name "sub:Hash-Size-Solution" \end_inset - -\change_unchanged Proposed Solution \end_layout @@ -1540,58 +1630,6 @@ http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoyin , it became clear that it is hard to beat a straight linear hash table which doubles in size when it reaches saturation. - -\change_deleted 0 1283307675 -There are three details which become important: -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -On encountering a full bucket, we use the next bucket. -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -Extra hash bits are stored with the offset, to reduce comparisons. -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -A marker entry is used on deleting an entry. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -The doubling of the table must be done under a transaction; we will not - reduce it on deletion, so it will be an unusual case. - It will either be placed at the head (other entries will be moved out the - way so we can expand). - We could have a pointer in the header to the current hashtable location, - but that pointer would have to be read frequently to check for hashtable - moves. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -The locking for this is slightly more complex than the chained case; we - currently have one lock per bucket, and that means we would need to expand - the lock if we overflow to the next bucket. - The frequency of such collisions will effect our locking heuristics: we - can always lock more buckets than we need. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -One possible optimization is to only re-check the hash size on an insert - or a lookup miss. - -\change_inserted 0 1283307770 Unfortunately, altering the hash table introduces serious locking complications : the entire hash table needs to be locked to enlarge the hash table, and others might be holding locks. @@ -1599,8 +1637,6 @@ One possible optimization is to only re-check the hash size on an insert \end_layout \begin_layout Standard - -\change_inserted 0 1283336187 Thus an expanding layered hash will be used: an array of hash groups, with each hash group exploding into pointers to lower hash groups once it fills, turning into a hash tree. @@ -1609,8 +1645,6 @@ Thus an expanding layered hash will be used: an array of hash groups, with \end_layout \begin_layout Standard - -\change_inserted 0 1283336586 Note that bits from the hash table entries should be stolen to hold more hash bits to reduce the penalty of collisions. We can use the otherwise-unused lower 3 bits. @@ -1621,8 +1655,14 @@ Note that bits from the hash table entries should be stolen to hold more bits are valid. This means we can choose not to re-hash all entries when we expand a hash group; simply use the next bits we need and mark them invalid. -\change_unchanged +\end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. \end_layout \begin_layout Subsection @@ -1749,8 +1789,6 @@ The single list lock limits our allocation rate; due to the other issues \begin_layout Subsubsection Proposed Solution -\change_deleted 0 1283336858 - \end_layout \begin_layout Standard @@ -1765,20 +1803,14 @@ The free list must be split to reduce contention. This implies that the number of free lists is related to the size of the hash table, but as it is rare to walk a large number of free list entries we can use far fewer, say 1/32 of the number of hash buckets. -\change_inserted 0 1283336910 - \end_layout \begin_layout Standard - -\change_inserted 0 1283337052 It seems tempting to try to reuse the hash implementation which we use for records here, but we have two ways of searching for free entries: for allocatio n we search by size (and possibly zone) which produces too many clashes for our hash table to handle well, and for coalescing we search by address. Thus an array of doubly-linked free lists seems preferable. -\change_unchanged - \end_layout \begin_layout Standard @@ -1792,24 +1824,28 @@ reference "sub:TDB-Becomes-Fragmented" ) but it's not clear this would reduce contention in the common case where all processes are allocating/freeing the same size. Thus we almost certainly need to divide in other ways: the most obvious - is to divide the file into zones, and using a free list (or set of free + is to divide the file into zones, and using a free list (or table of free lists) for each. This approximates address ordering. \end_layout \begin_layout Standard -Note that this means we need to split the free lists when we expand the - file; this is probably acceptable when we double the hash table size, since - that is such an expensive operation already. - In the case of increasing the file size, there is an optimization we can - use: if we use M in the formula above as the file size rounded up to the - next power of 2, we only need reshuffle free lists when the file size crosses - a power of 2 boundary, -\emph on -and -\emph default -reshuffling the free lists is trivial: we simply merge every consecutive - pair of free lists. +Unfortunately it is difficult to know what heuristics should be used to + determine zone sizes, and our transaction code relies on being able to + create a +\begin_inset Quotes eld +\end_inset + +recovery area +\begin_inset Quotes erd +\end_inset + + by simply appending to the file (difficult if it would need to create a + new zone header). + Thus we use a linked-list of free tables; currently we only ever create + one, but if there is more than one we choose one at random to use. + In future we may use heuristics to add new free tables on contention. + We only expand the file when all free tables are exhausted. \end_layout \begin_layout Standard @@ -1818,7 +1854,7 @@ The basic algorithm is as follows. \end_layout \begin_layout Enumerate -Identify the correct zone. +Identify the correct free list. \end_layout \begin_layout Enumerate @@ -1826,12 +1862,12 @@ Lock the corresponding list. \end_layout \begin_layout Enumerate -Re-check the zone (we didn't have a lock, sizes could have changed): relock +Re-check the list (we didn't have a lock, sizes could have changed): relock if necessary. \end_layout \begin_layout Enumerate -Place the freed entry in the list for that zone. +Place the freed entry in the list. \end_layout \begin_layout Standard @@ -1840,15 +1876,7 @@ Allocation is a little more complicated, as we perform delayed coalescing \end_layout \begin_layout Enumerate -Pick a zone either the zone we last freed into, or based on a -\begin_inset Quotes eld -\end_inset - -random -\begin_inset Quotes erd -\end_inset - - number. +Pick a free table; usually the previous one. \end_layout \begin_layout Enumerate @@ -1856,16 +1884,16 @@ Lock the corresponding list. \end_layout \begin_layout Enumerate -Re-check the zone: relock if necessary. +If the top entry is -large enough, remove it from the list and return it. \end_layout \begin_layout Enumerate -If the top entry is -large enough, remove it from the list and return it. +Otherwise, coalesce entries in the list.If there was no entry large enough, + unlock the list and try the next largest list \end_layout \begin_layout Enumerate -Otherwise, coalesce entries in the list.If there was no entry large enough, - unlock the list and try the next zone. +If no list has an entry which meets our needs, try the next free table. \end_layout \begin_layout Enumerate @@ -1897,73 +1925,8 @@ reference "sub:Records-Incur-A" \end_layout \begin_layout Standard -I anticipate that the number of entries in each free zone would be small, - but it might be worth using one free entry to hold pointers to the others - for cache efficiency. -\change_inserted 0 1283309850 - -\end_layout - -\begin_layout Standard - -\change_inserted 0 1283337216 -\begin_inset CommandInset label -LatexCommand label -name "freelist-in-zone" - -\end_inset - -If we want to avoid locking complexity (enlarging the free lists when we - enlarge the file) we could place the array of free lists at the beginning - of each zone. - This means existing array lists never move, but means that a record cannot - be larger than a zone. - That in turn implies that zones should be variable sized (say, power of - 2), which makes the question -\begin_inset Quotes eld -\end_inset - -what zone is this record in? -\begin_inset Quotes erd -\end_inset - - much harder (and -\begin_inset Quotes eld -\end_inset - -pick a random zone -\begin_inset Quotes erd -\end_inset - -, but that's less common). - It could be done with as few as 4 bits from the record header. -\begin_inset Foot -status open - -\begin_layout Plain Layout - -\change_inserted 0 1284424151 -Using -\begin_inset Formula $2^{16+N*3}$ -\end_inset - -means 0 gives a minimal 65536-byte zone, 15 gives the maximal -\begin_inset Formula $2^{61}$ -\end_inset - - byte zone. - Zones range in factor of 8 steps. - Given the zone size for the zone the current record is in, we can determine - the start of the zone. -\change_unchanged - -\end_layout - -\end_inset - - -\change_unchanged - +Each free entry has the free table number in the header: less than 255. + It also contains a doubly-linked list for easy deletion. \end_layout \begin_layout Subsection @@ -2165,8 +2128,6 @@ miss it reduces 99.9% of false memcmp). As an aside, as the lower bits are already incorporated in the hash table resolution, the upper bits should be used here. - -\change_inserted 0 1283336739 Note that it's not clear that these bits will be a win, given the extra bits in the hash table itself (see \begin_inset CommandInset ref @@ -2176,8 +2137,6 @@ reference "sub:Hash-Size-Solution" \end_inset ). -\change_unchanged - \end_layout \begin_layout Enumerate @@ -2214,11 +2173,11 @@ struct tdb_used_record { \end_layout \begin_layout LyX-Code - uint32_t magic : 16, + uint32_t used_magic : 16, \end_layout \begin_layout LyX-Code - prev_is_free: 1, + \end_layout \begin_layout LyX-Code @@ -2226,7 +2185,7 @@ struct tdb_used_record { \end_layout \begin_layout LyX-Code - top_hash: 10; + top_hash: 11; \end_layout \begin_layout LyX-Code @@ -2250,29 +2209,27 @@ struct tdb_free_record { \end_layout \begin_layout LyX-Code - uint32_t free_magic; + uint64_t free_magic: 8, \end_layout \begin_layout LyX-Code - uint64_t total_length; -\change_inserted 0 1283337133 - + prev : 56; \end_layout \begin_layout LyX-Code -\change_inserted 0 1283337139 - uint64_t prev, next; -\change_unchanged +\end_layout +\begin_layout LyX-Code + uint64_t free_table: 8, \end_layout \begin_layout LyX-Code - ... + total_length : 56 \end_layout \begin_layout LyX-Code - uint64_t tailer; + uint64_t next;; \end_layout \begin_layout LyX-Code @@ -2281,20 +2238,19 @@ struct tdb_free_record { \begin_layout Standard -\change_inserted 0 1283337235 -We might want to take some bits from the used record's top_hash (and the - free record which has 32 bits of padding to spare anyway) if we use variable - sized zones. - See -\begin_inset CommandInset ref -LatexCommand ref -reference "freelist-in-zone" - -\end_inset - -. +\change_deleted 0 1291206079 + \change_unchanged +Note that by limiting valid offsets to 56 bits, we can pack everything we + need into 3 64-byte words, meaning our minimum record size is 8 bytes. +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Complete. \end_layout \begin_layout Subsection @@ -2387,6 +2343,14 @@ Checking for recovery means identifying the latest bundle with a valid checksum a transaction in progress; we need only check for recovery if this is set. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -2398,13 +2362,7 @@ TDB Does Not Have Snapshot Support \end_layout \begin_layout Subsubsection -Proposed Solution -\change_deleted 0 1284423472 - -\end_layout - -\begin_layout Standard -None. +Proposed SolutionNone. At some point you say \begin_inset Quotes eld \end_inset @@ -2413,13 +2371,6 @@ use a real database \begin_inset Quotes erd \end_inset - -\change_inserted 0 1284423891 - -\change_deleted 0 1284423891 -. - -\change_inserted 0 1284423901 (but see \begin_inset CommandInset ref LatexCommand ref @@ -2428,8 +2379,6 @@ reference "replay-attribute" \end_inset ). -\change_unchanged - \end_layout \begin_layout Standard @@ -2452,8 +2401,14 @@ This would not allow arbitrary changes to the database, such as tdb_repack \begin_layout Standard We could then implement snapshots using a similar method, using multiple different hash tables/free tables. -\change_inserted 0 1284423495 +\end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. \end_layout \begin_layout Subsection @@ -2473,8 +2428,6 @@ Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284424201 None (but see \begin_inset CommandInset ref LatexCommand ref @@ -2483,15 +2436,21 @@ reference "replay-attribute" \end_inset ). - -\change_unchanged -We could solve a small part of the problem by providing read-only transactions. + We could solve a small part of the problem by providing read-only transactions. These would allow one write transaction to begin, but it could not commit until all r/o transactions are done. This would require a new RO_TRANSACTION_LOCK, which would be upgraded on commit. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. +\end_layout + \begin_layout Subsection Default Hash Function Is Suboptimal \end_layout @@ -2532,6 +2491,14 @@ The seed should be created at tdb-creation time from some random source, hash bombing. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -2569,6 +2536,14 @@ reference "traverse-Proposed-Solution" . \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Fcntl Locking Adds Overhead \end_layout @@ -2670,19 +2645,13 @@ At some later point, a sync would allow recovery of the old data into the free lists (perhaps when the array of top-level pointers filled). On crash, tdb_open() would examine the array of top levels, and apply the transactions until it encountered an invalid checksum. -\change_inserted 0 1284423555 - \end_layout \begin_layout Subsection - -\change_inserted 0 1284423617 Tracing Is Fragile, Replay Is External \end_layout \begin_layout Standard - -\change_inserted 0 1284423719 The current TDB has compile-time-enabled tracing code, but it often breaks as it is not enabled by default. In a similar way, the ctdb code has an external wrapper which does replay @@ -2690,8 +2659,6 @@ The current TDB has compile-time-enabled tracing code, but it often breaks \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284423864 Proposed Solution \begin_inset CommandInset label LatexCommand label @@ -2703,8 +2670,6 @@ name "replay-attribute" \end_layout \begin_layout Standard - -\change_inserted 0 1284423850 Tridge points out that an attribute can be later added to tdb_open (see \begin_inset CommandInset ref @@ -2715,8 +2680,14 @@ reference "attributes" ) to provide replay/trace hooks, which could become the basis for this and future parallel transactions and snapshot support. -\change_unchanged +\end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. \end_layout \end_body diff --git a/ccan/tdb2/doc/design.lyx,v b/ccan/tdb2/doc/design.lyx,v index 70fe70e2..03d9a4bc 100644 --- a/ccan/tdb2/doc/design.lyx,v +++ b/ccan/tdb2/doc/design.lyx,v @@ -1,10 +1,25 @@ -head 1.10; +head 1.13; access; symbols; locks; strict; comment @# @; +1.13 +date 2010.12.01.12.22.08; author rusty; state Exp; +branches; +next 1.12; + +1.12 +date 2010.12.01.12.20.49; author rusty; state Exp; +branches; +next 1.11; + +1.11 +date 2010.12.01.11.55.20; author rusty; state Exp; +branches; +next 1.10; + 1.10 date 2010.09.14.00.33.57; author rusty; state Exp; branches; @@ -61,12 +76,12 @@ desc @ -1.10 +1.13 log -@Tracing attribute, talloc support. +@Merged changes. @ text -@#LyX 1.6.5 created this file. For more info see http://www.lyx.org/ +@#LyX 1.6.7 created this file. For more info see http://www.lyx.org/ \lyxformat 345 \begin_document \begin_header @@ -118,13 +133,7 @@ Rusty Russell, IBM Corporation \end_layout \begin_layout Date - -\change_deleted 0 1283307542 -26-July -\change_inserted 0 1284423485 -14-September -\change_unchanged --2010 +1-December-2010 \end_layout \begin_layout Abstract @@ -544,8 +553,6 @@ The tdb_open() call was expanded to tdb_open_ex(), which added an optional \begin_layout Subsubsection Proposed Solution -\change_inserted 0 1284422789 - \begin_inset CommandInset label LatexCommand label name "attributes" @@ -553,8 +560,6 @@ name "attributes" \end_inset -\change_unchanged - \end_layout \begin_layout Standard @@ -658,6 +663,14 @@ This allows future attributes to be added, even if this expands the size of the union. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection tdb_traverse Makes Impossible Guarantees \end_layout @@ -699,6 +712,16 @@ Abandon the guarantee. You can prevent changes by using a transaction or the locking API. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. + Delete-during-traverse will still delete every record, too (assuming no + other changes). +\end_layout + \begin_layout Subsection Nesting of Transactions Is Fraught \end_layout @@ -753,6 +776,14 @@ least-surprise -obscure case. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete; nesting flag is still defined as per tdb1. +\end_layout + \begin_layout Subsection Incorrect Hash Function is Not Detected \end_layout @@ -774,6 +805,14 @@ The header should contain an example hash result (eg. hash function produces the same answer, or fail the tdb_open call. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection tdb_set_max_dead/TDB_VOLATILE Expose Implementation \end_layout @@ -818,6 +857,16 @@ With the scalability problems of the freelist solved, this API can be removed. tuning, but initially will become a no-op. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. + TDB_VOLATILE still defined, but implementation should fail on unknown flags + to be future-proof. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -870,6 +919,14 @@ I do not see benefit in an additional tdb_open flag to indicate whether an API. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection TDB API Is Not POSIX Thread-safe \end_layout @@ -914,8 +971,6 @@ Internal locking is required to make sure that fcntl locks do not overlap \begin_layout Standard The aim is that building tdb with -DTDB_PTHREAD will result in a pthread-safe version of the library, and otherwise no overhead will exist. - -\change_inserted 0 1284016998 Alternatively, a hooking mechanism similar to that proposed for \begin_inset CommandInset ref LatexCommand ref @@ -924,8 +979,14 @@ reference "Proposed-Solution-locking-hook" \end_inset could be used to enable pthread locking at runtime. -\change_unchanged +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Incomplete. \end_layout \begin_layout Subsection @@ -1043,6 +1104,14 @@ This is flexible enough to handle any potential locking scenario, even when It also keeps the complexity out of the API, and in ctdbd where it is needed. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection tdb_chainlock Functions Expose Implementation \end_layout @@ -1124,6 +1193,14 @@ It may be possible to make this race-free in some implementations by having \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection The API Uses Gratuitous Typedefs, Capitals \end_layout @@ -1200,6 +1277,14 @@ It should simply take an extra argument, since we are prepared to break the API/ABI. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Various Callback Functions Are Not Typesafe \end_layout @@ -1239,6 +1324,14 @@ With careful use of macros, we can create callback functions which give See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete. +\end_layout + \begin_layout Subsection TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic \end_layout @@ -1274,19 +1367,21 @@ reference "TDB_CLEAR_IF_FIRST-Imposes-Performance" \end_inset . -\change_inserted 0 1284015637 +\end_layout +\begin_layout Subsubsection +Status \end_layout -\begin_layout Subsection +\begin_layout Standard +Incomplete, TDB_CLEAR_IF_FIRST still defined, but not implemented. +\end_layout -\change_inserted 0 1284015716 +\begin_layout Subsection Extending The Header Is Difficult \end_layout \begin_layout Standard - -\change_inserted 0 1284015906 We have reserved (zeroed) words in the TDB header, which can be used for future features. If the future features are compulsory, the version number must be updated @@ -1296,14 +1391,10 @@ We have reserved (zeroed) words in the TDB header, which can be used for \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284015637 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284016114 The header should contain a \begin_inset Quotes eld \end_inset @@ -1317,58 +1408,48 @@ format variant \end_layout \begin_layout Enumerate - -\change_inserted 0 1284016149 The lower part reflects the format variant understood by code accessing the database. \end_layout \begin_layout Enumerate - -\change_inserted 0 1284016639 The upper part reflects the format variant you must understand to write to the database (otherwise you can only open for reading). \end_layout \begin_layout Standard - -\change_inserted 0 1284016821 The latter field can only be written at creation time, the former should be written under the OPEN_LOCK when opening the database for writing, if the variant of the code is lower than the current lowest variant. \end_layout \begin_layout Standard - -\change_inserted 0 1284016803 This should allow backwards-compatible features to be added, and detection if older code (which doesn't understand the feature) writes to the database. -\change_deleted 0 1284016101 +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Incomplete. \end_layout \begin_layout Subsection - -\change_inserted 0 1284015634 Record Headers Are Not Expandible \end_layout \begin_layout Standard - -\change_inserted 0 1284015634 If we later want to add (say) checksums on keys and data, it would require another format change, which we'd like to avoid. \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284015634 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284422552 We often have extra padding at the tail of a record. If we ensure that the first byte (if any) of this padding is zero, we will have a way for future changes to detect code which doesn't understand a @@ -1377,28 +1458,28 @@ We often have extra padding at the tail of a record. not present on that record. \end_layout -\begin_layout Subsection +\begin_layout Subsubsection +Status +\end_layout -\change_inserted 0 1284422568 +\begin_layout Standard +Incomplete. +\end_layout + +\begin_layout Subsection TDB Does Not Use Talloc \end_layout \begin_layout Standard - -\change_inserted 0 1284422646 Many users of TDB (particularly Samba) use the talloc allocator, and thus have to wrap TDB in a talloc context to use it conveniently. \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284422656 Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284423065 The allocation within TDB is not complicated enough to justify the use of talloc, and I am reluctant to force another (excellent) library on TDB users. @@ -1424,15 +1505,19 @@ context \end_layout \begin_layout Standard - -\change_inserted 0 1284423042 This would form a talloc heirarchy as expected, but the caller would still have to attach a destructor to the tdb context returned from tdb_open to close it. All TDB_DATA fields would be children of the tdb_context, and the caller would still have to manage them (using talloc_free() or talloc_steal()). -\change_unchanged +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Deferred. \end_layout \begin_layout Section @@ -1490,6 +1575,14 @@ Remove the flag. point. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Incomplete; TDB_CLEAR_IF_FIRST still defined, but does nothing. +\end_layout + \begin_layout Subsection TDB Files Have a 4G Limit \end_layout @@ -1537,6 +1630,14 @@ Old versions of tdb will fail to open the new TDB files (since 28 August be erased and initialized as a fresh tdb!) \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection TDB Records Have a 4G Limit \end_layout @@ -1566,6 +1667,14 @@ reference "sub:Records-Incur-A" ). \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Hash Size Is Determined At TDB Creation Time \end_layout @@ -1580,16 +1689,12 @@ TDB contains a number of hash chains in the header; the number is specified \end_layout \begin_layout Subsubsection - -\change_inserted 0 1283336713 \begin_inset CommandInset label LatexCommand label name "sub:Hash-Size-Solution" \end_inset - -\change_unchanged Proposed Solution \end_layout @@ -1608,58 +1713,6 @@ http://rusty.ozlabs.org/?p=89 and http://rusty.ozlabs.org/?p=94 This was annoyin , it became clear that it is hard to beat a straight linear hash table which doubles in size when it reaches saturation. - -\change_deleted 0 1283307675 -There are three details which become important: -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -On encountering a full bucket, we use the next bucket. -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -Extra hash bits are stored with the offset, to reduce comparisons. -\end_layout - -\begin_layout Enumerate - -\change_deleted 0 1283307675 -A marker entry is used on deleting an entry. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -The doubling of the table must be done under a transaction; we will not - reduce it on deletion, so it will be an unusual case. - It will either be placed at the head (other entries will be moved out the - way so we can expand). - We could have a pointer in the header to the current hashtable location, - but that pointer would have to be read frequently to check for hashtable - moves. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -The locking for this is slightly more complex than the chained case; we - currently have one lock per bucket, and that means we would need to expand - the lock if we overflow to the next bucket. - The frequency of such collisions will effect our locking heuristics: we - can always lock more buckets than we need. -\end_layout - -\begin_layout Standard - -\change_deleted 0 1283307675 -One possible optimization is to only re-check the hash size on an insert - or a lookup miss. - -\change_inserted 0 1283307770 Unfortunately, altering the hash table introduces serious locking complications : the entire hash table needs to be locked to enlarge the hash table, and others might be holding locks. @@ -1667,8 +1720,6 @@ One possible optimization is to only re-check the hash size on an insert \end_layout \begin_layout Standard - -\change_inserted 0 1283336187 Thus an expanding layered hash will be used: an array of hash groups, with each hash group exploding into pointers to lower hash groups once it fills, turning into a hash tree. @@ -1677,8 +1728,6 @@ Thus an expanding layered hash will be used: an array of hash groups, with \end_layout \begin_layout Standard - -\change_inserted 0 1283336586 Note that bits from the hash table entries should be stolen to hold more hash bits to reduce the penalty of collisions. We can use the otherwise-unused lower 3 bits. @@ -1689,8 +1738,14 @@ Note that bits from the hash table entries should be stolen to hold more bits are valid. This means we can choose not to re-hash all entries when we expand a hash group; simply use the next bits we need and mark them invalid. -\change_unchanged +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Complete. \end_layout \begin_layout Subsection @@ -1817,8 +1872,6 @@ The single list lock limits our allocation rate; due to the other issues \begin_layout Subsubsection Proposed Solution -\change_deleted 0 1283336858 - \end_layout \begin_layout Standard @@ -1833,20 +1886,14 @@ The free list must be split to reduce contention. This implies that the number of free lists is related to the size of the hash table, but as it is rare to walk a large number of free list entries we can use far fewer, say 1/32 of the number of hash buckets. -\change_inserted 0 1283336910 - \end_layout \begin_layout Standard - -\change_inserted 0 1283337052 It seems tempting to try to reuse the hash implementation which we use for records here, but we have two ways of searching for free entries: for allocatio n we search by size (and possibly zone) which produces too many clashes for our hash table to handle well, and for coalescing we search by address. Thus an array of doubly-linked free lists seems preferable. -\change_unchanged - \end_layout \begin_layout Standard @@ -1860,24 +1907,28 @@ reference "sub:TDB-Becomes-Fragmented" ) but it's not clear this would reduce contention in the common case where all processes are allocating/freeing the same size. Thus we almost certainly need to divide in other ways: the most obvious - is to divide the file into zones, and using a free list (or set of free + is to divide the file into zones, and using a free list (or table of free lists) for each. This approximates address ordering. \end_layout \begin_layout Standard -Note that this means we need to split the free lists when we expand the - file; this is probably acceptable when we double the hash table size, since - that is such an expensive operation already. - In the case of increasing the file size, there is an optimization we can - use: if we use M in the formula above as the file size rounded up to the - next power of 2, we only need reshuffle free lists when the file size crosses - a power of 2 boundary, -\emph on -and -\emph default -reshuffling the free lists is trivial: we simply merge every consecutive - pair of free lists. +Unfortunately it is difficult to know what heuristics should be used to + determine zone sizes, and our transaction code relies on being able to + create a +\begin_inset Quotes eld +\end_inset + +recovery area +\begin_inset Quotes erd +\end_inset + + by simply appending to the file (difficult if it would need to create a + new zone header). + Thus we use a linked-list of free tables; currently we only ever create + one, but if there is more than one we choose one at random to use. + In future we may use heuristics to add new free tables on contention. + We only expand the file when all free tables are exhausted. \end_layout \begin_layout Standard @@ -1886,7 +1937,7 @@ The basic algorithm is as follows. \end_layout \begin_layout Enumerate -Identify the correct zone. +Identify the correct free list. \end_layout \begin_layout Enumerate @@ -1894,12 +1945,12 @@ Lock the corresponding list. \end_layout \begin_layout Enumerate -Re-check the zone (we didn't have a lock, sizes could have changed): relock +Re-check the list (we didn't have a lock, sizes could have changed): relock if necessary. \end_layout \begin_layout Enumerate -Place the freed entry in the list for that zone. +Place the freed entry in the list. \end_layout \begin_layout Standard @@ -1908,15 +1959,7 @@ Allocation is a little more complicated, as we perform delayed coalescing \end_layout \begin_layout Enumerate -Pick a zone either the zone we last freed into, or based on a -\begin_inset Quotes eld -\end_inset - -random -\begin_inset Quotes erd -\end_inset - - number. +Pick a free table; usually the previous one. \end_layout \begin_layout Enumerate @@ -1924,16 +1967,16 @@ Lock the corresponding list. \end_layout \begin_layout Enumerate -Re-check the zone: relock if necessary. +If the top entry is -large enough, remove it from the list and return it. \end_layout \begin_layout Enumerate -If the top entry is -large enough, remove it from the list and return it. +Otherwise, coalesce entries in the list.If there was no entry large enough, + unlock the list and try the next largest list \end_layout \begin_layout Enumerate -Otherwise, coalesce entries in the list.If there was no entry large enough, - unlock the list and try the next zone. +If no list has an entry which meets our needs, try the next free table. \end_layout \begin_layout Enumerate @@ -1965,73 +2008,8 @@ reference "sub:Records-Incur-A" \end_layout \begin_layout Standard -I anticipate that the number of entries in each free zone would be small, - but it might be worth using one free entry to hold pointers to the others - for cache efficiency. -\change_inserted 0 1283309850 - -\end_layout - -\begin_layout Standard - -\change_inserted 0 1283337216 -\begin_inset CommandInset label -LatexCommand label -name "freelist-in-zone" - -\end_inset - -If we want to avoid locking complexity (enlarging the free lists when we - enlarge the file) we could place the array of free lists at the beginning - of each zone. - This means existing array lists never move, but means that a record cannot - be larger than a zone. - That in turn implies that zones should be variable sized (say, power of - 2), which makes the question -\begin_inset Quotes eld -\end_inset - -what zone is this record in? -\begin_inset Quotes erd -\end_inset - - much harder (and -\begin_inset Quotes eld -\end_inset - -pick a random zone -\begin_inset Quotes erd -\end_inset - -, but that's less common). - It could be done with as few as 4 bits from the record header. -\begin_inset Foot -status open - -\begin_layout Plain Layout - -\change_inserted 0 1284424151 -Using -\begin_inset Formula $2^{16+N*3}$ -\end_inset - -means 0 gives a minimal 65536-byte zone, 15 gives the maximal -\begin_inset Formula $2^{61}$ -\end_inset - - byte zone. - Zones range in factor of 8 steps. - Given the zone size for the zone the current record is in, we can determine - the start of the zone. -\change_unchanged - -\end_layout - -\end_inset - - -\change_unchanged - +Each free entry has the free table number in the header: less than 255. + It also contains a doubly-linked list for easy deletion. \end_layout \begin_layout Subsection @@ -2233,8 +2211,6 @@ miss it reduces 99.9% of false memcmp). As an aside, as the lower bits are already incorporated in the hash table resolution, the upper bits should be used here. - -\change_inserted 0 1283336739 Note that it's not clear that these bits will be a win, given the extra bits in the hash table itself (see \begin_inset CommandInset ref @@ -2244,8 +2220,6 @@ reference "sub:Hash-Size-Solution" \end_inset ). -\change_unchanged - \end_layout \begin_layout Enumerate @@ -2282,11 +2256,11 @@ struct tdb_used_record { \end_layout \begin_layout LyX-Code - uint32_t magic : 16, + uint32_t used_magic : 16, \end_layout \begin_layout LyX-Code - prev_is_free: 1, + \end_layout \begin_layout LyX-Code @@ -2294,7 +2268,7 @@ struct tdb_used_record { \end_layout \begin_layout LyX-Code - top_hash: 10; + top_hash: 11; \end_layout \begin_layout LyX-Code @@ -2318,29 +2292,27 @@ struct tdb_free_record { \end_layout \begin_layout LyX-Code - uint32_t free_magic; + uint64_t free_magic: 8, \end_layout \begin_layout LyX-Code - uint64_t total_length; -\change_inserted 0 1283337133 - + prev : 56; \end_layout \begin_layout LyX-Code -\change_inserted 0 1283337139 - uint64_t prev, next; -\change_unchanged +\end_layout +\begin_layout LyX-Code + uint64_t free_table: 8, \end_layout \begin_layout LyX-Code - ... + total_length : 56 \end_layout \begin_layout LyX-Code - uint64_t tailer; + uint64_t next;; \end_layout \begin_layout LyX-Code @@ -2349,20 +2321,19 @@ struct tdb_free_record { \begin_layout Standard -\change_inserted 0 1283337235 -We might want to take some bits from the used record's top_hash (and the - free record which has 32 bits of padding to spare anyway) if we use variable - sized zones. - See -\begin_inset CommandInset ref -LatexCommand ref -reference "freelist-in-zone" - -\end_inset - -. +\change_deleted 0 1291206079 + \change_unchanged +Note that by limiting valid offsets to 56 bits, we can pack everything we + need into 3 64-byte words, meaning our minimum record size is 8 bytes. +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Complete. \end_layout \begin_layout Subsection @@ -2455,6 +2426,14 @@ Checking for recovery means identifying the latest bundle with a valid checksum a transaction in progress; we need only check for recovery if this is set. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -2466,13 +2445,7 @@ TDB Does Not Have Snapshot Support \end_layout \begin_layout Subsubsection -Proposed Solution -\change_deleted 0 1284423472 - -\end_layout - -\begin_layout Standard -None. +Proposed SolutionNone. At some point you say \begin_inset Quotes eld \end_inset @@ -2481,13 +2454,6 @@ use a real database \begin_inset Quotes erd \end_inset - -\change_inserted 0 1284423891 - -\change_deleted 0 1284423891 -. - -\change_inserted 0 1284423901 (but see \begin_inset CommandInset ref LatexCommand ref @@ -2496,8 +2462,6 @@ reference "replay-attribute" \end_inset ). -\change_unchanged - \end_layout \begin_layout Standard @@ -2520,8 +2484,14 @@ This would not allow arbitrary changes to the database, such as tdb_repack \begin_layout Standard We could then implement snapshots using a similar method, using multiple different hash tables/free tables. -\change_inserted 0 1284423495 +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Deferred. \end_layout \begin_layout Subsection @@ -2541,8 +2511,6 @@ Proposed Solution \end_layout \begin_layout Standard - -\change_inserted 0 1284424201 None (but see \begin_inset CommandInset ref LatexCommand ref @@ -2551,15 +2519,21 @@ reference "replay-attribute" \end_inset ). - -\change_unchanged -We could solve a small part of the problem by providing read-only transactions. + We could solve a small part of the problem by providing read-only transactions. These would allow one write transaction to begin, but it could not commit until all r/o transactions are done. This would require a new RO_TRANSACTION_LOCK, which would be upgraded on commit. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Deferred. +\end_layout + \begin_layout Subsection Default Hash Function Is Suboptimal \end_layout @@ -2600,6 +2574,14 @@ The seed should be created at tdb-creation time from some random source, hash bombing. \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection \begin_inset CommandInset label LatexCommand label @@ -2637,6 +2619,14 @@ reference "traverse-Proposed-Solution" . \end_layout +\begin_layout Subsubsection +Status +\end_layout + +\begin_layout Standard +Complete. +\end_layout + \begin_layout Subsection Fcntl Locking Adds Overhead \end_layout @@ -2738,19 +2728,13 @@ At some later point, a sync would allow recovery of the old data into the free lists (perhaps when the array of top-level pointers filled). On crash, tdb_open() would examine the array of top levels, and apply the transactions until it encountered an invalid checksum. -\change_inserted 0 1284423555 - \end_layout \begin_layout Subsection - -\change_inserted 0 1284423617 Tracing Is Fragile, Replay Is External \end_layout \begin_layout Standard - -\change_inserted 0 1284423719 The current TDB has compile-time-enabled tracing code, but it often breaks as it is not enabled by default. In a similar way, the ctdb code has an external wrapper which does replay @@ -2758,8 +2742,6 @@ The current TDB has compile-time-enabled tracing code, but it often breaks \end_layout \begin_layout Subsubsection - -\change_inserted 0 1284423864 Proposed Solution \begin_inset CommandInset label LatexCommand label @@ -2771,8 +2753,6 @@ name "replay-attribute" \end_layout \begin_layout Standard - -\change_inserted 0 1284423850 Tridge points out that an attribute can be later added to tdb_open (see \begin_inset CommandInset ref @@ -2783,8 +2763,14 @@ reference "attributes" ) to provide replay/trace hooks, which could become the basis for this and future parallel transactions and snapshot support. -\change_unchanged +\end_layout + +\begin_layout Subsubsection +Status +\end_layout +\begin_layout Standard +Deferred. \end_layout \end_body @@ -2792,6 +2778,996 @@ reference "attributes" @ +1.12 +log +@Add status, some fixes, linked freelists. +@ +text +@d53 1 +a53 7 + +\change_deleted 0 1291204535 +14-September +\change_inserted 0 1291204533 +1-December +\change_unchanged +-2010 +a580 2 +\change_inserted 0 1291204563 + +a583 2 + +\change_inserted 0 1291204572 +a587 2 + +\change_inserted 0 1291204573 +a588 2 +\change_unchanged + +a629 2 +\change_inserted 0 1291204588 + +a632 2 + +\change_inserted 0 1291204588 +a636 2 + +\change_inserted 0 1291204631 +a639 2 +\change_unchanged + +a693 2 +\change_inserted 0 1291204639 + +a696 2 + +\change_inserted 0 1291204640 +a700 2 + +\change_inserted 0 1291204665 +a701 2 +\change_unchanged + +a722 2 +\change_inserted 0 1291204671 + +a725 2 + +\change_inserted 0 1291204671 +a729 2 + +\change_inserted 0 1291204673 +a730 2 +\change_unchanged + +a774 2 +\change_inserted 0 1291204731 + +a777 2 + +\change_inserted 0 1291204732 +a781 2 + +\change_inserted 0 1291204779 +a784 2 +\change_unchanged + +a836 2 +\change_inserted 0 1291204830 + +a839 2 + +\change_inserted 0 1291204831 +a843 2 + +\change_inserted 0 1291204834 +a844 2 +\change_unchanged + +a898 2 +\change_inserted 0 1291204847 + +a901 2 + +\change_inserted 0 1291204847 +a905 2 + +\change_inserted 0 1291204852 +a906 2 +\change_unchanged + +a1021 2 +\change_inserted 0 1291204881 + +a1024 2 + +\change_inserted 0 1291204881 +a1028 2 + +\change_inserted 0 1291204885 +a1029 2 +\change_unchanged + +a1110 2 +\change_inserted 0 1291204898 + +a1113 2 + +\change_inserted 0 1291204898 +a1117 2 + +\change_inserted 0 1291204901 +a1118 2 +\change_unchanged + +a1194 2 +\change_inserted 0 1291204908 + +a1197 2 + +\change_inserted 0 1291204908 +a1201 2 + +\change_inserted 0 1291204908 +a1202 2 +\change_unchanged + +a1241 2 +\change_inserted 0 1291204917 + +a1244 2 + +\change_inserted 0 1291204917 +a1248 2 + +\change_inserted 0 1291204920 +a1249 2 +\change_unchanged + +a1286 2 +\change_inserted 0 1291204927 + +a1289 2 + +\change_inserted 0 1291204928 +a1293 2 + +\change_inserted 0 1291204942 +a1294 2 +\change_unchanged + +a1345 2 +\change_inserted 0 1291205003 + +a1348 2 + +\change_inserted 0 1291205004 +a1352 2 + +\change_inserted 0 1291205007 +a1375 2 +\change_inserted 0 1291205019 + +a1378 2 + +\change_inserted 0 1291205019 +a1382 2 + +\change_inserted 0 1291205023 +a1383 2 +\change_unchanged + +a1429 2 +\change_inserted 0 1291205029 + +a1432 2 + +\change_inserted 0 1291205029 +a1436 2 + +\change_inserted 0 1291206020 +a1437 2 +\change_unchanged + +a1492 2 +\change_inserted 0 1291205043 + +a1495 2 + +\change_inserted 0 1291205043 +a1499 2 + +\change_inserted 0 1291205057 +a1500 2 +\change_unchanged + +a1547 2 +\change_inserted 0 1291205062 + +a1550 2 + +\change_inserted 0 1291205062 +a1554 2 + +\change_inserted 0 1291205062 +a1555 2 +\change_unchanged + +a1584 2 +\change_inserted 0 1291205072 + +a1587 2 + +\change_inserted 0 1291205073 +a1591 2 + +\change_inserted 0 1291205073 +a1592 2 +\change_unchanged + +a1632 4 + +\change_deleted 0 1291204504 + +\change_unchanged +a1657 2 +\change_inserted 0 1291205079 + +a1660 2 + +\change_inserted 0 1291205080 +a1664 2 + +\change_inserted 0 1291205080 +a1665 2 +\change_unchanged + +a1791 2 +\change_inserted 0 1291205090 + +d1827 2 +a1828 7 + is to divide the file into zones, and using a free list (or +\change_inserted 0 1291205498 +table +\change_deleted 0 1291205497 +set +\change_unchanged + of free lists) for each. +a1829 2 +\change_inserted 0 1291205203 + +a1832 2 + +\change_inserted 0 1291205358 +a1848 21 +\change_unchanged + +\end_layout + +\begin_layout Standard + +\change_deleted 0 1291205198 +Note that this means we need to split the free lists when we expand the + file; this is probably acceptable when we double the hash table size, since + that is such an expensive operation already. + In the case of increasing the file size, there is an optimization we can + use: if we use M in the formula above as the file size rounded up to the + next power of 2, we only need reshuffle free lists when the file size crosses + a power of 2 boundary, +\emph on +and +\emph default +reshuffling the free lists is trivial: we simply merge every consecutive + pair of free lists. +\change_unchanged + +d1857 1 +a1857 7 +Identify the correct +\change_inserted 0 1291205366 +free list +\change_deleted 0 1291205364 +zone +\change_unchanged +. +d1865 2 +a1866 7 +Re-check the +\change_inserted 0 1291205372 +list +\change_deleted 0 1291205371 +zone +\change_unchanged + (we didn't have a lock, sizes could have changed): relock if necessary. +d1870 1 +a1870 5 +Place the freed entry in the list +\change_deleted 0 1291205382 + for that zone +\change_unchanged +. +d1879 1 +a1879 15 +Pick a +\change_deleted 0 1291205403 +zone either the zone we last freed into, or based on a +\begin_inset Quotes eld +\end_inset + +random +\begin_inset Quotes erd +\end_inset + + number. +\change_inserted 0 1291205411 +free table; usually the previous one. +\change_unchanged + +a1883 10 +\change_deleted 0 1291205432 + +\end_layout + +\begin_layout Enumerate + +\change_deleted 0 1291205428 +Re-check the zone: relock if necessary. +\change_unchanged + +d1892 1 +a1892 7 + unlock the list and try the next +\change_inserted 0 1291205455 +largest list +\change_deleted 0 1291205452 +zone. +\change_inserted 0 1291205457 + +a1895 2 + +\change_inserted 0 1291205476 +a1896 2 +\change_unchanged + +a1924 2 +\change_inserted 0 1291205542 + +a1927 2 + +\change_inserted 0 1291205591 +a1929 70 +\change_unchanged + +\end_layout + +\begin_layout Standard + +\change_deleted 0 1291205539 +I anticipate that the number of entries in each free zone would be small, + but it might be worth using one free entry to hold pointers to the others + for cache efficiency. +\change_unchanged + +\end_layout + +\begin_layout Standard + +\change_deleted 0 1291205534 +\begin_inset CommandInset label +LatexCommand label +name "freelist-in-zone" + +\end_inset + +If we want to avoid locking complexity (enlarging the free lists when we + enlarge the file) we could place the array of free lists at the beginning + of each zone. + This means existing array lists never move, but means that a record cannot + be larger than a zone. + That in turn implies that zones should be variable sized (say, power of + 2), which makes the question +\begin_inset Quotes eld +\end_inset + +what zone is this record in? +\begin_inset Quotes erd +\end_inset + + much harder (and +\begin_inset Quotes eld +\end_inset + +pick a random zone +\begin_inset Quotes erd +\end_inset + +, but that's less common). + It could be done with as few as 4 bits from the record header. +\begin_inset Foot +status collapsed + +\begin_layout Plain Layout +Using +\begin_inset Formula $2^{16+N*3}$ +\end_inset + +means 0 gives a minimal 65536-byte zone, 15 gives the maximal +\begin_inset Formula $2^{61}$ +\end_inset + + byte zone. + Zones range in factor of 8 steps. + Given the zone size for the zone the current record is in, we can determine + the start of the zone. +\end_layout + +\end_inset + + +\change_inserted 0 1291205139 + +d2176 1 +a2176 5 + uint32_t +\change_inserted 0 1291205758 +used_ +\change_unchanged +magic : 16, +a2180 4 +\change_deleted 0 1291205693 + prev_is_free: 1, +\change_unchanged + +d2188 1 +a2188 7 + top_hash: 1 +\change_inserted 0 1291205704 +1 +\change_deleted 0 1291205704 +0 +\change_unchanged +; +d2212 1 +a2212 9 + uint +\change_inserted 0 1291205725 +64 +\change_deleted 0 1291205723 +32 +\change_unchanged +_t +\change_inserted 0 1291205753 +free_magic: 8, +a2215 2 + +\change_inserted 0 1291205746 +a2220 24 +\change_deleted 0 1291205749 +free_magic; +\change_unchanged + +\end_layout + +\begin_layout LyX-Code + uint64_t +\change_inserted 0 1291205786 +free_table: 8, +\end_layout + +\begin_layout LyX-Code + +\change_inserted 0 1291205788 + +\change_unchanged +total_length +\change_inserted 0 1291205792 + : 56 +\change_deleted 0 1291205790 +; +\change_unchanged + +d2224 1 +a2224 7 + uint64_t +\change_deleted 0 1291205801 +prev, +\change_unchanged +next; +\change_deleted 0 1291205811 + +d2228 1 +a2228 3 + +\change_deleted 0 1291205811 + ... +d2232 1 +a2232 5 + +\change_deleted 0 1291205808 + uint64_t tailer +\change_unchanged +; +d2241 5 +a2245 16 +\change_deleted 0 1291205827 +We might want to take some bits from the used record's top_hash (and the + free record which has 32 bits of padding to spare anyway) if we use variable + sized zones. + See +\begin_inset CommandInset ref +LatexCommand ref +reference "freelist-in-zone" + +\end_inset + +. + +\change_inserted 0 1291205885 + Note that by limiting valid offsets to 56 bits, we can pack everything + we need into 3 64-byte words, meaning our minimum record size is 8 bytes. +a2248 2 + +\change_inserted 0 1291205886 +a2252 2 + +\change_inserted 0 1291205886 +a2253 2 +\change_unchanged + +a2343 2 +\change_inserted 0 1291205894 + +a2346 2 + +\change_inserted 0 1291205894 +a2350 2 + +\change_inserted 0 1291205902 +a2351 2 +\change_unchanged + +a2373 4 + +\change_deleted 0 1291204504 + +\change_unchanged +a2403 2 +\change_inserted 0 1291205910 + +a2406 2 + +\change_inserted 0 1291205910 +a2410 2 + +\change_inserted 0 1291205914 +a2411 2 +\change_unchanged + +a2443 2 +\change_inserted 0 1291205919 + +a2446 2 + +\change_inserted 0 1291205919 +a2450 2 + +\change_inserted 0 1291205922 +a2451 2 +\change_unchanged + +a2491 2 +\change_inserted 0 1291205929 + +a2494 2 + +\change_inserted 0 1291205929 +a2498 2 + +\change_inserted 0 1291205929 +a2499 2 +\change_unchanged + +a2536 2 +\change_inserted 0 1291205932 + +a2539 2 + +\change_inserted 0 1291205933 +a2543 2 + +\change_inserted 0 1291205933 +a2544 2 +\change_unchanged + +a2682 2 +\change_inserted 0 1291205944 + +a2685 2 + +\change_inserted 0 1291205945 +a2689 2 + +\change_inserted 0 1291205948 +a2690 2 +\change_unchanged + +@ + + +1.11 +log +@Merge changes +@ +text +@d53 7 +a59 1 +14-September-2010 +d587 16 +d644 18 +d716 16 +d753 16 +d813 18 +d883 16 +d953 16 +d1084 16 +d1181 16 +d1273 16 +d1328 16 +d1381 16 +d1447 19 +a1465 2 + if older code (which doesn't understand the feature) writes to the database.Reco +rd Headers Are Not Expandible +d1484 16 +d1546 16 +d1617 16 +d1680 16 +d1725 16 +d1810 16 +d1951 8 +a1958 3 +Proposed SolutionThe first step is to remove all the current heuristics, + as they obviously interact, then examine them once the lock contention + is addressed. +d1989 7 +a1995 2 + is to divide the file into zones, and using a free list (or set of free + lists) for each. +d1997 2 +d2002 25 +d2039 2 +d2049 7 +a2055 1 +Identify the correct zone. +d2063 7 +a2069 2 +Re-check the zone (we didn't have a lock, sizes could have changed): relock + if necessary. +d2073 5 +a2077 1 +Place the freed entry in the list for that zone. +d2086 3 +a2088 1 +Pick a zone either the zone we last freed into, or based on a +d2097 4 +d2105 2 +d2110 2 +d2113 2 +d2123 15 +a2137 1 + unlock the list and try the next zone. +d2166 11 +d2180 2 +d2185 2 +d2190 2 +d2223 1 +a2223 1 +status open +d2243 2 +d2491 5 +a2495 1 + uint32_t magic : 16, +d2499 2 +d2502 2 +d2511 7 +a2517 1 + top_hash: 10; +d2541 29 +a2569 1 + uint32_t free_magic; +d2573 11 +a2583 1 + uint64_t total_length; +d2587 7 +a2593 1 + uint64_t prev, next; +d2597 2 +d2603 5 +a2607 1 + uint64_t tailer; +d2615 2 +d2628 18 +d2736 16 +d2808 16 +d2856 16 +d2912 16 +d2965 16 +d3119 16 +@ + + +1.10 +log +@Tracing attribute, talloc support. +@ +text +@d1 1 +a1 1 +#LyX 1.6.5 created this file. For more info see http://www.lyx.org/ +d53 1 +a53 7 + +\change_deleted 0 1283307542 +26-July +\change_inserted 0 1284423485 +14-September +\change_unchanged +-2010 +a472 2 +\change_inserted 0 1284422789 + +a479 2 +\change_unchanged + +a838 2 + +\change_inserted 0 1284016998 +a846 2 +\change_unchanged + +a1194 2 +\change_inserted 0 1284015637 + +a1197 2 + +\change_inserted 0 1284015716 +a1201 2 + +\change_inserted 0 1284015906 +a1210 2 + +\change_inserted 0 1284015637 +a1214 2 + +\change_inserted 0 1284016114 +a1227 2 + +\change_inserted 0 1284016149 +a1232 2 + +\change_inserted 0 1284016639 +a1237 2 + +\change_inserted 0 1284016821 +a1243 2 + +\change_inserted 0 1284016803 +d1245 2 +a1246 9 + if older code (which doesn't understand the feature) writes to the database. +\change_deleted 0 1284016101 + +\end_layout + +\begin_layout Subsection + +\change_inserted 0 1284015634 +Record Headers Are Not Expandible +a1249 2 + +\change_inserted 0 1284015634 +a1254 2 + +\change_inserted 0 1284015634 +a1258 2 + +\change_inserted 0 1284422552 +a1267 2 + +\change_inserted 0 1284422568 +a1271 2 + +\change_inserted 0 1284422646 +a1276 2 + +\change_inserted 0 1284422656 +a1280 2 + +\change_inserted 0 1284423065 +a1305 2 + +\change_inserted 0 1284423042 +a1310 2 +\change_unchanged + +a1457 2 + +\change_inserted 0 1283336713 +a1463 2 + +\change_unchanged +d1482 2 +d1485 1 +a1485 51 +\change_deleted 0 1283307675 +There are three details which become important: +\end_layout + +\begin_layout Enumerate + +\change_deleted 0 1283307675 +On encountering a full bucket, we use the next bucket. +\end_layout + +\begin_layout Enumerate + +\change_deleted 0 1283307675 +Extra hash bits are stored with the offset, to reduce comparisons. +\end_layout + +\begin_layout Enumerate + +\change_deleted 0 1283307675 +A marker entry is used on deleting an entry. +\end_layout + +\begin_layout Standard + +\change_deleted 0 1283307675 +The doubling of the table must be done under a transaction; we will not + reduce it on deletion, so it will be an unusual case. + It will either be placed at the head (other entries will be moved out the + way so we can expand). + We could have a pointer in the header to the current hashtable location, + but that pointer would have to be read frequently to check for hashtable + moves. +\end_layout + +\begin_layout Standard + +\change_deleted 0 1283307675 +The locking for this is slightly more complex than the chained case; we + currently have one lock per bucket, and that means we would need to expand + the lock if we overflow to the next bucket. + The frequency of such collisions will effect our locking heuristics: we + can always lock more buckets than we need. +\end_layout + +\begin_layout Standard + +\change_deleted 0 1283307675 +One possible optimization is to only re-check the hash size on an insert + or a lookup miss. + +\change_inserted 0 1283307770 +a1492 2 + +\change_inserted 0 1283336187 +a1500 2 + +\change_inserted 0 1283336586 +a1510 2 +\change_unchanged + +d1636 3 +a1638 8 +Proposed Solution +\change_deleted 0 1283336858 + +\end_layout + +\begin_layout Standard +The first step is to remove all the current heuristics, as they obviously + interact, then examine them once the lock contention is addressed. +a1647 2 +\change_inserted 0 1283336910 + +a1650 2 + +\change_inserted 0 1283337052 +a1655 2 +\change_unchanged + +a1776 2 +\change_inserted 0 1283309850 + +a1779 2 + +\change_inserted 0 1283337216 +a1813 2 + +\change_inserted 0 1284424151 +a1825 2 +\change_unchanged + +a1830 2 +\change_unchanged + +a2031 2 + +\change_inserted 0 1283336739 +a2040 2 +\change_unchanged + +a2117 2 +\change_inserted 0 1283337133 + +a2120 2 + +\change_inserted 0 1283337139 +a2121 2 +\change_unchanged + +a2136 2 + +\change_inserted 0 1283337235 +a2147 2 +\change_unchanged + +d2251 1 +a2251 7 +Proposed Solution +\change_deleted 0 1284423472 + +\end_layout + +\begin_layout Standard +None. +d2261 1 +a2261 1 +\change_inserted 0 1284423891 +d2263 1 +a2263 4 +\change_deleted 0 1284423891 +. + +\change_inserted 0 1284423901 +a2271 2 +\change_unchanged + +a2293 2 +\change_inserted 0 1284423495 + +a2312 2 + +\change_inserted 0 1284424201 +d2321 1 +a2321 3 + +\change_unchanged +We could solve a small part of the problem by providing read-only transactions. +a2505 2 +\change_inserted 0 1284423555 + +a2508 2 + +\change_inserted 0 1284423617 +a2512 2 + +\change_inserted 0 1284423719 +a2519 2 + +\change_inserted 0 1284423864 +a2530 2 + +\change_inserted 0 1284423850 +a2540 2 +\change_unchanged + +@ + + 1.9 log @Extension mechanism. diff --git a/ccan/tdb2/doc/design.pdf b/ccan/tdb2/doc/design.pdf index 52d0f9b0..558dc1f8 100644 Binary files a/ccan/tdb2/doc/design.pdf and b/ccan/tdb2/doc/design.pdf differ diff --git a/ccan/tdb2/doc/design.txt b/ccan/tdb2/doc/design.txt index 233a43ab..c2994a4c 100644 --- a/ccan/tdb2/doc/design.txt +++ b/ccan/tdb2/doc/design.txt @@ -2,7 +2,7 @@ TDB2: A Redesigning The Trivial DataBase Rusty Russell, IBM Corporation -14-September-2010 +1-December-2010 Abstract @@ -129,6 +129,10 @@ union tdb_attribute { This allows future attributes to be added, even if this expands the size of the union. +2.1.2 Status + +Complete. + 2.2 tdb_traverse Makes Impossible Guarantees tdb_traverse (and tdb_firstkey/tdb_nextkey) predate transactions, @@ -148,6 +152,11 @@ occur during your traversal, otherwise you will see some subset. You can prevent changes by using a transaction or the locking API. +2.2.2 Status + +Complete. Delete-during-traverse will still delete every record, +too (assuming no other changes). + 2.3 Nesting of Transactions Is Fraught TDB has alternated between allowing nested transactions and not @@ -182,6 +191,10 @@ However, this behavior can be simulated with a wrapper which uses tdb_add_flags() and tdb_remove_flags(), so the API should not be expanded for this relatively-obscure case. +2.3.2 Status + +Incomplete; nesting flag is still defined as per tdb1. + 2.4 Incorrect Hash Function is Not Detected tdb_open_ex() allows the calling code to specify a different hash @@ -195,6 +208,10 @@ The header should contain an example hash result (eg. the hash of 0xdeadbeef), and tdb_open_ex() should check that the given hash function produces the same answer, or fail the tdb_open call. +2.4.2 Status + +Complete. + 2.5 tdb_set_max_dead/TDB_VOLATILE Expose Implementation In response to scalability issues with the free list ([TDB-Freelist-Is] @@ -216,6 +233,11 @@ hint that store and delete of records will be at least as common as fetch in order to allow some internal tuning, but initially will become a no-op. +2.5.2 Status + +Incomplete. TDB_VOLATILE still defined, but implementation should +fail on unknown flags to be future-proof. + 2.6 TDB Files Cannot Be Opened Multiple Times In The Same Process @@ -251,6 +273,10 @@ whether re-opening is allowed, as though there may be some benefit to adding a call to detect when a tdb_context is shared, to allow other to create such an API. +2.6.2 Status + +Incomplete. + 2.7 TDB API Is Not POSIX Thread-safe The TDB API uses an error code which can be queried after an @@ -281,6 +307,10 @@ will exist. Alternatively, a hooking mechanism similar to that proposed for [Proposed-Solution-locking-hook] could be used to enable pthread locking at runtime. +2.7.2 Status + +Incomplete. + 2.8 *_nonblock Functions And *_mark Functions Expose Implementation @@ -343,6 +373,10 @@ locks it doesn't need to obtain. It also keeps the complexity out of the API, and in ctdbd where it is needed. +2.8.2 Status + +Incomplete. + 2.9 tdb_chainlock Functions Expose Implementation tdb_chainlock locks some number of records, including the record @@ -391,6 +425,10 @@ EINVAL if the signal occurs before the kernel is entered, otherwise EAGAIN. ] +2.10.2 Status + +Incomplete. + 2.11 The API Uses Gratuitous Typedefs, Capitals typedefs are useful for providing source compatibility when types @@ -433,6 +471,10 @@ the tdb_open_ex for logging. It should simply take an extra argument, since we are prepared to break the API/ABI. +2.12.2 Status + +Complete. + 2.13 Various Callback Functions Are Not Typesafe The callback functions in tdb_set_logging_function (after [tdb_log_func-Doesnt-Take] @@ -455,6 +497,10 @@ their parameter. See CCAN's typesafe_cb module at http://ccan.ozlabs.org/info/typesafe_cb.html +2.13.2 Status + +Incomplete. + 2.14 TDB_CLEAR_IF_FIRST Must Be Specified On All Opens, tdb_reopen_all Problematic @@ -475,6 +521,11 @@ it alone has opened the TDB and will erase it. Remove TDB_CLEAR_IF_FIRST. Other workarounds are possible, but see [TDB_CLEAR_IF_FIRST-Imposes-Performance]. +2.14.2 Status + +Incomplete, TDB_CLEAR_IF_FIRST still defined, but not +implemented. + 2.15 Extending The Header Is Difficult We have reserved (zeroed) words in the TDB header, which can be @@ -505,6 +556,10 @@ This should allow backwards-compatible features to be added, and detection if older code (which doesn't understand the feature) writes to the database. +2.15.2 Status + +Incomplete. + 2.16 Record Headers Are Not Expandible If we later want to add (say) checksums on keys and data, it @@ -519,6 +574,10 @@ understand a new format: the new code would write (say) a 1 at the tail, and thus if there is no tail or the first byte is 0, we would know the extension is not present on that record. +2.16.2 Status + +Incomplete. + 2.17 TDB Does Not Use Talloc Many users of TDB (particularly Samba) use the talloc allocator, @@ -541,6 +600,10 @@ returned from tdb_open to close it. All TDB_DATA fields would be children of the tdb_context, and the caller would still have to manage them (using talloc_free() or talloc_steal()). +2.17.2 Status + +Deferred. + 3 Performance And Scalability Issues 3.1 TDB_CLEAR_IF_FIRST @@ -570,6 +633,10 @@ Remove the flag. It was a neat idea, but even trivial servers tend to know when they are initializing for the first time and can simply unlink the old tdb at that point. +3.1.2 Status + +Incomplete; TDB_CLEAR_IF_FIRST still defined, but does nothing. + 3.2 TDB Files Have a 4G Limit This seems to be becoming an issue (so much for “trivial”!), @@ -596,6 +663,10 @@ Old versions of tdb will fail to open the new TDB files (since 28 August 2009, commit 398d0c29290: prior to that any unrecognized file format would be erased and initialized as a fresh tdb!) +3.2.2 Status + +Complete. + 3.3 TDB Records Have a 4G Limit This has not been a reported problem, and the API uses size_t @@ -610,6 +681,10 @@ implementation would return TDB_ERR_OOM in a similar case). It seems unlikely that 32 bit keys will be a limitation, so the implementation may not support this (see [sub:Records-Incur-A]). +3.3.2 Status + +Complete. + 3.4 Hash Size Is Determined At TDB Creation Time TDB contains a number of hash chains in the header; the number is @@ -628,20 +703,9 @@ This was annoying because I was previously convinced that an expanding tree of hashes would be very close to optimal. ], it became clear that it is hard to beat a straight linear hash table which doubles in size when it reaches saturation. - -1. - -2. - -3. - - - - - - Unfortunately, altering the hash table introduces serious -locking complications: the entire hash table needs to be locked -to enlarge the hash table, and others might be holding locks. +Unfortunately, altering the hash table introduces serious locking +complications: the entire hash table needs to be locked to +enlarge the hash table, and others might be holding locks. Particularly insidious are insertions done under tdb_chainlock. Thus an expanding layered hash will be used: an array of hash @@ -662,6 +726,10 @@ means we can choose not to re-hash all entries when we expand a hash group; simply use the next bits we need and mark them invalid. +3.4.2 Status + +Complete. + 3.5 TDB Freelist Is Highly Contended TDB uses a single linked list for the free list. Allocation @@ -749,45 +817,45 @@ There are various benefits in using per-size free lists (see [sub:TDB-Becomes-Fr case where all processes are allocating/freeing the same size. Thus we almost certainly need to divide in other ways: the most obvious is to divide the file into zones, and using a free list -(or set of free lists) for each. This approximates address +(or table of free lists) for each. This approximates address ordering. -Note that this means we need to split the free lists when we -expand the file; this is probably acceptable when we double the -hash table size, since that is such an expensive operation -already. In the case of increasing the file size, there is an -optimization we can use: if we use M in the formula above as the -file size rounded up to the next power of 2, we only need -reshuffle free lists when the file size crosses a power of 2 -boundary, and reshuffling the free lists is trivial: we simply -merge every consecutive pair of free lists. +Unfortunately it is difficult to know what heuristics should be +used to determine zone sizes, and our transaction code relies on +being able to create a “recovery area” by simply appending to the +file (difficult if it would need to create a new zone header). +Thus we use a linked-list of free tables; currently we only ever +create one, but if there is more than one we choose one at random +to use. In future we may use heuristics to add new free tables on +contention. We only expand the file when all free tables are +exhausted. The basic algorithm is as follows. Freeing is simple: -1. Identify the correct zone. +1. Identify the correct free list. 2. Lock the corresponding list. -3. Re-check the zone (we didn't have a lock, sizes could have +3. Re-check the list (we didn't have a lock, sizes could have changed): relock if necessary. -4. Place the freed entry in the list for that zone. +4. Place the freed entry in the list. Allocation is a little more complicated, as we perform delayed coalescing at this point: -1. Pick a zone either the zone we last freed into, or based on a “ - random” number. +1. Pick a free table; usually the previous one. 2. Lock the corresponding list. -3. Re-check the zone: relock if necessary. - -4. If the top entry is -large enough, remove it from the list and +3. If the top entry is -large enough, remove it from the list and return it. -5. Otherwise, coalesce entries in the list.If there was no entry - large enough, unlock the list and try the next zone. +4. Otherwise, coalesce entries in the list.If there was no entry + large enough, unlock the list and try the next largest list + +5. If no list has an entry which meets our needs, try the next + free table. 6. If no zone satisfies, expand the file. @@ -798,24 +866,9 @@ ordering seems to be fairly good for keeping fragmentation low does not need a tailer to coalesce, though if we needed one we could have one cheaply: see [sub:Records-Incur-A]. -I anticipate that the number of entries in each free zone would -be small, but it might be worth using one free entry to hold -pointers to the others for cache efficiency. - -If we want to avoid locking complexity -(enlarging the free lists when we enlarge the file) we could -place the array of free lists at the beginning of each zone. This -means existing array lists never move, but means that a record -cannot be larger than a zone. That in turn implies that zones -should be variable sized (say, power of 2), which makes the -question “what zone is this record in?” much harder (and “pick a -random zone”, but that's less common). It could be done with as -few as 4 bits from the record header.[footnote: -Using 2^{16+N*3}means 0 gives a minimal 65536-byte zone, 15 gives -the maximal 2^{61} byte zone. Zones range in factor of 8 steps. -Given the zone size for the zone the current record is in, we can -determine the start of the zone. -] +Each free entry has the free table number in the header: less +than 255. It also contains a doubly-linked list for easy +deletion. 3.6 TDB Becomes Fragmented @@ -944,13 +997,13 @@ This produces a 16 byte used header like this: struct tdb_used_record { - uint32_t magic : 16, + uint32_t used_magic : 16, + - prev_is_free: 1, key_data_divide: 5, - top_hash: 10; + top_hash: 11; uint32_t extra_octets; @@ -962,21 +1015,27 @@ And a free record like this: struct tdb_free_record { - uint32_t free_magic; + uint64_t free_magic: 8, + + prev : 56; - uint64_t total_length; - uint64_t prev, next; - ... + uint64_t free_table: 8, - uint64_t tailer; + total_length : 56 + + uint64_t next;; }; -We might want to take some bits from the used record's top_hash -(and the free record which has 32 bits of padding to spare -anyway) if we use variable sized zones. See [freelist-in-zone]. +Note that by limiting valid offsets to 56 bits, we can pack +everything we need into 3 64-byte words, meaning our minimum +record size is 8 bytes. + +3.7.2 Status + +Complete. 3.8 Transaction Commit Requires 4 fdatasync @@ -1029,12 +1088,14 @@ but need only be done at open. For running databases, a separate header field can be used to indicate a transaction in progress; we need only check for recovery if this is set. -3.9 TDB Does Not Have Snapshot Support +3.8.2 Status -3.9.1 Proposed Solution +Deferred. -None. At some point you say “use a real database” (but see [replay-attribute] -). +3.9 TDB Does Not Have Snapshot Support + +3.9.1 Proposed SolutionNone. At some point you say “use a real + database” (but see [replay-attribute]). But as a thought experiment, if we implemented transactions to only overwrite free entries (this is tricky: there must not be a @@ -1053,6 +1114,10 @@ rewrite some sections of the hash, too. We could then implement snapshots using a similar method, using multiple different hash tables/free tables. +3.9.2 Status + +Deferred. + 3.10 Transactions Cannot Operate in Parallel This would be useless for ldb, as it hits the index records with @@ -1069,6 +1134,10 @@ allow one write transaction to begin, but it could not commit until all r/o transactions are done. This would require a new RO_TRANSACTION_LOCK, which would be upgraded on commit. +3.10.2 Status + +Deferred. + 3.11 Default Hash Function Is Suboptimal The Knuth-inspired multiplicative hash used by tdb is fairly slow @@ -1090,6 +1159,10 @@ The seed should be created at tdb-creation time from some random source, and placed in the header. This is far from foolproof, but adds a little bit of protection against hash bombing. +3.11.2 Status + +Complete. + 3.12 Reliable Traversal Adds Complexity We lock a record during traversal iteration, and try to grab that @@ -1104,6 +1177,10 @@ indefinitely. Remove reliability guarantees; see [traverse-Proposed-Solution]. +3.12.2 Status + +Complete. + 3.13 Fcntl Locking Adds Overhead Placing a fcntl lock means a system call, as does removing one. @@ -1176,3 +1253,7 @@ tdb_open (see [attributes]) to provide replay/trace hooks, which could become the basis for this and future parallel transactions and snapshot support. +3.15.2 Status + +Deferred. +