File System Design

Updated

What exactly is a file system? The general concept is that the file system provides naming organization. It manages the physical disk layout such as picking a block constituting a file, balancing locality with expandability, and managing free space. It can translate from file name and offset to the actual data block. In a nutshell, it is a servant that manages all the dirty details of communicating the data between system and the hardware in an optimal way which you aren’t required to understand so you can go on and do other things with your life. So what are the functionalities of file systems? In general, it provides file name organizations such as directories. It can manage disk layout by picking blocks that constitute a file, balancing locality with expandability, and manage free space. It can translate from file name and offset to the actual data block.

File

Let’s start from and bottom-to-top pattern to describe file system by first introducing the most fundamental unit: the file itself. So a file is composed of two parts: the metadata and the actual data. The metadata is a file header that holds information about where the data is stored and attributes of the file such as a permission, access time, owner id, size, and so on. One thing to note is that meta data blocks are stored on a location that is known by the OS and thus it can be accessed without having to check another data structure. Then the actual data is the part users actually care about. There are two kinds of blocks (there can be more than these two data blocks but we will only discuss two here), The directory data block which maps file names to file headers, and file data block that contains information we care about.

Design File Layout

There are several factors we need to take into consideration when designing file layout:

Block VS Sector

Before we dig deeper into file system design, it’s important to note the the block size of file system is different from disk blocks size. According to Practical File System Design, block is the smallest unit writable by a disk or file system. Everything a file system does is composed of operations done on blocks. A file system block is always the same size as or larger (in integer multiples) than the disk block size. Also each blocks consists of consecutive sectors so that sequential access becomes possible. A larger block size increases transfer efficiency also because of sequential access since you don’t have to move the head too many times, it may be convenient if the block size matches the machine’s page size, this is because we don’t have to switch pages assuming the block is bigger than the page size. Many systems allows transfer of many sectors between interrupts.

Allocation methods

Contiguous Allocation

Linked Allocation

FAT File System (File Allocation Table)

FAT32 file system is very important file system created by Microsoft. It was introduced the solve the volume problem posed by FAT16. Although named FAT32, only 28 of the 32 bits are actually used and the remaining 4 bits are “reserved for future use”. As a result, a FAT32 partition has a maximum cluster count of (268,435,455)2^28-1. I found this description about FAT32 on StackExchange that is useful:

Although VFAT was a clever system, it did not address the limitations of With the appearance of the FAT32 file system, the maximum number of clusters per partition went increased from 65535 to 268,435,455 (228-1). FAT32 thus allows much bigger partitions (up to 8 terabytes). Although the maximum theoretical size of a FAT32 partition is 8 TB, Microsoft has voluntarily limited it to 32 GB on Windows 9x systems to promote NTFS

FAT32 is implemented in a completely different way . Unlike FFS in UNIX, each entry in in the MTF merely represents a block of data. Each block is able to point to another block, with multiple entries in the table to represent a file represented multiple blocks. Each file’s file number is indicated using the index of the first entry in the MTF. Thus, in order to locate a specific block of a file, we need to search the MTF sequentially.