From: Joanna Muench (joannam_at_spro.net)
Date: Sun Feb 22 2004 - 22:34:49 PST
Rosenblum and Ousterhout (1992) present an excellent discussion of
Sprite, a log-structured file system (LFS). They motivate the need for a
LFS over the more traditional file system such as the Unix fast file
system (FFS) with the compelling argument that most Unix systems use
over 90% of the disk's raw bandwidth seeking when making a write. They
correctly note that memory keeps getting larger (so disk reads can be
cached), processors are faster and disks are larger but disk transfer
bandwidth isn't scaling with other increases in size. The log-structured
file system is specifically optimized for disks writes, which is where
they identify the bottle-neck.
The log-structured file system is quite simple in concept. Rather than
re-writing a file that has changed, the system buffers a sequence of
changes and then writes them out to disk sequentially. File location are
store within an inode, in a similar fashion to Unix FFS. The major
difference is that LFS doesn't place these inodes in fixed positions,
but uses an inode-map. I would like to see a little more detail on how
the inode-map worked, but it seems to use a chaining mechanism similar
to others we've seen.
I found the discussion of how the authors came up with an efficient
cleaning policy to be the most interesting part of the paper. The
resulting analysis of the difference between hot (frequently selected)
and cold (rarely selected) files proved important, but not within the
locality based approach they started with. Instead they found that
cleaning up cold segments preferentially resulted in the best use of
clean up resources. This led to an elegant cost-benefit policy that had
a lower write cost than the improved FFS out to greater than 80% disk
utilization.
Crash recovery seemed well-thought out, and again much faster that FFS.
While the authors state early in the paper that that some loss of data
in a crash was acceptable, the recovery system clearly went to great
lengths to minimize that loss as much as possible using a roll-forward
mechanism.
The only point in which the paper has not withstood the test of time is
in the bold assertion "Design for file systems of the 1990's".
Unfortunately the file systems of the 1990's closely resembled those of
the 1980's, as do those of the 2000's. Maybe by 2010?
This archive was generated by hypermail 2.1.6 : Sun Feb 22 2004 - 22:31:09 PST