8 ms·

How the append-only btree works (2010)

209 points by kevmo314 3y ago

seunosewa 3y ago
Append-only struxtures are not efficient enough for general use. You're paying a steep price for creating a snapshot of the data for every single operation. I saw this when I was playing with Scala's immutable and mutable data structures - written by the same team - ages ago. The immutable structures were much slower for common operations. The fastest databases tend to use undo logs to re-construct snapshots when they are needed.
- vlovich123 3y ago
  A mutable approach requires a write ahead log meaning you have to copy the data twice on every write which seems worse.
  - hyc_symas 3y ago
    There's an obvious tradeoff. With a 4K page size, the breakeven point is around 768 bytes per record. For larger records, the WAL approach is less efficient than LMDB. For smaller records, the WAL is more efficient in terms of write amplification. All thoroughly explored here http://www.lmdb.tech/bench/ondisk/ http://www.lmdb.tech/bench/ondisk/
  - vajrabum 3y ago
    In a well designed database system (hardware!) you aren't going to use the same CPU, disk or controller to write the log and the data structure. So the performance penalty if any is going to be low.
    - loeg 3y ago
      Now you’re paying for double the hardware.
    - vlovich123 3y ago
      Low but non 0 and you’re still duplicating the values written to disk. So your SSD lifetime is decreased and this is effectively a RAID0 layout which means data loss is risky too.
  - iambvk 3y ago
    It is: two writes for write ahead log vs. log-n (tree-height) writes for CoW
- londons_explore 3y ago
  I don't think this is generally true. Especially on mediums where sequentially writing large blocks is faster than random writes, you get much better performance to use a log-structured datastructure and put anything new/any changes at the end. Due to the design of modern SSD's, 'write in place' is pretty much an illusion.
- scottlamb 3y ago
  You can build real useful systems on them. For example, Gmail used to be implemented on top of GFS as two append-only files per user: the zlog and the index. The zlog held (zlib-compressed) operations such as "add this message" and "delete this message". The index was an append-only btree as described here. It was a true index in that it didn't include the actual message contents. Those were simply pointers into the log. Thus, it was much smaller than the zlog and its efficiency was less of a concern. Also, periodically both files were "compacted" by writing a fresh log (that built the current state in the most efficient way) and matching index. This was primarily for privacy (otherwise your deleted messages would never actually go away) but also improved efficiency. Gmail's now built on top of Spanner so uses a log-structured merge tree. Still append-only files but a bit different. Files aren't per user but per some arbitrary key range boundary; no more btree; multiple layers with the top ones getting compacted more frequently; etc.
  - pclmulqdq 3y ago
    It's worth noting that Google's internal scale-out filesystem is append-only (for various distributed systems and operational reasons), so you end up with append-only data structures proliferating in that ecosystem. That does not necessarily mean that the append-only data structures were chosen for any technical merit other than ability to be implemented on the append-only filesystem.
    - btilly 3y ago
      So if we ignore the technical merits based on which append-only data structures were chosen in general, we don't necessarily have additional technical merits for any particular time append-only was chosen. The reasons why append-only structures were chosen in general apply surprisingly often to any particular system that scales to large data, which would like to be robust to a wide variety of real world problems. You won't see it in looking at the data structure because the hard parts are abstracted away from you. But you'll see it if you try to reimplement the same system from scratch, then scale it up to production.
      - 3y ago
- valenterry 3y ago
  That usually happens when you try to work with immutable data structures like you are used to with mutable datastructures. For example, if you append to a mutable list then it's going to be fast. But prepending to it is much slower. With immutable lists, it's the other way around. Not knowing that will make you think that immutable datastructures are generally slow, but they are not. That being said, I would say they are generally more tricky, so it's good to understand in which cases it's worth to sacrifize safety and readability and switch to mutable datastructures for performance reasons.
- slashdev 3y ago
  LMDB is a strong counter-example to your argument. Based on its benchmarks, you're wrong. [1] Yes immutable in-memory data structures are slower than their mutable counterpoints, but we're not talking about either of those here. Databases are not in-memory data structures. [1] http://www.lmdb.tech/bench/microbench/july/ http://www.lmdb.tech/bench/microbench/july/
