Filesystem Journaling: From Write-Ahead Logging and Cedar to JFS, VxFS, XFS and ext3 (1977-2001)

Short answer: journaling in file systems is database write-ahead logging applied to metadata, and the sources opened show it in working file systems from 1987 (Cedar), with IBM's JFS described in a January 1990 paper, VxFS cited from a 1991 vendor document, Episode in 1992, XFS shipping from December 1994 and ext3 merged into the Linux kernel in November 2001. They do not name a single first journaling file system, and the Cedar report itself was only read through a university course's notes. The motive was the same each time: the Linux design paper of 1998 says that every doubling of disk capacity leads to a doubling of recovery time with traditional file-system checking, and the XFS authors wrote in 1996 that running fsck over an 8 gigabyte file system with a few hundred thousand inodes already took a few minutes (vendor statement).

The rule from databases, 1977 to 1992. Jim Gray's notes of summer 1977, printed in 1978, state the write-ahead log protocol in a section on recovery: if an object were recorded in non-volatile storage before the log records for it, a crash would leave no way to undo the update, so 'the log should be written to non-volatile storage before the object is written'. His implementation gives every log record a unique sequence number, every recoverable object a 'high water mark' equal to the largest sequence number that applies to it, and forbids writing the object until the log has been forced past that mark. Gray also says a transaction must force its redo and undo log before commit so that it can go either way. The ARIES paper of 1992 states the same rule in its own words, that an updated page may not replace the previous version on non-volatile storage until at least the undo portions of the log records describing the updates have reached stable storage. The two papers come from IBM, and the card does not claim that Gray's notes are the first statement of the rule, only the earliest opened here, written when he worked at IBM's San Jose laboratory and noting that the field has few references.

Cedar, 1987. Robert Hagmann's report (Xerox PARC CSL-87-7, August 1987, 14 pages according to the Computer History Museum catalogue; the paper appeared at SOSP in November 1987 according to the XFS and Prabhakaran et al. reference lists) describes the reimplementation of the Cedar workstation file system around a log. The ACM copy of the paper returned an access error, which was not worked around, so what follows is from the MIT 6.824 course notes on it and from later papers that describe it. The notes list the design goals as recovery after an unexpected crash while modifying the name table, damage limited to the file when a single or double sector fails, fast recovery and fast ordinary operation; they describe a name table kept as a b-tree, a log kept in a fixed disk area rather than in a file and divided in thirds, an in-memory log of modified name-table pages that is forced out by group commit 'every few seconds', and replay of the log at recovery. In the notes, creating a file takes the free pages from the volume allocation map, updates the name table in memory, writes the file's leader and data to disk synchronously and appends the changed name-table pages to the in-memory log. The Episode authors say Hagmann 'followed a similar approach in building a log-based version of the Cedar file system', the XFS authors cite him for the batching of log writes, and Prabhakaran et al. cite Cedar and Episode as examples of techniques that 'have existed for many years'.

JFS, VxFS and Episode, 1990 to 1992. The first dated reference to a Unix-style journaling file system in the sources is the January 1990 IBM Journal paper by Chang, Mergen, Rader, Roberts and Porter on AIX Version 3. Its abstract, the only part opened, says that database memory and other database techniques manage file-system metadata and that the result includes 'reliable file systems with short restart times'; it does not use the name JFS. The Episode paper (January 1992) names that paper as its reference for JFS, 'the IBM RS/6000's local file system', and describes JFS as using operation logging for the allocation bitmap and new-value-only logging for other metadata, with hardware lock bits in the memory-management unit used to decide which records to lock in memory-mapped transactional storage, a technique it says the IBM RT/PC had earlier supported although not in a commercially available file system. The same paragraph says Veritas's VxFS, cited to a 1991 Veritas overview, 'apparently also uses new value-only logging technology'. The card therefore dates JFS by the 1990 paper and by a 1992 description, not by a release note: which AIX release first shipped JFS is not shown by any opened source. The Veritas documentation read, undated and from SCO and Xinuos manuals for the later OpenServer and UnixWare products, describes VxFS 'intent logging' as a circular log of pending changes to the file-system structure that the VxFS fsck scans after a failure, nullifying or completing the active operations, with recovery 'only seconds after a system failure' (vendor claim) and a full structural fsck still required after a disk hardware failure.

