Fractal Tree Indexing over B-Trees?

The case has been made on Phoronix for F-Trees: They makes use hard drive speeds, not (relatively slow) access times; beat SSD's; and scale perfectly across multiple cores with hundreds of millions of entries.

http://en.wikipedia.org/wiki/TokuDB#Fractal_tree_indexes

How TokuDB Fractal Tree Databases Work

Via: http://www.phoronix.com/scan.php?page=news_item&px=MTA3NjM

Time for someone to get started on ftrfs? Or can it be implemented in Btrfs?
https://bugzilla.kernel.org/show_bug.cgi?id=43004

The case has been made on Phoronix for F-Trees: They makes use hard drive speeds, not (relatively slow) access times; beat SSD's; and scale perfectly across multiple cores with hundreds of millions of entries.

http://en.wikipedia.org/wiki/TokuDB#Fractal_tree_indexes

How TokuDB Fractal Tree Databases Work

Via: http://www.phoronix.com/scan.php?page=news_item&px=MTA3NjM

Time for someone to get started on ftrfs? Or can it be implemented in Btrfs?
https://bugzilla.kernel.org/show_bug.cgi?id=43004

Quoted 4 lines · Danny Piccirillo

The case has been made on Phoronix for F-Trees: They makes use hard drive speeds, not (relatively slow) access times; beat SSD's; and scale perfectly across multiple cores with hundreds of millions of entries.

So no I don't think it's time for someone to get started on ftrfs. Thanks,

Quoted 6 lines · Danny Piccirillo

The case has been made on Phoronix for F-Trees: They makes use hard drive speeds, not (relatively slow) access times; beat SSD's; and scale perfectly across multiple cores with hundreds of millions of entries.

http://en.wikipedia.org/wiki/TokuDB#Fractal_tree_indexes

Quoted 8 lines

How TokuDB Fractal Tree Databases Work

Via: http://www.phoronix.com/scan.php?page=news_item&px=MTA3NjM

Time for someone to get started on ftrfs? Or can it be implemented in Btrfs?
https://bugzilla.kernel.org/show_bug.cgi?id=43004

This is dumber shit than usual out of phoronix. I did some just basic calculations for worst case scenarios, let's say we max out btrfs's 8 level limit, so we have 7 levels of nodes and then our leaves. Lets just for simplicity sake say we can fit 1 billion objects into this kind of tree, and for each node/leaf we can only hold 10 objects. (Keep in mind these are just random numbers I'm pulling out of my ass and may not work out right with such a large tree, just work with me here).

So worst case scenario doing a binary search for an object with 10 objects is 4 comparisons, so with a full 8 level btree we're doing 4 comparisons per level, so 32 comparisons worst possible case to find our object.

Now let's consider a fractal tree with 1 billion objects. So that would have a 29 row fractal tree (if I did my math right). Now I have to make some assumptions about how you would implement a fractal tree here, but let's assume that every level tells you it's min and max value to make it easier to tell which level you need to search in. So worst case you're object is in the 29th level, so you have to read 29 blocks in and check the min/max levels to figure out which row to search. Let's be fair and say these are in memory, we're still doing 29 comparisons right out of the gate to find the right row. Now we have the right row, but this is a file system and the rows are split up into blocks,

so we not only have to binary search each block, but the blocks themselves to find the right block with our object. And we can't do this directed either because we have no way of indexing the individual blocks, so worst case scenario we're having to read in 268435456 blocks to then do a normal binary search on _each_ block! Now lets again say just to give fractal trees an added benefit that each block has it's own min/max setting, we only have to binary search the one that will have our actual data, but we're still talking about reading in 33554432 times the number of blocks as compared to a btree!!!!!!

but lets say O(log N/2) where N is the number of elements in the row. So in the situation I describe you are looking at having to do minimum of 29 reads, one for each row,

Quoted 4 lines

but lets say O(log N/2) where N is the number of elements in the row. So in the situation I describe you are looking at having to do minimum of 29 reads, one for each row,

Hmm.

Levels are powers of two and are either full or empty. So the total item count tells you which levels are full or empty.

(gdb) print/t 1000000000
$3 = 111011100110101100101000000000

So no, definitely not reading 29 levels.

After realizing this, I have to be honest: I'm not finding your hand-wavey dismissal of the technology convincing at all. :)

There's a *ton* of detail that they don't describe about how to actually translate the logical notion of power-of-two node sizes into coherent block IO that scales. I don't doubt that it's possible.

I imagine there is, but based on what little information they've shown I don't see how it's a hands down win against b-trees. If anything we're talking about having to solve really complex problems in order to get any sort of good performance out of this thing.

You are still going to have to have at least 29 levels to accomodate 1 billion
objects, though they won't all be full (sorry I missed the must be full or empty
bit). So it looks like we'll have to actually search what 13 rows right? So
still more rows than a b-tree, and again you are talking about binary searching
each row's blocks and then following its forward pointer down to the next one,
so maybe not 100's of times slower than a b-tree, but we're not talking about a
5-10% difference either, probably still measured in multiples.

Hah my math was a little off I'll grant you but the basic idea still stands,
once we start getting into larger and larger rows we're going to have to binary
search just to find the right _block_ to use, which in my mind is much more of a
problem than having to binary search inside of multiple blocks. At the very
least as the number of objects grows the time it takes to find something in the
tree increases exponentially.

Quoted 4 lines

There's a *ton* of detail that they don't describe about how to actually translate the logical notion of power-of-two node sizes into coherent block IO that scales. I don't doubt that it's possible.

I imagine there is, but based on what little information they've shown I don't
see how it's a hands down win against b-trees. If anything we're talking about
having to solve really complex problems in order to get any sort of good performance out of this thing. Thanks,

Quoted 15 lines

You are still going to have to have at least 29 levels to accomodate 1 billion
objects, though they won't all be full (sorry I missed the must be full or empty
bit). So it looks like we'll have to actually search what 13 rows right? So
still more rows than a b-tree, and again you are talking about binary searching
each row's blocks and then following its forward pointer down to the next one,
so maybe not 100's of times slower than a b-tree, but we're not talking about a
5-10% difference either, probably still measured in multiples.

They say that they can do the block pointers in a way that limits the number for searches per row to a constant, so it's not that bad. They do less random seeks, but bigger ones at the cost of more cpu usage.

Quoted 12 lines

Hah my math was a little off I'll grant you but the basic idea still stands,
once we start getting into larger and larger rows we're going to have to binary
search just to find the right _block_ to use, which in my mind is much more of a
problem than having to binary search inside of multiple blocks. At the very
least as the number of objects grows the time it takes to find something in the
tree increases exponentially.

That's not what they say. A lot of info is missing though.

Quoted 11 lines

Quoted 4 lines

There's a *ton* of detail that they don't describe about how to actually translate the logical notion of power-of-two node sizes into coherent block IO that scales. I don't doubt that it's possible.

I imagine there is, but based on what little information they've shown I don't
see how it's a hands down win against b-trees. If anything we're talking about
having to solve really complex problems in order to get any sort of good performance out of this thing. Thanks,

They don't claim to win hands down for the search case, they say they are similar for the search case, but much better at inserts.

I don't think it's good for the linux fs general use case, but it's not as bad as you think. But it will be very hard to implement anyway unless they release more details.

I'd like to see how they do that. The fact is you are still going to get random
seeks since you have to binary search the blocks in an entire row since there is
no way you can read a several thousand block row into memory to search it, so
once your rows get pretty big you are doing just as much if not more random io
as a btree.

I don't buy that its better in the insert case either for similar reasons, you
are talking about having to rewrite entire rows to maintain the sequential nature of everything, so if you end up adding a giant row you have to go and
write the whole thing out again, so you are talking about a lot more IO than
with b-trees, albeit sequential. So maybe it's a win since it's sequential but
I wonder at what tree size that benefit no longer exists.

Of course all this analysis is based on a power point presentation and there may
be some detail I'm missing, but that's mostly my point, claiming that b-trees
are now obsolete because we can maybe do inserts faster is just idiotic.

Quoted 9 lines

I'd like to see how they do that. The fact is you are still going to get random
seeks since you have to binary search the blocks in an entire row since there is
no way you can read a several thousand block row into memory to search it, so
once your rows get pretty big you are doing just as much if not more random io
as a btree.

Why? The rows are sequential on disk, so you're never doing more random seeks than the number of rows as long as you can search faster than the disk can provide data. If they indeed can limit the number of searches per row to a constant, it shouldn't be an issue at all.

Quoted 10 lines

I don't buy that its better in the insert case either for similar reasons, you
are talking about having to rewrite entire rows to maintain the sequential nature of everything, so if you end up adding a giant row you have to go and
write the whole thing out again, so you are talking about a lot more IO than
with b-trees, albeit sequential. So maybe it's a win since it's sequential but
I wonder at what tree size that benefit no longer exists.

The worst case might be bad, but on average it should be good. I don't doubt it is always better on rotating disks, probably not on ssd's.

Quoted 6 lines

Of course all this analysis is based on a power point presentation and there may
be some detail I'm missing, but that's mostly my point, claiming that b-trees
are now obsolete because we can maybe do inserts faster is just idiotic.

It's a presentation from a company, so lots of marketing. Of course it doesn't make btrees obsolete, it's optimized for specific cases. Like they say they reduce random seeks at the cost of disk bandwidth and cpu usage. It depends on the use case if that is useful or not. Probably not for btrfs, since the future will be ssd's, and meta data will generally be cached.

Niels