A Fast File System for UNIX

  • Superblock stores the information relevant to the file system as a whole. This includes things like the total size of the file system, the block size (i.e., the granularity of a read and write), and which data blocks and inodes (discussed below) are available for use.
  • Inodes hold the information or data about a file, i.e., the file metadata. This includes things like the file name, size of the file, which blocks hold the file data, and when was it last accessed or modified.
  • Data blocks, as the name suggests, hold the data belonging to the files in the file system. One thing to note is that directories are treated just as files whose data is a list of other files (which could be directories themselves) in the directory.
A common design for storing a file’s data blocks is via direct and indirect pointers. Direct pointers in blue point to data blocks containing the file’s data in pink. Indirect pointers are in green and point to blocks of direct pointers. Double indirect pointers are in orange pointing to blocks of indirect pointers, and triple indirect pointers are in red pointing to blocks of double indirect pointers. Having indirect pointers help scale the file (and its number of data blocks). For example, consider a block that can hold 4 pointers. With all direct pointers, it can point to 4 data blocks, but with 1 direct pointer it can point to 7 data blocks (3 direct, and 4 via the indirect block).
The first image shows the layout of the old file system (OFS) — superblock, inodes, and data blocks laid out sequentially. The second image shows one of the performance problems with OFS’s layout — a file’s inode and data can be far apart on the disk, requiring costly seek operations. The third image shows another problem with OFS’s layout — over time, because of file allocations and deletions, the free blocks can be fragmented across the disk. When a new file is allocated using these fragmented free blocks, its data is spread across the disk and accessing it requires expensive seek operations.
  • A file’s inode and data blocks can be far apart on the disk. This meant that the disk would have to do a costly seek to access the file’s data after accessing the file’s inode (to identify where the file’s data is).
  • There was no attempt to locate the inodes of files belonging to the same directory close-by. This meant that any operation that required accessing all the inodes in a directory (e.g., listing all files in a directory) could also incur seeks.
  • As the old file system was used over time with file allocations and deletions, the list of its free blocks (called the free list) got fragmented, i.e., the free blocks were spread over the disk’s address space into small groups. This meant that a newly allocated file’s blocks were spread all over the disk and accessing the file sequentially would lead to random accesses on the disk, hurting performance.
  • Lastly, the old file system used a block size of 512 bytes, which limited its throughput. Larger block sizes improve throughput because they amortize the cost of the seeking of the disk head to the required track and block.
Cylinder groups, as shown in the OSTEP chapter on fast file system. The diagram shows platter with tracks. The outermost tracks (in dark gray) across all the platters form a cylinder. A group of cylinder (here, 3 outermost ones) form a cylinder group.
An schematic diagram of the fast file system (FFS) layout. It shows 4 cylinder groups. Each cylinder group has a copy of the file system’s super block. Each group has its own set of inodes and data blocks. Essentially, each cylinder group has its own mini-OFS. This addresses the key performance problem of OFS that it required costly seek operations. Each mini-OFS instance is within a cylinder group and seeks within a cylinder group are fast. FFS also tries to allocated related data (e.g., files in the same directory) to the same cylinder group while also trying to load-balance across cylinder groups (e.g., in its allocation of directories to cylinder groups).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store