Log-structured File Systems

1 43 Log-structured File SystemsIn the early 90 s, a group at Berkeley led by Professor John Ousterhoutand graduate student Mendel Rosenblum developed a new file systemknown as the Log-structured file system [RO91]. Their motivationto doso was based on the following observations: system memories are growing: As memory gets bigger, more datacan be cached in memory. As more data is cached, disk traffic in-creasingly consists of writes, as reads are serviced by the , file system performance is largely determined by its writeperformance. There is a large gap between random I/O performance and se-quential I/O performance: Hard-drive transfer bandwidth has in-creased a great deal over the years [P98]; as more bits are packedinto the surface of a drive, the bandwidth when accessing saidbitsincreases.

2 Seek and rotational delay costs, however, have decreasedslowly; it is challenging to make cheap and small motors spin theplatters faster or move the disk arm more quickly. Thus, if you areable to use disks in a sequential manner, you gain a sizeable perfor-mance advantage over approaches that cause seeks and rotations. Existing file Systems perform poorly on many common workloads:For example, FFS [MJLF84] would perform a large number of writesto create a new file of size one block: one for a new inode, one toupdate the inode bitmap, one to the directory data block that thefile is in, one to the directory inode to update it, one to the new datablock that is a part of the new file, and one to the data bitmap tomark the data block as allocated.

3 Thus, although FFS places all ofthese blocks within the same block group, FFS incurs many shortseeks and subsequent rotational delays and thus performance fallsfar short of peak sequential bandwidth. File Systems are not RAID-aware: For example, both RAID-4 andRAID-5 have thesmall-write problemwhere a logical write to asingle block causes 4 physical I/Os to take place. Existing file sys-tems do not try to avoid this worst-case RAID writing : DETAILSMATTERAll interesting Systems are comprised of a few general ideas and a num-ber of details. Sometimes, when you are learning about these Systems ,you think to yourself Oh, I get the general idea; the rest is just details, and you use this to only half-learn how things really work.

4 Don t do this!Many times, the details are critical. As we ll see with LFS, thegeneral ideais easy to understand, but to really build a working system , youhave tothink throughallof the tricky ideal file system would thus focus on write performance, and tryto make use of the sequential bandwidth of the disk. Further, itwouldperform well on common workloads that not only write out data but alsoupdate on-disk metadata structures frequently. Finally, itwould workwell on RAIDs as well as single new type of file system Rosenblum and Ousterhout introducedwas calledLFS, short for theLog- structured File system . When writ-ing to disk, LFS first buffers all updates (including metadata!) in an in-memorysegment; when the segment is full, it is written to disk in onelong, sequential transfer to an unused part of the disk.

5 LFS never over-writes existing data, but ratheralwayswrites segments to free segments are large, the disk (or RAID) is used efficiently, andperformance of the file system approaches its :HOWTOMAKEALLWRITESSEQUENTIALWRITES?How can a file system transform all writes into sequential writes? Forreads, this task is impossible, as the desired block to be read may be any-where on disk. For writes, however, the file system always has a choice,and it is exactly this choice we hope to Writing To Disk SequentiallyWe thus have our first challenge: how do we transform all updates tofile- system state into a series of sequential writes to disk? To understandthis better, let s use a simple example. Imagine we are writing a data blockDto a file.

6 Writing the data block to disk might result in the followingon-disk layout, withDwritten at disk addressA0:DA0 OPERATINGSYSTEMS[ ] , when a user writes a data block, it is not only data that getswritten to disk; there is also othermetadatathat needs to be this case, let s also write theinode(I) of the file to disk, and have itpoint to the data blockD. When written to disk, the data block and inodewould look something like this (note that the inode looks as big as thedata block, which generally isn t the case; in most Systems , data blocksare 4 KB in size, whereas an inode is much smaller, around 128 bytes):DA0Ib[0]:A0 This basic idea, of simply writing all updates (such as data blocks,inodes, etc.) to the disk sequentially, sits at the heart of you un-derstand this, you get the basic idea.

7 But as with all complicated Systems ,the devil is in the Writing Sequentially And EffectivelyUnfortunately, writing to disk sequentially is not (alone) enough toguarantee efficient writes. For example, imagine if we wrote a singleblock to addressA, at timeT. We then wait a little while, and write tothe disk at addressA+ 1(the next block address in sequential order),but at timeT+ . In-between the first and second writes, unfortunately,the disk has rotated; when you issue the second write, it will thus waitfor most of a rotation before being committed (specifically, if the rotationtakes timeTrotation, the disk will waitTrotation before it can committhe second write to the disk surface). And thus you can hopefullyseethat simply writing to disk in sequential order is not enough to achievepeak performance; rather, you must issue a large number ofcontiguouswrites (or one large write) to the drive in order to achieve good achieve this end, LFS uses an ancient technique known aswritebuffering1.

8 Before writing to the disk, LFS keeps track of updates inmemory; when it has received a sufficient number of updates, it writesthem to disk all at once, thus ensuring efficient use of the large chunk of updates LFS writes at one time is referred to bythe name of asegment. Although this term is over-used in computersystems, here it just means a large-ish chunk which LFS uses to groupwrites. Thus, when writing to disk, LFS buffers updates in anin-memory1 Indeed, it is hard to find a good citation for this idea, since it was likely invented by manyand very early on in the history of computing. For a study of the benefits of write buffering,see Solworth and Orji [SO90]; to learn about its potential harms, seeMogul [M94].

9 C 2008 19, ARPACI-DUSSEAUTHREEEASYPIECES4 LOG-STRUCTUREDFILESYSTEMS segment, and then writes the segment all at once to the disk. Aslong asthe segment is large enough, these writes will be is an example, in which LFS buffers two sets of updates into asmall segment; actual segments are larger (a few MB). The first update isof four block writes to filej; the second is one block being added to then commits the entire segment of seven blocks to disk at once. Theresulting on-disk layout of these blocks is as follows:Dj,0A0Dj,1A1Dj,2A2Dj,3A3b[0]:A0b [1]:A1b[2]:A2b[3]:A3 Inode jDk,0A5b[0]:A5 Inode How Much To Buffer?This raises the following question: how many updates should LFSbuffer before writing to disk? The answer, of course, depends on the diskitself, specifically how high the positioning overhead is in comparison tothe transfer rate; see the FFS chapter for a similar example, assume that positioning ( , rotation and seek over-heads) before each write takes roughlyTpositionseconds.

10 Assume furtherthat the disk transfer rate isRpeakMB/s. How much should LFS bufferbefore writing when running on such a disk?The way to think about this is that every time you write, you pay afixed overhead of the positioning cost. Thus, how much do you haveto write in order toamortizethat cost? The more you write, the better(obviously), and the closer you get to achieving peak obtain a concrete answer, let s assume we are writing time to write out this chunk of data (Twrite) is the positioning timeTpositionplus the time to transferD(DRpeak), or:Twrite=Tposition+DRpeak( )And thus the effectiverateof writing (Reffective), which is just theamount of data written divided by the total time to write it, is:Reffective=DTwrite=DTposition+DRpeak.