Hacker News Reader

The 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

I 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.

This idea dates to at least 1996: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

can 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-... 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

I think the main difference between Buffer Tree (Arge, Brodal and Fagerberg) and the more modern B-epsilon/Fractal/Hitchhiker Trees is what's stored in the branch buffer. Buffer Tree stores the data in the buffer. The newer Trees store the commands on data in the buffer, i.e. storing [insert(x), delete(y), update(a: 1), upsert(b: 2)] instead of [x, y, 1, 2]. The command+value are the data being migrated to the lower layers. The older papers just allude to "data" and show the asymptotic analysis.

Having commands is better because you can preserve the order of operations as multiple operations against the same record coming down the layers. Also it can short-circuit query at higher nodes, e.g. it's deleted. Upsert is much faster with a single upsert command added to the root node's buffer than the typical query-modify-write cycle.

thanks, this seems in agreement with what i thought, except that i hadn't thought about the upsert advantage

Here're what I found on the idea of adding buffers to branch nodes. L. Arge described the Buffer Tree idea in 1995 with (a,b)-Tree for other data structures. Brodal and Fagerberg formalized it for B+Tree in 2003. There's also the more modern Bε-Tree, the B-epsilon Tree, with similar idea, used in the BetrFS file system and various DBs. Tokutek built TokuDB using a similar idea and called it Fractal Tree (which was derived from Bε-Tree). Hitchhicker Tree is the append-only version of Fractal Tree, similar to the append-only B+Tree.

* L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 334–345, Springer Verlag, Berlin. 1995. https://link.springer.com/chapter/10.1007/3-540-60220-8_74

* G. S. Brodal, R. Fagerberg. Lower Bounds for External Memory Dictionaries. 2003. https://cs.au.dk/~gerth/papers/soda03.pdf

* Bε-Tree, https://www.betrfs.org/, https://www.youtube.com/watch?v=fBt5NuNsoII. An Introduction to Bε-trees and Write-Optimization, http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf, https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s

* Tokutek. How Fractal Trees Work. 2011. https://www.percona.com/blog/wp-content/uploads/2011/11/how-...

* Hitchhiker Tree. 2016. https://github.com/datacrypt-project/hitchhiker-tree

Yes, 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.

FFS. 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!

It 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.

it'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

Runtime immutability does not make anything easier to reason about.

Its only result is adding bugs and performance deficits.

haha

Tell that to NVMe zoned namespaces. Outside of RAM, immutable data structures exist for device technology (e.g. MLC NAND) inherent reasons.

I'm not familiar with ZFS internals beyond the deduplication part. Is that just the traditional transaction log + btree update approach most databases used? Does ZFS support transactional reading and writing?

> Does ZFS support transactional reading and writing?

I don't know that I understand your question. ZFS supports POSIX transactional semantics, which is not ACID, though ZFS's design could support ACID.

> Is that just the traditional transaction log + btree update approach most databases used?

Basically, yes. The idea is to write a sequential log of a) data blocks, b) metadata operations (e.g., renames) to support fast crash recovery. During normal operation ZFS keeps in-memory data structures up to date but delays writing new tree transactions so as to amortize write magnification. On unclean shutdown ZFS checks that all transactions recorded in the ZIL have been written to the tree or else it will do it by a) rewinding the ZFS state to the newest fully-written transaction, b) loading the contents of the ZIL from that point forward.

Because the ZIL was designed at a time when fast flash devices were expensive, it's really a separate thing from the rest of the tree. If one were to start over one might integrate the ZIL with the rest of the system more tightly so as to further minimize write magnification (e.g., data blocks written to the ZIL need not be re-written to the tree).

Good to know. Thanks for the explanation.

Basically ZFS maintains a ZIL based in-memory tree for the recent updates and a on-disk btree for the complete updates, minus the recent updates in ZIL. That's consistent with most database transaction log implementation. Some newer approach adds a Bloom filter to do fast decision between looking in the in-memory tree or in the on-disk btree.

> 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.

There 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.

> 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.

I 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.

Any append-only data-structure will have data that was true (when it was written), but has become false/obsolete/garbage at a later time. This is unavoidable.

I'm not saying that we write needless garbage to the logs or filesystem or whatever. I'm saying that the amount of garbage in your stream that you leave behind aids in later steps of (static) wear-leveling. So therefore, its not a big deal. You're going to be making plenty of this (initially true data, but later garbage data) as files get updated, moved around filesystems, or whatnot.

"Garbage" in this sense is perhaps the wrong word. Its more like "Obsolete data", or "outdated data".

If you read the article though, many of the updated nodes (which are now garbage) don't see any updates to their “data” but to internal tree pointers.

So lots of “data” is being copied, and garbage is being generated, only for the benefit of tidying up tree structure, not because the actual “data” in those pages changed.

Not generating such garbage in the first place is an obvious benefit.

I think I see what you mean now. Thanks.

I 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.

LMDB works like this. The MDB_env struct keeps pointers to both meta pages:

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

And I believe its first implementation was in IBM's System R.

LMDB is the poster child of COW btree implementation. That paper is a good find. Thanks.

I 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/

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.

This 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.

It'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.

Naively 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.

That's how the traditional transaction log + btree approach work. The append-only btree removes the need for a separate transaction log.

I 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.

If 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.

Of course, this implies a single-writer design (not necessarily a bad thing!).

Actually 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).

You 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.

The 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.

I 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.