Episode, written by Transarc for the OSF Distributed Computing Environment, is the best-documented early design. Its authors say it logs metadata only, uses write-ahead and old-value/new-value logging in the style of the database literature, and makes the buffer package write the log entries before it lets any dirty metadata buffer reach disk. On recovery it replays committed transactions and undoes uncommitted ones; because the log contains only transactions in progress, recovery time is proportional to activity at the crash, not to disk size, and ran 'orders of magnitude faster' than BSD's fsck (authors' claim). They explain the choice of old and new values: logging new values only means a dirty buffer cannot be written to its final place until its transaction commits, which would constrain the buffer package, and logging both decouples buffer writes from the end of transactions 'at the expense of having to write more data to the log'. Because data blocks are outside the transaction system, a crash between allocating a block and first writing it could expose old data in a new file, and Episode starts a second transaction at allocation that zeroes the block if the system crashes before the first write completes. Episode still has a salvager utility for cases such as corrupted critical metadata, and the authors say its performance characteristics are very similar to fsck.

XFS, shipping from December 1994. The SGI authors say XFS 'has been shipping to customers since December of 1994 in a version of IRIX 5.3' and that it logs all structural updates (inodes, directory blocks, free-extent and inode-allocation tree blocks, file extent maps, allocation group headers and the superblock) but not user data, writing 'a copy of the new image of the item as it should exist on disk'. Recovery 'requires nothing but replaying the block and inode images' to their real locations, so the log recovery 'does not know that it is recovering a B+ tree' and its cost does not depend on the size or complexity of the file system. They describe their scheme as very similar to the one in the Echo file system's report (Hisgen et al. 1993, not opened). Their log is written asynchronously: modified resources are unlocked and pinned in memory once the commit reaches the in-memory log buffers, which lets several updates share one log write and, they say, makes the speed of metadata updates independent of the speed of the drives within the limits of log buffering, with an option to put the log on a separate device such as a disk or non-volatile memory for very intense metadata workloads. They add that the log did not make a scavenger unnecessary: they had not provided a repair program in the initial release, 'naively thinking that it would not be necessary', their customers convinced them they were wrong, and without one 'the only way to bring a corrupted file system back on line is to re-create it with mkfs and restore it from backups'; they promised a scavenger program for all versions of XFS 'in the near future'. XFS logs new images only, whereas Episode logs old and new values, so the two designs are not the same even though both are described as write-ahead logging.

The alternative: ordering without a log. Ganger and Patt's OSDI paper of November 1994 explains the problem the logs were solving in terms of update dependencies. Renaming a file adds a new link and removes the old one; if the old directory block reaches disk first and the system stops before the new one does, neither name exists. They give three rules (never reset the old pointer before the new pointer is set, never reuse a resource before nullifying all previous pointers to it, never point to a structure before it has been initialised), say the Berkeley fast file system and many variants of the original Unix file system enforce them with synchronous writes, and that many implementations ignore some dependencies because of the cost. Their 'soft updates' keep delayed writes, track dependencies per pointer so that cycles between blocks do not arise, roll back any still-dependent update before a block is written and roll it forward afterwards; they report performance within 5 percent of a memory-based file system and more than a factor of two better than synchronous writes on metadata-intensive benchmarks (authors' research claim, 1994 prototype). McKusick and Ganger's 1999 FREENIX paper describes the 4.4BSD production implementation, says it removes most synchronous writes, reduces disk writes by 40 to 70 percent in file-intensive environments (authors' claim) and allows the system to come up immediately after a crash with a background task reclaiming lost blocks and inodes. Ganger and Patt's conclusion about logging is that write-ahead logging 'provides the same protection as soft updates, but must use delayed group commit to achieve the same performance levels' and that they planned to compare the two. Tweedie, from the journaling side, writes in 1998 that all ordering approaches including soft updates leave recovery scanning the entire disk to find unfinished operations, that with such ordering schemes 'recovery becomes more reliable, but is not necessarily any faster'; McKusick and Ganger's own text claims the opposite for the case with soft updates, so the card shows both views and does not resolve them.

