3 ms·

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 sh

by 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?
- btrask 12y ago
  Thanks for taking the time to reply. In Leif's post, the graph shows "b-trees" on the inner curve. The equivalent point on the outer curve would be a data structure that makes the same read/write tradeoffs as a b-tree, but is simply better in all cases. The other reply suggests cache oblivious b-trees. I haven't had time to look at them yet. It's worth pointing out that if cache oblivious b-trees really are better than normal b-trees, you could build an LSM-tree out of them. My interpretation is that TokuTek is conflating data structures' theoretical performance with their implementations' practical performance. So the graph is trying to represent "typical" b-trees as not using compression and other techniques that TokuDB uses. Under that interpretation, each data structure would have a spectrum of possible performance from poor to highly tuned, which the graph doesn't make clear. To be fair, I think TokuDB probably has very good real world performance, and there's a huge need for better LSM-trees (and better database engines in general). My objection is the comparison of the data structures, not the implementations.
  - bradleykuszmaul 12y ago
    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.

by btrask 12y ago

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?

btrask 12y ago
Thanks for taking the time to reply. In Leif's post, the graph shows "b-trees" on the inner curve. The equivalent point on the outer curve would be a data structure that makes the same read/write tradeoffs as a b-tree, but is simply better in all cases. The other reply suggests cache oblivious b-trees. I haven't had time to look at them yet. It's worth pointing out that if cache oblivious b-trees really are better than normal b-trees, you could build an LSM-tree out of them. My interpretation is that TokuTek is conflating data structures' theoretical performance with their implementations' practical performance. So the graph is trying to represent "typical" b-trees as not using compression and other techniques that TokuDB uses. Under that interpretation, each data structure would have a spectrum of possible performance from poor to highly tuned, which the graph doesn't make clear. To be fair, I think TokuDB probably has very good real world performance, and there's a huge need for better LSM-trees (and better database engines in general). My objection is the comparison of the data structures, not the implementations.
- bradleykuszmaul 12y ago
  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.