8 ms·

The Log-Structured Merge-Tree (LSM-Tree) (1996) [pdf]

59 points by espeed 11y ago

kev009 11y ago
Howard Chu of LMDB fame really bags on LSM: https://twitter.com/hyc_symas/status/650799297143836672 https://twitter.com/hyc_symas/status/650799297143836672 https://twitter.com/hyc_symas/status/657399873562656768 https://twitter.com/hyc_symas/status/657399873562656768
- pja 11y ago
  Yup. That exactly matches my past experience from when we tried levelDB as a possible replacement for our key-value store in a past project. On paper level DB looks great but the extra write load from the write amplification thanks to the multi-level data structure meant the real world performance was much worse than a plain BTree / B+Tree for continuous random write load. If you have a different workload, then levelDB might work for you: continuous appends of mostly new data perhaps?
  - jorangreef 11y ago
    Did you try different level multipliers? i.e. Using 4x instead of 10x, to trade write amplification for read amplification (which can be amortised by bloom filters)?
    - pja 11y ago
      I think we tried changing the level multiplier & it not making much difference - although I didn’t write the code, someone else in our team did. The problem space was a seen-set store for a exhaustive prover. (ie, a continuous loop of: have you seen this state yet? If No, add it to the set of known states, rinse and repeat.) Any memory you allocated to another data structure is memory you’ve just taken away from your in-memory cache for the seen set. Total throughput was ultimately disk IO limited, so anything that increased the number of reads/writes just made things slower. I don’t think the bloom filter would have helped, because every access was potentially a write, but I’d have to go away and think about it for a bit to be sure!
      - hedgehog 11y ago
        That makes some sense, performance is dependent on how writes are distributed in the key space. For logging analytics or telemetry data with keys that are roughly timestamps you get a really nice seekable log and usually good compression ratios and minimal to no compaction. Also for an application that was mostly any kind of writes & deletes I would guess LSMs would do pretty well.
        hyc_symas 11y ago
        The InfluxDB experience shows that the answer is more complicated than that - they're storing time-series data, which they thought an LSM would be good for. But in reality, they're storing multiple series simultaneously. That turns the simple sequential workload into a very random one. Each write is a sequence of K/V pairs: A:1, B:1, C:1, D:1, E:1 A:2, B:2, C:2, D:2, E:2 This turns into the worst-case key ordering for LevelDB because every write overlaps with the previous keys. Worst-case turns out to be ridiculously bad. https://news.ycombinator.com/item?id=10437621 https://news.ycombinator.com/item?id=10437621
        btrask 11y ago
        I think you're backwards. Random writes are LSM trees' forte because they can batch them. Sequential writes would be doable with a b-tree.
        hyc_symas 11y ago
        Batching doesn't help the write amplification from compaction. Read the doc. http://leveldb.googlecode.com/svn/trunk/doc/impl.html http://leveldb.googlecode.com/svn/trunk/doc/impl.html Do the math.
        btrask 11y ago
        Write amplification is not the only thing that matters. For small keys, higher write amplification is a good tradeoff for doing less seeks (which yes, are still a performance problem on SSDs, probably because of the block size). For large keys, I agree with you, you shouldn't use an LSM-tree. There is a threshold between seek time and compaction.
- btrask 11y ago
  It's true that LevelDB has a lot of drawbacks, including its complexity (making reliability problems much more likely). However, I think Howard Chu is way too pessimistic about (I'd say biased against) LSM-trees. I wrote an LSM-tree database based on Chu's LMDB[1] that was able to support a much higher write throughput than LMDB, although it was still slower than LevelDB for writes. Unfortunately it had some other drawbacks and would be hard to make it "production ready" so I'm not using it. I'm using LMDB by default in my current project because of it's simplicity and read performance (which are truly amazing). But I'm convinced that a write-optimized database on par with LMDB is possible. SQLite4[2] might eventually be it, if it ever gets finished. [1] https://github.com/btrask/lsmdb https://github.com/btrask/lsmdb [2] https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki
