Content deleted Content added
misc; added →Why fragmentation occurs |
Guy Harris (talk | contribs) →File scattering: There's no "file sequence" page any more. |
||
| (242 intermediate revisions by more than 100 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]], '''
[[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>
==Why fragmentation occurs==▼
Initially, when a file system is initialized on a partition (the partition is formatted for the file system), the entire space alotted is empty.<ref>The partition is not ''completely empty'': some internal file system structures are always created. However, these are typically contiguous, and their existence is negligible. Some file systems, such as [[NTFS]] and [[ext2]]+, might also preallocate empty contiguous regions for special purposes.</ref> This means that the allocator algorithm is completely free to position newly created files anywhere on the disk. For some time after creation, files on the file system can be laid out near-optimally. When the [[operating system]] and [[application software|application]]s are installed, or [[archive (computing)|archive]]s are unpacked, laying out separate files sequentially also means that related files are likely to be positioned close to each other.▼
==Causes==
However, as existing files are deleted or truncated, new regions of free space are created. When existing files are appended to, it is often impossible to resume the write exactly where the file used to end, as another file may already be allocated there — thus, a new fragment has to be allocated. As time goes on, and the same factors are continuously present, free space as well as frequently appended files tend to fragment more. Shorter regions of free space also mean that the allocator is no longer able to allocate new files contiguously, and has to break them into fragments.▼
▲
▲
===Example===
[[File:File system fragmentation.svg|thumb|Simplified example of how free space fragmentation and file fragmentation occur]]The following example is a simplification of an otherwise complicated subject. Consider the following scenario: A new disk has had five files, named A, B, C, D and E, saved continuously and sequentially in that order. Each file is using 10 ''blocks'' of space. (Here, the block size is unimportant.) The remainder of the disk space is one free block. Thus, additional files can be created and saved after the file E.
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 an 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 33–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>▼
If the file B is deleted, a second region of ten blocks of free space is created, and the disk becomes fragmented. The empty space is simply left there, marked as and available for later use, then used again as needed.{{efn|The practice of leaving the space occupied by deleted files largely undisturbed is why [[undeletion|undelete]] programs were able to work; they simply recovered the file whose name had been deleted from the directory, but whose contents were still on disk.}} The file system ''could'' defragment the disk immediately after a deletion, but doing so would incur a severe performance penalty at unpredictable times.
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, and unsurprisingly, 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>▼
Now, a new file called F, which requires seven blocks of space, can be placed into the first seven blocks of the newly freed space formerly holding the file B, and the three blocks following it will remain available. If another new file called G, which needs only three blocks, is added, it could then occupy the space after F and before C.
If subsequently F needs to be expanded, since the space immediately following it is occupied, there are three options for the file system:
# Adding a new block somewhere else and indicating that F has a second [[Extent (file systems)|extent]]
# Moving files in the way of the expansion elsewhere, to allow F to remain contiguous
# Moving file F so it can be one contiguous file of the new, larger size
The second option is probably impractical for performance reasons, as is the third when the file is very large. The third option is impossible when there is no single contiguous free space large enough to hold the new file. Thus the usual practice is simply to create an ''extent'' somewhere else and chain the new extent onto the old one.
Material added to the end of file F would be part of the same extent. But if there is so much material that no room is available after the last extent, then ''another'' extent would have to be created, and so on. Eventually the file system has free segments in many places and some files may be spread over many extents. Access time for those files (or for all files) may become excessively long.
==Necessity==
{{Essay-like|section|date=June 2019}}
Some early file systems were unable to fragment files. One such example was the [[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.
Standards of [[error handling]] at the time were primitive and in any case programs squeezed into the limited memory of the BBC Micro could rarely afford to waste space attempting to handle errors gracefully. Instead, the user would find themselves dumped back at the command prompt with the ''Can't extend'' message and all the data which had yet to be appended to the file would be lost. The problem could not be solved by simply checking the free space on the disk beforehand, either. While free space on the disk may exist, the size of the largest contiguous block of free space was not immediately apparent without analyzing the numbers presented by the disk catalog and so would escape the user's notice. In addition, almost all DFS users had previously used [[Data cassette|cassette file storage]], which does not suffer from this error. The upgrade to a [[floppy disk]] system was an expensive upgrade, and it was a shock that the upgrade might without warning cause [[data loss]].<ref>http://www.8bs.com/hints/083.txt - Description of the ''can't extend'' error</ref><ref>http://8bs.com/mag/1to4/basegd1.txt - Possible data loss caused by the ''can't extend'' error</ref>
==Types==
File system fragmentation may occur on several levels:
* Fragmentation within individual [[computer file|file]]s
* * Fragmentation within the data structures or special files reserved for the file system itself
▲* The decrease of [[locality of reference]] between separate, but related files.
Individual file fragmentation occurs when a single file has been broken into multiple pieces (called [[extent (file systems)|extent]]s on extent-based file systems). While disk file systems attempt to keep individual files contiguous, this is not often possible without significant performance penalties. File system check and defragmentation tools typically only account for file fragmentation in their "fragmentation percentage" statistic.
Free (unallocated) space fragmentation occurs when there are several unused areas of the file system where new files or metadata can be written to. Unwanted free space fragmentation is generally caused by deletion or truncation of files, but file systems may also intentionally insert fragments ("bubbles") of free space in order to facilitate extending nearby files (see [[#
===
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
==
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>
Several techniques have been developed to fight fragmentation. They can usually be classified into two categories: ''proactive'' and ''retroactive''. Due to the hard predictability of access patterns, these techniques are most often [[heuristic (computer science)|heuristic]] in nature, and may degrade performance under unexpected workloads.▼
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>
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.▼
==Negative consequences==
Many today's file systems attempt to preallocate longer chunks, or chunks from different free space fragments, called [[extent]]s 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/>▼
▲File system fragmentation is
▲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
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 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 |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>▼
==Mitigation==
▲Several techniques have been developed to fight fragmentation. They can usually be classified into two categories: ''
▲
▲Many of today's file systems attempt to
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]].
<!-- TODO: Cylinder groups and locality of reference; XFS allocation groups (are they actually relevant?) -->
===Defragmentation===
{{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 often also increase [[locality of reference]] by keeping smaller files in [[file directory|directories]], or directory trees, close to each another on the disk. Some file systems, such as [[HFS Plus]], utilize idle time to defragment data on the disk in the background.▼
▲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
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>
The now obsolete Commodore Amiga [[Smart File System]] (SFS) defragmented itself while the filesystem was in use. The defragmentation process is almost completely stateless (apart from the ___location it is working on), so that it can be stopped and started instantly. During defragmentation data integrity is ensured for both metadata and normal data.
==See also==
* [[List of defragmentation software]]
* [[
* [[
==Notes==
{{Notelist}}
==References==
{{reflist|30em}}
==Further reading==
{{refbegin}}
* {{cite thesis |url=https://dash.harvard.edu/bitstream/handle/1/26506455/tr-35-94.pdf?sequence=1 |first= Keith |last=Smith |first2=Margo |last2=Seltzer |title=File Layout and File System Performance |publisher=[[Harvard University]] |type=Paper}}
{{refend}}
{{DEFAULTSORT:File System Fragmentation}}
[[Category:
| |||