6 ms·

A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing

81 points by ddorian43 12y ago

koverstreet 12y ago
Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first. I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now. Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in practice with a hybrid compacting data structure/B+ tree. I don't much care for LSMs, though.
- skybrian 12y ago
  Seems like the root could be sharded if it's an issue?
  - koverstreet 12y ago
    How would you do that? You have to be able to do lookups on the root. You have to have something to shard /on/. B+ trees shard the updates by splitting the keyspace up into different leaf nodes.
  - thorwahnawa 12y ago
    Not really. But you could imagine hacks like forcing updates instead of logging to the first N-levels (N = 1 or 2) of the B-tree. I don't know how well that would work in practice. I do know that B-tree block contention is a big problem for my $DAYJOB's use case for smaller B-trees.
    - koverstreet 12y ago
      Block contention? You mean contention on the locks for individual nodes?
      - thorwahnawa 12y ago
        Yes. You can grab the ancestors shared and the leaf or subtree you want to modify exclusive. If all of your writers land in the root of the tree because it's a small tree, they all contend on the same lock.
        skybrian 12y ago
        I'm no expert, but it seems like you need to guess at some key ranges and start the BTree at some minimum size even if most of the leaves start out empty. Either that, or don't write anything until the tree grows a bit and rely on a writeahead log for durability. Hotspots could still show up further down, though, if writes aren't fairly random.
        koverstreet 12y ago
        So it's only an issue with small trees? I'm not really seeing the issue then, use smaller btree nodes if it's really an issue...
        dignati 12y ago
        The issue seems yo be that writes in Fractal trees always go through the root node. This would lead to a situation similar to small B-Trees where writes will most likely access the root node and contend.
- bradleykuszmaul 12y ago
  To complain about contention under multithreaded workloads seems to be missing the point. At the point that multithreaded workloads are becoming a problem, the ingestion rate is huge (hundreds of thousands of insertions per second). For an in-memory database, that may not seem like much, but for a disk-resident database, that's a lot. I don't know what a "hybrid compacting data structure/B+ tree" is. Is there somewhere I can read about how you get the best performance in practice with it?
tokenrove 12y ago
The same paper is available here without filling in a form: http://insideanalysis.com/wp-content/uploads/2014/08/Tokutek_lsm-vs-fractal.pdf http://insideanalysis.com/wp-content/uploads/2014/08/Tokutek...
- jlarocco 12y ago
  Thanks
btrask 12y ago
Fractal trees are not "LSM-trees, but better." Fractal trees are more read-optimized, whereas LSM-trees are more write-optimized. A fully compacted LSM-tree should be equivalent to a b-tree in terms of read performance. However I don't think any existing implementations are anywhere near that. I appreciate TokuTek's work in this area but their marketing should be taken with a grain of salt. They've published some stupid stuff before (look at the graph here[1] and tell me how to make something just like a b-tree, but faster). [1] http://www.tokutek.com/2011/10/write-optimization-myths-comparison-clarifications-part-2/ http://www.tokutek.com/2011/10/write-optimization-myths-comp...
- joe_the_user 12y ago
  ...tell me how to make something just like a b-tree, but faster If you wanted to do that on modern multilayer-memory architecture, you would use a "cache-obvious" structure like cache-oblivious b-tree, cache-oblivious Lookahead Array and similar structures. Because these kinds of structures allow large and small scale locality of data, meaning that a disk-read will pull several pieces of data at once, a jump between nodes produces fewer cache misses (at each level) and so-forth. Michael A. Bender wrote of the original papers on cache oblivious structures and not coincidentally is TokuTek founder. http://www.tokutek.com/company/team/ http://www.tokutek.com/company/team/ http://en.wikipedia.org/wiki/Cache-oblivious_algorithm http://en.wikipedia.org/wiki/Cache-oblivious_algorithm http://supertech.csail.mit.edu/cacheObliviousBTree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html
- bradleykuszmaul 12y ago
  I'm the author of this paper, and I'll try to respond to some of what has been stated on this thread. > A fully compacted LSM-tree should be equivalent to a b-tree in terms of read performance. A fully compacted LSM tree arises only when writes stop happening for a sufficiently long time. It's a long-solved problem to build a read-only B-tree. The challenge is to not cause your read performance to fall when there are writes in the workload. This paper attempts to analyze that penalty. > They've published some stupid stuff before (look at the graph here[1] and tell me how to make something just like a b-tree, but faster). Possibly we've published some stupid stuff, but I don't think that Leif's blog posting qualifies. Is there something specific there that is incorrect?
