A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
highscalability.com
A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
1–10 of 30 posts
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#2Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first.
I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now.
Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in practice with a hybrid compacting data structure/B+ tree.
I don't much care for LSMs, though.
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#3The same paper is available here without filling in a form:
http://insideanalysis.com/wp-content/uploads/2014/08/Tokutek...
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#4Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first. I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now. Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in pract…
Seems like the root could be sharded if it's an issue?
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#5Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first. I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now. Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in pract…
Seems like the root could be sharded if it's an issue?
How would you do that? You have to be able to do lookups on the root. You have to have something to shard /on/.
B+ trees shard the updates by splitting the keyspace up into different leaf nodes.
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#6Downside of fractal trees is the root of the tree inevitably becomes contended under multithreaded workloads - everything has to go through the root and updates modify the root first. I vaguely recall there being other downsides to the pure fractal tree approach I can't recall right now. Compacting data structures are quite nifty though and do have useful properties - you'll actually get the best performance in pract…
Seems like the root could be sharded if it's an issue?
Not really. But you could imagine hacks like forcing updates instead of logging to the first N-levels (N = 1 or 2) of the B-tree. I don't know how well that would work in practice.
I do know that B-tree block contention is a big problem for my $DAYJOB's use case for smaller B-trees.
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#7Fractal 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-comp...
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#8The related patents:
http://www.google.com/patents/US8185551 http://www.google.com/patents/US8489638
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#9Earlier quoted context omitted.
Seems like the root could be sharded if it's an issue?
Not really. But you could imagine hacks like forcing updates instead of logging to the first N-levels (N = 1 or 2) of the B-tree. I don't know how well that would work in practice. I do know that B-tree block contention is a big problem for my $DAYJOB's use case for smaller B-trees.
Block contention? You mean contention on the locks for individual nodes?
Re: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
#10Earlier quoted context omitted.
Not really. But you could imagine hacks like forcing updates instead of logging to the first N-levels (N = 1 or 2) of the B-tree. I don't know how well that would work in practice. I do know that B-tree block contention is a big problem for my $DAYJOB's use case for smaller B-trees.
Block contention? You mean contention on the locks for individual nodes?
Yes. You can grab the ancestors shared and the leaf or subtree you want to modify exclusive. If all of your writers land in the root of the tree because it's a small tree, they all contend on the same lock.