- halayli 3y ago
  You're comparing apples and oranges. Anytime you write/modify on an SSD you're writing on a new page. So you might as well leverage this behavior to your advantage. It has several benefits when it comes to implementing transactions.
- teo_zero 3y ago
  IF reads dominate writes, and multiple threads read the data concurrently, this approach may win by eliminating the need for locks.
- hinkley 3y ago
  You probably need something special for batch operations. Adding five records in one transaction shouldn’t pay >= 5 times as much as a single one. You need a different API for something like that however.
  - joshlemer 3y ago
    Yes, for instance Clojure's "transients" as well as the JavaScript "immer" library
- cryptonector 3y ago
  The biggest cost to copy-on-write data structures is write magnification. Adding a log to amortize that cost helps a lot. That's what the ZFS intent log does. Any CoW b-tree scheme can benefit from that approach. The benefits of CoW data structures are tremendous: - easy to reason about - easy to multi-thread for reading - O(1) snashopts (and clones) The downsides of CoW data structures are mainly: - the need to amortize write magnification - difficulty in multi-threading writes
- joshlemer 3y ago
  Scala's immutable data structures, and especially the way they are used idiomatically and most obviously, have a lot of performance issues that are much bigger than the basic cost of persistent data structures. Namely, most commonly I will see developers default to pipelining strict operations like myList.map(...).filter(...).flatMap(...).collect(...).take(2) which forces/materializes the whole collection in memory for every operation. Better would be to first transform the list into a lazy view or iterator with myList.view or myList.iterator, and then do the pipeline. They also lack the ability to perform multiple updates in a batch, except for some very limited cases. Other implementations like Clojure's support "transients" where you get access to mutate the data structure over and over again (as well as do reads), and then freeze the structure in place as a new persistent collection. JavaScript libraries like immer allow for the same thing. Scala's collections don't generally support this except in the form of "builders" which don't support reads and also don't support all the write access patterns (such as updating a vector at a specific index, or removing a key from a map/set, etc).
btilly 3y ago
One of the advantages of this kind of architecture is that if one reader is reading the old tree while it is replaced, it just works. Databases are really good at having multiple versions of the same data structure be accessible at the same time. I hand rolled some similar data structures in higher order languages when I couldn't find any Python packages that gave me the same capability. But I couldn't figure out what a good name would be for, say, a dictionary that could have multiple concurrent versions. So I never went anything where with that.
- Hnrobert42 3y ago
  As Phil Karlton, “There are only two hard things in computer science: cache validation and naming things.” Seems like you found a way to work on both! https://skeptics.stackexchange.com/questions/19836/has-phil-karlton-ever-said-there-are-only-two-hard-things-in-computer-science#39178 https://skeptics.stackexchange.com/questions/19836/has-phil-...
  - timeimp 3y ago
    I always have to add the "and off-by-one" at the end. Nothing like reading memory you don't own!
    - airstrike 3y ago
      There are actually only two hard problems in computer science: 0) Cache invalidation 1) Naming things 5) Asynchronous callbacks 2) Off-by-one errors 3) Scope creep 6) Bounds checking
      - alternative_a 3y ago
        Let’s be pedantic here and get all religious over the words “Science” and “hard”. Computer “science” has a difficult conceptual problem with caching. The optimal cache, this science tells us, is indistinguishable from a fortune teller who is never wrong (oracle). Fortune telling is a “hard” problem for a science based on reasoning. The best we can do is hedge bets (which is what the science of caching focuses on). This same science also has a difficulty with naming things. Now numbering things is easy and science loves maths and maths love sciences, but science and letters have a more difficult history. Science would approve of “factoryfactoryfactoryImpl” btw ... it’s “a rational scheme of naming”. . Here we see a “science” that is facing actual difficulties. The rest of your list are difficult but not “hard”. The science of these matters is clear and the rest is up to the “scientists” struggling with “scope creep” and “bounds checking” ..
zogomoox 3y ago
Instead of cloning the branches all the way up to root, wouldn't it be more efficient to just write delta-records, so a structure per inner node that says "it's like this original node, but with the following modifications x,y,z"
- PartiallyTyped 3y ago
  You may want to rebalance a tree, or you may want to have multiple readers while a writer exists without relying on mutexes or locking.
  - zogomoox 3y ago
    as long as you don't modify the original nodes that would still work, no locks needed.
