Editing Unix File System (section)

== History and evolution ==

Early Unix filesystems were referred to simply as ''FS''. FS only included the boot block, superblock, a clump of [[inode]]s, and the data blocks. This worked well for the small disks early Unixes were designed for, but as technology advanced and disks grew larger, moving the head back and forth between the clump of inodes and the data blocks they referred to caused [[Hard disk drive performance characteristics#Seek time|thrashing]]. [[Kirk McKusick|Marshall Kirk McKusick]], then a [[University of California, Berkeley|Berkeley]] graduate student, optimized the V7 FS layout to create [[4.2BSD|BSD 4.2]]'s FFS (Fast File System) by inventing cylinder groups, which break the disk up into smaller chunks, with each group having its own inodes and data blocks.<ref>{{cite web |title=Open Sources: Voices from the Open Source Revolution |date=29 March 1999 |url=https://www.oreilly.com/openbook/opensources/book/kirkmck.html}}</ref><ref>{{cite journal |last1=McKusick |first1=K M |last2=Joy |first2=W |last3=Leffler |first3=S |last4=Fabry |first4=R |title=A Fast File System for UNIX |journal=ACM Transactions on Computer Systems |date=August 1984 |volume=2 |issue=3 |pages=181–197 | url = https://www.cs.cornell.edu/Courses/cs614/2003SP/papers/KJL84.pdf | doi = 10.1145/989.990 | s2cid = 222285164 | access-date = 2013-04-08}}</ref>

The intent of BSD FFS is to try to localize associated data blocks and metadata in the same cylinder group and, ideally, all of the contents of a directory (both data and metadata for all the files) in the same or nearby cylinder group, thus reducing [[file system fragmentation|fragmentation]] caused by scattering a directory's contents over a whole disk.

Some of the performance parameters in the superblock included number of tracks and sectors, disk rotation speed, head speed, and alignment of the sectors between tracks. In a fully optimized system, the head could be moved between close tracks to read scattered sectors from alternating tracks while waiting for the platter to spin around.

As disks grew larger and larger, sector-level optimization became obsolete (especially with disks that used linear sector numbering and variable sectors per track). With larger disks and larger files, fragmented reads became more of a problem. To combat this, BSD originally increased the filesystem block size from one sector to 1&nbsp;K in 4.0 BSD; and, in FFS, increased the filesystem block size from 1&nbsp;K to 8&nbsp;K. This has several effects. The chance of a file's sectors being contiguous is much greater. The amount of overhead to list the file's blocks is reduced, while the number of bytes representable by any given number of blocks is increased.

Larger disk sizes are also possible, since the maximum number of blocks is limited by a fixed bit-width block number. However, with larger block sizes, disks with many small files will waste space, since each file must occupy at least one block. Because of this, BSD added ''block-level fragmentation'', also called [[block suballocation|block suballocation, tail merging, or tail packing]], where the last partial block of data from several files may be stored in a single "fragment" block instead of multiple mostly empty blocks.<ref>{{cite web | url = http://ws.edu.isoc.org/workshops/2005/ccTLD-Nairobi/day1/freebsd/intro-freebsd-additional-topics-1up.pdf | title = UFS2 and Soft Updates make for a powerful combination | last = Allen | first = Hervey | work = Introduction to FreeBSD, PacNOG I Workshop, Additional Topics | publisher = Network Startup Resource Center | date = 2005-06-20 | page = 23 | access-date = 2013-04-08 }}</ref>

The work on Berkeley FFS was widely adopted by other Unix vendors, and the family of filesystems derived from it are collectively known as UFS.