File system fragmentation: Difference between revisions

Revision as of 06:43, 5 February 2022

Latest revision as of 22:54, 3 December 2023

(15 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Condition where a segmented file system is used inefficiently}}

[[File:FragmentationDefragmentation.gif|thumb|Visualization of fragmentation and then of defragmentation]]In [[computing]], '''file system fragmentation''', sometimes called '''file system aging''', is the tendency of a [[file system]] to lay out the contents of [[Computer file|files]] non-continuously to allow in-place modification of their contents. It is a special case of [[fragmentation (computer)#Data fragmentation|data fragmentation]]. File system fragmentation increasesnegatively disk head movement orimpacts [[seek time]] (wherein itspinning applies)storage media, which areis known to hinder [[throughput (disk drive)|throughput]]. TheFragmentation correctioncan tobe existingremedied fragmentation is toby reorganizere-organizing files and free space back into contiguous areas, a process called [[defragmentation]].

[[Solid-state drive]]s do not physically seek, so their non-sequential data access is hundreds of times faster than moving drives, making fragmentation less of an issue. It is recommended to not manually defragment solid-state storage, because this can prematurely wear drives via unnecessary write–erase operations.<ref>{{Cite news |last=Fisher |first=Ryan |date=2022-02-11 |title=Should I defrag my SSD? |language=en |work=PC Gamer |url=https://www.pcgamer.com/should-i-defrag-my-ssd/ |url-status=live |access-date=2022-04-26 |archive-url=https://web.archive.org/web/20220218151612/https://www.pcgamer.com/should-i-defrag-my-ssd/ |archive-date=2022-02-18}}</ref>

In computers with [[solid-state drives]], file system fragmentation is much less of a performance problem, as there is no movement of heads or discs. In fact, defragmenting such drives can slowly shorten their lifespan.{{citation needed|date=December 2021}}

==Causes==

Line 28 ⟶ 29:

{{Essay-like|section|date=June 2019}}

Some early file systems were unable to fragment files. One such example was the [[Acorn Computers|Acorn]] [[Disc Filing System|Acorn DFS]] file system used on the [[BBC Micro]]. Due to its inability to fragment files, the error message ''can't extend'' would at times appear, and the user would often be unable to save a file even if the disk had adequate space for it.

DFS used a very simple disk structure and [[Computer file|files]] on [[Hard disk|disk]] were located only by their length and starting sector. This meant that all files had to exist as a continuous block of sectors and fragmentation was not possible. Using the example in the table above, the attempt to expand file F in step five would have failed on such a system with the ''can't extend'' error message. Regardless of how much free space might remain on the disk in total, it was not available to extend the data file.

Line 36 ⟶ 37:

==Types==

File system fragmentation may occur on several levels:

* Fragmentation within individual [[computer file|file]]s

* Free space fragmentation

* The decrease of [[locality of reference]] between separate, but related files

* Fragmentation within the data structures or special files reserved for the file system itself

===File fragmentation===

Line 48 ⟶ 49:

===File scattering===

File segmentation, also called related-file fragmentation, or application-level (file) fragmentation, refers to the lack of [[locality of reference]] (within the storing medium) between related files (see [[file sequence]] for more detail). Unlike the previous two types of fragmentation, file scattering is a much more vague concept, as it heavily depends on the access pattern of specific applications. This also makes objectively measuring or estimating it very difficult. However, arguably, it is the most critical type of fragmentation, as studies have found that the most frequently accessed files tend to be small compared to available disk throughput per second.<ref name="filesys-contents">{{cite journal | title=A Large-Scale Study of File-System Contents | date=June 1999 | last=Douceur | first=John R. | last2=Bolosky | first2=William J. | journal=ACM SIGMETRICS Performance Evaluation Review | volume=27 | issue=1 | pages=59–70 | doi=10.1145/301464.301480| doi-access=free }}</ref>

{{See also|File sequence}}

File segmentation, also called related-file fragmentation, or application-level (file) fragmentation, refers to the lack of [[locality of reference]] (within the storing medium) between related files (see [[file sequence]] for more detail). Unlike the previous two types of fragmentation, file scattering is a much more vague concept, as it heavily depends on the access pattern of specific applications. This also makes objectively measuring or estimating it very difficult. However, arguably, it is the most critical type of fragmentation, as studies have found that the most frequently accessed files tend to be small compared to available disk throughput per second.<ref name="filesys-contents">{{cite journal | title=A Large-Scale Study of File-System Contents | date=June 1999 | last=Douceur | first=John R. | last2=Bolosky | first2=William J. | journal=ACM SIGMETRICS Performance Evaluation Review | volume=27 | issue=1 | pages=59–70 | doi=10.1145/301464.301480}}</ref>

To avoid related file fragmentation and improve locality of reference (in this case called ''file contiguity''), assumptions or active observations about the operation of applications have to be made. A very frequent assumption made is that it is worthwhile to keep smaller files within a single [[file directory|directory]] together, and lay them out in the natural file system order. While it is often a reasonable assumption, it does not always hold. For example, an application might read several different files, perhaps in different directories, in exactly the same order they were written. Thus, a file system that simply orders all writes successively, might work faster for the given application.

===Data structure fragmentation===

The catalogs or indices used by a file system itself can also become fragmented over time, as the entries they contain are created, changed, or deleted. This is more of a concern when the volume contains a multitude of very small files than when a volume is filled with fewer larger files. Depending on the particular file system design, the files or regions containing that data may also become fragmented (as described above for 'regular' files), regardless of any fragmentation of the actual data records maintained within those files or regions.<ref name="ntfs-reserves-space-for-mft">{{cite web |title=How NTFS reserves space for its Master File Table (MFT) |url=https://learn.microsoft.com/en-us/troubleshoot/windows-server/backup-and-storage/ntfs-reserves-space-for-mft |website=learn.microsoft.com |publisher=Microsoft |access-date=22 October 2022 |language=en-us}}</ref>

For some file systems (such as [[NTFS]]{{efn|NTFS reserves 12.5% of the volume for the 'MFT zone', but ''only'' until that space is needed by other files. ''(i.e., if the volume ~ever~ becomes more than 87.5% full, an un-fragmented MFT can no longer be guaranteed.)''<ref name="ntfs-reserves-space-for-mft" />}} and [[Hierarchical File System (Apple)|HFS]]/[[HFS Plus]]<ref name="diskwarrior-hfs-hfsplus">{{cite web |title=DiskWarrior in Depth |url=https://www.alsoft.com/in-depth |website=Alsoft |access-date=22 October 2022}}</ref>), the [[collation]]/[[sorting]]/[[Data compaction|compaction]] needed to optimize this data cannot easily occur while the file system is in use.<ref name="windows-2000-defrag-performance">{{cite web |title=Maintaining Windows 2000 Peak Performance Through Defragmentation |url=https://learn.microsoft.com/en-us/previous-versions/windows/it-pro/windows-2000-server/bb742585(v=technet.10) |website=learn.microsoft.com |publisher=Microsoft |access-date=22 October 2022 |language=en-us}}</ref>

==Negative consequences==

Line 63 ⟶ 67:

===Preventing fragmentation===

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

Many of today's file systems attempt to preallocatepre-allocate longer chunks, or chunks from different free space fragments, called [[extent (file systems)|extent]]s to files that are actively appended to. This largely avoids file fragmentation when several files are concurrently being appended to, thus avoiding their becoming excessively intertwined.<ref name=mcvoy-extent/>

If the final size of a file subject to modification is known, storage for the entire file may be preallocated. For example, the [[Microsoft Windows]] [[swap file]] (page file) can be resized dynamically under normal operation, and therefore can become highly fragmented. This can be prevented by specifying a page file with the same minimum and maximum sizes, effectively preallocating the entire file.

[[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/ |archive-url=https://web.archive.org/web/20090401152937/http://www.linux-mag.com/id/7272 |url-status=usurped |archive-date=April 1, 2009 }}</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 |access-date=2009-10-27 |archive-date=2012-11-18 |archive-url=https://web.archive.org/web/20121118173110/http://osxbook.com/software/hfsdebug/fragmentation.html |url-status=dead }}</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]] |book-title=Proceedings of the USENIX 1996 Annual Technical Conference |___location=[[San Diego, California]] |url=http://www.soe.ucsc.edu/~sbrandt/290S/xfs.pdf |access-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 |access-date=2006-12-14 |archive-url=https://web.archive.org/web/20110519215817/http://video.google.com/videoplay?docid=6866770590245111825&q=reiser4 |archive-date=19 May 2011 |url-status=dead }}</ref>

Line 77 ⟶ 81:

{{Main|Defragmentation}}

Retroactive techniques attempt to reduce fragmentation, or the negative effects of fragmentation, after it has occurred. Many file systems provide [[defragmentation]] tools, which attempt to reorder fragments of files, and sometimes also decrease their scattering (i.e. improve their contiguity, or [[locality of reference]]) by keeping either smaller files in [[file directory|directories]], or directory trees, or even [[file sequence]]ssequences close to each other on the disk.

The [[HFS Plus]] file system transparently defragments files that are less than 20 [[MiB]] in size and are broken into 8 or more fragments, when the file is being opened.<ref name=osx-intern>{{cite book |first=Amit |last=Singh |year=2007 |title=Mac OS X Internals: A Systems Approach |publisher=[[Addison Wesley]] |chapter=12 The HFS Plus File System |isbn=0321278542<!--Surprisingly, ISBN lookup on Google Books returns nothing. Hence, I supplied a URL.--> |chapter-url=https://books.google.com/books?id=UZ7AmAEACAAJ}}</ref>