13 ms·

BetrFS: an in-kernel file system that uses Bε trees to organize on-disk storage

240 points by swills 5y ago

seirl 5y ago
Is the name designed to be intentionally confusing?
- pauldavis 5y ago
  Looks like they are starting with the popular BTRFS, and then making the pun of this being "better," and also implying the Be tree data structure they use. I bet it's intended to be pronounced "Better Eff Ess."
  - nerdponx 5y ago
    But that's already how a lot of people pronounce Btrfs...
    - fnord123 5y ago
      I thought everyone said butterface.
      - yakubin 5y ago
        I'm definitely calling it that starting today.
  - BlackLotus89 5y ago
    > Amanda: To clear this up, once and for all: is it pronounced BetterFS or ButterFS? > Chris: <Grin> Definitely both. https://web.archive.org/web/20120627065427/http://www.linuxfoundation.org/news-media/blogs/browse/2009/06/conversation-chris-mason-btrfs-next-generation-file-system-linux https://web.archive.org/web/20120627065427/http://www.linuxf...
  - emptysongglass 5y ago
    I personally find it really douchey. BTRFS definitely had this first and using such a name in full knowledge of BTRFS is just in poor taste.
- Lhiw 5y ago
  Only if you don't know how to pronounce btrfs.
- myself248 5y ago
  Letting programmers name their projects was always a mistake.
  - toolslive 5y ago
    letting C-level name projects is always a mistake too. "project Crossbow!" (Microsoft, Sun, EU, ...)
    - asplake 5y ago
      After a former colleague of mine, Stuart’s rule of system naming: The whizzier the name, the crappier the system. Inside corporates the correlation is uncanny.
      - toolslive 5y ago
        for operating systems, it's the opposite: the crappier the name, the better the OS. "Plan 9", "Fiasco", ...
        asplake 5y ago
        That’s the thing with correlations, they work both ways :-)
  - klyrs 5y ago
    UUID4 or go home?
  - mixmastamyk 5y ago
    WSL would like a word with you.
- vletal 5y ago
  Is it that bad? There is plenty of technical shortcuts which differ in a single letter - that should not be an issue. Plus one is pronounced /ˈbiːtriː/ and the other likely /ˈbɛtə/ (or /ˈbɛtəɹ/ in the US :)).
  - zauguin 5y ago
    I think that this is particularly bad since there are many different pronunciations for btrfs. E.g. Wikipedia says > 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.
    - vletal 5y ago
      Oh, thx for pointing that out. I was not aware of the other possible pronunciations.
    - lillecarl 5y ago
      Swedish person thinking I'll just pronounce it "bee tee arr FS". I mean that's what it says and it isn't a tounge warper so... Same with SQL, never got the sequel / whatever pronunciation, I just say the darn letters.
  - willis936 5y ago
    It's the single letter in a relatively complex acronym where the single letter doesn't distinguish the underlying name.
- mcdonje 5y ago
  They should call it Bepsilon FS, or Bepsi for short.
  - junon 5y ago
    Oh no, we're kindling the Bepis vs Conk debate now.
    - cerved 5y ago
      OMAN BEPIS
  - dkdbejwi383 5y ago
    Bepsi Max for when you need large volume support
stjo 5y ago
Looks very promising. Anybody tested it yet? The benchmarks look phenomenal https://www.betrfs.org/faq.html https://www.betrfs.org/faq.html ! 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.
- marco_craveiro 5y ago
  Indeed, sounds very interesting. However, from their github [1]: > 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... [1] https://github.com/oscarlab/betrfs https://github.com/oscarlab/betrfs
  - tyingq 5y ago
    It's also currently stacked on top of ext4, and the tree data has to sit on some other filesystem as well. So promising design, but quite a long way from ready for production.
  - klyrs 5y ago
    Not only that, but they need some fun patches... > 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
- mnw21cam 5y ago
  I'd be very cautious about the benchmarks. For example, betrfs was measured performing 1000 4-byte writes into a 1GB file. It isn't clear whether there were any sync operations - there certainly wasn't a sync after each write, although there might have been a sync after the whole set of 1000. That speed up is a simple characteristic of a filesystem that is log-structured (so it is writing those 1000 events as a single sequential disc access) and doesn't store data in 4kB blocks (so it doesn't have to load the other 4092 bytes in the block before writing it). The filesystem I wrote in 1999 for my undergrad project would have done the same thing. One of the benchmarks I wrote for my system showed exactly the same amazing performance benefit. (My benchmark had me generate a tree of a thousand small files in a ridiculously short time - ext2 thrashed all over the disc doing the same thing.) Unfortunately it is unrealistically optimistic because that isn't a write pattern that is going to happen very often. Usually each small write will have an fsync after it. Unless you actually have a thousand writes without a separating sync, then this speedup isn't going to be realised. 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.
williamkuszmaul 5y ago
The website doesn't seem to mention that several of the papers on the filesystem won best-paper awards at major conferences. The paper, Optimizing Every Operation in a Write-Optimized File System, in particular, won best-paper award at FAST '16. 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 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.
- swills 5y ago
  The reason I posted it was I saw it in the FAST21 playlist: https://www.youtube.com/watch?v=6KueHK9i8lE https://www.youtube.com/watch?v=6KueHK9i8lE
- pengaru 5y ago
  > 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 https://www.youtube.com/watch?v=fBt5NuNsoII 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.
  - zokier 5y ago
    On the other hand I can easily imagine lot of applications that don't care about full posix compliance, and are perfectly happy to trade handling of some obscure feature for improved performance.
    - 5y ago
dralley 5y ago
Wonder how it compares to bcachefs which, I believe, uses similar data structures.
- pxc 5y ago
  Bcachefs has gotten a lot more development time and seems close to ready for mainstream use, and this seems like it's much more in very early stages. It'd be cool to hear a conversation on the overall design of each project from the authors of both, though
  - kzrdude 5y ago
    Bcachefs seems like it needs the attention of a team, not just one good dev. Since it's not even merged, I guess it's still 5 years out before we can use it..
    - pxc 5y ago
      I think it's already usable in a way that BεTRFS is not. Like it can be installed on modern kernels, and there are a handful of people using it as their root filesystem today. 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!
      - kzrdude 5y ago
        Good points, but bcachefs does not have releases (ZFS has versioned releases) or a development team. (Obviously I'm not comparing anything to Bepsilon - they are irrelevant until implemented as an actual linux filesystem)
BlackLotus89 5y ago
> NOTE: The BetrFS prototype currently only works on the 3.11.10 kernel. 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?
- MisterTea 5y ago
  > 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. This is most certainly a use case for running this in a virtual machine.
  - jandrese 5y ago
    Using a VM to benchmark disk IO is a whole other can of worms.
    - derefr 5y ago
      When the limiting factor for IO perf that you’re trying to measure with your benchmark is the filesystem, rather than the disk, you don’t actually want a real disk backing your filesystem; that would just introduce noise to your measurements. Instead, you want your filesystem to be backed with an entirely in-memory block-device loopback image or some equivalent — which VMs are perfectly capable of (and in fact better at) providing. 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.
      - MobiusHorizons 5y ago
knl 5y ago
That’s all fine and dandy, but it only means that there is some good/great research in the topic. Winning best paper awards doesn’t say a thing about the implementation and handling of various edge cases. Like many research projects, this one will also probably last as long as there is funding. Remember, the goal of PhD students is to publish papers, not develop and maintain software. Thus, without skin in the game, I couldn’t trust my data/workloads to such systems.
- hhmc 5y ago
  Where did you get the impression that this is the product of PhD students?
  - lvh 5y ago
    Not OP, but the majority of people involved have .edu homepages (stints in industry, still research emphasis) and many of the alums appear to have become alums contemporaneously with the end of their academic career, most of them via Stony Brook, and finally there are a bunch of academic papers with authors clearly acting in their academic capacity (and typically prior to their stints in industry), so, IDK, seems like a reasonable assertion that this has a strong academic emphasis and a lot of the work was done by academic students. Whether it's actually unreliable is a different question, but it seems pretty reasonable to suggest that it's a research project and not a production filesystem.
  - knl 5y ago
    The sibling comment described it well. In addition, the majority of github commits are done by the people that are listed in the alumni section, while they where PhD students. There aren’t many commits from people listed as current members, and last significant commits are from the last year.
  - deleted 5y ago
    [deleted]
- wittycardio 5y ago
  You realize that most of the core software that we depend on was built by graduate students right ? Idk why the average programmer assumes that PhDs in freaking computer science can't code. Implementation and edge cases are the easy part, the hard part is design and algorithms. One just requires some focused work , the other requires real skill and intelligence
carterschonwald 5y ago
Last time I looked at this, it was using the toku db b-epsilon tree mysql db code. I wonder how much has changed.
mnw21cam 5y ago
Way back in my final year undergrad project, I put together a LSM-based filesystem that was write-optimised. I even thought that I had invented the notion of an LSM tree, but the original LSM tree paper pre-dated my invention by 3 years. I applied to take the idea and run with it for a PhD afterwards, but no joy. 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.
- vlovich123 5y ago
  Random access patterns don’t matter so much for SSDs which is where LSMs make the most amount of sense if I recall correctly.
  - skyde 5y ago
    This is not completely true. LSM does not just convert random write into sequential write. It also reduce the number of write IO when the dataset is larger than memory. 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.
    - vlovich123 5y ago
      Right. So it's more a problem of data dependency than it is with the access being random/sequential. Eg. if LSM needed to do 1 large sequential read & then jump around in RAM the same way, it would still largely have the same basic problem, no?
mirekrusin 5y ago
Wasn't tokutek's, now part of percona, fractal tree open source _BUT_ patented? edit: yes, it seems [0] [0] https://github.com/Tokutek/ft-index/blob/master/PATENTS https://github.com/Tokutek/ft-index/blob/master/PATENTS
- mbravenboer 5y ago
  Be-trees were invented in 2003, predating the Tokutek patent: see citation [1] in http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf . I think Tokutek was originally not aware of Be-trees and only later discovered the similarity to Be-trees.
  - mirekrusin 5y ago
    This paper (from 2015) seems to be saying that: "(...) 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/brodal_fagerberg_LB_EM_dict.pdf 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?
    - mbravenboer 5y ago
      Yeah, though I'm not a laywer and I have not personally studied the Tokutek patent in detail. I did consult at some point on this with somebody experienced in database-related software patents, but please do not take legal advice from me :). 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).
deleted 5y ago
[deleted]
david_draco 5y ago
I wish there was a file system that, when the CPU is unused, trawled the disk for unused files and transparently compressed them.
- pxc 5y ago
  aren't the existing forms of transparent compression for filesystems better than that?
  - david_draco 5y ago
    such as? Do you have a link?
- koverstreet 5y ago
  bcachefs does that, with the background_compression option
  - pxc 5y ago
    Why is it nice to have that behavior as an option in addition to/instead of just trying to compress everything as it's written? 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.
derefr 5y ago
If this filesystem "has comparable random-write performance to an LSM tree", would it be viable to use this filesystem directly as the storage for a key-value store (i.e. to swap out LevelDB/RocksDB for a simple library that just creates each key as its own file, expecting to be backed by this filesystem)? 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.)
- ww520 5y ago
  I think the BeTree operation model is simpler than the BeTree based file system. It might be better to use a BeTree database directly.
  - derefr 5y ago
    Yeah, that's true. Analogous to using LMDB/BoltDB, directly instead of using Btrfs. 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.
donporter 5y ago
As one of the authors of this project, first off, I appreciate the interest. 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.
- adgjlsfhk1 5y ago
  Since you're answering questions here, what is the impact of the patents on the fractal tree for other implimentations? Are other projects legally allowed to implement their own fractal/B^epsilon trees?
- matmatmatmat 5y ago
  Looking forward to the results of your work, good luck and thank you!
- dang 5y ago
  (This comment was originally a reply to https://news.ycombinator.com/item?id=29404038 https://news.ycombinator.com/item?id=29404038 but I've detached it so that more people will see it—the other thread has been moderated since it's a tedious flamewar.)
dang 5y ago
One previous thread, if anyone's curious: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage - https://news.ycombinator.com/item?id=18202935 https://news.ycombinator.com/item?id=18202935 - Oct 2018 (46 comments)
notfed 5y ago
If you want this to succeed, I suggest you change the name. 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".

240 points by swills 5y ago

seirl 5y ago

Is the name designed to be intentionally confusing?

pauldavis 5y ago
Looks like they are starting with the popular BTRFS, and then making the pun of this being "better," and also implying the Be tree data structure they use. I bet it's intended to be pronounced "Better Eff Ess."
- nerdponx 5y ago
  But that's already how a lot of people pronounce Btrfs...
  - fnord123 5y ago
    I thought everyone said butterface.
    - yakubin 5y ago
      I'm definitely calling it that starting today.
- BlackLotus89 5y ago
  > Amanda: To clear this up, once and for all: is it pronounced BetterFS or ButterFS? > Chris: <Grin> Definitely both. https://web.archive.org/web/20120627065427/http://www.linuxfoundation.org/news-media/blogs/browse/2009/06/conversation-chris-mason-btrfs-next-generation-file-system-linux https://web.archive.org/web/20120627065427/http://www.linuxf...
- emptysongglass 5y ago
  I personally find it really douchey. BTRFS definitely had this first and using such a name in full knowledge of BTRFS is just in poor taste.
Lhiw 5y ago
Only if you don't know how to pronounce btrfs.
myself248 5y ago
Letting programmers name their projects was always a mistake.
- toolslive 5y ago
  letting C-level name projects is always a mistake too. "project Crossbow!" (Microsoft, Sun, EU, ...)
  - asplake 5y ago
    After a former colleague of mine, Stuart’s rule of system naming: The whizzier the name, the crappier the system. Inside corporates the correlation is uncanny.
    - toolslive 5y ago
      for operating systems, it's the opposite: the crappier the name, the better the OS. "Plan 9", "Fiasco", ...
      - asplake 5y ago
        That’s the thing with correlations, they work both ways :-)
- klyrs 5y ago
  UUID4 or go home?
- mixmastamyk 5y ago
  WSL would like a word with you.
vletal 5y ago
Is it that bad? There is plenty of technical shortcuts which differ in a single letter - that should not be an issue. Plus one is pronounced /ˈbiːtriː/ and the other likely /ˈbɛtə/ (or /ˈbɛtəɹ/ in the US :)).
- zauguin 5y ago
  I think that this is particularly bad since there are many different pronunciations for btrfs. E.g. Wikipedia says > 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.
  - vletal 5y ago
    Oh, thx for pointing that out. I was not aware of the other possible pronunciations.
  - lillecarl 5y ago
    Swedish person thinking I'll just pronounce it "bee tee arr FS". I mean that's what it says and it isn't a tounge warper so... Same with SQL, never got the sequel / whatever pronunciation, I just say the darn letters.
