CSE221 FFS and LFS

Andreas Anagnostatos (aanagnos@cs.ucsd.edu)
Thu, 01 Jun 2000 08:20:34 -0700

Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S.
Fabry, "A Fast File System for Unix," ACM Transactions on Computer
Systems, 2(3), August 1984, pp. 181-197.

The paper discusses a new implementation of the old UNIX file system. By
taking into consideration many different aspects of the target system,
such as the processor, the I/O controller and the storage media, they
try to improve the throughput rates, which in traditional systems was
well below 25% of the hardware limit. They present in detail their
proposal, as well as performance comparisons between the old and the new
file system. The last sections describe the functional enhancements that
the rebuilt of the file system will allow them to perform.

The paper identifies the issues that needed to be targeted in trying to
improve the performance of the traditional file system and gives
effective solutions to most of them. Something that I do not understand
is why they are hesitant in using periodically a program to correct and
improve the file system, such as a defragmenter. Instead, they are
trying to do this work on-line, whenever new allocation is needed. Other
than that, I found the paper easy to read and the changes proposed quite

Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation
of a Log-Structured File System," Proceedings of the 13th ACM Symposium
on Operating Systems Principles, December 1991.

This paper discusses the design of a log-structured file system called
LFS. LFS stores data on disk in a sequential, log-style manner by
buffering all changes to the file system in the cache and then appending
the changes at the end of the log in a single disk operation. A
background service "cleans" the fragmented areas of the log to make room
for more free contiguous space at the head of the log. Periodically the
system writes a checkpoint entry to the log which means that the file
system is in a consistent state. This technique also makes recovery
after a crash very simple and fast by replaying the log after the last
checkpoint. Simulations and measurements show that LFS is an order of
magnitude faster than traditional file systems.

LFS seems to be a very efficient and fast file system but looking at
table 4 we see that it uses almost 15% of the disk for metadata and
indexing information which is a big percentage of the disk space. This
is probably due to the fact that checkpoint are written to disk every 30
seconds, forcing indexing information and metadata to be written to
disk. If the interval between checkpoints increased (without
compromising crash recovery by installing the log-rollforward
mechanism), the overhead of metadata and indexing info would probably
fall considerably.