File system fragmentation: Difference between revisions

Revision as of 09:21, 14 December 2006

Revision as of 09:38, 14 December 2006

Line 1:

In computing, '''[[file system]] [[fragmentation (computer)|fragmentation]]''', sometimes called '''file system aging''', is the inability of a file system to lay out related data sequentially (contiguously), an inherent phenomenaphenomenon in [[computer storage|storage]]-backed file systems that allow in-place modification of their contents. It is a special case of [[fragmentation (computer)#Data fragmentation|data fragmentation]]. File system fragmentation introduces disk head seeks which are known to hinder [[throughput]].

==Why fragmentation matters==

File system fragmentation is projected to become more problematic with newer hardware due to the increasing disparity between sequential access speed and [[rotational delay]] (and to a lesser extent [[seek time]]), of consumer-grade [[hard disk]]s,<ref name=seagate-future>{{cite conference |author=Dr. Mark H. Kryder |publisher=[[Seagate Technology]] |date=2006-04-03 |title=Future Storage Technologies: A Look Beyond the Horizon |booktitle=Storage Networking World conference |url=http://www.snwusa.com/documents/presentations-s06/MarkKryder.pdf |format=[[PDF]] |accessdate=2006-12-14 }}</ref> which file systems are usually placed on. Thus, fragmentation is a important problem in recent file system research and design. The containment of fragmentation not only depends on the on-disk format of the file system, but also heavily on its implementation.<ref name=mcvoy-extent>{{cite conference |author=L. W. McVoy, S. R. Kleiman |date=1991 winter |title=Extent-like Performance from a UNIX File System |booktitle=Proceedings of [[USENIX]] winter '91 |pages=pages&nbsp;33&ndash;43 |___location=Dallas, Texas |publisher=[[Sun Microsystems, Inc.]] |url=http://www.cis.upenn.edu/~bcpierce/courses/dd/papers/mcvoy-extent.ps |format=[[PostScript]] |accessdate=2006-12-14 }}</ref>

In simple file system [[benchmark (computing)|benchmark]]s, the fragmentation factor is often omitted, as realistic aging and fragmentation is difficult to model. Rather, for simplicity of comparison, file system benchmarks are often ranrun on empty file systems, and unsuprisinglyunsurprisingly, the results may vary heavily from real -life access patterns.<ref name=workload-benchmarks>{{cite paper |author=Keith Arnold Smith |date=2001-01 |title=Workload-Specific File System Benchmarks |publisher=[[Harvard University]] |url=http://www.eecs.harvard.edu/vino/fs-perf/papers/keith_a_smith_thesis.pdf |format=[[PDF]] |accessdate=2006-12-14 }}</ref>

==Types of fragmentation==

Line 27:

Proactive techniques attempt to keep fragmentation at a minimum at the time data is being written on the disk. The simplest of such is, perhaps, appending data to an existing fragment in place where possible, instead of allocating new blocks to a new fragment.

Most of today's file systems attempt to preallocate longer chunks, or chunks from different free space fragments, to files that are actively appended to. This mainly avoids file fragmentation when several files are concurrently being appended to, thus avoiding them from becoming excessively intertwined.<ref name=mcvoy-extent/>

A relatively recent technique is [[delayed allocation]] in [[XFS]] and [[ZFS]],; the same technique is also called allocate-on-flush in [[reiser4]] and [[ext4]]. This means that when the file system is being written to, file system blocks are reserved, but their locations are not laid down yet. Later, when the file system is forced to flush as a result of memory pressure or a transaction commit, the allocator will have much better knowledge of the files' characteristics. Most file systems with this approach try to flush files in a single directory contiguously. Assuming that multiple reads from a single directory are common, locality of reference is improved.<ref name=xfs-scalability>{{cite conference |author=Adam Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, Geoff Peck |date=1996-01 |title=Scalability in the XFS File System |publisher=[[Silicon Graphics]] |booktitle=Proceedings of the USENIX 1996 Annual Technical Conference |___location=San Diego, California |url=http://www.soe.ucsc.edu/~sbrandt/290S/xfs.pdf |format=[[PDF]] |accessdate=2006-12-14 }}</ref> Reiser4 also orders the layout of files according to the directory [[hash table]], so that when files are being accessed in the natural file system order (as dictated by [[readdir]]), they are always read sequentially.<ref name=reiser4-google>{{cite web |author=Hans Reiser |date=2006-02-06 |title=The Reiser4 Filesystem |work=A lecture given by the author, Hans Reiser |url=http://video.google.com/videoplay?docid=6866770590245111825&q=reiser4 |format=[[Google Video]] |accessdate=2006-12-14 }}</ref>

====Retroactive techniques====