AN IMPLEMENTATION OF A LOG-STRUCTURED FILE SYSTEM FOR UNIXOverviewHistorical PerspectiveLimitations of FFS (I)Limitations of FFS (II)Log-Structured File SystemsGeneral OrganizationOverviewLFS Data StructuresLimitations of Sprite LFSRecovery (I)Recovery (II)Recovery (III)Memory ConsumptionBlock AccountingSegment Structure (I)Segment Structure (II)File System VerificationThe CleanerImplementation IssuesMore Implementation IssuesThe Buffer Cache (I)The Buffer Cache (II)The IFILEDirectory Operations (I)Directory Operations (II)Directory Operations (III)COMPARISONEFSMulti-user Andrew BenchmarkCONCLUSIONSAN IMPLEMENTATION OF ALOG-STRUCTURED FILE SYSTEM FOR UNIXMargo Seltzer, Harvard U.Keith Bostic, U. C. BerkeleyMarshall Kirk McKusick, U. C. BerkeleyCarl Staelin, HP LabsOverview•Paper presents a redesign and implementation of the Sprite LFS•BSD-LFS is–Faster than conventional UNIX FFS (the “fast” file system of the early 80’s)–Not as fast as an enhanced version of FFS with read and write clusteringHistorical Perspective•Early UNIX FS used small block sizes and did not try to optimize block placement•The UNIX FFS–Increased block sizes–Added cylinder groups–Incorporated rotational disk positioning to reduce delays when accessing sequential blocksLimitations of FFS (I)•Synchronous file deletion and creation–Makes file system recoverable after a crash•Same result can be achieved through NVRAM hardware or logging softwareLimitations of FFS (II)•Seek times between I/O requests for different files–Has most impact on performance whenever vast majority of files are small–FFS does not address the problemLog-Structured File Systems•Attempt to address both limitations of FFS•Store all data in a single, continuous log•Optimized for–All writes–Reading files written in their entirety over a short period of time –Accessing files that were created or modified at the same timeGeneral Organization•Disk is partitioned into segments–Writes are always sequential within a segment•Segment cleaner maintains a pool of empty (“clean”) segments through disk compaction–“Live” data existing in a a set of segments are regrouped in a smaller subset of segmentsOverviewTask FFS LFSAllocate disk addressBlock creation Segment WriteAllocate i-node Fixed location Appended to logMap an i-node number into a disk addressStatic address Lookup ini-node mapMaintain free spaceBitmap CleanerSegment usage tableLFS Data Structures•Superblock:–Same function as one used by FFS•I-node map:–Maps i-node numbers into disk addresses•Segment usage tables:–Show number of live bytes in a segment and last modification time•Checkpoints:–Created every time system does a sync()Limitations of Sprite LFS•Recovery does not verify the consistency of the file system directory structure •LFS consumes “excessive amounts” of main memory [ by 1993 standards]•Write requests are successful even if there is insufficient disk space•Segment validation is hardware dependent•All file systems use a single cleaner and a single cleaning policy•No measure of the cleaner overheadRecovery (I)•Two major aspects–Bringing the file system to a physically consistent state–Verifying the logical structure of the file system•FFS achieves both goals through fsck–Rebuilds the whole file system –Verifies the directory structure and all block pointersRecovery (II)•Sprite LFS uses a two-step recovery process:–Initializes first all the file structures from the most recent checkpoint–“Roll forward” to incorporate all subsequent modifications•Done by reading each segment intime order after the last checkpointRecovery (III)•Standard LFS recovery does not verify the directory structure–Weakness to be addressed in BSD-LFSMemory Consumption•Sprite LFS reserves “large amounts” of main memory including four half-megabyte segments and many buffers•BSD-LFS:–Does not use special staging buffers –Does not reserve two read-only segments that can be reclaimed without any I/O–Implements cleaner as a user-level processBlock Accounting•Sprite LFS maintained a count of disk blocks available for physical writing–Blocks written to the cache but not written to disk do not affect that count•What if a block is “successfully” written to the cache but the disk becomes full before the blocks are actually written?•BSD-LFS keeps a separate count of disk blocks that are not yet committed to any dirty block in the cacheSegment Structure (I)•Sprint LFS places segment summary blocks at the end of the segment–Write containing the segment summary validates the whole segment•Makes two incorrect assumptions1. Controller will not reorder write requests2. Disk will always write the contents of a buffer in the order presentedSegment Structure (II)•BSD-LFS –Does not make these assumptions•Segment blocks can be written in any order–Segment summary is in front of each partial segment and contains a checksum of four bytes of every block in the partial segment•Partial segments constitute the atomic recovery units of BDS-LFSFile System Verification•BSD-LFS offers two recovery strategies–Quick roll forward from last checkpoint–Complete consistency check of the file system•Recovers lost or corrupted data•Same functionality as FFS fsck()•Takes a long time to run•Can be run in the backgroundThe Cleaner•BSD-LFS makes it possible to implement the cleaner as a user process–Allows for multiple cleaning policies–Makes it easier to experiment with new policiesImplementation Issues•BSD-LFS uses on-disk data structures that are nearly identical to those used by FFS–Existing performance tools can continue to function with only minor modification–Makes system easier to implement and maintain•Two type of operations–Vfs operations affect the whole file system–Vnode operations affect individual filesMore Implementation Issues•BSD-LFS does not implement block fragments–Less needed block sizes could be smaller–Still want large blocks to keep metadata to data ratio low–BSD-LFS should (but does not yet) allocate progressively larger blocks.The Buffer Cache (I)•Had to modify the FFS buffer cache–Cannot assume that cache blocks can be flushed one at a time•Would destroy any performance advantage of LFS•LFS may need extra memory to write modified metadata and partial segment summary blocksThe Buffer Cache (II)–Cache blocks do not