Paper Evaluations for 06/01/00...

Michael U. Datuin (
Thu, 1 Jun 2000 08:05:22 -0700

"A Fast File System for UNIX"

This paper describes the "new" file system of Unix. It is an improvement
over the "old" file system in that it has better performance and is easily
configurable to a wider range of hardware. The "new" file system improves
on the "old" file system by having the block size to be at least 4 kbytes.
The new file system also introduces the notion of "cylinder groups", which
is associated with some information such as a redundant copy of the
superblock, as well a listing of blocks that are available and the usage.
The map of free blocks replaces the old free list.
Another concept introduced in the paper was that of "fragments", which
divides a block into equal sizes (determined during file system creation)
for efficiently storing data that doesn't fit a block.
The paper goes on to describe how the new file system takes advantage
of the underlying hardware, which they call "parameterization", in how to
allocate blocks. It describes how blocks are positioned on the cylinders
to be "rotationally optimal", and describes the algorithm used to find these
blocks using such data structures as "rotational layout tables."
The paper also describes the two parts of its layout policies: global policies
and local allocation routines. Also, it mentions that two methods for improving
performance are to increase the locality of reference and to improve the
layout of data. It goes on to describe how inodes (using what they call a
"next-free" strategy) and data blocks are used to improve the performance.
Lastly, the new file system introduced new enhancements, such as
support for long file names, file locking schemes, symbolic links, the rename
system call, and the use of quotas.
To me it looks like they succeeded in improving the old system. The
peformance data shows that the new system met, if not exceeded, the
performance of the old system. Also, since only the underlying components
of the system were changed, there was minimal impact to the users of the


"The Design and Implementation of a Log-Structured File System"

This paper describes a new scheme for managing disk storage. The
main idea is that the log is the only structure on the disk, and that with
it's use, it is more efficient than current file systems (which they compare
with the Unix Fast File System). This log system was used to implement
the Sprite LFS.
The paper states that the most difficult challenge was how to ensure
that there are always large extents of free space for writing new data. Here
they introduce the notions of "segments" and a "segment cleaner".
This system takes advantage of new technology, such as larger memory
sizes, and what the worloads are for current computer applications. The idea
of the log system in improving performance, particularly writes, is to buffer
the changes and make the changes sequentially to disk in one large, single
The paper goes on to describe how information is retrieved from the
logs and how free space is managed (by going into detail on such items
as segment cleaning, the cleaning policies, and how Sprite LFS uses a
combination of threading and copying).
What I thought was the more interesting part of the paper was in how
the system handled crashes and recovery (something the previous paper
failed to mention). The use of checkpoints and roll-forwarding were neat ideas
(even though they mentioned that the code wasn't available on the
production system).