- btilly 3y ago
  Efficient in what way? Yes, a delta record would be smaller. But now you have to fetch both the new and the old, plus do computation to figure out what you have. This is trading off space and time. I'm going to go to a reasonably low level to explain this. Databases have generally found that the right tradeoff between space and time is to always work in terms of pages of fixed size. Now all reads are memory aligned, of known size. All writes are as well. And inside the CPU, processing a page in the most straightforward and predictable way possible is very fast. In particular you want to avoid complex logic that introduces too many pipeline stalls. If you're going to work with pages anyways, you want to find ways to fetch as few pages as possible. Only have this page point to that page where you really need to. And put as much as reasonable on each page. The name of the game is to fetch as few pages as you need, and get everything you need from a page when you fetch it. Because when you're getting a new page, often you have to wait for a disk read. That's slow. It used to be really slow, you needed to wait for the right part of the disk to rotate around. Those disks went at something like 7200 rpm, but that means 120 revolutions per second, which means you're waiting for anywhere from 0 to 8.333... milliseconds for the read. Now consider reading through a million record database... That's where a BTree comes in. It is a tree structure built around a page layout. When a page gets too full, it is split and one record is promoted to the level above. When the top page gets too full, a new level is created at top. That keeps it perfectly balanced at all times. So you can get to any record in very few reads. And if you're walking the whole data structure, a single page generally has many records.
hoytech 3y ago
LMDB [0] was derived from this project, as mentioned in its copyright notice section [1]. [0] http://www.lmdb.tech/doc/ http://www.lmdb.tech/doc/ [1] https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1058cad1dd08b74/libraries/liblmdb/lmdb.h#L150-L152 https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1...
- jnwatson 3y ago
  Importantly, the LMDB API allows append mode, and it is very fast.
bob1029 3y ago
Some years ago I was playing around with the idea of an append-only splay tree for storing a database file. The thinking was that the algorithm would keep recently-accessed items at the business end of the log (in addition to any new/updated/deleted items). This concept is clearly quite heavy on writes, but the tradeoff is that you would then have the ability to expire unused entries simply by picking an offset in the log and chopping everything that precedes it. Any record accessed more recently than that cutoff point would be guaranteed to have been written one or more times later on in the log. Any access would result in a new modified tree & root node being written, but the prototype did batch IO using an MPSC queue abstraction which meant that I could amortize things a bit. Multiple transactions could fit in a single IO command if they are issued from different threads, occur within a small slice of time and are smaller than the block size.
paulsutter 3y ago
Every historical version of the database is available as a snapshot. The metadata block should point back to previous meta block(s), not just the new root And of course emphasizing the closing statement: > there is no need for a transaction log, because the database file is the transaction log
ww520 3y ago
The immutable b+tree is a great idea, except it generates a tremendous amount of garbage pages. Every update of a record generates several new pages along the path of the tree. There are two additional techniques to make immutable b+tree practical. One is to reclaim stale unreachable pages after the transactions using them have closed. Two is to use a pair of oscillating fixed location meta pages. A page is active if it’s in the latest snapshot or it is in use by an open transition; otherwise, it’s unreadable and can be reclaimed. When a transaction closes, it hands its list of in-use pages to the reclaimer. The reclaimer tracks these pages. When no other open transactions hold on to a page, it can be reclaimed. When the write transaction commits, it hands the list of old pages being overwritten to the reclaimer as candidates for freeing, pending no open transactions using them. The reclaimer can batch a number of reclaimed pages together to update the free page list, by appending to the end of the file a page of the newly freed page pointers. Update the meta page to point to the new head page of the free page list at the end of the file. This can be done as a write transaction to keep things consistent. At a crash all the pending reclaiming pages in memory are lost and the garbage pages in disk linger. This requires periodic garbage collection or compaction. The most frequently updated page in the tree is the meta page. Every write transaction updates it. This creates a lot of garbage pages. The second technique addresses this problem. One insight is that the meta page is only needed when a new transaction begins by finding the tree root of the latest committed snapshot. That means we only need two copies of the meta pages, one for the last committed snapshot and one for the new pending write transaction. When the write transaction commits, the pending meta page becomes the latest committed snapshot. The other page becomes available for the next pending transaction. We can have two fixed location meta pages, oscillating between the latest committed snapshot and the pending new transaction. The fixed location removes the need to search for the meta page from the end of file.
- dragontamer 3y ago
  > except it generates a tremendous amount of garbage pages Note that this is an advantage on say, controller-less NAND Flash (JFFS-like embedded NAND Flash). More modern Flash drives have embedded FTL (flash translation layers) that internalizes that garbage collection process. But *someone* had to write the FTL to begin with, and methinks this append-only btree would work very well for that. ------- In NAND Flash, only 10,000ish erase/write cycles are allowed before any block becomes unusable. (Depending on tech of course: could be 1000 on QLC could be 100k on SLC). All that garbage helps cycle the write/erase cycles across the drive more evenly / more consistently. Especially if you combine that garbage with TRIM-like commands. That might be a little bit too low level for a lot of folks though.
