Locality and The Fast File System

When the UNIX operating system was first introduced, the UNIX wizard himself Ken Thompson wrote the first file system. We will call that the “old UNIX file system”, and it was really simple. Basically, its data struc-tures looked like this on the disk: S Inodes Data The super block (S) contained information about the entire file system: how big the volume is, how many inodes there are, a pointer to the head of a free list of blocks, and so forth. The inode region of the disk contained all the inodes for the file system. Finally, most of the disk was taken up by data blocks. The good thing about the old file system was that it was simple, and supported the basic abstractions the file system was trying to deliver: files and the directory hierarchy. This easy-to-use system was a real step forward from the clumsy, record-based storage systems of the past, and the directory hierarchy a true advance over simpler, one-level hierarchies provided by earlier systems. 41.1 The Problem: Poor Performance The problem: performance was terrible. As measured by Kirk McKu-sick and his colleagues at Berkeley [MJLF84], performance started off bad and got worse over time, to the point where the file systemwas delivering only 2 % of overall disk bandwidth! Themain issuewas that the old UNIX file system treated the disk like it was a random-access memory; data was spread all over the place without regard to the fact that the medium holding the data was a disk, and thus had real and expensive positioning costs. For example, the data blocks of a file were often very far away from its inode, thus inducing an expensive seek whenever one first read the inode and then the data blocks of a file (a pretty common operation). 1 2 LOCALITY AND THE FAST FILE SYSTEM Worse, the file system would end up getting quite fragmented, as the free space was not carefully managed. The free list would end up point-ing to a bunch of blocks spread across the disk, and as files got allocated, they would simply take the next free block. The result was that a logi-cally contiguous file would be accessed by going back and forth across the disk, thus reducing performance dramatically. For example, imagine the following data block region, which contains four files (A, B, C, and D), each of size 2 blocks