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:
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. 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.
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. |