packetlost 3y ago
One enhancement I've toyed with in the past is to have subtrees beneath each leaf node for the historical data for each record. You switch the indexing value to the timestamp of record insertion time or a TX number and keep inserting in append-only fashion. There's some enhancements you can make because the common case is for the key to be a monotonically increasing number, but nothing is strictly necessary. I'd love to build a datalog system on top of something like that at some point, even if it's just for fun.
hlship 3y ago
In such a system, how does a reader find the root node? I'd be concerned about a) readers seeing a partial write to disk (or page buffer) during an update or b) a crash while the writer writes to disk. I could imagine using two files, one containing the actual b-tree, the second containing the offset to the latest root note; the second file gets overwritten only after a successful write is verifiably written to disk. Datomic's (https://www.datomic.com/ https://www.datomic.com/) architecture is similar to this, but uses many write-once "segments" (which could be files in EFS or S3, or rows in DynamoDB or other stores).
- twoodfin 3y ago
  There’s a “canonical” pointer to the root node which is updated atomically on every append. For an in-memory database, a CAS is adequate. Persistent stores ultimately need some kind of file-level locking. If you look at the Apache Iceberg spec, you get a good idea of how this works: The only “mutability” in that universe is the root table pointer in the catalog.
- ww520 3y ago
  The pointer to the root tree node is stored in the last committed metadata page. A read transaction starts with the reading of the metadata page. Reaching the partial written pages is impossible as the writer has not committed the latest metadata page yet. The transaction is committed when the latest metadata page is written as the last step.
  - hyc_symas 3y ago
    A read txn starts with reading the last page of the file and searching backward for a valid metapage. This can be time-consuming if the previous use crashed while a large write was in progress. Yet another reason LMDB doesn't use append-only design.
JensRantil 3y ago
IIRC, this is how CouchDB was implemented. The benefit is that it was resilient to crash without needing a write-ahead log. The downside was that it required running background compaction of the B+tree regularly.
- josephg 3y ago
  LMDB works the same way. But it also stores a second data structure on disk listing all free blocks. Writes preferentially take free blocks when they’re available. The result is it doesn’t need any special compaction step. It sort of automatically compacts constantly.
toolslive 3y ago
with append-only data structures, you could turn the fact that you rewrite the path from the node to the root to your advantage and rebalance. This means you abandon the "balanced" property and use update statistics to get an optimal shape. Who cares about the length of paths to parts of the tree you never visit?
- kragen 3y ago
  this is how splay trees work, but you might actually care about the lengths of paths to parts of the tree you rarely visit; for many real systems, worst-case response time is more important than throughput
o11c 3y ago
One thing that's not explicitly mentioned: append-only trees necessarily lack `parent` pointers. This means that your "iterator" can't be a lightweight type, it has to contain an array of parent nodes to visit (again) later. You can use a fixed-size array if you can reason about the maximum height of the tree (for a balanced binary tree, this means around `2*POINTER_BITS`, which is 1024 bytes on a 64-bit platform; it will be less for a B-tree (`2*log(POINTER_MAX, CHILDREN_PER_NODE)`) but you now have to either track or re-scan for the index of the child you just returned from). Beware buffer overflow logic bugs if your tree isn't as balanced as you thought!

209 points by kevmo314 3y ago

Append-only struxtures are not efficient enough for general use. You're paying a steep price for creating a snapshot of the data for every single operation. I saw this when I was playing with Scala's immutable and mutable data structures - written by the same team - ages ago. The immutable structures were much slower for common operations. The fastest databases tend to use undo logs to re-construct snapshots when they are needed.

vlovich123 3y ago
A mutable approach requires a write ahead log meaning you have to copy the data twice on every write which seems worse.
- hyc_symas 3y ago
  There's an obvious tradeoff. With a 4K page size, the breakeven point is around 768 bytes per record. For larger records, the WAL approach is less efficient than LMDB. For smaller records, the WAL is more efficient in terms of write amplification. All thoroughly explored here http://www.lmdb.tech/bench/ondisk/ http://www.lmdb.tech/bench/ondisk/
- vajrabum 3y ago
  In a well designed database system (hardware!) you aren't going to use the same CPU, disk or controller to write the log and the data structure. So the performance penalty if any is going to be low.
  - loeg 3y ago
    Now you’re paying for double the hardware.
  - vlovich123 3y ago
    Low but non 0 and you’re still duplicating the values written to disk. So your SSD lifetime is decreased and this is effectively a RAID0 layout which means data loss is risky too.
- iambvk 3y ago
  It is: two writes for write ahead log vs. log-n (tree-height) writes for CoW
londons_explore 3y ago
I don't think this is generally true. Especially on mediums where sequentially writing large blocks is faster than random writes, you get much better performance to use a log-structured datastructure and put anything new/any changes at the end. Due to the design of modern SSD's, 'write in place' is pretty much an illusion.
scottlamb 3y ago
You can build real useful systems on them. For example, Gmail used to be implemented on top of GFS as two append-only files per user: the zlog and the index. The zlog held (zlib-compressed) operations such as "add this message" and "delete this message". The index was an append-only btree as described here. It was a true index in that it didn't include the actual message contents. Those were simply pointers into the log. Thus, it was much smaller than the zlog and its efficiency was less of a concern. Also, periodically both files were "compacted" by writing a fresh log (that built the current state in the most efficient way) and matching index. This was primarily for privacy (otherwise your deleted messages would never actually go away) but also improved efficiency. Gmail's now built on top of Spanner so uses a log-structured merge tree. Still append-only files but a bit different. Files aren't per user but per some arbitrary key range boundary; no more btree; multiple layers with the top ones getting compacted more frequently; etc.
- pclmulqdq 3y ago
  It's worth noting that Google's internal scale-out filesystem is append-only (for various distributed systems and operational reasons), so you end up with append-only data structures proliferating in that ecosystem. That does not necessarily mean that the append-only data structures were chosen for any technical merit other than ability to be implemented on the append-only filesystem.
  - btilly 3y ago
    So if we ignore the technical merits based on which append-only data structures were chosen in general, we don't necessarily have additional technical merits for any particular time append-only was chosen. The reasons why append-only structures were chosen in general apply surprisingly often to any particular system that scales to large data, which would like to be robust to a wide variety of real world problems. You won't see it in looking at the data structure because the hard parts are abstracted away from you. But you'll see it if you try to reimplement the same system from scratch, then scale it up to production.
    - 3y ago
valenterry 3y ago
That usually happens when you try to work with immutable data structures like you are used to with mutable datastructures. For example, if you append to a mutable list then it's going to be fast. But prepending to it is much slower. With immutable lists, it's the other way around. Not knowing that will make you think that immutable datastructures are generally slow, but they are not. That being said, I would say they are generally more tricky, so it's good to understand in which cases it's worth to sacrifize safety and readability and switch to mutable datastructures for performance reasons.
slashdev 3y ago
LMDB is a strong counter-example to your argument. Based on its benchmarks, you're wrong. [1] Yes immutable in-memory data structures are slower than their mutable counterpoints, but we're not talking about either of those here. Databases are not in-memory data structures. [1] http://www.lmdb.tech/bench/microbench/july/ http://www.lmdb.tech/bench/microbench/july/
halayli 3y ago
You're comparing apples and oranges. Anytime you write/modify on an SSD you're writing on a new page. So you might as well leverage this behavior to your advantage. It has several benefits when it comes to implementing transactions.
teo_zero 3y ago
IF reads dominate writes, and multiple threads read the data concurrently, this approach may win by eliminating the need for locks.
hinkley 3y ago
You probably need something special for batch operations. Adding five records in one transaction shouldn’t pay >= 5 times as much as a single one. You need a different API for something like that however.
- joshlemer 3y ago
  Yes, for instance Clojure's "transients" as well as the JavaScript "immer" library
cryptonector 3y ago
The biggest cost to copy-on-write data structures is write magnification. Adding a log to amortize that cost helps a lot. That's what the ZFS intent log does. Any CoW b-tree scheme can benefit from that approach. The benefits of CoW data structures are tremendous: - easy to reason about - easy to multi-thread for reading - O(1) snashopts (and clones) The downsides of CoW data structures are mainly: - the need to amortize write magnification - difficulty in multi-threading writes
joshlemer 3y ago
Scala's immutable data structures, and especially the way they are used idiomatically and most obviously, have a lot of performance issues that are much bigger than the basic cost of persistent data structures. Namely, most commonly I will see developers default to pipelining strict operations like myList.map(...).filter(...).flatMap(...).collect(...).take(2) which forces/materializes the whole collection in memory for every operation. Better would be to first transform the list into a lazy view or iterator with myList.view or myList.iterator, and then do the pipeline. They also lack the ability to perform multiple updates in a batch, except for some very limited cases. Other implementations like Clojure's support "transients" where you get access to mutate the data structure over and over again (as well as do reads), and then freeze the structure in place as a new persistent collection. JavaScript libraries like immer allow for the same thing. Scala's collections don't generally support this except in the form of "builders" which don't support reads and also don't support all the write access patterns (such as updating a vector at a specific index, or removing a key from a map/set, etc).

btilly 3y ago

One of the advantages of this kind of architecture is that if one reader is reading the old tree while it is replaced, it just works. Databases are really good at having multiple versions of the same data structure be accessible at the same time. I hand rolled some similar data structures in higher order languages when I couldn't find any Python packages that gave me the same capability. But I couldn't figure out what a good name would be for, say, a dictionary that could have multiple concurrent versions. So I never went anything where with that.

Hnrobert42 3y ago
As Phil Karlton, “There are only two hard things in computer science: cache validation and naming things.” Seems like you found a way to work on both! https://skeptics.stackexchange.com/questions/19836/has-phil-karlton-ever-said-there-are-only-two-hard-things-in-computer-science#39178 https://skeptics.stackexchange.com/questions/19836/has-phil-...
- timeimp 3y ago
  I always have to add the "and off-by-one" at the end. Nothing like reading memory you don't own!
  - airstrike 3y ago
    There are actually only two hard problems in computer science: 0) Cache invalidation 1) Naming things 5) Asynchronous callbacks 2) Off-by-one errors 3) Scope creep 6) Bounds checking
    - alternative_a 3y ago
      Let’s be pedantic here and get all religious over the words “Science” and “hard”. Computer “science” has a difficult conceptual problem with caching. The optimal cache, this science tells us, is indistinguishable from a fortune teller who is never wrong (oracle). Fortune telling is a “hard” problem for a science based on reasoning. The best we can do is hedge bets (which is what the science of caching focuses on). This same science also has a difficulty with naming things. Now numbering things is easy and science loves maths and maths love sciences, but science and letters have a more difficult history. Science would approve of “factoryfactoryfactoryImpl” btw ... it’s “a rational scheme of naming”. . Here we see a “science” that is facing actual difficulties. The rest of your list are difficult but not “hard”. The science of these matters is clear and the rest is up to the “scientists” struggling with “scope creep” and “bounds checking” ..

