5 ms·

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

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

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