Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cache-Friendly B+Tree Nodes with Dynamic Fanout

jacobsherin.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#21

Post by whizzter »

thesz wrote: post #17
whizzter wrote: post #11

Earlier quoted context omitted.

This article doesn't seem to be for any disk based structure but rather in-memory, in an in-memory scenario with order requirements some users have reported B-tree's as being quite competitive in mostly-read scenarios. "Write-heavy" scenarios will probably be just fine with std::map (backed by an RB-tree) since the main downside of B-tree's is write amplification that isn't an issue since memory doesn't really have a…

We are talking about cache friendliness here, including compact data representation. B-trees algorithm requires leaf nodes to be filled up to some prespecified fill factor, usually from 50% to 70%. This is not compact by any measures. Both LSM trees and COLA allow for much more compact storage. They also pretty cache friendly in the "cache oblivious" sense.

Read up more on the COLA paper and funnily enough inspired by LSM-tree's I implemented something alike "basic-cola" a few months back (the thing I mentioned for size-coding), add to end of array, hierarchically re-sort for each of the bits of the new size that turns 0 from bottom up (divisible by 2, sort last 2, divisible by 4, sort last 4 and so on) and search with O((log2(n))^2) complexity.

B-tree fill factors are a parameter that can be tuned to avoid extra splits depending on your insertion patterns, an in-memory variant doesn't need to be tuned like a disk-based variation.

Also nothing preventing the "bottom" of an LSM variation to be a dense B-tree like structure that just gets less updates.

