Locality and The Fast File System

1 41 Locality and The fast File SystemWhen the UNIX operating System was first introduced, the UNIX wizardhimself Ken Thompson wrote the first file System . Let s call that the oldUNIX file System , and it was really simple. Basically, its data structureslooked like this on the disk:SInodesDataThe super block (S) contained information about the entire file System :how big the volume is, how many inodes there are, a pointer to the headof a free list of blocks, and so forth. The inode region of the disk containedall the inodes for the file System . Finally, most of the disk was taken upby data good thing about the old file System was that it was simple, andsupported the basic abstractions the file System was trying to deliver: filesand the directory hierarchy. This easy-to-use System was a real step for-ward from the clumsy, record-based storage systems of the past, and thedirectory hierarchy was a true advance over simpler, one-levelhierarchiesprovided by earlier The Problem: Poor PerformanceThe problem: performance was terrible.

2 As measured by Kirk McKu-sick and his colleagues at Berkeley [MJLF84], performance started off badand got worse over time, to the point where the file System was deliveringonly 2% of overall disk bandwidth!The main issue was that the old UNIX file System treated the disk like itwas a random-access memory; data was spread all over the place withoutregard to the fact that the medium holding the data was a disk, and thushad real and expensive positioning costs. For example, the data blocks ofa file were often very far away from its inode, thus inducing an expensiveseek whenever one first read the inode and then the data blocks of a file(a pretty common operation).12 Locality ANDTHEFASTFILESYSTEMW orse, the file System would end up getting quitefragmented, as thefree space was not carefully managed. The free list would end uppoint-ing to a bunch of blocks spread across the disk, and as files got allocated,they would simply take the next free block.

3 The result was that alogi-cally contiguous file would be accessed by going back and forth acrossthe disk, thus reducing performance example, imagine the following data block region, which containsfour files (A, B, C, and D), each of size 2 blocks:A1A2B1B2C1C2D1D2If B and D are deleted, the resulting layout is:A1A2C1C2As you can see, the free space is fragmented into two chunks of twoblocks, instead of one nice contiguous chunk of four. Let s say you nowwish to allocate a file E, of size four blocks:A1A2E1E2C1C2E3E4 You can see what happens: E gets spread across the disk, and as aresult, when accessing E, you don t get peak (sequential) performancefrom the disk. Rather, you first read E1 and E2, then seek, then read E3and E4. This fragmentation problem happened all the time in theoldUNIX file System , and it hurt performance. A side note: this problem isexactly what diskdefragmentationtools help with; they reorganize on-disk data to place files contiguously and make free space for one or afewcontiguous regions, moving data around and then rewriting inodes andsuch to reflect the other problem: the original block size was too small (512 bytes).

4 Thus, transferring data from the disk was inherently inefficient. Smallerblocks were good because they minimizedinternal fragmentation(wastewithin the block), but bad for transfer as each block might require a posi-tioning overhead to reach it. Thus, the problem:THECRUX:HOWTOORGANIZEON-DISKDATA TOIMPROVEPERFORMANCEHow can we organize file System data structures so as to improve per-formance? What types of allocation policies do we need on top of thosedata structures? How do we make the file System disk aware ?OPERATINGSYSTEMS[ ] FFS: Disk Awareness Is The SolutionA group at Berkeley decided to build a better, faster file System , whichthey cleverly called theFast File System (FFS). The idea was to designthe file System structures and allocation policies to be disk aware andthus improve performance, which is exactly what they did. FFS thus ush-ered in a new era of file System research; by keeping the sameinterfaceto the file System (the same APIs, includingopen(),read(),write(),close(), and other file System calls) but changing the internalimplemen-tation, the authors paved the path for new file System construction, workthat continues today.

5 Virtually all modern file systems adhere to the ex-isting interface (and thus preserve compatibility with applications) whilechanging their internals for performance, reliability, or other Organizing Structure: The Cylinder GroupThe first step was to change the on-disk structures. FFS divides thedisk into a number ofcylinder groups. A singlecylinderis a set of trackson different surfaces of a hard drive that are the same distancefrom thecenter of the drive; it is called a cylinder because of its clearresemblanceto the so-called geometrical shape. FFS aggregatesNconsecutive cylin-ders into a group, and thus the entire disk can thus be viewed asa collec-tion of cylinder groups. Here is a simple example, showing the fouroutermost tracks of a drive with six platters, and a cylinder group that consistsof three cylinders:Single track ( , dark gray)Cylinder:Tracks at same distance from centerof drive across different surfaces[all tracks with same color]Cylinder Group:Set of N consecutive cylinders[if N=3, first group doesnot include black track]Note that modern drives do not export enough information for thefile System to truly understand whether a particular cylinder is in use;as discussed previously [AD14a], disks export a logical address space ofblocks and hide details of their geometry from clients.