eternalban 12y ago
The related patents: http://www.google.com/patents/US8185551 http://www.google.com/patents/US8185551 http://www.google.com/patents/US8489638 http://www.google.com/patents/US8489638
jasonwatkinspdx 12y ago
Just scanning the beginning, parts of this are pretty misleading. For example: "... if a database row contains 100 bytes, and a B tree such as InnoDB employs 16KiB pages [11], then the B tree may perform 16KiB of I/O to write a single 100-byte row, for a write amplification of 160, compared to a write amplification of 30 to 70 for the other data structures." Reading this gives the impression that the only way pages are updated is by writing the page in whole. Storage engines commonly use a slotted page layout to avoid this. That is, variable length records are stored contiguously from the start of the page, and are indexed by an array of fixed sized offset entries that grows up from the end of the page. Inserting a 100 byte row will append it to the end of data area, then prepend a new offset to the slot array. On spinning disks this is typically two 512 byte writes (assuming page size is decently larger than block size, as is common). On SSD's it's more complicated due to the FTL, and state of the art systems tend to use a log structured approach. See the Bw-tree paper from Microsoft Research for example.
- hyc_symas 12y ago
  IMO they're being quite disingenuous in that note. InnoDB is the default storage engine in MySQL, and there are very few production SQL databases with a tiny 100 bytes per row. A typical DB row in common apps is a couple KB at least. As a further example, MySQL's NDB Cluster engine has a maximum row size of 8KB, and this is frequently a problem for apps that want to migrate to it. If you start a discussion of write amplification with such an unrealistic record size, that pretty much moots the rest of the discussion. For a real-world examination of write amplification, at multiple record sizes: http://symas.com/mdb/ondisk/ http://symas.com/mdb/ondisk/ "Academic math" means nothing when you get to real-world software. Tokutek FT code is a pig, by every measure.
  - jasonwatkinspdx 12y ago
    Yeah, and I should have mentioned LMDB as another example of how state of the art storage engines tend towards log structured allocation management. The RamCloud design is another example. The way I'd summarize the case on SSD's is: the FTL is going to log structure your writes anyhow, you might as well align with that and recoup what you can.
rdtsc 12y ago
Wonder how this compares with: https://github.com/couchbase/forestdb https://github.com/couchbase/forestdb The idea seems to be Trie uses B+tree as a node. Key is split into 8 byte chunks. Each chunk is used as a key for each level of B+tree (from their presentation at: http://db.csail.mit.edu/sigmod11contest/sigmod_2011_contest_poster_jungsang_ahn.pdf http://db.csail.mit.edu/sigmod11contest/sigmod_2011_contest_... )
thesz 12y ago
In a DB with LSM storage you are free to do whatever you need to do. For example, you can compact size-tiered levels when their size ratio exceeds some threshold. This approach will make situation presented in paper impossible. In short, levels 1..N should be compacted into one when sum_{i=1..N-1}level_size(i)>=C*level_size(N). The multiplier C is important. Compactions will be rare and writes will be faster if C is bigger than 1. The read performance will be worse - we have to read more levels. To make compactions more often, we make C smaller. This way we prioritize read speed. And the most important thing here that we can compact levels even for read transactions. If we have many read transactions, it is necessary to make then faster. This very important point of LSM design is not mentioned in any literature I read. Fractal trees can be seen as basically LSM trees with fixed coefficient C=1. And with embedded index, as smaller levels provide indexing for bigger levels. So they force database designer into some corner. Which is different from corner of B+trees, but corner nevertheless. LSM trees are more flexible in that regard, in my opinion.
- bradleykuszmaul 12y ago
  No, I don't think you can view a fractal tree as an LSM tree with C=1. One conclusion of this paper is that for worst-case workloads, LSM trees are not as good asympotically as fractal trees. It's all fine and good to be flexible, but if there is no good setting of the parameters, the flexibility doesn't actually help solve the problem.
  - thesz 12y ago
    You can change settins on the fly. Actually, you have to change only one setting, level merge multiplier. You encounter many reads - make merge multiplier bigger. You encounter many writes - make it smaller.

