50 years in filesystems: 1984 BSD FFS

Not entirely related, but recently I began re-reading Practical File System Design with the Be File System by Dominic Giampaolo. Not exactly an up-to-date text, but a good guide to the tradeoffs involved in designing a file system.

* https://web.archive.org/web/20170213221835/http://www.nobius...

brazzy• 3 years ago

Ahh, that brings back memories - I read that over 20 years ago in preparation for my master's thesis.

JdeBP2• 3 years ago

I keep idly thinking about getting the last one. I have the 4.3 and 4.4 ones. I'm not sure that I'd find it useful, however. I wouldn't be surprised if it misses out stuff that one can see from the FreeBSD version control.

For example: It's fairly well recorded that FreeBSD switched to Mewburn rc, which it got from NetBSD, in 2002. But what isn't so well recorded, that one can only really find out from the version control history, is that this was actually a regression in one aspect, as FreeBSD had some years earlier finally got rid of an old backwards-compatibility mechanism, that Mewburn rc promptly restored.

* http://jdebp.info/FGA/rc.local-is-history.html

One of the interesting things about FreeBSD et al. is that one can reach back decades in version control and look at this stuff.

Another example: Linux people often talk about BSD-style options to their "ps" command. But they actually aren't, and BSD has not documented any such things for the entire lifetime of any "ps" command on Linux. Inspecting BSD version control history one can find where the BSD "ps" switched to getopt(3) and changed its manual, and it was in 1990, a year before Linux even existed.

eichin• 3 years ago

BSD-style is more "anti-SVR4" style, but you also need to remember that everyone working on linux ps in 1991 had years of experience with BSD 4.3 and SunOS 4; the post-reno liberated BSDs (386, Free, Net, and a dozen others that only lasted a year or two) aren't really relevant to that use of the term.

pengaru2• 3 years ago

+1 for the McKusick books. The red one in particular was such a cherished publication in my collection, for years I wished I had an equivalent for the Linux kernel, it never quite arrived.

There's also a series of videos from classes McKusick taught. Back in the 90s/early 2000s I attended some viewings of these at the apartment of some High Voltage Software employees back in IL. They'd convinced their employer to foot the bill on buying the full VHS set (I think it was $1k/tape), and hosted a bunch of viewing "parties".

Whenever McKusick had to explain some virtual memory details, he'd have vi as the running process and some user started up emacs, then he'd walk through all the minutia of paging and swap. It was quite amusing at the time, he was a master at throwing fuel on the emacs vs. vi religious wars.

I was never a huge freebsd fan, but these books were very well done and McKusick a tremendous asset to that community.

MurrayHill1980• 3 years ago

If I recall correctly, log structured file systems and in general, making file systems more robust was a real breakthrough. Before that, fsck after a crash seemed a little too exciting. I can't recall the details, but didn't Microsoft go through a similar evolution in the early days of win32 where they recruited a prominent LSFS academic researcher to help them with this problem. The article mentions this but it seemed much more important at the time.

microtonal• 3 years ago

Did log-structured filesystems really take off for mainstream computing? IIRC they suffered from write amplification and required garbage collection.

Journaling did take off in a big way, with NTFS, HFS+, ext3, etc. supporting it. This mostly removed the long fsck on most modern operating systems.

Of course, traditional filesystems + journaling are now rapidly being replaced by CoW filesystems.

bombcar• 3 years ago

My personal recollection is that long FSCK times on ever-increasing disk sizes was the driving force; I remember switching to ReiserFS simply because my 160 GB mp3 drive would take forever to FSCK if the computer lost power or had to do a hard reset. I didn't even mind the amusing file corruption you'd get from tail-packing or whatever it was because I needed that speed.

I later manually did the needful to get XFS working as it was faster on deletes, iirc.

5e92cb50239222b• 3 years ago

Depends on your definition of mainstream computing. Samsung's f2fs has been in the linux kernel for many years and is used on their Android devices. It can be used on desktop or server SSDs and gives impressive results on some workloads compared to more traditional ones like ext4, but I've been steering clear of it because at least in 2019 it had really bad error detection (just silently discarding most i/o errors, not something you'd want in a filesystem):

https://www.usenix.org/system/files/atc19-jaffer.pdf

It may have improved since then, who knows.

cryptonector2• 3 years ago

ZFS is effectively log-structured. It's what the BSD 4.4 LFS wanted to be. In many ways the two are remarkably similar. ZFS merely solved the problems that had been left unsolved (like garbage collection / free space management), dropped the "all the blocks in a transaction must be contiguous" part, added the ZIL for speed, added a notion of volumes that contain multiple datasets, and reified snapshots.

Log-structured and CoW are very closely related.

pengaru2• 3 years ago

Before that, fsck after a crash seemed a little too exciting.

It was more the opposite IME (90s-era linux): fsck after a crash was boring and time-consuming, and we grew increasingly impatient as capacities grew.

Prior to having a journaling filesystem and log replay @ reboot/mount, the filesystem was often plain conservatively implemented using methods like two-phase-commits and arguably kept more consistent due to the repeated exhaustive checking process at every dirty mount.

We went through a phase of putting a lot of trust into the hardware keeping things consistent/no-bitrot and more or less assuming everything was fine after a journal replay. Only relatively recently did we start getting checksums of metadata to detect such failures, that's still not a universal feature.

The lack of frequent fscks creates opportunity for hidden corruption from either bugs or hardware errors to go unnoticed until it's far too late to recover from... There's a reason filesystems tend to have a max mount count before a fsck is forced, even if not dirty.

mjevans• 3 years ago

Checksums for integrity at all.

Scrubs / checks / etc for online consistency check.

e40• 3 years ago

I was at UCB during this time. Very exciting! Here's a story people may not know:

The dump program, once the FFS was deployed, had not been modified to backup the last fragment of a file (because it was smaller, possibly than 4k). There was a disk crash on the VAX with the BSD source code and the disk company (Ampex, I think) came out and meticulously scrapped the bits off the disk, so CSRG could recovered the source code. There was no complete backup of it anywhere else.

That was a fun, early lesson in "test your backups".

dekhn• 3 years ago

I worked at UCB about 20 years later and when running network cable in the drop ceiling (because the UCB network was so slow) I came across an old thicknet cable labelled CSRG and was told "don't cut that- you never know who might be using it".

daveslash• 3 years ago

Low quality comment here, but I've been feeling older as I keep seeing things from the 90s show up as "30 years ago" (which feels like yesterday!). My heart dropped for a moment when I saw "50 years" and "1984" right next to each other! I literally had to stop for a moment and go "oh, no, wait..., whew!"

joveian• 3 years ago

The author seems to have forgotten about DEC's MIPS DECstation line.

https://en.wikipedia.org/wiki/DECstation

Also, per recent discussion on the NetBSD tech-kern mailing list, it is better to describe flock as per open since it is not actually tied to the file descriptor itself. The article mentions issues with dup and thinking about it as per descriptor leads to surprises.

This is still a reasonable file system design today via slightly modernized versions of FFS or basic ext2. fsck times are not that bad with SSDs.

throwawaylinux• 3 years ago

The first UNIX journaling filesystem was JFS for AIX released in 1990.

Reason077• 3 years ago

I would have assumed "FFS" was named retroactively, by other developers who came later and examined its 1984 design.

50 years in filesystems: 1984 BSD FFS

Related Stories