File System Design
By: Rong Fan, Xinya Guo, Shwetha Kotekar
There are three topics we want to cover in File Systems:
Performance - we want IO to be fast
Robustness – we want it to work; don’t want to lose data when disk drive fails
The two constraints are performance and robustness.
BUT the faster you make your file system, the less robust it gets. But before we get into that...
WHAT IS A FILE SYSTEM?
A file system is the data structure designed to support the abstraction of the data blocks as an archive and collection of files. In other words, a file system organizes the data blocks into files, directories, and file information. This data structure is unique because it is stored on secondary storage (usually the disk), which is a very slow device.
An Embarrassingly Simple File System:
RT-11 File System
The following simple file system is very similar to the RT-11 files system (Real Time) (early 1970). In this file system, files are contiguous chunks of data. New files are allocated in any free space that will hold it. The deletion of a file frees up that disk space to be used later.
sequence of sectors: 0 → n
The directory is a fixed size of 10 sectors.
The directory entries are at the beginning of the file. They contain information about the files in the directory. These entries have three fields:
a null terminated string for the file name
the starting block number
number of blocks allocated.
File name \0
Start of file
(starting block number)
Length in bytes
(number of blocks allocated)
Advantages with RT-11:
It is very simple
There is no indirection, which means we do not need to store the file pointers
Contiguous access is fast
Allocation and freeing files is fast
Disadvantages with RT-11::
External fragmentation can occur; there could be a lot of free space, but it is scattered throughout the disk in smaller chunks. A file allocation may fail because we cannot find a single block of free space large enough to fit it, even though there is enough free net space on disk.
A fixed size directory may lead to unused space if there are few directory entries or not enough space if there are too many directory entries.
The size of the file must be known in advance
There can be no nested directories
If it is a big directory, where is the free space? How do we access it?
And I/O failure = mean very bad news.
FAT (File Allocation Table) File System
FAT (File Allocation TAble)
(Each sector is 512 Bytes)
The boot sector contains the bootstrapping programs to start the system upon a boot, as we have discussed in prior lectures. In a system with multiple disks, each disk has the boot sector.
The superblock contains all the metadata about the file system, such as the version number, the size of the entire system, the root directory, the pointer to the first data block, and more.
The file allocation table (FAT) contains the FAT structure, which is a map of the data region. It is described in more detail below.
The rest of the disk are the data blocks to store files.
SO: 232 x 212 = 244
FAT vs. the Simple File structure
Directories are Files. Unlike the simple file structure from before, FAT has no directory block. Instead, directories are stored like files as an array of directory entries.
= 16miB/file limit
FAT16: % disk in FAT = 2/4096 = 0.5%
For example, we want to find “FOO.pdf”. For this, we need to know where the first block. The FAT directory entry will give you the first block. The directory entry is found using the root in the superblock.
The FAT table is an array of entries where each entry represents the corresponding data block. Each entry either contains:
the number of the next block that is part of the file
0 which means the current block is the end of the file, or
-1, which means the block is free.
For example, suppose a file starts at data block 3. The FAT table entry 3 corresponds to data block 3. In this entry is the number 10, which means if we wanted to continue reading the file, we must go to data block 10. If the FAT table, entry 10 has a 0, data block 10 is the last data block in the file.
Issues with FAT:
If data block 3 pointed to data block 10, but the FAT entry for 10 was -1, this means the file points to a free block, which is an error. The file system is inconsistent.
Two directory entries cannot point to the same block as the first block or the file system is inconsistent. The method does now allow for links.
Originally the array was 16 bits. Now dues to increased memory demands, it uses 32 bits.
Advantages with FAT:
No more external fragmentation
File size is no longer fixed. We do not need to know the size of the file at the beginning
Disadvantages with FAT:
With external fragmentation: free space you know about but cant use it
Slower because files are not continuous
Cannot put a database on top of FAT because lseek is very slow. lseek should be as fast as a real hardware seek. This property is true for RT11. To seek, add address of the beginning to the start of file and go to that location. But it is NOT true in FAT: we need to go through a linked list on disk. How to fix this?
FIX: cache the FAT into RAM.
BSD: A UNIX FILE SYSTEM
The BSD (Berkeley Software Distribution) is a UNIX operating system. The UNIX file system is similar to the FAT file system but replaces the FAT with two of its own unique elements. The disk is portioned into the following components:
Boot Sector: like in FAT, contains information for booting and loading the OS.
Super Block: like in FAT, holds metadata about the file system. This includes data like: version number, size, amount of free space, and location of rootdir.
Bitmap Block: Used to locate free and used blocks. Free blocks = 0 and used blocks = 1. This method handles blocks more efficiently because only 1 bit is needed to indicate available blocks. FAT, on the other hand, allocates data corresponding to an array and fragments over time
Inode Table: table to store all the inodes
Data blocks: Contains the actual data
DATA (8kiB blocks)
Inode, or "Index node," is a block of fixed size that holds metadata about directory files or regular files. Each inode has the following information:
Type of the file (regular file or directory)
Dates/timestamp of last read, write, or change
Number of hard links to file
Array of pointers to blocks to store information about where the blocks are. Each pointer points to a block
Advantages with UNIX file system:
lseek is no longer ridiculous
Easy to grow a file - Change a value in the block bitmap and add a pointer to the inode
Safe, cheap file renaming and directory copying (still requires more seeks than RT-11)
No external fragmentation
files can have holes!
Api: open a file, create it
lseek ( ..., 10,000,0000,000)
Disadvantages with UNIX file system:
internal fragmentation still possible
FAT fragmentation also still possible