- willis936 5y ago
  It's the single letter in a relatively complex acronym where the single letter doesn't distinguish the underlying name.
mcdonje 5y ago
They should call it Bepsilon FS, or Bepsi for short.
- junon 5y ago
  Oh no, we're kindling the Bepis vs Conk debate now.
  - cerved 5y ago
    OMAN BEPIS
- dkdbejwi383 5y ago
  Bepsi Max for when you need large volume support

stjo 5y ago

Looks very promising. Anybody tested it yet? The benchmarks look phenomenal https://www.betrfs.org/faq.html https://www.betrfs.org/faq.html ! 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.

marco_craveiro 5y ago
Indeed, sounds very interesting. However, from their github [1]: > 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... [1] https://github.com/oscarlab/betrfs https://github.com/oscarlab/betrfs
- tyingq 5y ago
  It's also currently stacked on top of ext4, and the tree data has to sit on some other filesystem as well. So promising design, but quite a long way from ready for production.
- klyrs 5y ago
  Not only that, but they need some fun patches... > 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
mnw21cam 5y ago
I'd be very cautious about the benchmarks. For example, betrfs was measured performing 1000 4-byte writes into a 1GB file. It isn't clear whether there were any sync operations - there certainly wasn't a sync after each write, although there might have been a sync after the whole set of 1000. That speed up is a simple characteristic of a filesystem that is log-structured (so it is writing those 1000 events as a single sequential disc access) and doesn't store data in 4kB blocks (so it doesn't have to load the other 4092 bytes in the block before writing it). The filesystem I wrote in 1999 for my undergrad project would have done the same thing. One of the benchmarks I wrote for my system showed exactly the same amazing performance benefit. (My benchmark had me generate a tree of a thousand small files in a ridiculously short time - ext2 thrashed all over the disc doing the same thing.) Unfortunately it is unrealistically optimistic because that isn't a write pattern that is going to happen very often. Usually each small write will have an fsync after it. Unless you actually have a thousand writes without a separating sync, then this speedup isn't going to be realised. 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.

williamkuszmaul 5y ago

The website doesn't seem to mention that several of the papers on the filesystem won best-paper awards at major conferences. The paper, Optimizing Every Operation in a Write-Optimized File System, in particular, won best-paper award at FAST '16. 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 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.

swills 5y ago
The reason I posted it was I saw it in the FAST21 playlist: https://www.youtube.com/watch?v=6KueHK9i8lE https://www.youtube.com/watch?v=6KueHK9i8lE
pengaru 5y ago
> 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 https://www.youtube.com/watch?v=fBt5NuNsoII 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.
- zokier 5y ago
  On the other hand I can easily imagine lot of applications that don't care about full posix compliance, and are perfectly happy to trade handling of some obscure feature for improved performance.
  - 5y ago

dralley 5y ago

Wonder how it compares to bcachefs which, I believe, uses similar data structures.

pxc 5y ago
Bcachefs has gotten a lot more development time and seems close to ready for mainstream use, and this seems like it's much more in very early stages. It'd be cool to hear a conversation on the overall design of each project from the authors of both, though
- kzrdude 5y ago
  Bcachefs seems like it needs the attention of a team, not just one good dev. Since it's not even merged, I guess it's still 5 years out before we can use it..
  - pxc 5y ago
    I think it's already usable in a way that BεTRFS is not. Like it can be installed on modern kernels, and there are a handful of people using it as their root filesystem today. 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!
    - kzrdude 5y ago
      Good points, but bcachefs does not have releases (ZFS has versioned releases) or a development team. (Obviously I'm not comparing anything to Bepsilon - they are irrelevant until implemented as an actual linux filesystem)

BlackLotus89 5y ago

> NOTE: The BetrFS prototype currently only works on the 3.11.10 kernel. 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?

MisterTea 5y ago
> 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. This is most certainly a use case for running this in a virtual machine.
- jandrese 5y ago
  Using a VM to benchmark disk IO is a whole other can of worms.
  - derefr 5y ago
    When the limiting factor for IO perf that you’re trying to measure with your benchmark is the filesystem, rather than the disk, you don’t actually want a real disk backing your filesystem; that would just introduce noise to your measurements. Instead, you want your filesystem to be backed with an entirely in-memory block-device loopback image or some equivalent — which VMs are perfectly capable of (and in fact better at) providing. 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.
    - MobiusHorizons 5y ago

knl 5y ago

That’s all fine and dandy, but it only means that there is some good/great research in the topic. Winning best paper awards doesn’t say a thing about the implementation and handling of various edge cases. Like many research projects, this one will also probably last as long as there is funding. Remember, the goal of PhD students is to publish papers, not develop and maintain software. Thus, without skin in the game, I couldn’t trust my data/workloads to such systems.

hhmc 5y ago
Where did you get the impression that this is the product of PhD students?
- lvh 5y ago
  Not OP, but the majority of people involved have .edu homepages (stints in industry, still research emphasis) and many of the alums appear to have become alums contemporaneously with the end of their academic career, most of them via Stony Brook, and finally there are a bunch of academic papers with authors clearly acting in their academic capacity (and typically prior to their stints in industry), so, IDK, seems like a reasonable assertion that this has a strong academic emphasis and a lot of the work was done by academic students. Whether it's actually unreliable is a different question, but it seems pretty reasonable to suggest that it's a research project and not a production filesystem.
- knl 5y ago
  The sibling comment described it well. In addition, the majority of github commits are done by the people that are listed in the alumni section, while they where PhD students. There aren’t many commits from people listed as current members, and last significant commits are from the last year.
- deleted 5y ago
  [deleted]
wittycardio 5y ago
You realize that most of the core software that we depend on was built by graduate students right ? Idk why the average programmer assumes that PhDs in freaking computer science can't code. Implementation and edge cases are the easy part, the hard part is design and algorithms. One just requires some focused work , the other requires real skill and intelligence

carterschonwald 5y ago

Last time I looked at this, it was using the toku db b-epsilon tree mysql db code. I wonder how much has changed.

mnw21cam 5y ago

Way back in my final year undergrad project, I put together a LSM-based filesystem that was write-optimised. I even thought that I had invented the notion of an LSM tree, but the original LSM tree paper pre-dated my invention by 3 years. I applied to take the idea and run with it for a PhD afterwards, but no joy. 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.

vlovich123 5y ago
Random access patterns don’t matter so much for SSDs which is where LSMs make the most amount of sense if I recall correctly.
- skyde 5y ago
  This is not completely true. LSM does not just convert random write into sequential write. It also reduce the number of write IO when the dataset is larger than memory. 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.
  - vlovich123 5y ago
    Right. So it's more a problem of data dependency than it is with the access being random/sequential. Eg. if LSM needed to do 1 large sequential read & then jump around in RAM the same way, it would still largely have the same basic problem, no?

mirekrusin 5y ago

Wasn't tokutek's, now part of percona, fractal tree open source _BUT_ patented? edit: yes, it seems [0] [0] https://github.com/Tokutek/ft-index/blob/master/PATENTS https://github.com/Tokutek/ft-index/blob/master/PATENTS

mbravenboer 5y ago
Be-trees were invented in 2003, predating the Tokutek patent: see citation [1] in http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf . I think Tokutek was originally not aware of Be-trees and only later discovered the similarity to Be-trees.
- mirekrusin 5y ago
  This paper (from 2015) seems to be saying that: "(...) 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/brodal_fagerberg_LB_EM_dict.pdf 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?
  - mbravenboer 5y ago
    Yeah, though I'm not a laywer and I have not personally studied the Tokutek patent in detail. I did consult at some point on this with somebody experienced in database-related software patents, but please do not take legal advice from me :). 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).

deleted 5y ago

[deleted]

david_draco 5y ago

I wish there was a file system that, when the CPU is unused, trawled the disk for unused files and transparently compressed them.

pxc 5y ago
aren't the existing forms of transparent compression for filesystems better than that?
- david_draco 5y ago
  such as? Do you have a link?
koverstreet 5y ago
bcachefs does that, with the background_compression option
- pxc 5y ago
  Why is it nice to have that behavior as an option in addition to/instead of just trying to compress everything as it's written? 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.

derefr 5y ago

If this filesystem "has comparable random-write performance to an LSM tree", would it be viable to use this filesystem directly as the storage for a key-value store (i.e. to swap out LevelDB/RocksDB for a simple library that just creates each key as its own file, expecting to be backed by this filesystem)? 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.)

ww520 5y ago
I think the BeTree operation model is simpler than the BeTree based file system. It might be better to use a BeTree database directly.
- derefr 5y ago
  Yeah, that's true. Analogous to using LMDB/BoltDB, directly instead of using Btrfs. 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.

donporter 5y ago

As one of the authors of this project, first off, I appreciate the interest. 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.

adgjlsfhk1 5y ago
Since you're answering questions here, what is the impact of the patents on the fractal tree for other implimentations? Are other projects legally allowed to implement their own fractal/B^epsilon trees?
matmatmatmat 5y ago
Looking forward to the results of your work, good luck and thank you!
dang 5y ago
(This comment was originally a reply to https://news.ycombinator.com/item?id=29404038 https://news.ycombinator.com/item?id=29404038 but I've detached it so that more people will see it—the other thread has been moderated since it's a tedious flamewar.)

dang 5y ago

One previous thread, if anyone's curious: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage - https://news.ycombinator.com/item?id=18202935 https://news.ycombinator.com/item?id=18202935 - Oct 2018 (46 comments)

notfed 5y ago

If you want this to succeed, I suggest you change the name. 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".