File system fragmentation: Difference between revisions

Revision as of 18:34, 8 January 2021

Revision as of 21:53, 13 January 2021

Line 55:

==Negative consequences==

File system fragmentation is more problematic with consumer-grade [[hard disk drive]]s because of the increasing disparity between [[sequential access]] speed and [[rotational latency]] (and to a lesser extent [[seek time]]) on which file systems are usually placed.<ref name="seagate-future">{{cite conference |first=Mark H. |last=Kryder |publisher=[[Seagate Technology]] |date=2006-04-03 |title=Future Storage Technologies: A Look Beyond the Horizon |conference=Storage Networking World conference |url=http://www.snwusa.com/documents/presentations-s06/MarkKryder.pdf |archiveurlarchive-url=https://web.archive.org/web/20060717001830/http://www.snwusa.com/documents/presentations-s06/MarkKryder.pdf |archivedatearchive-date=17 July 2006}}</ref> Thus, fragmentation is an important problem in 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 |first=L. W. |last=McVoy |first2=S. R. |last2=Kleiman |date=Winter 1991 |title=Extent-like Performance from a UNIX File System |booktitlebook-title=Proceedings of [[USENIX]] winter '91 |pages=33–43 |___location=Dallas, Texas |publisher=[[Sun Microsystems, Inc.]] |url=http://www.cis.upenn.edu/~bcpierce/courses/dd/papers/mcvoy-extent.ps |format=[[PostScript]] |accessdateaccess-date=2006-12-14 }}</ref> File system fragmentation has less performance impact upon [[solid-state drive]]s, as there is no mechanical [[seek time]] involved.<ref name=":0">{{Cite web|url = http://www.hanselman.com/blog/TheRealAndCompleteStoryDoesWindowsDefragmentYourSSD.aspx|title = The real and complete story - Does Windows defragment your SSD?|date = 3 December 2014|accessdate = |website = Scott Hanselman's blog |last = Hanselman|first = Scott}}</ref> However, the file system needs to store additional metadata for each non-contiguous part of the file. Each piece of metadata itself occupies space and requires processing power and processor time. If the maximum fragmentation limit is reached, write requests fail.<ref name=":0" />

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 run on empty file systems. Thus, the results may vary heavily from real-life access patterns.<ref name="workload-benchmarks">{{cite journal |first=Keith Arnold |last=Smith |date=January 2001 |title=Workload-Specific File System Benchmarks |publisher=[[Harvard University]] |___location=[[Cambridge, Massachusetts]] |url=http://www.eecs.harvard.edu/vino/fs-perf/papers/keith_a_smith_thesis.pdf |accessdateaccess-date=2006-12-14 |url-status=dead |archiveurlarchive-url=https://web.archive.org/web/20041117233607/http://www.eecs.harvard.edu/vino/fs-perf/papers/keith_a_smith_thesis.pdf |archivedatearchive-date=2004-11-17 }}</ref>

==Mitigation==

Line 71:

[[BitTorrent (protocol)|BitTorrent]] and other [[peer-to-peer]] [[filesharing]] applications limit fragmentation by preallocating the full space needed for a file when initiating [[download]]s.<ref>{{cite journal |date=29 March 2009 |first=Jeffrey |last=Layton |title=From ext3 to ext4: An Interview with Theodore Ts'o |journal=[[Linux Magazine]] |publisher=[[QuinStreet]] |url=http://www.linux-mag.com/id/7272/ }}</ref>

A relatively recent technique is [[delayed allocation]] in [[XFS]], [[HFS+]]<ref>{{cite web |first=Amit |last=Singh |date=May 2004 |title=Fragmentation in HFS Plus Volumes |work=Mac OS X Internals |url=http://osxbook.com/software/hfsdebug/fragmentation.html }}</ref> and [[ZFS]]; the same technique is also called allocate-on-flush in [[reiser4]] and [[ext4]]. When the file system is being written to, file system blocks are reserved, but the locations of specific files are not laid down yet. Later, when the file system is forced to flush changes 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 |first=Adam |last=Sweeney |first2=Doug |last2=Doucette |first3=Wei |last3=Hu |first4=Curtis |last4=Anderson |first5=Mike |last5=Nishimoto |first6=Geoff |last6=Peck |date=January 1996 |title=Scalability in the XFS File System |publisher=[[Silicon Graphics]] |booktitlebook-title=Proceedings of the USENIX 1996 Annual Technical Conference |___location=[[San Diego, California]] |url=http://www.soe.ucsc.edu/~sbrandt/290S/xfs.pdf |accessdateaccess-date=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 |first=Hans |last=Reiser |date=2006-02-06 |title=The Reiser4 Filesystem |url=http://video.google.com/videoplay?docid=6866770590245111825&q=reiser4 |work=Google TechTalks |accessdateaccess-date=2006-12-14 |archiveurlarchive-url=https://web.archive.org/web/20110519215817/http://video.google.com/videoplay?docid=6866770590245111825&q=reiser4 |archivedatearchive-date=19 May 2011 |url-status=dead }}</ref>

<!-- TODO: Cylinder groups and locality of reference; XFS allocation groups (are they actually relevant?) -->