File System Structures | Storage Networking Fundamentals: An Introduction to Storage Devices, Subsystems, Applications, Management, and File Systems (Vol 1)

There are two fundamental structural elements to understand in most file systems:

The logical directory structure
The layout of data within a storage address space

Logical Directory Structures

The most obvious and intuitive structure in a file system is the logical structure of directories, also referred to as folders. This structure is usually represented as a tree hierarchy that starts with a single root directory. Each directory in the hierarchy can contain a number of files and subdirectories, which in turn can have additional files and directories. It's assumed that readers of this book are familiar with file system directory structures as users of computer systems. A hierarchical directory tree is shown in Figure 14-2.

Figure 14-2. The Structure of a Directory Hierarchy

Directory hierarchies allow users as well as system and application developers to organize their stored data. Without this hierarchical structure, finding data would be difficult, at best, and naming would become much more difficult to manage than it is.

Access to files in directories can be made through the graphical user interface of some operating systems as well as through a command-line interface (CLI). Most file system interfaces have a concept for a "current" directory that is being viewed by the user. Clicking the file or entering its name and pressing the Enter key normally results in the file system opening the file.

Files

Files are granular containers of data, created by the system or an application. Applications and system processes often include formatting and interpretation data along with raw application data composed of such things as numerical values and text strings. For instance, a word processing document may have information about the margins, fonts, and styles used in addition to the alphanumeric text that communicates the message of the document.

Files can be unstructured, meaning the data does not have an externally understood, regular logical structure. They also can be structured, which means the file has prescribed, regular boundaries for placing data values that are associated with each other. In general, file systems store unstructured data, and databases store structured data.

Directories

Directories are special-purpose container files that list all the files and subdirectories that are in them. In addition to files and subdirectories, directories also contain references to their parent directory as well as a reference to itself.

The listings of files and subdirectories also contain data from the file system's internal reference system that indicates the addresses where the file or directory is stored within the storage address space. For instance, when you click an icon for a directory in the file system's user interface, the file system "jumps" to the referenced storing location, opens that directory file, and creates a view of its contents that is shown in the user interface.

A Detailed Look at Directory Scanning

The process behind viewing the contents of a file system is actually much more fragmented than it appears to a system user. For instance, the file system does not provide a view of its informationthe user interface does. While each file system/operating system combination would do it differently, here is a hypothetical process that approximates how it might be done:

The pointing device click action causes the GUI to determine the object that is being acted on; in this case, it's a subdirectory. Assuming the operating system recognizes the object is a directory file, it creates an internal directory-display process to receive the directory information when it is available from the file system (this process probably runs in user space, not kernel space). Then the OS communicates with the file system to open the (directory) file. Because the storage I/O process is approximately five orders of magnitude slower than the processor cycle speed, the operating system continues managing all other system processes, including the execution of other file system processes.

The file system determines the location of the (directory) file in storage and notifies the operating system when it is ready to open its contents. The file system and the operating system kernel exchange a reference handle to identify the directory scan uniquely amid all the other file I/O processes that are occurring. Optionally, the OS kernel and the directory display process also exchange a separate handle.

The operating system then requests that the contents of the directory be read by the file system. When the data starts arriving from storage, the file system notifies the kernel and transfers data to internal buffer memory. The OS notifies the directory display process and points to the buffer location where the directory information was stored. The directory display process reads this data and formats it for display through the GUI, sending the data to it through the system's display interface. When the subdirectory is displayed, the whole process can begin all over again when the user clicks another file or directory.

The point of this discussion is to show that the file system acts like a logical go-fer on behalf of other processes and applications. It does not have its own user interface that allows it to interact directly with users or applications. Instead, it takes its orders from the operating system kernel. Furthermore, the file system does not interpret the data it is working withthat is the responsibility of the application. It looks like you think you are interacting directly with the file system, but you are actually interacting with the GUI.

Full and Relative Path Names

The sequence of directories, beginning with the root directory and including all the directories used to access a particular file, form the full or absolute path to the file. The full path filename includes this full path and appends the filename at the end. A full path filename must be unique.

In other words, a file system can have files with the same name in different directories (such as setup.exe), but two files are not allowed to have the same name and be located in the same directory.

A relative path is the sequence of directories taken from a given directory to access a file. Usually, this refers to a directory that is currently being viewed through a user interface. For instance, if a user is viewing the C:\black directory and wants to access a file named beige.txt in the C:\black\brown directory, the relative path would be \brown.

Layout of Data Within a Storage Address Space

The logical directory structure of a file system is completely independent of the way data is located in a storage address space.

Storage address spaces are flat, which means they are a sequence of contiguous addresses stretched between a beginning and an ending address. File systems provide the method that determines where files are placed within a storage address space and how they are accessed later. The complete collection of file placements on block addresses can be thought of as the layout of data in the block address space. Figure 14-3 shows a storage address space and the location of three different files within that block address space.

Figure 14-3. The Layout of Three Files Within a Storage Address Space

Sometimes the layout of data in a storage address space is referred to as the "physical layout" or the "on-disk" layout of data. Unfortunately, those intuitive terms are not necessarily very accurate when virtualization and volume management are involved. More often than not, the file system is presented with a virtual storage address space rather than an actual physical storage address space.

Several different file system technologies have been developed over the decades that lay out files in a number of different ways. The discussions that follow are intended to describe generalized layout processes and are not intended to reflect any particular file system.

