1

A 1994 book called 'The Design and Implementation of a Log-structured file system' contains the claim "We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current Unix file systems by an order of magnitude for small-file writes while matching or exceeding Unix performance for reads and large writes." That would seem on the face of it to constitute a compelling case to start using the file system in question, which raises the question of why this did not happen.

The Unix Haters Handbook claims this is because Sprite LFS not only was not compatible with the Unix API, but could not be; that user-visible aspects of the Unix API preclude high performance in any file system that retains compatibility. Granted that this book disclaims impartiality by its very title, I'm still interested in whether they are right.

Did the classic Unix API indeed preclude high-performance file systems like Sprite LFS? If so, what features of the API were responsible for this? (And how was the problem eventually resolved? I haven't seen anyone claim modern Linux file systems lack performance, and I'm under the impression Linux retains a high degree of backward compatibility.)

  • 1
    I don't know whatproblem the UHH was talking about, but it should be noted that ZFS (which I believe manages similar performance to Sprite) and was in use in Solaris (which, being a System-V derivative, is much closer to traditional Unix than Linux ever has been) starting from only a handful of years after the UHH was published, so whatever the issue was, it must have been easy to resolve. – Jules Mar 20 '18 at 11:12
  • Without a clear definition what "Performance" means in this context, and in which setup it is to be measured, what defines a filesystem in this context and what parts are considered, no clear answer to the question and regarding any of the mentioned claims can be given. – Raffzahn Mar 20 '18 at 11:23
  • 1
    It should be noted that "current" filesystems in 1994 were mostly careful-write and didn't include logging or journalling: other than JFS1, I can't think of any mainstream filesystems at that time which included features like that. XFS and UFS didn't come out until 1994, possibly after the book was written. – ErikF Mar 20 '18 at 23:04
2

The Sprite LFS paper explains some of the performance issues its designers were trying to solve:

  • lack of locality (even if FFS tries to keep individual files’ blocks contiguous on disk, they end up separated from the inode, and often separate from related files);
  • synchronous writes.

The first issue is indeed driven by Unix-like semantics: Unix-like file systems always end up with concepts representing directories, files, and inodes. The second issue has seen common practice move back and forth over the years, and isn’t intricately tied to Unix-like semantics (although the definitions of sync operations do impose some constraints).

A variety of techniques have been used to address locality concerns, starting with block groups in ext2, more “intelligent” pre-allocation (and additional APIs allowing programs to tell the file systems about their allocation patterns), and moving to tree-structured file systems more recently.

Write performance has been addressed using a number of techniques too: for example, dropping fully-synchronous operations in favour of barriers, and using techniques from log-based file systems, re-implemented as the journal in journalling file systems.

As proof that logging file systems aren’t inherently incompatible with Unix-like semantics, you can look at real log-structured file systems which implement POSIX semantics, such as NILFS2. I’m not actually convinced that Sprite LFS itself is incompatible with Unix-like semantics; the paper doesn’t support this, and the UHH doesn’t give enough detail...

  • 1
    Actually the synchronous IO is very much a Posix thing. On other operating systems, (I'm thinking mainly of VMS and NT) you can issue an IO request and then go off and do other things while it completes. – JeremyP Mar 21 '18 at 9:54
  • @JeremyP you can do that in POSIX too, with O_NONBLOCK. The big POSIX requirement there on file systems is that any read after a write (even a non-blocking one) must return the written data. – Stephen Kitt Mar 21 '18 at 10:18
  • 2
    No it's not the same. Non blocking reads and write still operate synchronously, they just return prematurely if the IO operation can't be done. – JeremyP Mar 21 '18 at 10:26
  • 2
    @JeremyP ah yes, you’re right, the real equivalent would be AIO. That said, the synchronicity issues with regards to performance, especially for writes, have been largely dealt with by caches etc. (which is one of the reasons why POSIX AIO never got anywhere). – Stephen Kitt Mar 21 '18 at 10:36
  • 3
    And the synchronous model is simpler for the programmer. However, I don't see anything in the paper that precludes implementing the Posix IO model on top of an asynchronous API. – JeremyP Mar 21 '18 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.