Log-structured File System (BSD)

Last updated July 31, 2020

The Log-Structured File System (or LFS) is an implementation of a log-structured file system (a concept originally proposed and implemented by John Ousterhout), originally developed for BSD. It was removed from FreeBSD and OpenBSD; the NetBSD implementation was nonfunctional until work leading up to the 4.0 release made it viable again as a production file system.^[1]

Design

Most of the on-disk format of LFS is borrowed from UFS. The indirect block, inode and directory formats are almost identical. This allows well-tested UFS file system code to be re-used; current implementations of LFS share the higher-level UFS code with the lower-level code for FFS, since both of these file systems share much in common with UFS.

LFS divides the disk into segments, only one of which is active at any one time. Each segment has a header called a summary block. Each summary block contains a pointer to the next summary block, linking segments into one long chain that LFS treats as a linear log. The segments do not necessarily have to be adjacent to each other on disk; for this reason, larger segment sizes (between 384KB and 1MB) are recommended because they amortize the cost of seeking between segments.^[2]

Whenever a file or directory is changed, LFS writes to the head of this log:

Any changed or new data blocks.
Indirect blocks updated to point to (1).
Inodes updated to point to (2).
Inode map blocks updated to point at (3).^[3]

Unlike UFS, inodes in LFS do not have fixed locations. An inode map—a flat list of inode block locations—is used to track them. As with everything else, inode map blocks are also written to the log when they are changed.

When a segment is filled, LFS goes on to fill the next free or clean segment. Segments are said to be dirty if they contain live blocks, or blocks for which no newer copies exist further ahead in the log. The LFS garbage collector turns dirty segments into clean ones by copying live blocks from the dirty segment into the current segment and skipping the rest. The summary block in each segment contains a map to track live blocks.

Generally, garbage collection is delayed until there are no clean segments left; it can also be deferred for when the system is idle. Even then, only the least-dirty segments are picked for collection. This is intended to avoid the penalty of cleaning full segments when I/O bandwidth is most needed.^[2]

At a checkpoint (usually scheduled about once every 30 seconds), LFS writes the last known block locations of the inode map and the number of the current segment to a checkpoint region at a fixed place on disk. There are two such regions; LFS alternates between them each checkpoint. Once written, a checkpoint represents the last consistent snapshot of the file system. Recovery after a crash and normal mounting work the same way—the file system simply reconstructs its state from the last checkpoint and resumes logging from there.

Disadvantages

There can be severe file system fragmentation in LFS, especially for slowly growing files or multiple simultaneous large writes. This inflicts a severe performance penalty, even though the design rationale for log-structured file systems assumes disk reads will mostly be cached away.
LFS becomes progressively less efficient as it nears maximum capacity, when the garbage collector has to run almost constantly to make clean segments available.
LFS does not allow snapshotting or versioning, even though both features are trivial to implement in general on log-structured file systems.

Notes

Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (January 1993), "An Implementation of a Log-Structured File System for UNIX" (PDF), Proceedings of the 1993 Winter Usenix

Matthews, Jeanna Neefe; Roselli, Drew; Costello, Adam M.; Wang, Randolph Y.; Anderson, Thomas E. (October 1997), "Improving the performance of log-structured file systems with adaptive methods", SOSP '97 Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles: 238–251, doi:10.1145/268998.266700, ISBN 978-0897919166

Related Research Articles

XFS is a high-performance 64-bit journaling file system created by Silicon Graphics, Inc (SGI) in 1993. It was the default file system in SGI's IRIX operating system starting with its version 5.3. XFS was ported to the Linux kernel in 2001; as of June 2014, XFS is supported by most Linux distributions, some of which use it as the default file system.

The ext2 or second extended file system is a file system for the Linux kernel. It was initially designed by Rémy Card as a replacement for the extended file system (ext). Having been designed according to the same principles as the Berkeley Fast File System from BSD, it was the first commercial-grade filesystem for Linux.

ext3, or third extended filesystem, is a journaled file system that is commonly used by the Linux kernel. It used to be the default file system for many popular Linux distributions. Stephen Tweedie first revealed that he was working on extending ext2 in Journaling the Linux ext2fs Filesystem in a 1998 paper, and later in a February 1999 kernel mailing list posting. The filesystem was merged with the mainline Linux kernel in November 2001 from 2.4.15 onward. Its main advantage over ext2 is journaling, which improves reliability and eliminates the need to check the file system after an unclean shutdown. Its successor is ext4.

John Ousterhout creator of the Tcl/Tk development environment

John Kenneth Ousterhout is a professor of computer science at Stanford University. He founded Electric Cloud with John Graham-Cumming. Ousterhout was a professor of computer science at University of California, Berkeley where he created the Tcl scripting language and the Tk platform-independent widget toolkit, and proposed the idea of coscheduling. Ousterhout led the research group that designed the experimental Sprite operating system and the first log-structured file system. Ousterhout also led the team that developed the Magic VLSI computer-aided design (CAD) program.

The Unix file system is a file system supported by many Unix and Unix-like operating systems. It is a distant descendant of the original filesystem used by Version 7 Unix.