NOTE

File system design discussions tend to use specific terminology from specific file systems. This makes it difficult to analyze in general, abstract terms. These terms work if you are trying to develop a file system, but they don't necessarily help communicate concepts. So, the discussions here depart from some of the language that may be more familiar but obscures the bigger picture.

Block Size Definition

File systems store files in block address locations, which are defined by the file system as the granular capacity of storage used by the system. The file system's block size definition determines how large or small most storage I/O operations are. File systems used in open-systems computers typically have fixed block sizes that are consistent across the entire storage address space. These block sizes can be set to many different values by most file systems, and multiples of 4 KB are common.

As discussed in previous chapters, storage address spaces are made from one or more discrete block storage locations and formed into a logical sequence of incremental addresses. Downstream storing-level processes such as volume management software, RAID, and virtualization processes are responsible for creating the collection of block address locations. All contributing storage resources that are managed by the same file system have the same block size. The file system is responsible for figuring out how those block addresses are used.

Allocating Storage from File System Free Space

The process of determining where data should be placed is called allocation. The file system allocates storage addresses for a file when it is created or updated, requiring a change in the number of blocks. Usually file updates mean more blocks are needed, but it is also possible for file updates to decrease the size of a file.

Allocation depends on the file system's method for determining which addresses are available for storing data. This is often done through a bitmap table that the file system maintains. The free block map has a single bit for each block that indicates which blocks are not storing data.

When a file system is first installed, most of the storage address space is available as free blocks. When files are written to an empty file system, a relatively high percentage of data can be stored in contiguous blocks to provide excellent performance.

File system designers take into account the mechanical limitations of disk drive performance. As a result, one of the design goals of most file systems is to provide fair (as in equal) performance to all files, regardless of when they are written. Allocating storage by scattering data throughout the complete address range ensures that I/O performance levels will degrade slowly as the storage address space is filled.

In general, I/O performance is best if file blocks are contiguous. For this reason the allocation method employed by most file systems typically attempts to place file data in "clumps" of contiguous blocks in the various block ranges where the file is stored.

NOTE

Although it could be an advantage, file systems typically do not differentiate between different classes of files, such as system files, application files, or data files. Therefore, there is no QoS element in file systems today. That could certainly change in the future.

Fragmentation

Fragmentation is a natural process that occurs in file systems. It refers to the gradual reduction in the number of contiguous address spaces that can be allocated to a file. As a file system ages, its free space is consumed, and data is stored in fewer contiguous blocks that are scattered over more locations that are farther apart. This results in more actuator movements to read files and a corresponding decrease in I/O performance.

Administrative actions and file system utilities that "clean up" disk space return blocks to the free block map so they can be re-allocated. However, to improve performance, a defragmentation tool is needed to restructure the disk layout and place fragmented data back together in longer contiguous block sections.

The Layout Reference System

One of the most important parts of any file system is the reference system it uses to record where files are written. In UNIX file systems this is commonly referred to as the inodes.

The layout reference system is used to locate all file data created in the system and stored by the file system. Each file in the system is stored in one or more blocks. The reference system provides the method that identifies all the blocks used to store a file. The layout reference system must correctly identify all blocks as well as their relative order within the file. Figure 14-4 shows the layout reference system data that exists for files and subdirectories located in a directory called Forrest.

Figure 14-4. Layout Reference Data for Files and Directories in a Directory Named Forrest

NOTE

The term layout reference system may strike some readers as odd or unnecessary, considering that there is already a reasonable term, inode, from UNIX systems that can be used. The problem with using terms like inode is that it specifically reflects UNIX system implementations. There is no reason to believe that a layout reference system for a non-UNIX file system would resemble inodes or be called inodes.

When a user or an application makes a request for a file, the request is converted to a full path name by the operating system and passed to the file system. The file system finds the filename in the appropriate directory and then looks up the requested block location(s) using the file system's reference data.

Byte-range file I/O requests are accommodated by locating data at byte offsets from block locations that correspond to the file system's block size. For instance, if an application is seeking data beginning at the tenth KB of a file in a file system with 4-KB blocks, the file system can locate the data requested by moving to the file's third block, starting at 8 KB and reading ahead an additional 2 KB within that block.

It is obviously essential that all files written by the file system have data and layout reference data that match each other. This is referred to as file system consistency. A loss of file system consistency is equivalent to losing data.

The layout reference system used by a file system can have a profound effect on the scalability of the system and its performance. Historically, these reference systems were structured as indexes, and the file system had a limited number of them, limiting its size. Over time, these evolved to include multiple levels of indexes to increase the scalability of the file system.

However, the more indexes there are, the slower the file system performance. Not only that, but recovering from errors and unexpected system shutdowns becomes a much bigger problem.

Most newer file systems use a reference system based on B-tree algorithms. B-trees have the advantage of being relatively compact and fast and are generally viewed as superior technology for creating scalable storage.

Traversing the File System

User searches for files and system management utilities such as backup and virus scanners traverse (scan) the entire reference system and all the files in a file system. Typically this involves moving from directory to directory, looking for a particular name, reading attributes, or scanning the data within a file. Backup and virus scanning create an enormous amount of work for a file system.

The efficiency of the file system's reference system is paramount to the performance of these utilities and applications. As file systems increase in size, automated utilities that traverse the file system will become needed to help administrators handle the workload.