6 Thus, modern file 2008 21, ARPACI-DUSSEAUTHREEEASYPIECES4 Locality ANDTHEFASTFILESYSTEM systems (such as Linux ext2, ext3, and ext4) instead organizethe driveintoblock groups, each of which is just a consecutive portion of the disk saddress space. The picture below illustrates an example where every 8blocks are organized into a different block group (note that real groupswould consist of many more blocks):Group 0 Group 1 Group 2 Whether you call them cylinder groups or block groups, these groupsare the central mechanism that FFS uses to improve performance. Crit-ically, by placing two files within the same group, FFS can ensure thataccessing one after the other will not result in long seeks across the use these groups to store files and directories, FFS needs to have theability to place files and directories into a group, and track all necessaryinformation about them therein. To do so, FFS includes all the structuresyou might expect a file System to have within each group, , space forinodes, data blocks, and some structures to track whether each ofthoseare allocated or free.

7 Here is a depiction of what FFS keeps withina singlecylinder group:Sib dbInodesDataLet s now examine the components of this single cylinder group inmore detail. FFS keeps a copy of thesuper block(S) in each group forreliability reasons. The super block is needed to mount the file System ;by keeping multiple copies, if one copy becomes corrupt, you can stillmount and access the file System by using a working each group, FFS needs to track whether the inodes and datablocks of the group are allocated. A per-groupinode bitmap(ib) anddata bitmap(db) serve this role for inodes and data blocks in each are an excellent way to manage free space in a file System be-cause it is easy to find a large chunk of free space and allocate itto a file,perhaps avoiding some of the fragmentation problems of the free list inthe old file , theinodeanddata blockregions are just like those in the pre-vious very-simple file System (VSFS). Most of each cylinder group, asusual, is comprised of data [ ] ANDTHEFASTFILESYSTEM5 ASIDE: FFS FILECREATIONAs an example, think about what data structures must be updated whena file is created; assume, for this example, that the user creates a new file/ that the file is one block long (4KB).

8 The file is new,and thus needs a new inode; thus, both the inode bitmap and the newly-allocated inode will be written to disk. The file also has data init andthus it too must be allocated; the data bitmap and a data block will thus(eventually) be written to disk. Hence, at least four writes to the currentcylinder group will take place (recall that these writes may be bufferedin memory for a while before they take place). But this is not all! Inparticular, when creating a new file, you must also place the file in thefile- System hierarchy, , the directory must be updated. Specifically, theparent directoryfoomust be updated to add the entry ; thisupdate may fit in an existing data block offooor require a new block tobe allocated (with associated data bitmap). The inode offoomust alsobe updated, both to reflect the new length of the directory as wellas toupdate time fields (such as last-modified-time). Overall, it is a lot of workjust to create a new file!

9 Perhaps next time you do so, you should be morethankful, or at least surprised that it all works so Policies: How To Allocate Files and DirectoriesWith this group structure in place, FFS now has to decide how to placefiles and directories and associated metadata on disk to improve perfor-mance. The basic mantra is simple:keep related stuff together(and its corol-lary,keep unrelated stuff far apart).Thus, to obey the mantra, FFS has to decide what is related andplace it within the same block group; conversely, unrelated items shouldbe placed into different block groups. To achieve this end, FFSmakes useof a few simple placement first is the placement of directories. FFS employs a simple ap-proach: find the cylinder group with a low number of allocated direc-tories (to balance directories across groups) and a high number offreeinodes (to subsequently be able to allocate a bunch of files), andput thedirectory data and inode in that group.

10 Of course, other heuristics couldbe used here ( , taking into account the number of free data blocks).For files, FFS does two things. First, it makes sure (in the general case)to allocate the data blocks of a file in the same group as its inode, thuspreventing long seeks between inode and data (as in the old file System ).Second, it places all files that are in the same directory in the cylindergroup of the directory they are in. Thus, if a user creates four files,/a/b,/a/c,/a/d, andb/f, FFS would try to place the first three near oneanother (same group) and the fourth far away (in some other group).Let s look at an example of such an allocation. In the example, as-sume that there are only 10 inodes and 10 data blocks in each group (both 2008 21, ARPACI-DUSSEAUTHREEEASYPIECES6 Locality ANDTHEFASTFILESYSTEM unrealistically small numbers), and that the three directories (the root di-rectory/,/a, and/b) and four files (/a/c, /a/d, /a/e, /b/f) areplaced within them per the FFS policies.