News for hackers. Stuff that matters.
Re:How the append-only btree works by seunosewa on Friday December 29, 2023 @10:44AM (#38806105)
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.

Re:How the append-only btree works by scottlamb on Friday December 29, 2023 @11:04AM (#38806353)
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.

Re:How the append-only btree works by pclmulqdq on Friday December 29, 2023 @11:35AM (#38806850)
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.
Re:How the append-only btree works by btilly on Friday December 29, 2023 @12:03PM (#38807278)
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.

Re:How the append-only btree works by alternative_a on Friday December 29, 2023 @12:37PM (#38807736)
The subtle point I read in GP is the historic correlation between storage systems and data structures. Your point is equally valid in that this correlation is not indicative of non-general applicability.

Both points need to be kept in mind imho in design.

Re:How the append-only btree works by _factor on Friday December 29, 2023 @08:00PM (#38811949)
Don't forget the security implications. If only root can run the compression/deletion script, all the compromised user can do is try to write to theirs. If you get into writing other users' data, that sucks, but nothing is deleted or exfiltrated, and the log is baked in. Break into root, well good luck with that on any system.
Re:How the append-only btree works by scottlamb on Friday December 29, 2023 @01:14PM (#38808233)
Good point. It's also worth noting that raw flash also is generally treated as roughly append-only for wear leveling. "General-purpose" may be in the eye of the beholder, but I'd say these append-only data structures are useful in at least two significant environments.
Re:How the append-only btree works by pclmulqdq on Saturday December 30, 2023 @02:59AM (#38813542)
Wear leveling generally happens well below the user-level filesystem (and is quite complicated!), and altering your user-level behavior because you think it helps is a little bit silly. Zoned NVMe is an obvious exception to this, where the FTL takes advantage of the append-only zones (even that is an abstraction only shown to filesystems), but it will frequently remap your blocks if you do a lot of read-modify-writes to keep the wear even.
Re:How the append-only btree works by namibj on Sunday December 31, 2023 @09:49AM (#38824401)
Well, you still don't get fine-grained random deletions on Zoned NVMe. Also, there is another storage target which expects append-only style: SMR HDDs. They don't support random writes into a zone.
Re:How the append-only btree works by scottlamb on Sunday December 31, 2023 @12:38PM (#38825800)
True, which is why I called out "raw" flash in particular. I think there are embedded cases for example where it might make sense to skip that layer. Even on general purpose machines I think it'd be interesting to see alternate filesystem models that avoid double logging for databases, but I don't know if it will ever happen...

> Zoned NVMe is an obvious exception to this

And host-managed SMR HDDs, as namibj pointed out. I still haven't managed to get my hands on one, though; they seem to be hyperscaler-only for now.

Re:How the append-only btree works by pclmulqdq on Sunday December 31, 2023 @08:30PM (#38829022)
Even "raw" flash as exposed in most Linux servers is not anywhere near raw. For embedded use cases, it absolutely matters, but if you have Linux and an enterprise NVMe SSD, nothing you do in userland will matter.
Re:How the append-only btree works by lloydatkinson on Friday December 29, 2023 @12:59PM (#38808033)
What you described is called event sourcing
Re:How the append-only btree works by slashdev on Friday December 29, 2023 @11:57AM (#38807174)
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/

Re:How the append-only btree works by londons_explore on Friday December 29, 2023 @10:56AM (#38806263)
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.

Re:How the append-only btree works by halayli on Friday December 29, 2023 @11:59AM (#38807208)
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.
Re:How the append-only btree works by vlovich123 on Friday December 29, 2023 @10:47AM (#38806144)
A mutable approach requires a write ahead log meaning you have to copy the data twice on every write which seems worse.
Re:How the append-only btree works by vajrabum on Friday December 29, 2023 @10:59AM (#38806298)
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.
Re:How the append-only btree works by loeg on Friday December 29, 2023 @11:19AM (#38806591)
Now you’re paying for double the hardware.
Re:How the append-only btree works by vlovich123 on Friday December 29, 2023 @01:14PM (#38808235)
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.
Re:How the append-only btree works by iambvk on Friday December 29, 2023 @04:14PM (#38810278)
It is: two writes for write ahead log vs. log-n (tree-height) writes for CoW
Re:How the append-only btree works by hyc_symas on Thursday January 04, 2024 @11:49PM (#38875800)
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/
Re:How the append-only btree works by valenterry on Friday December 29, 2023 @11:32AM (#38806811)
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.

Re:How the append-only btree works by teo_zero on Friday December 29, 2023 @01:00PM (#38808046)
IF reads dominate writes, and multiple threads read the data concurrently, this approach may win by eliminating the need for locks.
Re:How the append-only btree works by hinkley on Friday December 29, 2023 @02:05PM (#38808920)
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.

Re:How the append-only btree works by joshlemer on Friday December 29, 2023 @04:27PM (#38810389)
Yes, for instance Clojure's "transients" as well as the JavaScript "immer" library
Re:How the append-only btree works by cryptonector on Friday December 29, 2023 @02:24PM (#38809120)
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
Re:How the append-only btree works by joshlemer on Friday December 29, 2023 @04:23PM (#38810359)
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).