A Fast File System for UNIX (Berkeley, 1984)
Jonathan Ledlie
CS736, February 11, 2000

The central concept in the Berkeley group's new file system is locality.  Instead of having all of the inodes of the file system for one partition lie at the beginning of the partition, they propose putting the inodes, the directories which contain pointers to these inodes, and the data blocks of these files, into contiguous cylinders to the greatest possible extent.  They call these contiguous cylinders cylinder groups.  Recognizing that the greatest cost in most file system actions is seek time, putting blocks which are likely to be accessed together near each other minimizes seek time.  For example, the ls command does not need to go to the head of the partition and read in the appropriate inode for each file.  Instead the relevant inodes for this directory are very likely to be only a few cylinders away, if not on the one where the disk head is now.  Joy and company achieve this locality by spreading groups of inodes over the disk (on different platters for safety) and then by keeping their direct data blocks in the same cylinder group.  The remaining data blocks are then spread in chunks over subsequent blocks - this leaves room in the initial group for the rest of the direct blocks.  They are able to allocate blocks themselves by keeping the free list as a bit map instead of a linked list, as is the case in the original file system.  They keep internal fragmentation in check (which would be the result of their larger block size), by dividing blocks into fragments, into which the tail ends of files go.  The decision of which cylinder group a file should go is up to a global policy manager and then a local manager picks the exact blocks and fragments for the file's data.  They also introduce interleaving, long file names, symlinks, and a more secure renaming call.  Locking is a thorny issue and their idea of advisory locks points out the workarounds needed in an environment where one user can do anything.  Most software seems to use their own locking policies, conveying the inadequacies of this one.