ext3: from a 1998 design to a 2001 kernel. Tweedie's LinuxExpo '98 paper is a work in progress. Its stated goals were that performance should not suffer seriously, that compatibility with existing applications must not break and that reliability must not be compromised, and it chooses journaling over ordering because journaling achieves fast recovery by scanning the journal and copying committed data back. It reuses the ext2 layout: the journal is a file in a reserved inode, a new compatibility bit lets old kernels mount but not write a journaled file system, and the journal holds three kinds of block, whole metadata blocks, descriptor blocks naming where they belong, and header blocks at fixed places recording head, tail and a sequence number. Rather than one transaction per operation, it creates 'a new transaction every so often' and lets all file-system calls add to one compound transaction, so that a block updated many times is committed once; before a transaction that allocates blocks can commit, the data blocks must be on disk, which he calls dependent data. The paper predicts that newly created files will have to be synced rapidly, which 'may make the journaling filesystem unsuitable for use on /tmp filesystems'. The merge into the kernel is dated by the changelog that Linus Torvalds mailed with 2.4.15-pre4 on 12 November 2001, which lists 'Andrew Morton: ext3 merge' under pre2, by LWN's issue of 15 November 2001, and by a changelog reposted on 23 November 2001 for the final 2.4.15; the exact release day is not shown by the pages opened. The kernel documentation read says the ext3 journal is a regular file, that the HAS_JOURNAL feature is a COMPAT flag because of that, and that a RECOVER flag stops a kernel that does not understand the journal from mounting without replaying it.

What the later studies add. Prabhakaran, Arpaci-Dusseau and Arpaci-Dusseau (2005) state that 'modern file systems are journaling file systems', that the basic techniques 'have existed for many years (e.g., in Cedar and Episode)' and that scan-based recovery is 'prohibitively slow' on modern drives and RAID volumes. Their description of Linux ext3 gives three modes chosen at mount time: writeback, where only metadata is journaled and nothing orders data against the journal; ordered, where metadata is journaled and data writes to their fixed locations are ordered before the journal writes; and full data journaling, where both are logged and a data block usually reaches disk twice. Ext3 groups updates into compound transactions, logs whole blocks, writes a descriptor block, the blocks and a commit block, and recovers by replaying committed complete transactions and discarding incomplete ones. For JFS they report a preliminary black-box analysis: they infer it behaves like ordered mode, logs at the record level so that only the changed inode, index tree or directory tree structure is logged rather than a whole block, and does not by default group concurrent updates into a compound transaction, so it writes fewer journal blocks than ext3 for the same operations. Best's IBM paper of 2000 on Linux JFS says JFS 'provides a log-based, byte-level file system', logs metadata only and does not guarantee user data after a crash, wraps a file operation between TxBegin and TxEnd, writes log records and then a commit record in txCommit and replays after a crash with a utility called logredo that reads the log backwards from its end to the most recent synchronisation point; it says the default log size is '.4 of the aggregate size' rounded up to a megabyte with a maximum of 32 MB, and gives 8192 blocks of 4 KB for a 15 GB partition, which is 32 MB when multiplied out (the multiplication is the card's own).

What the sources do not settle. Which AIX release first shipped JFS and whether the 1990 paper's body describes logging as the 1992 Episode paper does; whether Cedar or JFS was the first journaling file system to reach users, since the Cedar report itself was not read; what exactly VxFS logged in 1991, because the only opened statement from the era is the Episode authors' hedged 'apparently'; whether the Linux JFS studied in 2000 and 2005 behaves like the AIX JFS of 1990 and 1992, since Best and Prabhakaran et al. describe the Linux port and Chang et al. and Episode describe the RS/6000 file system, so the logging-type descriptions of JFS (operation logging for the bitmap, record-level, undo of partial transactions) come from different systems and are shown side by side in the table, not merged; and whether soft updates or journaling recovers faster (the authors of each say theirs does, and the opened sources contain no neutral measurement). Not covered: ext4 and later changes to the Linux journal, NTFS and HFS Plus journaling (Prabhakaran et al. mention that NTFS journals records, but it was not studied here), ReiserFS, Btrfs and ZFS copy-on-write designs beyond the mention in Tweedie's survey of WAFL and log-structured systems, journals on flash, and the semantics of fsync.