Difference between revisions of "BSD Fast File System"
m (add ref) |
(Add content about changes for performance) |
||
| Line 3: | Line 3: | ||
==Issues== | ==Issues== | ||
| − | The performance issue were the most critical, but there were lesser functionality and robustness issue as well. The FFS fixed most of these issues (although without duplication of most meta-data, and all data, it was still susceptible to hardware failures such as [[head crash]]es. | + | The performance issue were the most critical, but there were lesser functionality and robustness issue as well. The FFS fixed most of these issues (although without duplication of most meta-data, and all data, it was still susceptible to hardware failures such as [[head crash]]es). |
===Performance=== | ===Performance=== | ||
| Line 17: | Line 17: | ||
Another problematic limitation was the length of file names; although all [[ASCII]] characters could be use, the maximum length of any element (level) of a file name was only 14 characters. | Another problematic limitation was the length of file names; although all [[ASCII]] characters could be use, the maximum length of any element (level) of a file name was only 14 characters. | ||
| − | ==Robustness== | + | ===Robustness=== |
The old file system had only one copy of all the meta-data of a volume, including the [[super block]]. While some of the meta-data (such as the [[free list]] could be re-constructed from other meta-data (by scanning all the [[inode]]s), most could not. | The old file system had only one copy of all the meta-data of a volume, including the [[super block]]. While some of the meta-data (such as the [[free list]] could be re-constructed from other meta-data (by scanning all the [[inode]]s), most could not. | ||
| + | |||
| + | ==Performance changes== | ||
| + | |||
| + | The most fundamental changes to the file system were needed to increase the performance; in particular, to prevent the fragmentation which rendered high performance impossible. | ||
| + | |||
| + | The 'block size' was increased substantially, although to prevent excessive wastage of space when storing small files, all blocks were divisible into ''fragments'' - which are actually the true 'block size' of the new file system; FFS 'blocks' are better thought of as a method to aggregate contiguous groups of fragments into a unit. | ||
| + | |||
| + | Instead of the old layout, with all the inodes at the start of the disk, the disk was divided into ''cylinder groups'', each of which contains a tranche of inodes (along with associated meta-data, such as free inode and fragment bit maps), and a number of cylinders worth of data blocks. | ||
| + | |||
| + | Generally, an attempt is made to allocate all the storage for a file in the same cylinder group as its inode, so that seeks to retrieve the data are minimized. The blocks of a file are also placed on the disk in rotationally-optimized locations. | ||
| + | |||
| + | Inodes contained the block numbers of the first N blocks, so that all the data of files up to a fairly good size could be reached directly; all except the | ||
| + | last one were fully blocks, but the last one might contain only one or more | ||
| + | fragments. For large files, an inode also held the block numbers of a single indirect block, a double-indirect block (i.e. that block contained the block numbers of a set of indirect blocks), and a triple-indirect block. | ||
| + | |||
| + | To allow tuning of the file system to various applications, many of the 'constants' of the file system (such as the number of fragments in a block) were actually configuration parameters which could be set at the time the file-system was created; these values were stored in the 'super block'. Since the file system would be incomprehensible if these values were lost, a copy of the super-block was stored at the start of each cylinder group. | ||
| + | |||
| + | The full scheme is far too complex to be fully explained here; consult the paper on the FFS for the details. | ||
==Further reading== | ==Further reading== | ||
Revision as of 16:23, 5 February 2017
Until the creation of the Berkeley BSD Fast File System for BSD 4.1, all prior Unixes had used basically the file system designed for the early PDP-11 versions of Unix. While very simple (in on-disk structure, and thus implementation), it had some performance, functionality and robustness issues. The FFS fixed these, so successfully that the FFS and its descendants are still the file system of most Unix descendants today.
Contents
Issues
The performance issue were the most critical, but there were lesser functionality and robustness issue as well. The FFS fixed most of these issues (although without duplication of most meta-data, and all data, it was still susceptible to hardware failures such as head crashes).
Performance
The original Unix file system was too simple to be able to get good performance out of the disks of the era. One factor was the small block size (which was to some extent ameliorated in systems prior to the FFS by using larger block sizes); the other was the extreme non-locality of data placement, which was an endemic (albeit un-intended) feature of the earlier system.
Once the system had been running for a while, free blocks were scattered fairly randomly across the disk, and the blocks comprising a new file were thus widely scattered; reading the file resulted in a great deal of head motion (seeks). There was no cure for this state of affairs, other than dumping and re-building the disk.
Functionality
Although the original file system did include so-called hard links, those were non-optimal in a lot of ways; among other issue, they were restricted to a single logical volume.
Another problematic limitation was the length of file names; although all ASCII characters could be use, the maximum length of any element (level) of a file name was only 14 characters.
Robustness
The old file system had only one copy of all the meta-data of a volume, including the super block. While some of the meta-data (such as the free list could be re-constructed from other meta-data (by scanning all the inodes), most could not.
Performance changes
The most fundamental changes to the file system were needed to increase the performance; in particular, to prevent the fragmentation which rendered high performance impossible.
The 'block size' was increased substantially, although to prevent excessive wastage of space when storing small files, all blocks were divisible into fragments - which are actually the true 'block size' of the new file system; FFS 'blocks' are better thought of as a method to aggregate contiguous groups of fragments into a unit.
Instead of the old layout, with all the inodes at the start of the disk, the disk was divided into cylinder groups, each of which contains a tranche of inodes (along with associated meta-data, such as free inode and fragment bit maps), and a number of cylinders worth of data blocks.
Generally, an attempt is made to allocate all the storage for a file in the same cylinder group as its inode, so that seeks to retrieve the data are minimized. The blocks of a file are also placed on the disk in rotationally-optimized locations.
Inodes contained the block numbers of the first N blocks, so that all the data of files up to a fairly good size could be reached directly; all except the last one were fully blocks, but the last one might contain only one or more fragments. For large files, an inode also held the block numbers of a single indirect block, a double-indirect block (i.e. that block contained the block numbers of a set of indirect blocks), and a triple-indirect block.
To allow tuning of the file system to various applications, many of the 'constants' of the file system (such as the number of fragments in a block) were actually configuration parameters which could be set at the time the file-system was created; these values were stored in the 'super block'. Since the file system would be incomprehensible if these values were lost, a copy of the super-block was stored at the start of each cylinder group.
The full scheme is far too complex to be fully explained here; consult the paper on the FFS for the details.
Further reading
Marshall K. McKusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry, A Fast File System for UNIX
