I get excited every time I see a paper from Bradish. I've learned so much about high performance software from studying systems that he has worked on. (not to diminish his many co-authors and contributors)
I’ve only played with it at scale and haven’t had the balls to do production with it. We are still heavily reliant on our k8s stack but I want to go bare metal with Orleans.
No multithreaded write benchmarks. That's a major omission, given that's where you'll see the biggest difference between b-trees and LSM trees.
The paper also talks about the overhead of the mapping table for node lookups, and says "Bf-Tree by default pins the inner nodes in memory and uses direct pointer addresses to reference them. This allows a simpler inner node implementation, efficient node access, and reduced con-
tention on the mapping table".
But you don't have to pin nodes in memory to use direct pointer lookups. Reserve a field in your key/value pair for a direct in-memory pointer, and after chasing it check that you got the node you expect; only fall back to the mapping table (i.e. hash table of cached nodes) if the pointer is uninitialized or you don't get the node you expect.
"For write, conventional B-Tree performs the worst, as a single
record update would incur a full page write, as evidenced by the
highest disk IO per operation."
Only with a random distribution, but early on the paper talks about benchmarking with a Zip-f distribution. Err?
The benchmark does look like a purely random distribution, which is not terribly realistic for most use cases. The line about "a single record updating incurring a full page write" also ignores the effect of cache size vs. working set size, which is a rather important detail. I can't say I trust the benchmark numbers.
Prefix compression - nice to see this popping up.
"hybrid latching" - basically, they're doing what the Linux kernel calls seqlocks for interior nodes. This is smart, but given that their b-tree implementation doesn't use it, you shouldn't trust the b-tree benchmarks.
However, I found that approach problematic - it's basically software transactional memory, with all the complexity that implies, and it bleeds out into too much of the rest of your b-tree code. Using a different type of lock for interior nodes where read locks only use percpu counters gives the same performance (read locks touch no cachelines shared by other CPUs) for much lower complexity.
Not entirely state of the art, and I see a lot of focus on optimizations that likely wouldn't survive in a larger system, but it does look like a real improvement over LSM trees.
Sure, but on principle, looking at the paper, I'd expect it to outperform B-trees since write amplification is reduced, generally. You thinking about cases requiring ordering of writes to a given record (lock contention)?
I think their claims of write amplification reduction are a bit overstated given more realistic workloads.
It is true that b-trees aren't ideal in that respect, and you will see some amount of write amplification, but not enough that it should be a major consideration, in my experience
You really have to take into account workingset size and cache size to make any judgements there; your b-tree writes should be given by journal/WAL reclaim, which will buffer up updates.
A purely random update workload will kill a conventional b-tree on write amplification - like I mentioned, that's the absolute worst case scenario for a b-tree. But it just doesn't happen in the real world.
For the data I can give you, that would be bcachefs's hybrid b-tree - large btree nodes (256k, typically) which are internally log structured; I would consider it a minor variation on a classical b-tree. The log structuring mean that we can incrementally write only the dirty keys in a node, at the cost of some compaction overhead (drastically less than a conventional LSM).
In actual real world usage, when I've looked at the numbers (not recently, so this may have changed) we're always able to do giant highly efficient b-tree writes - the journal and in-memory cache are batching things up as much as we want - which means write amplification is negligible.
Also you can use dense B+-Trees for reads possibly with some bloom filters or the like if you expect/profile a high fraction of negative lookups, use LSM to eventually compact, and get both SSD/ZNS friendly write patterns as well as full freedom to only compact a layer once it's finer state is no longer relevant to any MVCC/multi-phase-commit schemes. Being able to e.g. run a compression algorithm until you just exceed the storage page size, take it's state from just before it exceeded, and begin the next bundle with the entry that made you exceed the page size.... It's quite helpful when storage space or IO bandwidth is somewhat scarce.
If you're worried about the last layer being a giant unmanageably large B+-Tree, just shard it similarly in key space to not need much free temporary working space on SSD to stream the freshly compacted data to while the inputs to the compaction still serve real time queries.
Of course mileage may vary with different workloads, but are there any good benchmarks/suites to use for comparison in cases like these? They used YCSB but I don't know if those workloads ([1]) are relevant to modern/typical access patterns nor if they're applicable to SQL databases.
You thinking about running some benchmarks in a bcachefs branch (:pray:)?
I want to see this data structure prototyped in PostgreSQL.
They're ancient, I only have pure random and sequential benchmarks - no zipf distribution, which really should be included.
Feel free to play around with them if you want :) I could even find the driver code, if you want.
I've always been curious about PostgreSQL's core b-tree implementation. I ran into a PostgreSQL developer at a conference once, and exchanged a few words that as I recall were enough to get me intrigued, but never learned anything about it.
In a system as big, complex and well optimized as either bcachefs or postgres, the core index implementation is no longer the main consideration - there's layers and layers, and the stuff that's fun to optimize and write paper about eventually gets buried (and you start thinking a lot more about how to lay out your data structures and less about optimizing the data structures themselves).
But you know in something like that there's going to be some clever tricks, that few people know about or even remember anymore :)
I think a fair comparison would be against a whitepaper? Clearly this is an exploratory venture and not production grade software.
You managed to clone the repo an run your test by yourself, whatever the outcome is this is a plus against the standard model for scientific research.
Also, a breath of fresh air among every other show HN thread using hundreds of adjectives to describe the "behavior" of a fully vibed system. I think this is a good model for presenting engineering projects.
> You managed to clone the repo an run your test by yourself, whatever the outcome is this is a plus against the standard model for scientific research.
That's so true, which is kinda funny since one of the cornerstone of scientific thinking is reproducibility.
Interesting. I've been on/off working on something, though it's an append-only hash index thing (based on Erlang's Bitcask): https://git.sr.ht/~tombert/feocask
I haven't done any benchmarks on it yet so I have no idea how well it performs, but I have a very strict "no explicit lock" policy, so everything is handled with separate files with a reconciliation service that uses a vector clock to determine ordering.
NOTE: A lot of this is AI-assisted, treat what I have written as more of a whiteboard proof of concept. I'm in the process of rewriting it by hand to do some more aggressive optimizations.
Why not add an LSM memtable on top of the cow b+ tree?
Use the skiplist as a write buffer and write to the b+ tree in batches when the skiplist is frozen.
Bftree solves one non-obvious pain point - caching when your data set is random (the key is a hash) and the data is smaller than the page size. LSM reads are based on block size; same with caching. So if your record is 8 bytes, you end up caching the remaining ~4 KB, and the hit rate will be pretty low.
I get excited every time I see a paper from Bradish. I've learned so much about high performance software from studying systems that he has worked on. (not to diminish his many co-authors and contributors)
Some of his other projects:
[0] https://github.com/microsoft/garnet [1] https://github.com/microsoft/FASTER [2] https://github.com/microsoft/Trill
You should check out Microsoft Orleans
https://github.com/dotnet/orleans
I am very familiar with it! My current project at work is taking an Orleans based payment processing system to production
Nice!!
I’ve only played with it at scale and haven’t had the balls to do production with it. We are still heavily reliant on our k8s stack but I want to go bare metal with Orleans.
Minor typo. Author's name is - Badrish.
No multithreaded write benchmarks. That's a major omission, given that's where you'll see the biggest difference between b-trees and LSM trees.
The paper also talks about the overhead of the mapping table for node lookups, and says "Bf-Tree by default pins the inner nodes in memory and uses direct pointer addresses to reference them. This allows a simpler inner node implementation, efficient node access, and reduced con- tention on the mapping table".
But you don't have to pin nodes in memory to use direct pointer lookups. Reserve a field in your key/value pair for a direct in-memory pointer, and after chasing it check that you got the node you expect; only fall back to the mapping table (i.e. hash table of cached nodes) if the pointer is uninitialized or you don't get the node you expect.
"For write, conventional B-Tree performs the worst, as a single record update would incur a full page write, as evidenced by the highest disk IO per operation."
Only with a random distribution, but early on the paper talks about benchmarking with a Zip-f distribution. Err?
The benchmark does look like a purely random distribution, which is not terribly realistic for most use cases. The line about "a single record updating incurring a full page write" also ignores the effect of cache size vs. working set size, which is a rather important detail. I can't say I trust the benchmark numbers.
Prefix compression - nice to see this popping up.
"hybrid latching" - basically, they're doing what the Linux kernel calls seqlocks for interior nodes. This is smart, but given that their b-tree implementation doesn't use it, you shouldn't trust the b-tree benchmarks.
However, I found that approach problematic - it's basically software transactional memory, with all the complexity that implies, and it bleeds out into too much of the rest of your b-tree code. Using a different type of lock for interior nodes where read locks only use percpu counters gives the same performance (read locks touch no cachelines shared by other CPUs) for much lower complexity.
Not entirely state of the art, and I see a lot of focus on optimizations that likely wouldn't survive in a larger system, but it does look like a real improvement over LSM trees.
Sure, but on principle, looking at the paper, I'd expect it to outperform B-trees since write amplification is reduced, generally. You thinking about cases requiring ordering of writes to a given record (lock contention)?
I think their claims of write amplification reduction are a bit overstated given more realistic workloads.
It is true that b-trees aren't ideal in that respect, and you will see some amount of write amplification, but not enough that it should be a major consideration, in my experience
You really have to take into account workingset size and cache size to make any judgements there; your b-tree writes should be given by journal/WAL reclaim, which will buffer up updates.
A purely random update workload will kill a conventional b-tree on write amplification - like I mentioned, that's the absolute worst case scenario for a b-tree. But it just doesn't happen in the real world.
For the data I can give you, that would be bcachefs's hybrid b-tree - large btree nodes (256k, typically) which are internally log structured; I would consider it a minor variation on a classical b-tree. The log structuring mean that we can incrementally write only the dirty keys in a node, at the cost of some compaction overhead (drastically less than a conventional LSM).
In actual real world usage, when I've looked at the numbers (not recently, so this may have changed) we're always able to do giant highly efficient b-tree writes - the journal and in-memory cache are batching things up as much as we want - which means write amplification is negligible.
Also you can use dense B+-Trees for reads possibly with some bloom filters or the like if you expect/profile a high fraction of negative lookups, use LSM to eventually compact, and get both SSD/ZNS friendly write patterns as well as full freedom to only compact a layer once it's finer state is no longer relevant to any MVCC/multi-phase-commit schemes. Being able to e.g. run a compression algorithm until you just exceed the storage page size, take it's state from just before it exceeded, and begin the next bundle with the entry that made you exceed the page size.... It's quite helpful when storage space or IO bandwidth is somewhat scarce.
If you're worried about the last layer being a giant unmanageably large B+-Tree, just shard it similarly in key space to not need much free temporary working space on SSD to stream the freshly compacted data to while the inputs to the compaction still serve real time queries.
Of course mileage may vary with different workloads, but are there any good benchmarks/suites to use for comparison in cases like these? They used YCSB but I don't know if those workloads ([1]) are relevant to modern/typical access patterns nor if they're applicable to SQL databases.
You thinking about running some benchmarks in a bcachefs branch (:pray:)?
I want to see this data structure prototyped in PostgreSQL.
[1]: https://github.com/brianfrankcooper/YCSB/tree/master/workloa...
I've got microbenchmarks for the bcachefs btree here: https://evilpiepirate.org/git/bcachefs.git/tree/fs/bcachefs/...
They're ancient, I only have pure random and sequential benchmarks - no zipf distribution, which really should be included.
Feel free to play around with them if you want :) I could even find the driver code, if you want.
I've always been curious about PostgreSQL's core b-tree implementation. I ran into a PostgreSQL developer at a conference once, and exchanged a few words that as I recall were enough to get me intrigued, but never learned anything about it.
In a system as big, complex and well optimized as either bcachefs or postgres, the core index implementation is no longer the main consideration - there's layers and layers, and the stuff that's fun to optimize and write paper about eventually gets buried (and you start thinking a lot more about how to lay out your data structures and less about optimizing the data structures themselves).
But you know in something like that there's going to be some clever tricks, that few people know about or even remember anymore :)
I think a better candidate to prototype would be SQLite, at least to have a better sense of how would bf-tree behave on real world
I've tested with wal enabled, got deadlock several times, so looks raw for now
I think a fair comparison would be against a whitepaper? Clearly this is an exploratory venture and not production grade software.
You managed to clone the repo an run your test by yourself, whatever the outcome is this is a plus against the standard model for scientific research.
Also, a breath of fresh air among every other show HN thread using hundreds of adjectives to describe the "behavior" of a fully vibed system. I think this is a good model for presenting engineering projects.
> You managed to clone the repo an run your test by yourself, whatever the outcome is this is a plus against the standard model for scientific research.
That's so true, which is kinda funny since one of the cornerstone of scientific thinking is reproducibility.
IMHO they're using the best tool for this, nix.
If anyone else was wondering,
> The ‘f’ in Bf-Tree stands for “faster”
Interesting. I've been on/off working on something, though it's an append-only hash index thing (based on Erlang's Bitcask): https://git.sr.ht/~tombert/feocask
I haven't done any benchmarks on it yet so I have no idea how well it performs, but I have a very strict "no explicit lock" policy, so everything is handled with separate files with a reconciliation service that uses a vector clock to determine ordering.
NOTE: A lot of this is AI-assisted, treat what I have written as more of a whiteboard proof of concept. I'm in the process of rewriting it by hand to do some more aggressive optimizations.
Why not add an LSM memtable on top of the cow b+ tree? Use the skiplist as a write buffer and write to the b+ tree in batches when the skiplist is frozen.
Bftree solves one non-obvious pain point - caching when your data set is random (the key is a hash) and the data is smaller than the page size. LSM reads are based on block size; same with caching. So if your record is 8 bytes, you end up caching the remaining ~4 KB, and the hit rate will be pretty low.
Was the link changed? Right now it points to the github page, and it doesn't really say why anyone would care about it.
The top of the readme links to the accompanying paper, which explains very clearly why you would care: https://badrish.net/papers/bftree-vldb2024.pdf
I admit I’ll agree that that extra hop was a little confusing to me though. I guess people just like GitHub and don’t like PDFs.
That's on me, I thought it would receive the attention it deserves if people jump straight into the code (and see the "written in Rust btw").