The No-Order File System (2012)
pages.cs.wisc.edu
pages.cs.wisc.edu
I've previously suggested that operating systems should have stronger file integrity guarantees. "Unit" files (rewriting replaces the whole file atomically, no reader ever sees a partially written file). That's the default. "Log" files (always end at a clean end point, don't tail off into junk). "Temp" files (disappear on reboot). And, for databases, "Managed" files.
Managed files have more I/O functions. In particular, you get two completion events on writes - "copy complete" (the caller can reuse the buffer) and "safely stored" (the data has reached its final resting place, all links are complete, etc.). Programs like databases would use that. Those are the semantics databases want, and struggle to get by flushing, waiting, and various workarounds.
When I mention this, what usually happens is that people get lost in complicated workarounds for simulating unit files. Different approaches are needed for Linux, Windows, NTFS, and various VM systems. This should Just Work.
This isn't my invention; it's from Popek's kernel in 1985 at UCLA, later seen as UCLA-Locus and as an IBM product. They had explicit commit and revert functions for file systems. I'd suggest having the default be commit on normal close or normal program exit, but if the program aborts or crashes or is killed, unit files don't commit and remain unchanged.
Oh, you just said to sync the file, not the directory? Too bad, data's gone.
I do agree with you that we need a better way to interact with the filesystem with regards to integrity and durability, although I'm not sure we entirely agree on how that would look. The idea of multiple modes makes a lot of sense:
* File-atomic mode. This is I believe trivial to implement in the filesystem layer for all filesystems, and the basic idea of this mode has existed for decades. When a reader opens a file for reading, it will never see any other writes to the file. A writer will only update the file when it closes the file [1], at which point any new reader will see only the new file created. The code is intrinsically safe in the face of multiple processes interacting with the file, and is probably the semantics most people would prefer in that situation.
* Append-only transactional files. Here, you can't random-access write into the file (but you can random-access read), only write at the end or truncate the file. A writer designates the text to append to the file as atomic blocks: the reader will only atomically see or not see the block [2]. If the file is truncated, all readers see the original contents of the file until they close.
* Raw files. Don't pretend that a file is a stream of bytes. Instead, expose it as a set of blocks that can be atomically updated (including atomically adding or removing blocks from the file at different places). I don't know filesystem semantics to give any good details here, but my understanding is that databases basically try to get these semantics today, and that getting good guarantees on fully random-access read/write semantics is effectively impossible anyways.
There does feel to me to be a bit of a hole here, where you basically get no multiprocess interactions via files unless you completely change how your code works, but I'm not sure it's entirely feasible to have a middle ground here. You can probably get close enough for most needs with a way to be notified and reopen the file in file-atomic mode, and anything where that's not sufficient probably needs you to go to raw files to really get the guarantees you want.
In addition to the basic file I/O issues, there also needs to be a way to be more transactional with directories, I think. Using paths as the basis for filesystem issues is already opening up programmers to time-of-check-time-of-use attacks today, and moving to a file descriptor-based approach for directory manipulation would solve that while opening up the possibility for better transactional support on the directory level.
The other issue is durability. Most applications in the first two modes would probably be fine with an optional durability: the result of an unexpected power outage would be a file that is out of date, but not corrupt. The filesystem could provide an optional callback on commit that returns when it is durability committed, which would handle those cases where you do actually need to make sure that the data will be committed on unexpected power outage. And the simple semantics of the first two modes means that providing durability reliably should be easy for filesystems.
[1] This also suggests that there should be a way to abort the write.
[2] You can also see how a file-atomic reader can interact with an append-only writer: the filesystem layer needs to remember the size the reader first saw and pretend that's the EOF, but otherwise there's no issue. And append-only readers will act as a file-atomic reader with respect to a file-atomic writer. The interactions make sense, that's a good sign for the model!
It is also important to note that complex semantics make building high performance systems much more difficult. Nobody in their right mind would use POSIX locks in a high performance application. More complex APIs often have implicit locking requirements which defeat the efforts made to improve scalability on multi-core systems over the past decades of system development.
Systems development is all about trade-offs, and complexity constraints choices in often unexpected ways.
I’ve been playing with the idea lately that the OS could support general transformation functions (eg “insert an ‘A’ character at this location”, “append this log entry”, “overwrite this byte range”, etc. Those transformation functions could be generic or written in wasm/BPF. The filesystem can process operations like this efficiently by storing them to a log and periodically flushing. (Or whatever makes sense for the operations).
Having a completion API that separates “buffer can be reused” and “persistently flushed” is great, and should be available for all filesystem operations. Not just for databases!
If an application wants to use traditional posix semantics, write() calls can just be one of the supported operation types.
And as a bonus, filesystem watching can become highly granular - you could subscribe to the stream of semantic changes to a file!
Having done a fair amount of work on long-term persistence of data from a Kafka queue to a distributed filesystem, I wish filesystems provided Lamport timestamp for the current time and a Lamport timestamp of the earliest uncommitted write. The distributed filesystem itself would internally keep track of the earliest uncommitted write using a vector clock, though only the minimum component of that vector would be externally visible.
When I perform a write, I want to send an opaque 64/128-bit ID of my choosing, the write location, and the data. I want to asynchronously get back a message with either an error message and the write ID, or else [the write ID, the current Lamport timestamp, and the minimum component of the uncommitted timestamp vector] (as known by the node where I just wrote). By keeping a mapping of these Lamport timestamps to my Kafka partion read offsets, this would reduce the number of network round-trips necessary to commit my Kafka partition read offsets back to Kafka. As it stands, I periodically need some extra network round-trips to query commit status of my async writes before committing read offset changes for my consumer group back to Kafka.
With the distributed filesestem keeping a vector cloock, and each async write getting back a message containing the current Lamport timestamp and the minimum uncommitted timestamp, then I could put that current time in my map of timestamps to Kafka read offsets, and then commit back to Kafka all read offsets corresponding to fs writes that are older than the earliest uncommitted write.
Presumably, the Lamport timestamp and vector clock maintenance would be piggy-backed on the internal messages necessary for the distributed filesystem to persist the writes to disk on multiple nodes. That is, I write to node A, which tells me "that's a write at time 9", and node A sends messages saying "here's a write at time 9, and my earliest uncommitted write is at time 4" to nodes B and G. The next time that node G needs to forward a write to node A, then node A will update its current time and its G component of the uncommitted timestamp vector clock. You'd also want each node to guarantee a maximum amount of time between its forwarding writes to any given node, forwarding an empty write for clock update purposes if it has been too long.
Which IBM product? I am guessing AIX PS/2 and AIX/370, since those are the two operating systems Locus Computing developed for IBM.
If extended to support non-file fds, the link function might also do some interesting things, like have TCP connections show up in the virtual file system, similar to Unix pipes.
[0] I would use honorifics, but they are married which makes it a bit confusing. [1] Which I never took but was well regarded when I was an undergrad
We collectively resolved the dilemma by all agreeing to be on a first name basis. Now that I've spent significant time in industry and have worked with more people with PhDs than were in my department in grad school, I've come to realize I was being a little bit silly. In my experience, at least once you get to the graduate level, anybody who insists on being called "doctor" seems a little full of it to me. That said, I still think it's appropriate for undergrads to call their professors "doctor," when applicable, and I was always careful to do so whenever I was in the presence of any undergrads.
Careful, this apparently is blasphemy these days.
However, in other countries, you would not call someone "professor X" unless they actually had the word "professor" in their job title. Here in Australia, a lot of academics don't – you start out as a "Lecturer", then get promoted to "Senior Lecturer", then "Associate Professor", then finally "Professor", and calling a lecturer "professor" is not done. And you certainly wouldn't use the word "professor" when addressing a PhD student.
But my question was about "professor" though, not "doctor". You say you wouldn't call a grad student instructor a "professor", but what about an instructor with a PhD (but without any formal academic title of "professor")?
When I was a grad student, I made a point when introducing myself on day 1 that I was not a professor, so please don't call me "Professor Pmiller2" Then, I said something about "if you call me "Mr. Pmiller2," I'm going to wonder if my dad is standing behind me, so, please just call me "$FIRSTNAME." That was pretty much the standard where I was among people in my department (grad students = first names).
This seems like it might gain a bit of performance in exchange for slightly-higher filesystem overhead, though it's not clear there are any stats on either. It's also not clear how exactly performance increases would surface: are reads slower but writes faster?
My intuition was wrong: reads are generally speedy, while writes are a bit slower than ext3.
The other potential shortcoming is that it provides substantially weaker consistency guarantees than what people are used to. After all of the scan threads are finished with the recovery, yes, the file system metadata will be self-consistent; but that's all you can count upon.
Suppose that a particular file is getting updated at the time of the crash. There might be several blocks that were newly allocated right before the crash, and the a larger number of data blocks that were getting overwritten right before the crash. There is no guarantee which set of data blocks will be persistent across the reboot, and which newly allocated blocks will actually be attached to the file. There might also be newly allocated blocks that were attached to the file, but the data might not be written to the block, such that stale data (the previous contents of the block, which mgiht be another user's medical data, or private e-mail, etc.) that would become visible to the file across the crash.
Basically, you create a B-tree.
Everything except the leaf nodes (that is, the root and all of the internal nodes) are stored outwardly from the center track of the hard drive, so if that's track 40, then it would be 40 then 39, then 41, then 38, then 42, etc.
Now, each leaf node is stored on the start of each track, and represents all of the blocks (after the blocks it itself takes up) on that track.
Now, when the OS needs to write or delete a block from a file, then the OS repositions the head to that track, writes the block, and then updates the leaf node (it's already on the same track -- so it's faster than moving the hard drive head to another track to do the update).
Yes, the rest of the B-Tree (on other tracks) might need to be updated as well, but if you were writing a whole bunch of blocks to an empty track at the same time, I think it could save some time...
If we were writing to a pre-existing file, and the B-Tree already had that track's leaf-node included in its pointers (that is, let's say that we're already writing to a file that already had one block on that track), then all we'd have to do is:
1) Move the hard drive head to that track
2) Write the new block
3) Update the leaf node of the B-Tree to say that the block is now part of the file.
It gets even better.
If there's a single block of the file on that track, and the track is otherwise empty, then if we have enough data to fill the track, then write all of the blocks, and cache writing to the B-Tree until all of that's done... in other words, a single write!
B-Tree entries are a key comprising FileID + DiskBlockID.
Files are ordered in DiskBlockID order.
Should be extremely fast -- for old spinning hard drives...
(Yes, I know... nobody uses spinning hard drives anymore! <g>)
On a more serious note however, Kafka sounds interesting! I will have to check it out...
The link seems to be dead :/
Could someone shed more light? In modern or older O/S, what exactly happens during the crash?
In the "not journaled" bucket, you have to hope something like fsck can make sense of the state of the filesystem. Often, the filesystem could be so "fscked" that you can't mount/boot.
In the "metadata only journaled" bucket, if you use order...meaning writing the data before you write the metadata, you will have a consistent filesystem that can be mounted, albeit possibly missing some data.
In the last bucket, you're also getting a consistent filesystem that can be mounted, but with less data loss. At the cost of some performance.
I think they are saying both buckets 2 and 3 are "modern". I certainly encountered lots of fsck giving up in the 90's on "bucket 1" type filesystems.
A bad mbr is also possible, for reasons unrelated to any filesystem. And a journaling filesystem doesn't always help with drive errors, etc. I was trying to scope down to filesystem issues due to an unorderly shutdown, where the disk drive itself is fine.
I guess you can modify the WORM fs to do the same as this No-Order fs does.
The number one problem is all the current abstractions are stupefied, with everyone conway's law-ing around everyone else.