I'm going to build a filesystem. The way I'm going about it might not be entirely proper. Still, I figured I should write something down, though I suspect this series won't have much actual technical content.
To open the series, allow me to explain the basic concepts of filesystems with my very limited knowledge.
A filesystem is the set of data structures and directory rules an operating system uses to organize, manage and retrieve data on disk. Whether or not you use a computer, you can't escape this storage system.
Traditional filesystems (like Ext4 and XFS) are update-in-place. The data unit (the block) has a fixed size, and changing one goes read → modify → write, back to the same spot. It's stable and solid, but since it's an overwrite, once you write, the old data is gone. Ext4 and XFS use a journal to protect metadata, so recovery after a power cut is fast. But the journal doesn't protect the data itself. And snapshots and rollback are hard to build in the filesystem alone, so you end up relying on something below it, like LVM, or on a separate backup system.
So if the traditional approach needs all this extra machinery, why not just put those features inside the filesystem? Don't overwrite data. Write it somewhere new, then point the pointer that used to reference the old data at the new data instead. When new data is written the old data isn't overwritten, and as long as some snapshot still references it, the old data stays. Snapshots come almost for free. Since old data doesn't vanish right away, rollback is easy too. By the same logic, if the power dies suddenly, as long as that final "pointer switch" hasn't completed, the disk still holds a complete old version. No long repair needed, and crash consistency is naturally stronger.
This is the COW (copy-on-write) filesystem, with Btrfs and ZFS as the famous examples. Of course, there's no free lunch. COW pays for it with write amplification, fragmentation, and the job of reclaiming space once nobody references the old data anymore.
That's the end of the main text. Everything below is not the main text.
So, why write a new COW filesystem?
One day in mid-August, while reading up on filesystems, two questions suddenly popped into my head:
- Why is the unit size of filesystems almost always 4K?
- Why do most systems go to such lengths to keep their data structures compact?
My answers:
- First, 4K is the memory page size. The page cache and memory mapping are all page-aligned, so making the block the same size as a page is simply the easiest thing to do. It's also the physical sector size after disks moved from 512-byte to 4K sectors (Advanced Format). The bigger the block, the more space small files waste (internal fragmentation), so nobody dared make it larger.
- Ten or twenty-odd years ago, storage was outrageously expensive. Every filesystem was desperately trimming itself down, saving as much disk space as possible for actual data, and leaving the organizing of structures to complicated, clever algorithms. It reminds me of a joke. The diameter of a rocket, the crystallization of human technology, is supposedly limited by the width of railway tracks, because of transport constraints. The track width came from the English, who set it to the width of two horses' backsides, because trains were originally pulled by horses. (It's a popular story, but whether it's true is doubtful. Take it as a joke.)
Looking at computers today, storage has become cheap and huge, even if prices have crept up a bit lately. An SSD has no head and no spinning platter. Data lives in NAND flash, is read and written in pages (roughly 16KiB), and inside there are multiple channels and dies working in parallel. So a big chunk of data can be pulled out at once.
So maybe a design like this
- A data unit carries, besides its data, a description of who it is and what it belongs to. It holds the information it needs about itself (self-contained). Even if it sits in some far corner of the disk, a scan is enough to find its owner.
- Since a unit can explain its own origin, the tree that used to describe it loses its main job. The tree becomes just an index for fast access to units. It has no other duties and doesn't carry small data. So it can be thrown away and rebuilt.
- For future compatibility, leave some bytes empty as extension points. That doesn't save space. It actively wastes it.
- Since we're choosing the future, old spinning hard disks stop being an optimization target. We aim entirely at new SSDs, newer FTLs and ZNS (Zoned Namespaces). That said, the SSD's own garbage collection and the filesystem's space reclamation are two different layers. The former handles erasing flash blocks. The latter handles which old versions nobody references anymore. We still have to do the latter ourselves, though it can cooperate with TRIM and ZNS.
- Since SSDs are the target, we align data to the SSD's pages and parallel stripes. Metadata is 16KiB and data is 32KiB, so one read can take in a whole stripe.
Problems still to solve
- How to implement it: who's going to build this?
- Which language: how do we make it easy to verify?
- Code style: how do we keep it simple and clear?
- What to verify with: how do we tell right from wrong? Scratches head. Fine, let's just do this.
Choosing how to implement it
I know very little about filesystems and definitely can't write a line of it. Writing this myself isn't realistic.
The keyboard goes to the AI. Tokens aren't that expensive right now, so let's be a little wasteful.
Choosing the language
- It must compile to something fast enough.
- It must have strong verification. Content goes to Rust. Write more verification. Let's be a little wasteful.
Choosing the code style
- Absolutely few branches. Too many if-else and the combinations to verify grow exponentially. AI makes mistakes easily.
- Abstract as little as possible. Don't reuse a function if you can avoid it. Copy-paste if you can. Never couple things together or mix them up.
- Variable names must be long. Seeing a name should tell you the function's past and present life. A bit bloated is fine. Write more code, write it longer. Let's be a little wasteful.
Choosing how to verify
- I don't understand code, so every plan must be put to a vote by several parties. Three AIs debate for three rounds, and I'm the referee.
- I can't tell right from wrong, so let's just simulate-verify every single point. As for power loss, QEMU, that's yours: cut at every possible crash point, replay, and see whether the filesystem still recognizes itself.
- I don't understand timing, so let's enumerate every reordering of concurrent operations. herd7, you're up: given a memory model, it lists every outcome that's allowed to happen. Order out of chaos.
** Not understanding is fine. Verify more. Let's be a little wasteful. **
And with that, our core decisions are done.
Day 1, and the most critical decisions are made.
Looking back, I reckon it's not bad. WAAAGH!
Top comments (0)