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 .

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

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

4 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).

5 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).

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

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

8 As discussed previously [AD14a], disks export a logical address space ofblocks and hide details of their geometry from clients. 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.

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

10 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).