The COLA paper also never mentions threading, an in-memory B-tree should scale better with size if there is multi-threading while I don't see an easy way to avoid big locks with COLA, maybe why the COLA paper was from 2000 and we haven't seen much additional development on it? (LSM-tree's work beautifully of course but then you basically have the double-space issue like with semi-space garbage collectors).

In the end, what you choose is dependent on your application and patterns, COLA is a clever structure that probably shines in some scenarios.

Like my scenario was a mostly heavy on consecutive insertions as well as lookups of potentially arbitrary compound keys, perfect for cola like since those are cheap.

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#22

Post by namibj »

whizzter wrote: post #11
thesz wrote: post #3

One would be better off implementing cache-oblivious lookahead array [1] or even log-structured merge trees. [1] https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaFi07.p... Both structures exploit the fact that most of the data does not change much and can be packed as tight as one wishes. Even prefixes (and suffixes) can be factored out.

This article doesn't seem to be for any disk based structure but rather in-memory, in an in-memory scenario with order requirements some users have reported B-tree's as being quite competitive in mostly-read scenarios. "Write-heavy" scenarios will probably be just fine with std::map (backed by an RB-tree) since the main downside of B-tree's is write amplification that isn't an issue since memory doesn't really have a…

LSMs are also useful for coping with (i.e., cleaning up the messes/consolidating no-longer-relevant historic events into just their final state) streaming/windowed multi-temporality as happens from lifting iterative/fixpoint computations from batch semantics to streaming/incremental updates.

You have to consolidate when the time has come to reclaim space and to avoid needless repeat compute during accesses. Might as well use it to run full LSM tactics. Especially when keeping in mind that array mapped trees have very simple index arithmetic once you treat them as semantically literally identical to a sorted (SoA) array with a cache-benefitting address/index scrambler.

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#23

Post by dataflow »

jagged-chisel wrote: post #20
dataflow wrote: post #15

Earlier quoted context omitted.

> Strictly speaking, in the C++ object model, malloc allocates storage but doesn't create objects. No - strictly speaking, it does create objects. https://en.cppreference.com/w/cpp/memory/c/malloc.html#:~:te... It gets confusing (to say the least) if you start questioning the details, but the spec does formally intend the objects to be implicitly created.

I’m not a C++ dev … Does that mean calling constructors? So a default, parameter-less constructor must exist for the given type, and it will be called N times - right?

It's only legal for types that are sufficiently trivial, so the "called constructor" would be trivial. You'll want to follow the links in the page I sent you, it's explained: https://en.cppreference.com/w/cpp/language/classes.html#Impl...

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#24

Post by apelapan »

aidenn0 wrote: post #14
apelapan wrote: post #2

Many mentions of things being too slow and other things being high performance. I'm not doubting the truthfulness, but it would have been really nice to see some hard numbers that show the magnitude of improvement in a scenario or two.

Also, it's very hard to make a b+tree that is ever faster than other data-structures in RAM. Obviously if you don't need (or only rarely need) in-order traversing (or related operations like successor), hash-tables are very fast. If you do need in-order traversing, for small amounts of data, sorted arrays are very fast, and for large amounts of data various types of prefix-tries do very well.

If you ever write a blog post about these things, I'd love to see some measurements! :-)

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#25

Post by thesz »

whizzter wrote: post #21
thesz wrote: post #17

Earlier quoted context omitted.

We are talking about cache friendliness here, including compact data representation. B-trees algorithm requires leaf nodes to be filled up to some prespecified fill factor, usually from 50% to 70%. This is not compact by any measures. Both LSM trees and COLA allow for much more compact storage. They also pretty cache friendly in the "cache oblivious" sense.

Read up more on the COLA paper and funnily enough inspired by LSM-tree's I implemented something alike "basic-cola" a few months back (the thing I mentioned for size-coding), add to end of array, hierarchically re-sort for each of the bits of the new size that turns 0 from bottom up (divisible by 2, sort last 2, divisible by 4, sort last 4 and so on) and search with O((log2(n))^2) complexity. B-tree fill factors are…

  > while I don't see an easy way to avoid big locks with COLA
Do not modify arrays in-place, create new arrays instead. This way you can have multiple readers as the data pretty much read-only, no write locks and, again, cache-oblivious merging (fast).

Extension of COLA called Fractal Indexes (on-disk storage) are commercialized by Tokutek: https://en.wikipedia.org/wiki/Fractal_tree_index

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#26

Post by kazinator »

whizzter wrote: post #10
kazinator wrote: post #4

> This pattern was officially standardized in C99, No it wasn't; the C99 flexible array uses [] not [1] or [0]. When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array. When using C99, you also cannot use sizeof to get the offset of the [0] element of the flexible array; sizeof is allowed to pretend that there is padding as if the flexible member were not…

Even better and simpler.. Payload *item = (Payload *)malloc(offsetof(Payload, elements[N])); The rest of the article does make me vary of a lot of other things that aren't done "per-spec" if you're making your own container and probably will cause unintended bugs in the future.

Unfortunately, ISO C requires offsetof to calculate a constant; moreover, the right operand is a "member designator", which elements[N] isn't.

However, the traditional (and pretty much the only sensible) ways of defining offsetof do make it work.

N3220 draft:

  offsetof(type, member-designator)
[expands] to an integer constant expression that has type size_t, the value of which is the offset in bytes, to the subobject (designated by member-designator), from the beginning of any object of type type. The type and member designator shall be such that given

  static type t;
then the expression &(t. member-designator) evaluates to an address constant. If the specified type name contains a comma not between matching parentheses or if the specified member is a bit-field, the behavior is undefined.

This doesn't mean I won't use it, but just something to be aware of.

It might not be a bad idea to propose to ISO C that offsetof(type, array[n]) should be required to work, and for non-constant n too.

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#27

Post by aidenn0 »

apelapan wrote: post #24
aidenn0 wrote: post #14

Earlier quoted context omitted.

Also, it's very hard to make a b+tree that is ever faster than other data-structures in RAM. Obviously if you don't need (or only rarely need) in-order traversing (or related operations like successor), hash-tables are very fast. If you do need in-order traversing, for small amounts of data, sorted arrays are very fast, and for large amounts of data various types of prefix-tries do very well.

If you ever write a blog post about these things, I'd love to see some measurements! :-)

Yeah, I really should put something out there. It may be that my b+trees are suboptimal, and some sunlight on it would help.

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#28

Post by apelapan »

aidenn0 wrote: post #27
apelapan wrote: post #24

Earlier quoted context omitted.

If you ever write a blog post about these things, I'd love to see some measurements! :-)

Yeah, I really should put something out there. It may be that my b+trees are suboptimal, and some sunlight on it would help.

Measurements of actual implementations make for fruitful, constructive discussion. Doesn't need to be perfect to be useful and interesting. Hope to see it on the front page!

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#29

Post by gxt »

pluto_modadic wrote: post #5

is there an implementation of B+ trees that fluidly pulls from disk vs RAM? e.g., two B+ trees, one in RAM and one on disk, with the RAM one evicted with sieve caching? possibly a very lite WAL? something that lets you use a B+ tree bigger than RAM, and persist to disk

You can implement a BTree with nodes stored in file-backed memmaps. It's plenty fast for the usual business case.

Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout

#30

Post by kazinator »

kazinator wrote: post #26
whizzter wrote: post #10

Earlier quoted context omitted.

Even better and simpler.. Payload *item = (Payload *)malloc(offsetof(Payload, elements[N])); The rest of the article does make me vary of a lot of other things that aren't done "per-spec" if you're making your own container and probably will cause unintended bugs in the future.

Unfortunately, ISO C requires offsetof to calculate a constant; moreover, the right operand is a "member designator", which elements[N] isn't. However, the traditional (and pretty much the only sensible) ways of defining offsetof do make it work. N3220 draft: offsetof(type, member-designator) [expands] to an integer constant expression that has type size_t, the value of which is the offset in bytes, to the subobject…

In GCC, __builtint_offsetof explicitly supports the extended syntax for the member designator. when the offsetof macro uses __builtin_offsetof, the capability is a documented extension.
Post reply on HN