zogomoox 3y ago

Instead of cloning the branches all the way up to root, wouldn't it be more efficient to just write delta-records, so a structure per inner node that says "it's like this original node, but with the following modifications x,y,z"

PartiallyTyped 3y ago
You may want to rebalance a tree, or you may want to have multiple readers while a writer exists without relying on mutexes or locking.
- zogomoox 3y ago
  as long as you don't modify the original nodes that would still work, no locks needed.
btilly 3y ago
Efficient in what way? Yes, a delta record would be smaller. But now you have to fetch both the new and the old, plus do computation to figure out what you have. This is trading off space and time. I'm going to go to a reasonably low level to explain this. Databases have generally found that the right tradeoff between space and time is to always work in terms of pages of fixed size. Now all reads are memory aligned, of known size. All writes are as well. And inside the CPU, processing a page in the most straightforward and predictable way possible is very fast. In particular you want to avoid complex logic that introduces too many pipeline stalls. If you're going to work with pages anyways, you want to find ways to fetch as few pages as possible. Only have this page point to that page where you really need to. And put as much as reasonable on each page. The name of the game is to fetch as few pages as you need, and get everything you need from a page when you fetch it. Because when you're getting a new page, often you have to wait for a disk read. That's slow. It used to be really slow, you needed to wait for the right part of the disk to rotate around. Those disks went at something like 7200 rpm, but that means 120 revolutions per second, which means you're waiting for anywhere from 0 to 8.333... milliseconds for the read. Now consider reading through a million record database... That's where a BTree comes in. It is a tree structure built around a page layout. When a page gets too full, it is split and one record is promoted to the level above. When the top page gets too full, a new level is created at top. That keeps it perfectly balanced at all times. So you can get to any record in very few reads. And if you're walking the whole data structure, a single page generally has many records.

