BetrFS: an in-kernel file system that uses Bε trees to organize on-disk storage
betrfs.org
betrfs.org
Also, if you're interested in learning more about B^\epsilon trees, here's a talk given by Rob Johnson a few years ago at Microsoft Research: BetrFS: A Right-Optimized Write-Optimized File System https://www.youtube.com/watch?v=fBt5NuNsoII
In general, I think it's really cool that there is a file system that exists today (i.e., BetrFS) that uses data structures which didn't exist 25 years ago. It's a great example of theoreticians and systems researchers working together.
Interesting talk, I wonder how much of the perf. advantage diminishes in a finished, production-ready implementation though.
Comparing an 80%-complete R&D prototype mule against crash-resilient posix-compliant production filesystems is basically never a fair perf. comparison.
You might find that just implementing rename and hard-links properly alone is going to kill your perf. since you dispensed with on-disk inode equivalents.
Nice to see people poking at these issues nonetheless, Linux needs better filesystem options.
And there are myriad mount options for tailoring performance vs. crash-resilience/posix-compliance to the application in most the existing production filesystems. Which was honestly another aspect of the talk that was somewhat lacking; what journaling modes were used? barrier/nobarrier? was it even made equivalent to what betrfs achieves? We don't even know if a betrfs instance can successfully mount after a mid-write hard reboot.
For those who are curious, our initial goal is indeed to build a PoC and understand whether the data structures actually deliver the potential performance gains in a realistic implementation that one might expect on paper. I see a long arc from a new idea to a production-quality implementation, and several iterations of increasingly thorough evaluation and hardening.
Our current prototype is not production-ready; this is a long-term goal, but we appreciate how much work this is. More of our focus at the moment is on exploring other ways these algorithmic techniques may be useful in a storage system or how to address current problems---i.e., understanding the best way to design such a system before trying to build a production-quality version. Each of our papers has yielded significant overhauls to the design.
We would also consider it a success if other file systems adopted any ideas from our papers, or a new file system were designed by someone else that adopted these techniques.
The commenters are right that there is a gap between when an idea is exciting new research and fundable via grants versus funding the "maturing" phase of the prototype. I will hasten to say that the NSF has been supportive of maturing this system, for which we are most grateful. Nonetheless, like many projects, we could use more resources, and I would be happy to engage constructive conversations out-of-band about how to address this gap.
The criticism of LSM on the FAQ that it can't have as good read performance is perhaps a little over-egged. A fair proportion of the work I did on my project was on how to optimise the read performance. The biggest problem with a LSM tree was working out which level of the hierarchy your entry was in, which involves looking in one, then the next, until you find it. When your data is larger than your RAM, then this becomes a disc access for each level. I was working on structures that could be very small and answer that, so they were more likely to fit in RAM.
The other difference between an LSM and a B-epsilon tree is that with an LSM, the merging is done in bulk as a single operation, whereas with a B-epsilon tree it is done on a node-by-node basis as the node buffers fill up. Therefore an LSM could potentially perform more of its housekeeping in long sequential disc operations than a B-epsilon tree, which is likely to have a more random-access pattern.
With B-tree inserting a random entry require reading all b-tree page from disk until the right page is found then writing the updated page (4KB) back to disk.
While in LSM if you are trying to add a new entry that is 300byte you only need to append 300 bytes to the top level file on disk.
Reason is because with a warm cache B-tree requires at most one disk read per query since internal nodes will be in cache but for LSM you need one Read per Level.
This advantage disappear if you don't have enough memory to cache all internal nodes.
Another advantage with LSM is it only does half the space amplification as a B-tree. This is because all level except the top level contain long run of sorted data that compress very well. In a b-tree page are small and most page are not full and you need to store metadata in each page.
This is like starting a band named "The Beetles". Word about your band will never spread, because people who hear the name in passing will will subconsciously read or hear this as "The Beatles". When you talk to strangers about whether they've heard of "The Beetles", even if you put in the extra effort of "no I mean Beetles with two 'E's", in most cases they will nod their head and say yes, because the association in their head to "Beatles" has already been made and they will simply assume you or they have the spelling wrong.
The effect is that they'll not mentally register that there's something new here, so they won't put time into learning about it. Even if they tried, search results for "The Beetles" will auto-correct to "The Beatles".
Even if far from production ready for important data, I can see its immediate uses for certain kinds of software, where the disk is used as a large scratch pad for example. Lot's of random writes are common in photogrammetry in large datasets, where I imagine BetrFS can be used during compute and the final output stored on ZFS.
> NOTE: The BetrFS prototype currently only works on the 3.11.10 kernel.
This is a tad limiting, hopefully they will port it to latest...
> Our design minimizes changes to the kernel. The current code requires a few kernel patches, such as enabling direct I/O from one file system to another. We expect to eliminate most of these patches in future versions.
I prefer half-baked projects that are honest about their status over overpromised vaporware, personally
I'm struggling to see how the find/grep benchmark could possibly have such a fantastic performance benefit for betrfs, given the fact that all those filesystems are effectively reading a tree or known-location structure. The only conclusion I can reach is that maybe the betrfs test had a hot cache and the others didn't. I could possibly be persuaded if betrfs keeps all its metadata in a small easily-cached part of the disc, but there are disadvantages to that too. I don't think this test is valid.
Based on that, it seems like the outcomes of the tests are pretty reasonable.
I do agree that this kind of filesystem mechanism should give good performance benefits. But in the general case they won't be quite as fantastic as these benchmarks make out.
edit: yes, it seems [0]
"(...) The Bε-tree has since been used by both the high-performance, commercial TokuDB database [4] and the BetrFS research file system [5]. (...)"
First citation from the paper links to http://perso.ens-lyon.fr/loris.marchal/docs-data-aware/broda... – is this the paper you're referring to as prior-art for Bε-trees?
My understanding is that Be-trees are not covered by a valid patent, either because of clear prior art or because Tokutek patented a different data structure. Be-trees are simpler than the original fractal tree afaik (they were not aware of Be-trees at the time of their innovation).
If not, why not? I'm guessing mainly because of kernel context-switching overhead?
And if that's why, then could use of this filesystem be made competitive with [or better-performing than!] e.g. "LevelDB writing to ext4", if that context-switch overhead was removed — e.g. if it was either used by a kernel-mode application (i.e. a unikernel approach); or if the driver itself were moved into userspace as a library, with the expectation that you'd compile it into a single daemon process which would own and have write access to a raw block device?
(I ask because part of my job involves tending to blockchain archive-nodes, and the operational management of LevelDB at scale sometimes makes me want to pull out my hair. A million little 2MB files all in one directory, constantly being created and deleted. If I could 1. work with the keys in those databases directly as a mounted [perhaps read-only] filesystem, and 2. get for free the BetrFS equivalent of Btrfs's incremental subvolume send/receive for them, rather than trying to organize parallel rsync(1) for a million tiny files, those factors alone would be worth dealing with an experimental FS.)
And I guess, as long as the BeTree library could understand the concept of a non-expandable database file, you could just point it directly at a raw block device as its "database file" and it would be happy.
The only concern I'd have in this case is that userspace database libraries usually don't worry about the possibility of interrupted partial-block writes, since they're usually writing to files on a filesystem, and the filesystem usually handles that possibility for them; while the filesystem itself — or a library working with a raw direct-write block device — does have to worry about partial-block writes.
I think, in the case of raw "everything is a tree" storage (B-tree or Be-tree), you'd only need to ensure that 1. there's a journal for root-node-page offsets, and that 2. there's a separate freelist for root-node pages, not hanging off of the root node, but rather attached to the journal; such that root-node pages are only freed for overwrite once the journal entry for the new page is guaranteed flushed to disk.
Of course, if you were lazy, you could get the semantics of a journal and rootnode-freelist, by making this database library write its root-node pages as regular sequence-numbered files in a directory backed by a real filesystem, relying on the real filesystem to declare those files fsync(2)'ed before it's willing to delete previous root-node-page files; and then considering the effective freelist to consist only of the intersection of the freelists from all currently-visible root-node-page files.
It'd be cool to hear a conversation on the overall design of each project from the authors of both, though
I don't think it being out-of-tree is a huge deal per se. ZFS is also out-of-tree. For use on personal systems, I think the bigger thing is that the on-disk format is not officially stable/permanent yet. But if that comes before the thing is merged to the Linux kernel, I'd be willing to try it on a personal system.
Try it at your own risk, of course, but BCacheFS doesn't look like any extra work to set up on NixOS if you wanna try it there— if you tell NixOS that you wanna use bcachefs it'll just transparently pull in the required kernel for you.
Idk about filesystems development, but I agree that eventually it would be ideal for BCacheFS to have a sizeable development and maintenance team. Maybe in the early stages, though, it's good for it to have the kind of coherence and simplicity required to fit all in one person's head. Time will tell, I guess!
(Obviously I'm not comparing anything to Bepsilon - they are irrelevant until implemented as an actual linux filesystem)
I totally agree with some parent commenter here that it needs a team to work with Kent. Documentation is almost nonexistent (tho ArchWiki saves the day a little).
BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage - https://news.ycombinator.com/item?id=18202935 - Oct 2018 (46 comments)
aside: gotta love that the commenter who said they wished for this feature got downvoted before a respected filesystem developer casually dropped by to mention that it was a feature he thought was worth implementing in his cool new filesystem.
I bet it's intended to be pronounced "Better Eff Ess."
> Chris: <Grin> Definitely both.
https://web.archive.org/web/20120627065427/http://www.linuxf...
> Btrfs (pronounced as "better F S", "butter F S", "b-tree F S", or simply by spelling it out)
and I heard all of them in practice (except for spelling it out). While you can hear the difference for "b-tree F S", the other ones are much harder to distinguish.
No thank you.
Why is it called ftfs in the kernel? To confuse potential users? I mean it was probably called fractaltreefs before and they just renamed it to jab at btrfs and get publicity? I don't know, but it seems weird to me.
PS I would have to create a completly new system from scratch just to test this since my systems won't boot with such a prehistoric kernel. Also many improvements that "recently" went into the linux kernel will be moot. Last commit was from march... why was this posted now and is there any interest/activity left?
This is most certainly a use case for running this in a virtual machine.
Think of it by analogy to e.g. GPU benchmarking: you’d never use anything slower than the fastest CPU you can get your hands on, because you want to benchmark the GPU on its own as a single system bottleneck; not how well the GPU idles when held back by a bottleneck somewhere else in the system.
It relies on TokuDB, which is a database server meant for userland, already a complex piece of code, patent-encumbered, probably well tweaked but heavy. It does not port that to the kernel, rather it reimplements userland interfaces in-kernel. For example, the file-based interfaces TokuDB expects are proxied to files in a different filesystem.
B_epsilon trees are a useful data structure, they may have a place in filesystems, but it will take a from scratch implementation to prove it. Repackaging TokuDB's patented fractal trees with extra duct tape does not address any needs outside of superficial marketing.
[1]: https://github.com/oscarlab/betrfs/blob/master/README.md
I work in an adjacent research group at UNC, and I can assure you that this is a very active project. Unfortunately, because most venues now use double-blind review, the updated code can't be posted until after the associated paper(s) are accepted.
I'd encourage any potentially interested parties to star/watch the GitHub repo to keep an eye on development. I've seen some very impressive benchmark improvements from work currently in the pipeline.