- jbapple 11y ago
  I don't understand his claim that B-tree write amplification is O(1). If I want to write one key to a B-tree, I only have to write O(1) nodes (amortized), but each node is presumably of size B >> 1, right?
  - hyc_symas 11y ago
    That's irrelevant. The point is that whether your record is 1 byte or 1000 bytes, you still write only 1 node. In an LSM, the write amplification is a large multiple of your record size.
    - btrask 11y ago
      In b-trees, there is an inherent tension in choosing a page size (or base). Larger pages are good for reads because of the higher branching factor (which is why we don't use binary trees). Smaller pages are good for random writes because you're rewriting less. This is why Tokutek claims their fractal trees are faster for reads than b-trees, because they can use larger pages without killing write performance.
      - hyc_symas 11y ago
        Tokutek makes a lot of claims but none of their code demonstrates any advantage. Since their algorithm is patented I've avoided reading it in depth. But assuming there's a "there" there, clearly their implementation of it sucks. When your code needs 2x RAM as the actual data volume to operate, you've failed as a database. I'm inclined to believe there's no "there" there.
    - jbapple 11y ago
      Assume a very simple LSM with one run per level and an expansion factor of 2. Call the block size B and the key size k. The first two levels have one run of size B, and each level thereafter has one run twice the size of the one from the previous level. For n records, there are nk/B blocks on disk and ceil(lg (nk/B)) + 1 levels, at most, in the database. Every insert writes one of levels 1 or 2. One out of every 2B/k writes also rewrites level 3, at a cost of 2 block writes. This adds an amortized cost of k/B block writes. One out of every 4B/k writes also rewrites level 4, at a cost of 4 block writes. This, again, adds an amortized cost of k/B block writes. This continues until we are out of levels. Since there are ceil(lg (nk/B)) + 1 levels (at most), the amortized cost of an insert is at most 1 + (k/B)(ceil(lg (nk/B)) + 1 - 1) block writes. For a block size of 4096 bytes, a key size of 32 bytes, and n = 2^30, this 1.18 block writes per insert. If k = 256 and n = 2^40, this is 3.25 block writes per insert. Is my math wrong?
- thesz 11y ago
  I implemented a variant of LSM in C# (BerkeleyDB feature/bug compatible, more or less) for our internal DB server (OO/relational DB). Yes, it is true that LSM can incur a O(logN) read amplification, it was clearly shown in our bare storage tests. But! The full table scan read in full server has 3% (three percent) difference between different storages (LSM is 3% slower). And, as I haven't used BTrees for LSM levels, but some other superficially similar structures with different construction (and no modification - MVCC), the read of complex structures from our DB (a PCB project - you can guess complexity) netted in clear benefit - that read operation was from 16 (sixteen) to 19 (nineteen) percents faster compared to BerkeleyDB. Given that BerkeleyDB storage backend has not occupied more than 20% of server runtime in our profiles, it amounts to 5 to 20 times speedup in read operations. This can be explained like using the following argument: because Btree gets fragmented when you randomly insert things - pages get scattered all over the place. The rebuild phase I employed made pages much less scattered (actually, there cannot be more than some fixed number (8 in our case) different contiguous runs of pages to hold all data). This amounted to radical difference in read performance. Take a look: https://cs.brown.edu/research/pubs/theses/masters/2010/newton.pdf https://cs.brown.edu/research/pubs/theses/masters/2010/newto... The paper above discusses Btree fragmentation and proposes something like small LSM structure for indices.
  - phpnode 11y ago
    This looks pretty similar to tokotek's fractal indexes
  - deleted 11y ago
    [deleted]
  - hyc_symas 11y ago
    Reads in LMDB are orders of magnitude faster than BerkeleyDB. Not just a tiny 16-19%. Both are B+trees. Using the right algorithm is important, but using it well matters too. http://symas.com/mdb/#bench http://symas.com/mdb/#bench Wy original comment was about write amplification, not read amplification. It's already a given that LSMs are slow for reads. LSMs are claimed to be write optimized and yet it's easy to demonstrate that their write amplification is prohibitively bad. They also are inherently unreliable, making them a choice suitable only for idiots. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pillai https://www.usenix.org/conference/osdi14/technical-sessions/...
- gearhart 11y ago
  This is the first time I've ever encountered the guy, but W.R.T. the second of those links: making a public statement denouncing a tool because a performance profile is O(N^2) and then, on being asked to prove it, admitting it's actually O(N logN) doesn't give me the greatest faith in the rigour with which he's considered the problem.
  - hyc_symas 11y ago
    Read the LevelDB implementation docs yourself. http://leveldb.googlecode.com/svn/trunk/doc/impl.html http://leveldb.googlecode.com/svn/trunk/doc/impl.html The math is correct https://news.ycombinator.com/item?id=10437621 https://news.ycombinator.com/item?id=10437621

59 points by espeed 11y ago

Howard Chu of LMDB fame really bags on LSM: https://twitter.com/hyc_symas/status/650799297143836672 https://twitter.com/hyc_symas/status/650799297143836672 https://twitter.com/hyc_symas/status/657399873562656768 https://twitter.com/hyc_symas/status/657399873562656768

pja 11y ago
Yup. That exactly matches my past experience from when we tried levelDB as a possible replacement for our key-value store in a past project. On paper level DB looks great but the extra write load from the write amplification thanks to the multi-level data structure meant the real world performance was much worse than a plain BTree / B+Tree for continuous random write load. If you have a different workload, then levelDB might work for you: continuous appends of mostly new data perhaps?
- jorangreef 11y ago
  Did you try different level multipliers? i.e. Using 4x instead of 10x, to trade write amplification for read amplification (which can be amortised by bloom filters)?
  - pja 11y ago
    I think we tried changing the level multiplier & it not making much difference - although I didn’t write the code, someone else in our team did. The problem space was a seen-set store for a exhaustive prover. (ie, a continuous loop of: have you seen this state yet? If No, add it to the set of known states, rinse and repeat.) Any memory you allocated to another data structure is memory you’ve just taken away from your in-memory cache for the seen set. Total throughput was ultimately disk IO limited, so anything that increased the number of reads/writes just made things slower. I don’t think the bloom filter would have helped, because every access was potentially a write, but I’d have to go away and think about it for a bit to be sure!
    - hedgehog 11y ago
      That makes some sense, performance is dependent on how writes are distributed in the key space. For logging analytics or telemetry data with keys that are roughly timestamps you get a really nice seekable log and usually good compression ratios and minimal to no compaction. Also for an application that was mostly any kind of writes & deletes I would guess LSMs would do pretty well.
      - hyc_symas 11y ago
        The InfluxDB experience shows that the answer is more complicated than that - they're storing time-series data, which they thought an LSM would be good for. But in reality, they're storing multiple series simultaneously. That turns the simple sequential workload into a very random one. Each write is a sequence of K/V pairs: A:1, B:1, C:1, D:1, E:1 A:2, B:2, C:2, D:2, E:2 This turns into the worst-case key ordering for LevelDB because every write overlaps with the previous keys. Worst-case turns out to be ridiculously bad. https://news.ycombinator.com/item?id=10437621 https://news.ycombinator.com/item?id=10437621
        btrask 11y ago
        I think you're backwards. Random writes are LSM trees' forte because they can batch them. Sequential writes would be doable with a b-tree.
        hyc_symas 11y ago
        Batching doesn't help the write amplification from compaction. Read the doc. http://leveldb.googlecode.com/svn/trunk/doc/impl.html http://leveldb.googlecode.com/svn/trunk/doc/impl.html Do the math.
        btrask 11y ago
        Write amplification is not the only thing that matters. For small keys, higher write amplification is a good tradeoff for doing less seeks (which yes, are still a performance problem on SSDs, probably because of the block size). For large keys, I agree with you, you shouldn't use an LSM-tree. There is a threshold between seek time and compaction.
btrask 11y ago
It's true that LevelDB has a lot of drawbacks, including its complexity (making reliability problems much more likely). However, I think Howard Chu is way too pessimistic about (I'd say biased against) LSM-trees. I wrote an LSM-tree database based on Chu's LMDB[1] that was able to support a much higher write throughput than LMDB, although it was still slower than LevelDB for writes. Unfortunately it had some other drawbacks and would be hard to make it "production ready" so I'm not using it. I'm using LMDB by default in my current project because of it's simplicity and read performance (which are truly amazing). But I'm convinced that a write-optimized database on par with LMDB is possible. SQLite4[2] might eventually be it, if it ever gets finished. [1] https://github.com/btrask/lsmdb https://github.com/btrask/lsmdb [2] https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki
jbapple 11y ago
I don't understand his claim that B-tree write amplification is O(1). If I want to write one key to a B-tree, I only have to write O(1) nodes (amortized), but each node is presumably of size B >> 1, right?
- hyc_symas 11y ago
  That's irrelevant. The point is that whether your record is 1 byte or 1000 bytes, you still write only 1 node. In an LSM, the write amplification is a large multiple of your record size.
  - btrask 11y ago
    In b-trees, there is an inherent tension in choosing a page size (or base). Larger pages are good for reads because of the higher branching factor (which is why we don't use binary trees). Smaller pages are good for random writes because you're rewriting less. This is why Tokutek claims their fractal trees are faster for reads than b-trees, because they can use larger pages without killing write performance.
    - hyc_symas 11y ago
      Tokutek makes a lot of claims but none of their code demonstrates any advantage. Since their algorithm is patented I've avoided reading it in depth. But assuming there's a "there" there, clearly their implementation of it sucks. When your code needs 2x RAM as the actual data volume to operate, you've failed as a database. I'm inclined to believe there's no "there" there.
  - jbapple 11y ago
    Assume a very simple LSM with one run per level and an expansion factor of 2. Call the block size B and the key size k. The first two levels have one run of size B, and each level thereafter has one run twice the size of the one from the previous level. For n records, there are nk/B blocks on disk and ceil(lg (nk/B)) + 1 levels, at most, in the database. Every insert writes one of levels 1 or 2. One out of every 2B/k writes also rewrites level 3, at a cost of 2 block writes. This adds an amortized cost of k/B block writes. One out of every 4B/k writes also rewrites level 4, at a cost of 4 block writes. This, again, adds an amortized cost of k/B block writes. This continues until we are out of levels. Since there are ceil(lg (nk/B)) + 1 levels (at most), the amortized cost of an insert is at most 1 + (k/B)(ceil(lg (nk/B)) + 1 - 1) block writes. For a block size of 4096 bytes, a key size of 32 bytes, and n = 2^30, this 1.18 block writes per insert. If k = 256 and n = 2^40, this is 3.25 block writes per insert. Is my math wrong?
thesz 11y ago
I implemented a variant of LSM in C# (BerkeleyDB feature/bug compatible, more or less) for our internal DB server (OO/relational DB). Yes, it is true that LSM can incur a O(logN) read amplification, it was clearly shown in our bare storage tests. But! The full table scan read in full server has 3% (three percent) difference between different storages (LSM is 3% slower). And, as I haven't used BTrees for LSM levels, but some other superficially similar structures with different construction (and no modification - MVCC), the read of complex structures from our DB (a PCB project - you can guess complexity) netted in clear benefit - that read operation was from 16 (sixteen) to 19 (nineteen) percents faster compared to BerkeleyDB. Given that BerkeleyDB storage backend has not occupied more than 20% of server runtime in our profiles, it amounts to 5 to 20 times speedup in read operations. This can be explained like using the following argument: because Btree gets fragmented when you randomly insert things - pages get scattered all over the place. The rebuild phase I employed made pages much less scattered (actually, there cannot be more than some fixed number (8 in our case) different contiguous runs of pages to hold all data). This amounted to radical difference in read performance. Take a look: https://cs.brown.edu/research/pubs/theses/masters/2010/newton.pdf https://cs.brown.edu/research/pubs/theses/masters/2010/newto... The paper above discusses Btree fragmentation and proposes something like small LSM structure for indices.
- phpnode 11y ago
  This looks pretty similar to tokotek's fractal indexes
- deleted 11y ago
  [deleted]
- hyc_symas 11y ago
  Reads in LMDB are orders of magnitude faster than BerkeleyDB. Not just a tiny 16-19%. Both are B+trees. Using the right algorithm is important, but using it well matters too. http://symas.com/mdb/#bench http://symas.com/mdb/#bench Wy original comment was about write amplification, not read amplification. It's already a given that LSMs are slow for reads. LSMs are claimed to be write optimized and yet it's easy to demonstrate that their write amplification is prohibitively bad. They also are inherently unreliable, making them a choice suitable only for idiots. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pillai https://www.usenix.org/conference/osdi14/technical-sessions/...
gearhart 11y ago
This is the first time I've ever encountered the guy, but W.R.T. the second of those links: making a public statement denouncing a tool because a performance profile is O(N^2) and then, on being asked to prove it, admitting it's actually O(N logN) doesn't give me the greatest faith in the rigour with which he's considered the problem.
- hyc_symas 11y ago
  Read the LevelDB implementation docs yourself. http://leveldb.googlecode.com/svn/trunk/doc/impl.html http://leveldb.googlecode.com/svn/trunk/doc/impl.html The math is correct https://news.ycombinator.com/item?id=10437621 https://news.ycombinator.com/item?id=10437621