A Fast File System for UNIX MARSHALL K. MCKUSICK, WILLIAM N. JOY, SAMUEL J. LEFFLER, and ROBERT S. FABRY Computer Systems Research Group A reimplementation of the UNIX TM file system is described. The reimplementation provides sub- stantially higher throughput rates by using more flexible allocation policies that allow better locality of reference and can be adapted to a wide range of peripheral and processor characteristics. The new file system clusters data that is sequentially accessed and provides two block sizes to allow fast access to large files while not wasting large amounts of space for small files. File access rates of up to ten times faster than the traditional UNIX file system are experienced. Long-needed enhancements to the programmers' interface are discussed. These include a mechanism to place advisory locks on files, extensions of the name space across file systems, the ability to use long file names, and provisions for administrative control of resource usage. Categories and Subject Descriptors: D.4.3 [Operating Systems]: File Systems Management--fi/e organization; directory structures; access methods; D.4.2 [Operating Systems]: Storage Manage- ment--allocation/deaUocation strategies; secondary storage devices; D.4.8 [Operating Systems]: Performance--measurements; operational analysis; H.3.2 [Information Systems]: Information Storage--fi/e organization General Terms: Measurement, Performance Additional Keywords and Phrases: UNIX, file system organization, file system performance, file system design, application program interface 1. INTRODUCTION This paper describes the changes from the original 512-byte UNIX 1 file system to file the new system released with the 4.2 Berkeley Software Distribution. It presents the motivations for the changes, the methods used to effect these changes, the rationale behind the design decisions, and a description of the new implementation. This discussion is followed by a summary of the results that have been obtained, directions for future work, and the additions and changes that have been made to the facilities that are available to programmers. 1 UNIX is a trademark of AT&T Bell Laboratories. This work was done under grants from the National Science Foundation under grant MCS80-05144, and the Defense Advance Research Projects Agency (DoD) under ARPA Order No. 4031 monitored by Naval Electronic System Command under contract N00039-82-C-0235. Authors' present addresses: M. K. McKusick and R. S. Fabry, Computer Science Division, Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA 94720; W. N. Joy, Sun Microsystems, Inc., 2550 Garcia Ave., Mountain View, CA 94043; S. J. Leffler, Lucasfilm Ltd., P.O. Box 2009, San Rafael, CA 94912. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1984 ACM 0734-2071/84/0181-0197 $00.75 ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, Pages 181-197.182 • M.K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry The original UNIX system that runs on the PDP-112 has simple and elegant file system facilities. File system I/0 is buffered by the kernel; there are no alignment constraints on data transfers and all operations are made to appear synchronous. All transfers to the disk are in 512-byte blocks, which can be placed arbitrarily within the data area of the file system. Virtually no constraints other than available disk space are placed on file growth [14, 18]. 3 When used on the VAX-11 together with other UNIX enhancements, the original 512-byte UNIX file system is incapable of providing the data throughput rates that many applications require. For example, applications such as very- large-scale integration (VLSI) design and image processing involve a small amount of processing on large quantities of data and need to have a high throughput from the file system. High throughput rates are also needed by programs that map files from the file system into large virtual address spaces. Paging data in and out of the file system is likely to occur frequently [5]. This requires a file system providing higher bandwidth than the original 512-byte UNIX one that provides only about two percent of the maximum disk bandwidth or about 20 kilobytes per second per arm [21, 16]. Modifications have been made to the original UNIX file system to improve its performance. Since the UNIX file system interface is well understood and not inherently slow, this development retained the abstraction and simply changed the underlying implementation to increase its throughput. Consequently, users of the system have not been faced with massive software conversion. Problems with file system performance have been dealt with extensively in the literature; see [15] for a survey. Previous work to improve the UNIX file system performance has been done by Ferrin [4]. The UNIX operating system drew many of its ideas from Multics, a large, high performance operating system [3]. Other work includes Hydra [1], Spice [19], and a file system for a LISP environment [17]. A good introduction to the physical latencies of disks is described in [11]. 2. OLD FILE SYSTEM In the file system developed at Bell Laboratories (the "traditional" file system), each disk drive is divided into one or more partitions. Each of these disk partitions may contain one file system. A file system never spans multiple partitions. 4 A file system is described by its superblock, which contains the basic parameters of the file system. These include the number of data blocks in the file system, a count of the maximum number of files, and a pointer to the free list, a linked list of all the free blocks in the file system. Within the file system are fries. Certain files are distinguished as directories and contain pointers to files that may themselves be