A Critique of Seltzer's 1993 USENIX Paper

John Ousterhout / john.ousterhout@eng.sun.com

The paper "An Implementation of a Log-Structured File System For UNIX", by Margo Seltzer et al., appears in the Winter 1993 USENIX Conference Proceedings (pages 307-326). The paper describes a new implementation of a log-structured file system (LFS) in the BSD UNIX kernel, then presents a performance comparison between three file systems: the new LFS implementation; FFS, the traditional BSD file system; and EFS, a modification of FFS that supports extent-based allocation.

The BSD implementation of LFS differs from the original Sprite implementation in several ways, some of which are definite improvements. The most notable improvement in BSD-LFS is a new approach to cleaning that uses optimistic concurrency control and a user-level cleaner; I believe that this is a much better way to do cleaning than the approach used in Sprite, and we adopted Seltzer's approach in Sprite's Zebra file system.

However, several of the differences between BSD-LFS and the Sprite implementation are steps backwards (see below for details). More importantly, the performance measurements in Section 5 of the paper are seriously flawed. The comparisons between BSD-LFS, FFS, and EFS suffer from three general problems: a bad implementation of BSD-LFS, a poor choice of benchmarks, and a poor analysis of the benchmarks. Combined together, these problems invalidate many of the paper's conclusions; LFS is a much better file system architecture than this paper suggests.

Fortunately, a newer paper by Seltzer in the Winter '95 USENIX, "File System Logging Versus Clustering: A Performance Comparison", corrects many of the flaws in the 1993 paper. Although the newer paper also has flaws, its conclusions are much closer to the truth. Thus I recommend that the quantitative results of the 1993 paper be disregarded in favor of those in the 1995 paper.

The sections below elaborate on the three general problems with Seltzer's implementation and measurements.

Poor BSD-LFS Implementation

At the time this paper was written the BSD-LFS implementation contained a number of flaws that affected its performance:

The first two of these problems were fixed for Seltzer's 1995 paper, while the other two bugs are still present in the system. I could not find a mention of these problems in the 1993 paper, yet they invalidate much of the data in Figures 9 and 12 and affect the other measurements as well.

Poor Benchmark Choice

The goal in choosing benchmarks should be to find ones that reflect as closely as possible the real-world usage of a system. This is a difficult task for file systems and I don't know of any "perfect" file system benchmarks, but the selection for the paper is particularly bad:

In discussions about the paper, Seltzer and one of her co-authors admitted that they intentionally chose benchmarks that were unfavorable to LFS and omitted benchmarks where LFS performed best. They justified this by claiming that the original LFS paper by Rosenblum and myself used benchmarks that favored LFS and they were trying to present the other side of the story. Although I disagree with this assessment of Rosenblum's and my paper, the proper response is to present a fair set of benchmarks, not an unfair set biased the other way.

Poor Analysis

Unfortunately, the analyses in the paper do not address the deficiencies in the BSD-LFS implementation and the benchmarks. As a result, readers are left with the conclusion that LFS is architecturally inferior to EFS. In addition, several important factors are omitted in the discussions of the benchmark. Here are some examples of problems:

Conclusion

Of all the performance numbers in the paper, only the single-user Andrew performance numbers are particularly useful. All of the other measurements are inadequate for one of the reasons given above. I recommend that readers ignore the measurements in this paper and use instead those in Seltzer's 1995 USENIX paper, which are better designed and reflect bug fixes in BSD-LFS.

The paper concludes that "FFS (with read and write clustering) provides comparable and sometimes superior performance to our LFS". This may have been true for certain benchmarks on the flawed version of BSD-LFS that existed when the paper was written, but it is not true for realistic benchmarks on a well-tuned LFS implementation. Seltzer's newer paper shows that in fact BSD-LFS is much faster than EFS over a wide variety of operating conditions (as much as an order of magnitude in places), and even at its worst it is only a few percent slower than EFS.