81 points by ddorian43 12y ago

Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first. I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now. Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in practice with a hybrid compacting data structure/B+ tree. I don't much care for LSMs, though.

skybrian 12y ago
Seems like the root could be sharded if it's an issue?
- koverstreet 12y ago
  How would you do that? You have to be able to do lookups on the root. You have to have something to shard /on/. B+ trees shard the updates by splitting the keyspace up into different leaf nodes.
- thorwahnawa 12y ago
  Not really. But you could imagine hacks like forcing updates instead of logging to the first N-levels (N = 1 or 2) of the B-tree. I don't know how well that would work in practice. I do know that B-tree block contention is a big problem for my $DAYJOB's use case for smaller B-trees.
  - koverstreet 12y ago
    Block contention? You mean contention on the locks for individual nodes?
    - thorwahnawa 12y ago
      Yes. You can grab the ancestors shared and the leaf or subtree you want to modify exclusive. If all of your writers land in the root of the tree because it's a small tree, they all contend on the same lock.
      - skybrian 12y ago
        I'm no expert, but it seems like you need to guess at some key ranges and start the BTree at some minimum size even if most of the leaves start out empty. Either that, or don't write anything until the tree grows a bit and rely on a writeahead log for durability. Hotspots could still show up further down, though, if writes aren't fairly random.
      - koverstreet 12y ago
        So it's only an issue with small trees? I'm not really seeing the issue then, use smaller btree nodes if it's really an issue...
        dignati 12y ago
        The issue seems yo be that writes in Fractal trees always go through the root node. This would lead to a situation similar to small B-Trees where writes will most likely access the root node and contend.
bradleykuszmaul 12y ago
To complain about contention under multithreaded workloads seems to be missing the point. At the point that multithreaded workloads are becoming a problem, the ingestion rate is huge (hundreds of thousands of insertions per second). For an in-memory database, that may not seem like much, but for a disk-resident database, that's a lot. I don't know what a "hybrid compacting data structure/B+ tree" is. Is there somewhere I can read about how you get the best performance in practice with it?

tokenrove 12y ago

The same paper is available here without filling in a form: http://insideanalysis.com/wp-content/uploads/2014/08/Tokutek_lsm-vs-fractal.pdf http://insideanalysis.com/wp-content/uploads/2014/08/Tokutek...

jlarocco 12y ago
Thanks

btrask 12y ago

Fractal trees are not "LSM-trees, but better." Fractal trees are more read-optimized, whereas LSM-trees are more write-optimized. A fully compacted LSM-tree should be equivalent to a b-tree in terms of read performance. However I don't think any existing implementations are anywhere near that. I appreciate TokuTek's work in this area but their marketing should be taken with a grain of salt. They've published some stupid stuff before (look at the graph here[1] and tell me how to make something just like a b-tree, but faster). [1] http://www.tokutek.com/2011/10/write-optimization-myths-comparison-clarifications-part-2/ http://www.tokutek.com/2011/10/write-optimization-myths-comp...

joe_the_user 12y ago
...tell me how to make something just like a b-tree, but faster If you wanted to do that on modern multilayer-memory architecture, you would use a "cache-obvious" structure like cache-oblivious b-tree, cache-oblivious Lookahead Array and similar structures. Because these kinds of structures allow large and small scale locality of data, meaning that a disk-read will pull several pieces of data at once, a jump between nodes produces fewer cache misses (at each level) and so-forth. Michael A. Bender wrote of the original papers on cache oblivious structures and not coincidentally is TokuTek founder. http://www.tokutek.com/company/team/ http://www.tokutek.com/company/team/ http://en.wikipedia.org/wiki/Cache-oblivious_algorithm http://en.wikipedia.org/wiki/Cache-oblivious_algorithm http://supertech.csail.mit.edu/cacheObliviousBTree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html
bradleykuszmaul 12y ago
I'm the author of this paper, and I'll try to respond to some of what has been stated on this thread. > A fully compacted LSM-tree should be equivalent to a b-tree in terms of read performance. A fully compacted LSM tree arises only when writes stop happening for a sufficiently long time. It's a long-solved problem to build a read-only B-tree. The challenge is to not cause your read performance to fall when there are writes in the workload. This paper attempts to analyze that penalty. > They've published some stupid stuff before (look at the graph here[1] and tell me how to make something just like a b-tree, but faster). Possibly we've published some stupid stuff, but I don't think that Leif's blog posting qualifies. Is there something specific there that is incorrect?

