The Log-Structured Merge-Tree (LSM-Tree) (1996) [pdf] | Hacker News Reader

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

citeseerx.ist.psu.edu

59 pointsespeed24 comments

Howard Chu of LMDB fame really bags on LSM:

https://twitter.com/hyc_symas/status/650799297143836672

https://twitter.com/hyc_symas/status/657399873562656768

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?

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

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!

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.

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

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.

Batching doesn't help the write amplification from compaction. Read the doc.

http://leveldb.googlecode.com/svn/trunk/doc/impl.html

Do the math.

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.

In the InfluxDB workload, they didn't get the "less seeks" you're talking about. Sure, you can delay paying for the seek by a second, if that. So can the buffer cache on any other DB structure. But when you have an overlapping range of keys and it's continuously growing, you hit the worst-case. Which InfluxDB did.

I think we're in violent agreement here, the case you note is exactly why key distribution matters. But even more than that the distribution of value lifetime matters too, if a lot of the values stored are very short lived then not only do they not get rewritten many times but you also get to only ever write them as part of sequential batches (no random seeks). The compressibility of your data also makes a big difference, if intra-key compression is effective on your data that can easily be 1.5x to 3x reduction in the footprint on disk. So, benchmark your workload.

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

[2] https://www.sqlite.org/src4/doc/trunk/www/lsmusr.wiki

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?

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.

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.

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.

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?

Your math is unrealistic. You are tossing around theoretical numbers, which are meaningless for an actual implementation.

Assume you have actually implemented this very simple LSM. Is it reliable? i.e., are you using ARIES WAL? If so, then every insert has an additional cost of at least k for the log record.

Are you using a raw block device, or are you using a filesystem? If a filesystem, then every insert has additional costs for metadata updates, and these costs are some multiple of the block size, not the key size.

If using a filesystem, every "rewrite" of a level includes multiple metadata updates to empty/delete existing files and create/allocate new files.

If not using a filesystem, then you must somehow manage metadata about the existence and size of your multiple levels yourself, as well as a space mapping of the raw block device.

A B+tree gets most of that for free because it uses a single file, so the amount of filesystem-level metadata updating is minimal.

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/newto...

The paper above discusses Btree fragmentation and proposes something like small LSM structure for indices.

This looks pretty similar to tokotek's fractal indexes

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

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

You answer not my analysis, but your idea of my analysis. The decrease of reading time for complex structure was 16%-19% for A WHOLE SERVER OPERATION, where BDB never amounted more than 20% in profile.

So I achieved speedup of 5-20 times over BDB (albeit not quite recent one, I admit).

Scale-free 1M nodes graph write does not even ends with BDB in reasonable time (and produces HUGE log). The difference between BDB and my LSM implementation for smaller graph size writes was in order of 200-300 times, LSM is faster.

Finally, I admit your code is here to test and use, mine's closed source and there are only my words. So I have to shut myself up and try to recreate that wonderful thing for everyone to use.

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.

Read the LevelDB implementation docs yourself. http://leveldb.googlecode.com/svn/trunk/doc/impl.html

The math is correct https://news.ycombinator.com/item?id=10437621

Reply on news.ycombinator.com