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.
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.
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.
Both points need to be kept in mind imho in design.
> 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.
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.
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).
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.
The benefits of CoW data structures are tremendous:
- easy to reason about
- easy to multi-thread for reading
- O(1) snashopts (and clones)
- the need to amortize write magnification
- difficulty in multi-threading writesYou need a different API for something like that however.
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.