eternalban 12y ago

The related patents: http://www.google.com/patents/US8185551 http://www.google.com/patents/US8185551 http://www.google.com/patents/US8489638 http://www.google.com/patents/US8489638

jasonwatkinspdx 12y ago

Just scanning the beginning, parts of this are pretty misleading. For example: "... if a database row contains 100 bytes, and a B tree such as InnoDB employs 16KiB pages [11], then the B tree may perform 16KiB of I/O to write a single 100-byte row, for a write amplification of 160, compared to a write amplification of 30 to 70 for the other data structures." Reading this gives the impression that the only way pages are updated is by writing the page in whole. Storage engines commonly use a slotted page layout to avoid this. That is, variable length records are stored contiguously from the start of the page, and are indexed by an array of fixed sized offset entries that grows up from the end of the page. Inserting a 100 byte row will append it to the end of data area, then prepend a new offset to the slot array. On spinning disks this is typically two 512 byte writes (assuming page size is decently larger than block size, as is common). On SSD's it's more complicated due to the FTL, and state of the art systems tend to use a log structured approach. See the Bw-tree paper from Microsoft Research for example.

hyc_symas 12y ago
IMO they're being quite disingenuous in that note. InnoDB is the default storage engine in MySQL, and there are very few production SQL databases with a tiny 100 bytes per row. A typical DB row in common apps is a couple KB at least. As a further example, MySQL's NDB Cluster engine has a maximum row size of 8KB, and this is frequently a problem for apps that want to migrate to it. If you start a discussion of write amplification with such an unrealistic record size, that pretty much moots the rest of the discussion. For a real-world examination of write amplification, at multiple record sizes: http://symas.com/mdb/ondisk/ http://symas.com/mdb/ondisk/ "Academic math" means nothing when you get to real-world software. Tokutek FT code is a pig, by every measure.
- jasonwatkinspdx 12y ago
  Yeah, and I should have mentioned LMDB as another example of how state of the art storage engines tend towards log structured allocation management. The RamCloud design is another example. The way I'd summarize the case on SSD's is: the FTL is going to log structure your writes anyhow, you might as well align with that and recoup what you can.

rdtsc 12y ago

Wonder how this compares with: https://github.com/couchbase/forestdb https://github.com/couchbase/forestdb The idea seems to be Trie uses B+tree as a node. Key is split into 8 byte chunks. Each chunk is used as a key for each level of B+tree (from their presentation at: http://db.csail.mit.edu/sigmod11contest/sigmod_2011_contest_poster_jungsang_ahn.pdf http://db.csail.mit.edu/sigmod11contest/sigmod_2011_contest_... )

thesz 12y ago

In a DB with LSM storage you are free to do whatever you need to do. For example, you can compact size-tiered levels when their size ratio exceeds some threshold. This approach will make situation presented in paper impossible. In short, levels 1..N should be compacted into one when sum_{i=1..N-1}level_size(i)>=C*level_size(N). The multiplier C is important. Compactions will be rare and writes will be faster if C is bigger than 1. The read performance will be worse - we have to read more levels. To make compactions more often, we make C smaller. This way we prioritize read speed. And the most important thing here that we can compact levels even for read transactions. If we have many read transactions, it is necessary to make then faster. This very important point of LSM design is not mentioned in any literature I read. Fractal trees can be seen as basically LSM trees with fixed coefficient C=1. And with embedded index, as smaller levels provide indexing for bigger levels. So they force database designer into some corner. Which is different from corner of B+trees, but corner nevertheless. LSM trees are more flexible in that regard, in my opinion.

bradleykuszmaul 12y ago
No, I don't think you can view a fractal tree as an LSM tree with C=1. One conclusion of this paper is that for worst-case workloads, LSM trees are not as good asympotically as fractal trees. It's all fine and good to be flexible, but if there is no good setting of the parameters, the flexibility doesn't actually help solve the problem.
- thesz 12y ago
  You can change settins on the fly. Actually, you have to change only one setting, level merge multiplier. You encounter many reads - make merge multiplier bigger. You encounter many writes - make it smaller.