hoytech 3y ago

LMDB [0] was derived from this project, as mentioned in its copyright notice section [1]. [0] http://www.lmdb.tech/doc/ http://www.lmdb.tech/doc/ [1] https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1058cad1dd08b74/libraries/liblmdb/lmdb.h#L150-L152 https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1...

jnwatson 3y ago
Importantly, the LMDB API allows append mode, and it is very fast.

bob1029 3y ago

Some years ago I was playing around with the idea of an append-only splay tree for storing a database file. The thinking was that the algorithm would keep recently-accessed items at the business end of the log (in addition to any new/updated/deleted items). This concept is clearly quite heavy on writes, but the tradeoff is that you would then have the ability to expire unused entries simply by picking an offset in the log and chopping everything that precedes it. Any record accessed more recently than that cutoff point would be guaranteed to have been written one or more times later on in the log. Any access would result in a new modified tree & root node being written, but the prototype did batch IO using an MPSC queue abstraction which meant that I could amortize things a bit. Multiple transactions could fit in a single IO command if they are issued from different threads, occur within a small slice of time and are smaller than the block size.

paulsutter 3y ago

Every historical version of the database is available as a snapshot. The metadata block should point back to previous meta block(s), not just the new root And of course emphasizing the closing statement: > there is no need for a transaction log, because the database file is the transaction log

