6 ms·
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 p
by 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.
- epcoa 3y agoThere are more appropriate and better data structures for an FTL especially with the assumption of some amount of auxiliary RAM (either host or on controller). Much of this literature is open access/free. “All that garbage helps cycle the write/erase cycles across the drive more evenly” Well no, you still want to minimize garbage production (and related GC overhead). Wear leveling doesn’t mean produce more garbage.
- dragontamer 3y ago> Well no, you still want to minimize garbage production (and related GC overhead). Wear leveling doesn’t mean produce more garbage. Surely some % of garbage helps as you're garbage collecting and reliably trying to shuffle data around to wear-level more evenly? Lets say you have 99% used data and 1% garbage. You have very little room for (static) wear leveling. Ex: If you're writing 10MB of new data, and your drive is 99% full of allocated data... you'd have to move 1000MB of data around to "find" the 10MB of garbage, on the average. In the other extreme case: 0% data used and 100% garbage (say a TRIM operation just completed), then you simply just write 10MB without having to worry about moving any data around. The 50% data + 50% garbage scales as appropriate. 10MB of written new data will need you to find and coalesce 10MB of garbage to write the new data. This will happen after moving 20MB of overall data around. ---------- I'm oversimplifying of course. But even in a real life system, I'd expect that the more "garbage" you have sitting around, the better the various algorithms work for FTL / SSD (static or dynamic) wear leveling.
- epcoa 3y agoI can’t state any more clearly: minimize the production of garbage. “Surely some % of garbage helps as you're garbage collecting ” Garbage that doesn’t exist doesn’t need collecting. The flaw here is confusing free space with garbage. You shouldn’t have written in the first place if you could have avoided it. Every environmentalist knows this: RRR, the first R is reduce not recycle.
- deleted 3y ago
- codetrotter 3y agoThis description reminds me of a document I read about how ZFS is implemented. In particular, how snapshots work in ZFS, and what happens when you delete a snapshot.
- cryptonector 3y agoIt's a very similar idea. Traditional Unix-ish filesystems, with inodes and indirect nodes are a lot like b-trees, but ones where the indices are block numbers and where you can only append indices, trim, or replace indices. The ZIL (ZFS intent log) is a mechanism for amortizing the write magnification of copy on write trees.
- thechao 3y agoI am immediately nerd-sniped by this. Is there any code out there you know of I can see? The dual meta-data pages sounds precisely like double-buffering (from graphics; my domain of expertise). I am also drawn to append-only-like and persistent data-structures.
- hyc_symas 3y agoI had never read any papers on shadow paging when I wrote LMDB. I refer to it as double-buffering in the original LMDB paper because of my own prior experience writing graphics code. You can find the (L)MDB paper here https://openldap.org/pub/ https://openldap.org/pub/ Other commenters noting that append-only isn't efficient enough for general use are correct. We found this as well in the early days of testing LMDB with append-only behavior; 99% of pages were obsolete after only 5 transactions. That's why LMDB is CoW but not append-only, and that's why it uses a double-buffered meta page. Bzero's work on append-only Btree was educational and illuminating, but not usable in the real world.
- hoytech 3y agoLMDB works like this. The MDB_env struct keeps pointers to both meta pages: https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1058cad1dd08b74/libraries/liblmdb/mdb.c#L1520 https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1... Which meta-page used is determined by the transaction ID (even IDs use first, odd IDs second). This is the earliest description I can find of the "shadow paging" concept: https://dl.acm.org/doi/10.1145/320521.320540 https://dl.acm.org/doi/10.1145/320521.320540 And I believe its first implementation was in IBM's System R.
- ww520 3y agoLMDB is the poster child of COW btree implementation. That paper is a good find. Thanks.
- senderista 3y agoOf course, this implies a single-writer design (not necessarily a bad thing!).
- ww520 3y agoActually immutable btree has a single writer in general since there’s no translation log and the meta page pointing to one latest tree root. Even if two write transactions updating different parts of the tree, they both need to update the same meta page, causing a contention. This is one downside (or upside depending on your need since single writer simplifies things a lot and great for sequential writes).
- namibj 3y agoYou could quite easily check if anything you care about was touched by the previous lock holder, so that they could indeed write everything but the root in parallel/concurrently. E.g. note batched operations, like "insert list elements into the immutable container", or transactions where you don't even want to see results that soon.
- ww520 3y agoThe two writers will have two different new root nodes which need to be merged, and that could trigger further merging of lower level new nodes recursively. It becomes a merging of two subtrees. The subtrees can be quite different if node-splitting happens during inserts by the writers. It quickly becomes a complicate problem.
- cryptonector 3y agoYes, CoW trees have tremendous write magnification. This is well-known. The fix is to amortize this cost by writing transactions as a log and then doing a b-tree update operation for numerous accumulated transactions. Think of ZFS and it's ZIL (ZFS Intent Log). That's exactly what the ZIL is: a CoW tree write magnification amortization mechanism.
- wredue 3y agoFFS. The fix for absolutely bonkers CoW costs is to stop buying in to this idiotic notion that “immutability is easier to reason about”. If you’re having difficulty reasoning about how to deal with major performance issues then your position is not easier to reason about. Full stop. Stop the madness!
- cryptonector 3y agoIt is easy to reason about the performance issues of CoW, and it's easy enough to reason about how to work around those issues. Ease of reasoning is a big deal when you're dealing with hundreds of millions of lines of code, as some of us do. Cognitive load is a big deal in today's world. It's why we're migrating from C to memory-safe languages.
- kragen 3y agoit's correct that aliasing makes performance harder to reason about but there are other things you might want to reason about, such as whether a subroutine terminates at all and what it returns, and immutability does make it easier to reason about those things
- ruuda 3y agoThe Hitchhiker Tree [1] addresses the write amplification at the cost of making lookups and scans slightly more expensive, by keeping a small array of "pending writes" in every non-leaf node. The entire thing is still immutable, but instead of writing a new leaf node + path from root to that leaf, in the majority of cases we only write a new root. When there is no space left in the array, all the pending values get pushed one level down at the same time, so the write amplification is amortized. [1]: https://www.youtube.com/watch?v=jdn617M3-P4 https://www.youtube.com/watch?v=jdn617M3-P4
- ww520 3y agoI believe the Bw-tree does the same thing, caching new updates in the intermediate branch nodes and only pushing the updates in batch down to the lower layers when running out of room at the branch node. These are the newer wave of algorithms to address the write amplification.
- senderista 3y agoThis idea dates to at least 1996: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5353ed87f7ec15c32d66f81a0ad9ba2f695f0855 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
- kragen 3y agocan you explain the similarities and differences between arge's 'buffer tree' and the fractal tree and hitchhiker tree? my tentative understanding is that arge's work, applied to an ordinary search tree, yields something very similar to the fractal tree, except that it will opportunistically flush buffers before they are full if the child nodes they route to must be brought in from disk anyway to answer a read query. but arge is more concerned with applying the technique to hairier data structures like segment trees and binary decision diagrams. and the hitchhiker tree seems to be precisely a copy-on-write fractal tree, no more and no less. but possibly i am misunderstanding something? there's a clear citation path, so maybe i can untangle this: greenberg describes the hitchhiker tree as 'synthesizing fractal trees and functional data structures', kuszmaul's 02011 slide deck https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-... cites brodal and fagerberg (02003, though he says 02002) and buchsbaum, goldwasser, venkatasubramanian, and westbrook (02000, though he says 02006), both of whom cite arge's 01996 paper
- mamcx 3y agoNaively thinking here, how about a 2 immutable b+tree setup: The "hot" tree is the WAL: All the data is there and copies are generated. The "cold" tree is behind: In the background move from WAL and at the same time compact it.
- ww520 3y agoThat's how the traditional transaction log + btree approach work. The append-only btree removes the need for a separate transaction log.
- senderista 3y agoI think you could view the append-only B-tree as a deamortized version of the traditional update-in-place B-tree + WAL. It's true that it eliminates the problem of maintaining a separate WAL, but only by trading it for an arguably harder problem: compacting the B-tree. It's easy and cheap to truncate the WAL; it's difficult and expensive to compact the B-tree. I guess LMDB solves this problem by only updating at page-level granularity so it can reuse entire pages without compaction, although I haven't studied its design in much detail.
- ww520 3y agoIf by compacting the tree you meant compacting the space left over by the users deleting the records, it's about the same amount of work between the two approaches. The WAL+btree case needs to merge the near empty pages and copy the remaining records while the append-only btree case needs to allocate new pages to merge in the near empty pages and fix up the parent path which can be done as a batching garbage collection phase. If by compacting you meant cleaning up the garbage pages, while the WAL+btree is simpler in truncating the WAL, the append-only btree is pretty easy. It's just doing upkeep on the free-page list. There're only three places to pay attention: 1. any page touched by a transaction (read/write) is added to the in-use list. 2. When a transaction closes, removes its touched pages from the in-use list by decrementing their in-use counters. 3. When a write transaction commits, adds all the old overwritten pages to a pending-delete list. Periodically check the pending-delete list against the in-use list and any page not in use is moved to the deleted-queue. When the deleted-queue reaches a large enough batch, create a new free-page to contain the pointers of the deleted pages from the queue. Chain up to the existing free-page list in the meta page by storing the pointer to the existing head of list in the new free-page. Append the new free-page to the db file. Update the new free-page as the new head of the free-page list in the meta page. That's it.
- jojohohanon 3y agoI think the insight here is that garbage is garbage and the generational hypothesis holds for DB trees as well. So if we track and treat young nodes specially, we can then promote a subset of them into the permanent tree and dispose of the rest. Per the hypothesis, nodes in the permanent tree will also die, but at a lower rate.