News for hackers. Stuff that matters.
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by koverstreet on Sunday March 22, 2015 @06:04PM (#9248442)
Downside 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 Tr... by bradleykuszmaul on Tuesday March 24, 2015 @03:30PM (#9258859)
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?

Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by skybrian on Sunday March 22, 2015 @07:17PM (#9248668)
Seems like the root could be sharded if it's an issue?
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by thorwahnawa on Sunday March 22, 2015 @07:24PM (#9248681)
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 Tr... by koverstreet on Sunday March 22, 2015 @07:51PM (#9248757)
Block contention? You mean contention on the locks for individual nodes?
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by thorwahnawa on Sunday March 22, 2015 @08:40PM (#9248882)
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.
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by skybrian on Sunday March 22, 2015 @09:07PM (#9248948)
I'm no expert, but it seems like you need to guess at some key ranges and start the BTree at some minimum size even if most of the leaves start out empty. Either that, or don't write anything until the tree grows a bit and rely on a writeahead log for durability.

Hotspots could still show up further down, though, if writes aren't fairly random.

Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by koverstreet on Sunday March 22, 2015 @09:14PM (#9248966)
So it's only an issue with small trees? I'm not really seeing the issue then, use smaller btree nodes if it's really an issue...
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by dignati on Monday March 23, 2015 @05:58AM (#9250104)
The issue seems yo be that writes in Fractal trees always go through the root node. This would lead to a situation similar to small B-Trees where writes will most likely access the root node and contend.
Re:A Comparison of Log-Structured Merge (LSM) and Fractal Tr... by koverstreet on Sunday March 22, 2015 @07:22PM (#9248677)
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.