ww520 3y ago

The immutable b+tree is a great idea, except it generates a tremendous amount of garbage pages. Every update of a record generates several new pages along the path of the tree. There are two additional techniques to make immutable b+tree practical. One is to reclaim stale unreachable pages after the transactions using them have closed. Two is to use a pair of oscillating fixed location meta pages. A page is active if it’s in the latest snapshot or it is in use by an open transition; otherwise, it’s unreadable and can be reclaimed. When a transaction closes, it hands its list of in-use pages to the reclaimer. The reclaimer tracks these pages. When no other open transactions hold on to a page, it can be reclaimed. When the write transaction commits, it hands the list of old pages being overwritten to the reclaimer as candidates for freeing, pending no open transactions using them. The reclaimer can batch a number of reclaimed pages together to update the free page list, by appending to the end of the file a page of the newly freed page pointers. Update the meta page to point to the new head page of the free page list at the end of the file. This can be done as a write transaction to keep things consistent. At a crash all the pending reclaiming pages in memory are lost and the garbage pages in disk linger. This requires periodic garbage collection or compaction. The most frequently updated page in the tree is the meta page. Every write transaction updates it. This creates a lot of garbage pages. The second technique addresses this problem. One insight is that the meta page is only needed when a new transaction begins by finding the tree root of the latest committed snapshot. That means we only need two copies of the meta pages, one for the last committed snapshot and one for the new pending write transaction. When the write transaction commits, the pending meta page becomes the latest committed snapshot. The other page becomes available for the next pending transaction. We can have two fixed location meta pages, oscillating between the latest committed snapshot and the pending new transaction. The fixed location removes the need to search for the meta page from the end of file.

