BetrFS: A Right-Optimized Write-Optimized File System

What people said

williamkuszmaul · 2021-12 · Recommendation

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 [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.

Read the original HN comment ↗

loeg · 2018-10 · Recommendation

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]: [VIDEO]

Read the original HN comment ↗

ww520 · 2023-12 · Reference

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 in Computer Science, pages 334–345, Springer Verlag, Berlin. 1995. [LINK] * G. S. Brodal, R. Fagerberg. Lower Bounds for External Memory Dictionaries. 2003. [LINK] * Bε-Tree, [LINK] , [VIDEO] . An Introduction to Bε-trees and Write-Optimization, [LINK] , [LINK] * Tokutek. How Fractal Trees Work. 2011. [LINK] * Hitchhiker Tree. 2016. [LINK]

Read the original HN comment ↗