News for hackers. Stuff that matters.

bradleykuszmaul

Tokutek licensed the fractal tree under GPLv2 with an explicit patent license to make clear that anyone could use the fractal tree code. I don't know what Percona did after the aquisiton.
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.

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.

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.

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?

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?

Re:TokuDB open sourced on Monday April 22, 2013 @12:54PM (#5590336)
If you are interested in this, you should look at our source distribution's license file. We have done the work to get a patent license from MIT, Stony Brook, and Rutgers so that the users of the GPL'd code can use the fractal tree patents.

Indemnification is a completely different issue: no open source software that I know of provides any kind of indemnification which would protect you from a lawsuit by a third party.

-Bradley ([email protected])

Re:TokuDB open sourced on Monday April 22, 2013 @11:32AM (#5589760)
Sadly, we don't use TokuDB to run our web site. It's some relatively inexpensive service.