A virtual file system (VFS) or virtual filesystem switch is an abstract layer on top of a more concrete file system. The purpose of a VFS is to allow client applications to access different types of concrete file systems in a uniform way. A VFS can, for example, be used to access local and network storage devices transparently without the client application noticing the difference. It can be used to bridge the differences in Windows, classic Mac OS/macOS and Unix filesystems, so that applications can access files on local file systems of those types without having to know what type of file system they are accessing.

A log-structured filesystem is a file system in which data and metadata are written sequentially to a circular buffer, called a log. The design was first proposed in 1988 by John K. Ousterhout and Fred Douglis and first implemented in 1992 by Ousterhout and Mendel Rosenblum for the Unix-like Sprite distributed operating system.

In computer storage, logical volume management or LVM provides a method of allocating space on mass-storage devices that is more flexible than conventional partitioning schemes to store volumes. In particular, a volume manager can concatenate, stripe together or otherwise combine partitions into larger virtual partitions that administrators can re-size or move, potentially without interrupting system use.

Soft updates is an approach to maintaining file system meta-data integrity in the event of a crash or power outage. Soft updates work by tracking and enforcing dependencies among updates to file system meta-data. Soft updates are an alternative to the more commonly used approach of journaling file systems.

In computing, a file system or filesystem controls how data is stored and retrieved. Without a file system, data placed in a storage medium would be one large body of data with no way to tell where one piece of data stops and the next begins. By separating the data into pieces and giving each piece a name, the data is easily isolated and identified. Taking its name from the way paper-based data management system is named, each group of data is called a "file." The structure and logic rules used to manage the groups of data and their names is called a "file system."

The Write Anywhere File Layout (WAFL) is a proprietary file system that supports large, high-performance RAID arrays, quick restarts without lengthy consistency checks in the event of a crash or power failure, and growing the filesystems size quickly. It was designed by NetApp for use in its storage appliances like NetApp FAS, AFF, Cloud Volumes ONTAP and ONTAP Select.

Journalling Flash File System version 2 or JFFS2 is a log-structured file system for use with flash memory devices. It is the successor to JFFS. JFFS2 has been included into the Linux kernel since September 23, 2001, when it was merged into the Linux kernel mainline as part of the kernel version 2.4.10 release. JFFS2 is also available for a few bootloaders, like Das U-Boot, Open Firmware, the eCos RTOS, the RTEMS RTOS, and the RedBoot. Most prominent usage of the JFFS2 comes from OpenWrt.

The Journaling Flash File System is a log-structured file system for use on NOR flash memory devices on the Linux operating system. It has been superseded by JFFS2.

NILFS or NILFS2 is a log-structured file system implementation for the Linux kernel. It is being developed by Nippon Telegraph and Telephone Corporation (NTT) CyberSpace Laboratories and a community from all over the world. NILFS was released under the terms of the GNU General Public License (GPL).

The following tables compare general and technical information for a number of file systems.

Marshall Kirk McKusick is a computer scientist, known for his extensive work on BSD UNIX, from the 1980s to FreeBSD in the present day. He was president of the USENIX Association from 1990 to 1992 and again from 2002 to 2004, and still serves on the board. He is on the editorial board of ACM Queue Magazine. He is known to friends and colleagues as "Kirk".

Btrfs, an abbreviation for b-tree file system, is a file system based on the copy-on-write (COW) principle, initially designed at Oracle Corporation for use in Linux. The development of Btrfs began in 2007, and since November 2013 the file system's on-disk format has been declared stable in the Linux kernel.

A journaling file system is a file system that keeps track of changes not yet committed to the file system's main part by recording the intentions of such changes in a data structure known as a "journal", which is usually a circular log. In the event of a system crash or power failure, such file systems can be brought back online more quickly with a lower likelihood of becoming corrupted.

F2FS is a flash file system initially developed by Samsung Electronics for the Linux kernel.

References

↑ Bouyer, Manuel (2007-12-15). "NetBSD 4.0 Release CHANGELOG" . Retrieved 2019-02-04..
1 2 Rosenblum, Mendel; Ousterhout, John K (February 1992), "The Design and Implementation of a Log-Structured Filesystem" (PDF), ACM Transactions on Computer Systems, 10 (1): 26–52, doi:10.1145/146941.146943 .
↑ Rosenblum, Mendel; Ousterhout, John K (June 1990), "The LFS Storage Manager" (PDF), Proceedings of the 1990 Summer Usenix: 315–324.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Bouyer, Manuel (2007-12-15). "NetBSD 4.0 Release CHANGELOG" . Retrieved 2019-02-04..

[ousterhout-1992-2] 1 2 Rosenblum, Mendel; Ousterhout, John K (February 1992), "The Design and Implementation of a Log-Structured Filesystem" (PDF), ACM Transactions on Computer Systems, 10 (1): 26–52, doi:10.1145/146941.146943 .

[3] Rosenblum, Mendel; Ousterhout, John K (June 1990), "The LFS Storage Manager" (PDF), Proceedings of the 1990 Summer Usenix: 315–324.