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

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?

Many important databases do contain 100-byte rows. Sometimes the biggest tables contain 100-byte rows, and then smaller tables contain larger rows.

I'd have to disagree with your assessment of the value of math.

It's nice to see someone trying to do performance benchmarks, but there are some serious problems with the benchmark presented at symas.com.

1) The benchmark hardware used fusion I/O. If you can afford fusion I/O, and you don't care about compression, you should use InnoDB. But you didn't measure InnoDB. If you use fusion I/O you probably actually care about compression, which you didn't measure, since you disabled compression. Why even report space used if you've disabled compression?

2) You used libc malloc to try to make a "uniform test". TokuDB recommends the use of JEmalloc, and you mentioned that some other storage engine requires TCmalloc. There's a reason to use a better memory allocator, and some storage engines need it. You've misconfigured at least two of the storage engines.

3) You wrote TokuDB code using the embedded API without passing the flags that make the high-ingestion rate possible. I'll be the first to admit that the documentation is poor for Tokutek's embedded API (the API that looks like Berkeley DB), but that doesn't change the fact that you are misusing the software. In particular, it appears that you used `0' for the flag argument to the DB->put() operations, meaning that every write is preceeded by a query. Since you apparently didn't mess up the LSM-based API's, it's not a fair comparision.

4) You ran your benchmarks for 20 minutes on each storage engine. That's not nearly long enough. For example, the system won't have aged at all. Interesting things start happening when the the database has been running for a long time. Interesting things that are predicted by the math.

Welcome, Bradley and Leif, to the club of people whom Howard has declared are doing it wrong. You are in fine company as I am also a member of that club. Although I do prefer snark from Turing Award winners. I don't think there is reason to pursue a discussion. It won't end well. But I do understand the desire to address the claims once.

https://gigaom.com/2011/07/07/facebook-trapped-in-mysql-fate...

Looking at that post on Leif's drawing, I think I agree that the B-tree is placed incorrectly. It turns out that B-trees are on the optimal read/write tradeoff curve, but they are in a very bad corner.

B-trees cost O(log_B N) to read or write.

Fractal trees cost O(log_B N) to read, and O((log_B N)/sqrt(N)) to write (for the case where epsilon=2).

The hidden constants inside the big-Oh are small; they seem to be less than 2 in practice. In fact, in the benchmarks that I've seen, the constants are in favor of the fractal tree. I suspect that this is because the block size in practical B-trees is too small, so the seek time is large compared to the transfer time on magnetic disk. Furthermore small block sizes hurt compression, small block sizes make the tree deeper. Furthermore, dynamic B-trees (ones that can be written) typically fill their blocks only about 3/4 full on average, making the effective block size even smaller. In most dynamic B-trees, the block size is 4KB or 16KB. In a few it's 32KB or even 64KB. For read-only databases I've seen people use 1MB blocks for B-trees. In the fractal tree, the effective block size is 4MB, and I suspect that's where we're winning on the constants.

So for a constant slowdown in read performance (a quite small constant slowdown, or possibly a small speedup) you can get dramatic speedups on write performance.

LSM trees are not on the optimal tradeoff curve. They suffer worse read perforamance that B-trees or Fractal trees, and their write performance is theoretically comparable to that of fractal trees.

So there's an error in that drawing, but the drawing is conceptual anyway, since there's no scale. The point of the drawing is that fractal trees dominate LSM trees, and for about the same cost as a B-tree on reads, you can get much better write performance. So the drawing is correct in spirit.

It makes no sense to build an LSM tree out of fractal trees. The resulting data structure would still be slower than a fractal tree. It's also unlikely to be faster than a B-tree-based LSM, since the B-trees used in LSM trees are static, not dynamic. You never have to insert into one of those B-trees, which means you can apply a bunch of tricks, such as using huge blocks. That probably shifts the constant inside the big-Oh back in favor of the B-tree for read operations, which are the only B-tree operations inside an LSM.

I don't think Tokutek is conflating the theoretical performance with the practical performance. Both the theoretical and practical performance appear to be better than the alternatives. In practice fractal trees appear to be slightly faster than B-trees at reads (assuming that the B-tree is actually a writeable data structure) in real workloads, and much faster at writes. In theory, the asymptotic read performance is the same, and the asymptotic write performance is much better for Fractal Trees.

It's true that the LSM implementations could all be bad, leading to the wrong conclusion when doing benchmarking. I'd find that surprising because the fractal tree seems to be better than any of the many LSM implementations in practice, and I'd hope that at least one of them would get it right. And the practical performance matches what the theory says it should, so it's not surprising that the fractal trees are faster.

I'm not sure why you object to comparing the data structures. We can compare them both theoretically using big-Oh notation. We can also do an analysis for specific database sizes and memory sizes of how the data structures compare, assuming a good implementation. That's what my paper tried to do. We could also compare the implementations, which my paper didn't do, but which others have done. For example, Tim Callaghan has done a lot of benchmarking which seems to be done right.

Thanks for acknowledging the problem with the graph. We'll have to disagree over "correct in spirit" versus "stupid."

I suggested building a LSM out of cache-oblivious b-trees because of the claim that they were better than b-trees in all cases, including (ostensibly) read performance. I didn't realize that it was another name for fractal trees. (It's been a while since I read the fractal tree papers.)

I'm not convinced that LSM-trees are suboptimal. The lower levels have shorter trees, so the price of redundant lookups is small, and you should get better write performance because you can do compaction without touching other levels.

Conversely, SQLite4 has designed an LSM-tree with forward pointers between the levels. However I think that actually sacrifices some write performance for read performance, which probably makes it closer to a fractal tree. (SQLite4 is also vaporware, unfortunately.)

I don't think there is a free lunch here. If you want to claim theoretically better read performance, you have to admit theoretically worse write performance. Tricks like compression or bloom filters (for LSM-trees) help in practice but don't change the theory.