Citation:
M.K. McKusick, W.N. Joy, S.J.Leffler, and R.S. Fabry, "A Fast File System
for UNIX", ACM Transactions on Computer Systems, August 1984, pp. 181-197.

* Summary

The UNIX file system is analyzed and reimplemented for better performance.
The new system provides substantially higher throughput by using more 
flexible allocation policies that allow better locality of reference. In
addition, long needed enhancements to the API are discussed.

* What's Wrong with UNIX FS

- Only achieves 20KB/s data transfer (2% of max sequential rate)

* Problem #1: Small Block Size

The original UNIX FS had 512B blocks. Since there are fixed costs for every
disk transfer, it makes sense to reduce overhead by increasing the amount
of data accessed per transfer. In addition, small block sizes lead to an
increase in the number of indirect blocks necessary.

Solution: Increase the block size (duh!!). But larger blocks leads to internal
fragmentation and wasted space, so we need to support fragments. All files
are composed of a number of full blocks and at most one fragmented one. Free
fragments are available for use by other files.

* Problem #2: Unorganized Freelist

Original free list was implemented as a linked list of free blocks, which
provided good performance in the initial stages of use. However, over time
with the creation and deletion of files, the free list became scrambled and
led to random placement of file blocks all over the disk. This caused 
additional seeks for even sequential disk transfers.

Solution: Use a bit map of blocks to represent free/allocated

* Problem #3: Poor Locality of Reference

The original UNIX FS placed all inodes together at the beginning of the disk,
and all data blocks in the remaining space. Thus, every file access incurred
at least two seeks. In addition, the inodes of files in the same directory
were not colocated, leading to a seek for every inode when performing common
operations such as listing a directory.

Solution: Each disk partition is divided into one or more cylinder groups 
consisting of one or more consecutive cylinders on the disk. Each cylinder
group includes bookkeeping information with a redundant superblock, space for
a fixed number of inodes, a bit map for the free list of blocks in the group, 
summary information describing the usage of data blocks within the group, and
of course data blocks. The bookkeeping information is kept at a different 
offset for each cylinder group, to increase reliability of maintaining a valid
superblock. 

To maintain locality for a single file, runs of blocks for the file are 
allocated from the same cylinder group. In order to prevent one file from 
filling an entire cylinder group, the group on which data is stored is
switched after the first 48KB and every 1MB thereafter. To maintain locality
for files and inodes in the same directory, they are kept in the same cylinder
group. To accomodate expansion of the number of files in a directory, the
directories are spread amongst the cylinder groups, with new directories being
placed in groups with a greater than average # of free inodes and smallest #
of directories. 

Since maintaining complete information to support these global layout 
policies is costly, allocation is decomposed into global and local steps. 
Global policy routines maintain only parital information, and make requests 
for specific blocks to local allocation routines. If the requested block is 
available, it is allocated by the local routine. Otherwise, the local
allocator tries the following four steps: (1) use the next available block
rotationally closest on the same cylinder, (2) if no blocks on the same
cylinder are available, use a block in the same cylinder group, (3) if the
cylinder group is entirely full, hash the group number to choose another group
to search for a free block, and (4) if the hash fails, use exhaustive search. 

* Other FS Enhancements

- Long file names
- File locking using lock operations instead of separate lock files
- Symbolic links
- Atomic renaming of files
- Disk quotas