dragontamer 3y ago
> except it generates a tremendous amount of garbage pages Note that this is an advantage on say, controller-less NAND Flash (JFFS-like embedded NAND Flash). More modern Flash drives have embedded FTL (flash translation layers) that internalizes that garbage collection process. But *someone* had to write the FTL to begin with, and methinks this append-only btree would work very well for that. ------- In NAND Flash, only 10,000ish erase/write cycles are allowed before any block becomes unusable. (Depending on tech of course: could be 1000 on QLC could be 100k on SLC). All that garbage helps cycle the write/erase cycles across the drive more evenly / more consistently. Especially if you combine that garbage with TRIM-like commands. That might be a little bit too low level for a lot of folks though.

packetlost 3y ago

One enhancement I've toyed with in the past is to have subtrees beneath each leaf node for the historical data for each record. You switch the indexing value to the timestamp of record insertion time or a TX number and keep inserting in append-only fashion. There's some enhancements you can make because the common case is for the key to be a monotonically increasing number, but nothing is strictly necessary. I'd love to build a datalog system on top of something like that at some point, even if it's just for fun.

hlship 3y ago

In such a system, how does a reader find the root node? I'd be concerned about a) readers seeing a partial write to disk (or page buffer) during an update or b) a crash while the writer writes to disk. I could imagine using two files, one containing the actual b-tree, the second containing the offset to the latest root note; the second file gets overwritten only after a successful write is verifiably written to disk. Datomic's (https://www.datomic.com/ https://www.datomic.com/) architecture is similar to this, but uses many write-once "segments" (which could be files in EFS or S3, or rows in DynamoDB or other stores).

twoodfin 3y ago
There’s a “canonical” pointer to the root node which is updated atomically on every append. For an in-memory database, a CAS is adequate. Persistent stores ultimately need some kind of file-level locking. If you look at the Apache Iceberg spec, you get a good idea of how this works: The only “mutability” in that universe is the root table pointer in the catalog.
ww520 3y ago
The pointer to the root tree node is stored in the last committed metadata page. A read transaction starts with the reading of the metadata page. Reaching the partial written pages is impossible as the writer has not committed the latest metadata page yet. The transaction is committed when the latest metadata page is written as the last step.
- hyc_symas 3y ago
  A read txn starts with reading the last page of the file and searching backward for a valid metapage. This can be time-consuming if the previous use crashed while a large write was in progress. Yet another reason LMDB doesn't use append-only design.

JensRantil 3y ago

IIRC, this is how CouchDB was implemented. The benefit is that it was resilient to crash without needing a write-ahead log. The downside was that it required running background compaction of the B+tree regularly.

josephg 3y ago
LMDB works the same way. But it also stores a second data structure on disk listing all free blocks. Writes preferentially take free blocks when they’re available. The result is it doesn’t need any special compaction step. It sort of automatically compacts constantly.

toolslive 3y ago

with append-only data structures, you could turn the fact that you rewrite the path from the node to the root to your advantage and rebalance. This means you abandon the "balanced" property and use update statistics to get an optimal shape. Who cares about the length of paths to parts of the tree you never visit?

kragen 3y ago
this is how splay trees work, but you might actually care about the lengths of paths to parts of the tree you rarely visit; for many real systems, worst-case response time is more important than throughput

o11c 3y ago

One thing that's not explicitly mentioned: append-only trees necessarily lack `parent` pointers. This means that your "iterator" can't be a lightweight type, it has to contain an array of parent nodes to visit (again) later. You can use a fixed-size array if you can reason about the maximum height of the tree (for a balanced binary tree, this means around `2*POINTER_BITS`, which is 1024 bytes on a 64-bit platform; it will be less for a B-tree (`2*log(POINTER_MAX, CHILDREN_PER_NODE)`) but you now have to either track or re-scan for the index of the child you just returned from). Beware buffer overflow logic bugs if your tree isn't as balanced as you thought!