BetrFS: A Right-Optimized Write-Optimized File System
Why Hacker News recommends it
HN points to it as a solid, if long, introduction to B-epsilon trees and why BetrFS is built the way it is.
What it is
A Microsoft Research talk on BetrFS, a file system built on B-epsilon trees, a write-optimized data structure. It covers WODS such as LSM-trees, how to design a file system around them, and benchmark wins over ext4 and xfs.
Recommended by 2 HN commenters across 2 different months, 2016 to 2023.
What Hacker News said
Recommends loeg · 2018-10 · on “BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage”
This isn't completely fair, although most of it is. Some of the reasons for modifying Linux are performance enhancements to the filesystem layer that only make sense with a Bε-tree filesystem (and are not possible without patching Linux). They cover this in the hour-long talk at MS research linked elsewhere in this thread.[1] (Yes, it's long, but it's a pretty good presentation.) E.g., they describe modifying the page cache to write-through small modifications to file data, rather than dirtying the entire page and writing it back later (a form of write amplification). [1]: [this video]
Recommends williamkuszmaul · 2021-12 · on “BetrFS: an in-kernel file system that uses Bε trees to organize on-disk storage”
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 [this video] 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.
Cites gbrown_ · 2016-07 · on “Datastructures for external memory”
This reminded me of BetrFS presented at FAST 15. It looks like there's a more up to date presentation online[1] where the delete performance issues have been fixed. [1] [this video]
Cites espeed · 2018-10 · on “BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage”
Talk given by Rob Johnson [1] at MSR a few years back... BetrFS: A Right-Optimized Write-Optimized File System [this video] [1] [LINK]
Cites pengaru · 2021-12 · on “BetrFS: an in-kernel file system that uses Bε trees to organize on-disk storage”
> here's a talk given by Rob Johnson a few years ago at Microsoft Research: BetrFS: A Right-Optimized Write-Optimized File System [this video] 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.
Cites ww520 · 2023-12 · on “How the append-only btree works (2010)”
Here're what I found on the idea of adding buffers to branch nodes. L. Arge described the Buffer Tree idea in 1995 with (a,b)-Tree for other data structures. Brodal and Fagerberg formalized it for B+Tree in 2003. There's also the more modern Bε-Tree, the B-epsilon Tree, with similar idea, used in the BetrFS file system and various DBs. Tokutek built TokuDB using a similar idea and called it Fractal Tree (which was derived from Bε-Tree). Hitchhicker Tree is the append-only version of Fractal Tree, similar to the append-only B+Tree. * L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes