XHFS, CoW and File System design

The idea of XHFS came to me one night because I thought it would be funny to have a fully working File System that can run on top of something as high level as an edge Cloudflare worker equipped with a KV storage for persistence.

After daily driving it for months, dog-fooding corruption bugs here and there, fixing it, redesigning some components, fixing it again… It has proven to be useful and now has become an integral part of my computer life.

XHFS is primarily designed to be cross-platform and to run on user-space. Nothing prevents you from writing dedicated drivers for it, however.

Motivations

You really have to see it from a poor man’s perspective. Say for example you found many cheap database providers (could be Redis, Postgres, MySQL, etc.) that you don’t trust, a file on a shared computer or server machine, a shared cloud drive, some random USB, or really anything that can store and persist arbitrary data.

You can quite literally convert them into a Frankensteined ‘Cloud Storage’, and safely store encrypted cat girl pictures onto them without the fear of having people judge you.

You then format, mount and use it as what you’d normally do with any other File System.

It’s HARD

Let’s face it; File Systems are hard to implement correctly, let alone design one from scratch.

Even something as exceptionally simple as FAT32’s spec can be quite involved when it comes to the details.

But at a high level, it should still be pretty simple… right?

Sort of, you basically need:

• A File abstraction
• A Folder abstraction as a means to store a list/directory of Files
• Some way to serialize a tree-like data-structure
• Mutex your way out to protect reads from ongoing writes
• life is good

The “Not so obvious” things:

1. Decide on a good on-disk format:
   • Correctness vs Speed: Does it need to be fast? Often cannot do both.
   • How much future-proofing do you want?
   • Will it support encryption?
   • What about compression?
2. Efficient, safe allocation:
   • Allocate available storage constrained by your on-disk format design.
   • Reclaim provably unused space.
   • Heuristics for choosing the best address space for writes at time $t$.
3. File & Folders:
   • Allow in-place growth? (e.g. appending content in a log file)
   • What are all critical concurrent read/write scenarios?
4. Comprehensible failure modes:
   • What type of failures can occur given the implementation?
   • What do you do if case X fails?
   • How good can we detect corruption?
   • Are leaks recoverable?

…and more!

The engineering involved is just really hard. But it’s the good type of “hard problem” and that’s what makes it interesting.

Where to get ideas from?

Rule of thumb: don’t reinvent more than you have to; you don’t want to increase the chances of an unwanted overwrite or accidental data loss, do you?

Learn core principles and ideas from every existing File System that you have used and/or pick the popular ones.

They are all different yet the same, why is that? For example, you’d most likely want to incorporate what they share in your own design (or some of it).

In this blog post, we will focus on the data corruption aspect and how to prevent or mitigate it.

File Systems are Databases

The main difference is that File Systems are optimized for read/write ops but not so much for search and diversity of node types. This realization implies that most Databases and File Systems implementations will have their fundamentals overlap:

1. Requirement for an allocator (includes free/reclaim storage)
2. Fail-safe read/write strategies:
   • Transaction semantics
   • Locks/Mutex semantics
   • Operation logs: journal replays, write ahead logs (WAL)
   • Copy-On-Write (CoW)
3. Persistent ways of indexing data (index nodes, name/key, object mapping)
4. Data blocks, actual payload: extents, variable-sized records, etc.
5. Cleanup & Recovery:
   • Garbage collection
   • Error detection
   • Log replay
   • Fixing metadata

Journaling vs Copy-on-Write (CoW)

Journaling is fundamentally log-based consistency, you log most operations into a journal. You can safely rollback uncommitted operations afterwards (such as reclaiming unused memory after a power cut or crash). The File System state at some time $t$ can usually be recreated by replaying the full log up to that time $t$.

Copy-on-Write on the other hand relies on version-based consistency, you re-order the steps and design your data-structures such that at every externally observable commit time $t$, reachable live data are never touched during the whole operation. For example, this means that from a user’s POV while reading a file at the same time a write occurs, their version remains unchanged i.e. during a crash or power cut for example, worst case is always a leak (recoverable through GC) and never corruption as the version seen from user POV (reachable from root) should always be the version before the crash.

Journaling is often slower and can be workload-dependent due to the fact it requires a full transaction mechanism, and you are often required to write data twice (in the journal, then live data) i.e. it makes mutation durable first before making the File System state durable. This also complicates exotic features such as doing snapshots.

CoW on the other hand is more appealing for heavy write ops. For it to work however, many stars need to be aligned as its mechanism is tightly coupled to the choice of data-structures and the File System format spec itself.

CoW in XHFS

At its core, XHFS format is highly inspired from ext4: index nodes, bitmaps, extents, groups, repeated metadata across groups. Mechanically, it’s a totally different beast as every operation is designed to be copy-on-write and additional data-structures are needed just to make it work, such as extent vectors.

Speaking of which, extent vectors to me are one of these “aha” moments as its introduction was such an easy trick that it helped to implement a very cheap CoW mechanism that is both fast and resilient within just a few hours.

Here is how it works:

Initially, I had index nodes point directly to a forward linked list of extents. I designed it that way because it made data streaming really simple to implement (all you do is emit chunks in order). Writes can be made CoW pretty easily as long as you don’t expect files to mutate or grow in-place.

/Pictures/neko.jpg
 -> INode
     + size 100Kb
     + data -> ext1 -> ext2 -> ... -> extN
                                        \
                                         extN+1

A reader could be seeing extN+1 before the write is finished i.e. they could be reading garbage.

An append operation will be very hard to do CoW cheaply on a forward linked list, unless you duplicate the whole chain then atomically swap the root pointer as a way to ensure that the current readers are not seeing the new version yet (under strict version-consistency that is, where a reader must always see exactly one committed version; under a looser semantics one atomic tail link would suffice for pure appends).

A reverse linked list is another story, however: you can make an extremely cheap CoW.

/Pictures/neko.jpg
 -> INode
     + data -> extN -> ... -> ext2 -> ext1
          /
     extN+1

Notice that any concurrent readers are guaranteed to have gone past extN at any given time. And since extN+1 trusts that extN will always be a valid extent pointer, you can easily prove that at ANY given time the reader will always see either the old version if read past extN or the new version if a read operation happens after atomic swap of the root pointer. On top of that, it costs almost nothing to go from the old version to the new one.

One major downside: to read the first byte of a file, you have to walk the chain up to the first extent then process backwards again!

Seek operations are almost equivalent in both cases: a random access requires you to traverse half of the extents chain on average (assuming each extent is uniformly sized), and in the worst case you have to traverse the full range, making seek operations $O(n)$, which is very bad given that random access should always be near constant.

The solution: replace linked-list to an array

The trick is to have another layer of indirection that allows both cheap seek operations and safe mutations: an array list of pointers.

 struct INode {
     // ...
-    uint64_t* data; // immediate extent address
+    uint64_t count; // number of extents in ext_vector
+    uint64_t** ext_vector; // array of pointers each referencing an extent
 }

An append operation will look like:

/Pictures/neko.jpg
 -> INode
     + ext_vector
            +-> vector  -> addr1, addr2, ..., addrN
                           |      |           |
                          ext1   ext2        extN

            +-> vector' -> addr1, addr2, ..., addrN, addrN+1
                           |      |           |       |
                          ext1   ext2        extN    extN+1

Notice that vector != vector'.

CoW becomes easier since you never touch the physical extents, loading the extent vector list in memory is cheap; this also implies that swapping the ext_vector pointer never affects the reader.

This approach also makes seek operations run much faster as you are allowed to cache the current extent vector and index the logical offsets of the chunks you care about, which is fundamentally safe since $\text{vector} \subseteq \text{vector}’$ at any time; old references will remain valid as it follows the rule that reachable elements from root are always valid from a reader’s POV even during mutations. That being said, mutually excluding concurrent writers to the index nodes is often required, i.e. only a single writer at any externally visible time $t$ can mutate the data (or some part of it) while multiple readers can read the data at any time.

Small twist before wrapping things up: that array list is actually just an extent whose data is a list of pointers to other extents. That’s also how directory entries are implemented in XHFS. So we only ever have to implement an allocator for the extents, and we must do it really well.

There’s still a lot left to discuss, such as detecting metadata inconsistency, crash recovery, GC quiescence, atomic swaps, encryption, future-proofing data structures, and more, but each deserves its own post. For now, this one covers the CoW side of things, which is what I really wanted to talk about as it guarantees so many things without having to deal with annoying special cases once you get it right.