File system fragmentation

Last updated
Visualization of fragmentation and then of defragmentation FragmentationDefragmentation.gif
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 files non-continuously to allow in-place modification of their contents. It is a special case of data fragmentation. File system fragmentation negatively impacts seek time in spinning storage media, which is known to hinder throughput. Fragmentation can be remedied by re-organizing files and free space back into contiguous areas, a process called defragmentation.

Contents

Solid-state drives 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. [1]

Causes

When a file system is first initialized on a partition, it contains only a few small internal structures and is otherwise one contiguous block of empty space. [lower-alpha 1] This means that the file system is able to place newly created files anywhere on the partition. For some time after creation, files can be laid out near-optimally. When the operating system and applications are installed or archives are unpacked, separate files end up occurring sequentially so related files are positioned close to each other.

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 file system is no longer able to allocate new files contiguously, and has to break them into fragments. This is especially true when the file system becomes full and large contiguous regions of free space are unavailable.

Example

Simplified example of how free space fragmentation and file fragmentation occur File system fragmentation.svg
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.

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. [lower-alpha 2] The file system could defragment the disk immediately after a deletion, but doing so would incur a severe performance penalty at unpredictable times.

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:

  1. Adding a new block somewhere else and indicating that F has a second extent
  2. Moving files in the way of the expansion elsewhere, to allow F to remain contiguous
  3. 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

Some early file systems were unable to fragment files. One such example was the 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 files on 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 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. [2] [3]

Types

File system fragmentation may occur on several levels:

File fragmentation

Individual file fragmentation occurs when a single file has been broken into multiple pieces (called extents 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 space fragmentation

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 preventing fragmentation below).

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. 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. [4]

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 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. [5]

For some file systems (such as NTFS [lower-alpha 3] and HFS/HFS Plus [6] ), the collation/sorting/compaction needed to optimize this data cannot easily occur while the file system is in use. [7]

Negative consequences

File system fragmentation is more problematic with consumer-grade hard disk drives 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. [8] 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. [9] File system fragmentation has less performance impact upon solid-state drives, as there is no mechanical seek time involved. [10] 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. [10]

In simple file system benchmarks, 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. [11]

Mitigation

Several techniques have been developed to fight fragmentation. They can usually be classified into two categories: preemptive and retroactive. Due to the difficulty of predicting access patterns these techniques are most often heuristic in nature and may degrade performance under unexpected workloads.

Preventing fragmentation

Preemptive techniques attempt to keep fragmentation to 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 pre-allocate longer chunks, or chunks from different free space fragments, called extents 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. [9]

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 and other peer-to-peer filesharing applications limit fragmentation by preallocating the full space needed for a file when initiating downloads. [12]

A relatively recent technique is delayed allocation in XFS, HFS+ [13] 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. [14] 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. [15]

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 directories, or directory trees, or even file sequences 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. [16]

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

Notes

  1. Some file systems, such as NTFS and ext2+, might preallocate empty contiguous regions for special purposes.
  2. The practice of leaving the space occupied by deleted files largely undisturbed is why 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.
  3. 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.) [5]

Related Research Articles

New Technology File System (NTFS) is a proprietary journaling file system developed by Microsoft. Starting with Windows NT 3.1, it is the default file system of the Windows NT family. It superseded File Allocation Table (FAT) as the preferred filesystem on Windows and is supported in Linux and BSD as well. NTFS reading and writing support is provided using a free and open-source kernel implementation known as NTFS3 in Linux and the NTFS-3G driver in BSD. By using the convert command, Windows can convert FAT32/16/12 into NTFS without the need to rewrite all files. NTFS uses several files typically hidden from the user to store metadata about other files stored on the drive which can help improve speed and performance when reading data. Unlike FAT and High Performance File System (HPFS), NTFS supports access control lists (ACLs), filesystem encryption, transparent compression, sparse files and file system journaling. NTFS also supports shadow copy to allow backups of a system while it is running, but the functionality of the shadow copies varies between different versions of Windows.

ext3, or third extended filesystem, is a journaled file system that is commonly used by the Linux kernel. It used to be the default file system for many popular Linux distributions. Stephen Tweedie first revealed that he was working on extending ext2 in Journaling the Linux ext2fs Filesystem in a 1998 paper, and later in a February 1999 kernel mailing list posting. The filesystem was merged with the mainline Linux kernel in November 2001 from 2.4.15 onward. Its main advantage over ext2 is journaling, which improves reliability and eliminates the need to check the file system after an unclean shutdown. Its successor is ext4.

Hierarchical File System (HFS) is a proprietary file system developed by Apple Inc. for use in computer systems running Mac OS. Originally designed for use on floppy and hard disks, it can also be found on read-only media such as CD-ROMs. HFS is also referred to as Mac OS Standard, while its successor, HFS Plus, is also called Mac OS Extended.

In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.

<span class="mw-page-title-main">Defragmentation</span> Rearrangement of sectors on a hard disk into contiguous units

In the maintenance of file systems, defragmentation is a process that reduces the degree of fragmentation. It does this by physically organizing the contents of the mass storage device used to store files into the smallest number of contiguous regions. It also attempts to create larger regions of free space using compaction to impede the return of fragmentation. Some defragmentation utilities try to keep smaller files within a single directory together, as they are often accessed in sequence.

Reiser4 is a computer file system, successor to the ReiserFS file system, developed from scratch by Namesys and sponsored by DARPA as well as Linspire. Reiser4 was named after its former lead developer Hans Reiser. As of 2021, the Reiser4 patch set is still being maintained, but according to Phoronix, it is unlikely to be merged into mainline Linux without corporate backing.

HFS Plus or HFS+ is a journaling file system developed by Apple Inc. It replaced the Hierarchical File System (HFS) as the primary file system of Apple computers with the 1998 release of Mac OS 8.1. HFS+ continued as the primary Mac OS X file system until it was itself replaced with the Apple File System (APFS), released with macOS High Sierra in 2017. HFS+ is also one of the formats supported by the iPod digital music player.

<span class="mw-page-title-main">File system</span> Format or program for storing files and directories

In computing, a file system or filesystem is a method and data structure that the operating system uses to control how data is stored and retrieved. Without a file system, data placed in a storage medium would be one large body of data with no way to tell where one piece of data stopped and the next began, or where any piece of data was located when it was time to retrieve it. By separating the data into pieces and giving each piece a name, the data are easily isolated and identified. Taking its name from the way a paper-based data management system is named, each group of data is called a "file". The structure and logic rules used to manage the groups of data and their names is called a "file system."

The Smart File System (SFS) is a journaling filesystem used on Amiga computers and AmigaOS-derived operating systems. It is designed for performance, scalability and integrity, offering improvements over standard Amiga filesystems as well as some special or unique features.

Allocate-on-flush is a file system feature implemented in HFS+, XFS, Reiser4, ZFS, Btrfs, and ext4. The feature also closely resembles an older technique that Berkeley's UFS called "block reallocation".

In computing, an extent is a contiguous area of storage reserved for a file in a file system, represented as a range of block numbers, or tracks on count key data devices. A file can consist of zero or more extents; one file fragment requires one extent. The direct benefit is in storing each range compactly as two numbers, instead of canonically storing every block number in the range. Also, extent allocation results in less file fragmentation.

<span class="mw-page-title-main">Sparse file</span>

In computer science, a sparse file is a type of computer file that attempts to use file system space more efficiently when the file itself is partially empty. This is achieved by writing brief information (metadata) representing the empty blocks to the data storage media instead of the actual "empty" space which makes up the block, thus consuming less storage space. The full block size is written to the media as the actual size only when the block contains "real" (non-empty) data.

In computer storage, fragmentation is a phenomenon in which storage space, main storage or secondary storage, is used inefficiently, reducing capacity or performance and often both. The exact consequences of fragmentation depend on the specific system of storage allocation in use and the particular form of fragmentation. In many cases, fragmentation leads to storage space being "wasted", and in that case the term also refers to the wasted space itself.

The following tables compare general and technical information for a number of file systems.

ext4 is a journaling file system for Linux, developed as the successor to ext3.

<span class="mw-page-title-main">Microsoft Drive Optimizer</span> Windows utility which defragments a hard drive

Microsoft Drive Optimizer is a utility in Microsoft Windows designed to increase data access speed by rearranging files stored on a disk to occupy contiguous storage locations, a technique called defragmentation. Defragmenting a disk minimizes head travel, which reduces the time it takes to read files from and write files to the disk. As a result of the decreased read and write times, Microsoft Drive Optimizer decreases system startup times for systems starting from magnetic storage devices such as a hard drive. However, defragmentation is not helpful on storage devices such as solid state drives, USB drives or SD cards that use flash memory to increase speeds, as these drives do not use a head. Defragmentation may decrease lifespan for certain technologies, e.g. solid state drives. Microsoft Drive Optimizer was first officially shipped with Windows XP.

Contig is a command line defragmentation utility for Windows developed by Microsoft as part of the Sysinternals Suite.

Block suballocation is a feature of some computer file systems which allows large blocks or allocation units to be used while making efficient use of empty space at the end of large files, space which would otherwise be lost for other use to internal fragmentation.

File carving is the process of reassembling computer files from fragments in the absence of filesystem metadata.

A journaling file system is a file system that keeps track of changes not yet committed to the file system's main part by recording the goal of such changes in a data structure known as a "journal", which is usually a circular log. In the event of a system crash or power failure, such file systems can be brought back online more quickly with a lower likelihood of becoming corrupted.

References

  1. Fisher, Ryan (2022-02-11). "Should I defrag my SSD?". PC Gamer. Archived from the original on 2022-02-18. Retrieved 2022-04-26.
  2. http://www.8bs.com/hints/083.txt - Description of the can't extend error
  3. http://8bs.com/mag/1to4/basegd1.txt - Possible data loss caused by the can't extend error
  4. Douceur, John R.; Bolosky, William J. (June 1999). "A Large-Scale Study of File-System Contents". ACM SIGMETRICS Performance Evaluation Review. 27 (1): 59–70. doi: 10.1145/301464.301480 .
  5. 1 2 "How NTFS reserves space for its Master File Table (MFT)". learn.microsoft.com. Microsoft. Retrieved 22 October 2022.
  6. "DiskWarrior in Depth". Alsoft. Retrieved 22 October 2022.
  7. "Maintaining Windows 2000 Peak Performance Through Defragmentation". learn.microsoft.com. Microsoft. Retrieved 22 October 2022.
  8. Kryder, Mark H. (2006-04-03). Future Storage Technologies: A Look Beyond the Horizon (PDF). Storage Networking World conference. Seagate Technology. Archived from the original (PDF) on 17 July 2006.
  9. 1 2 McVoy, L. W.; Kleiman, S. R. (Winter 1991). "Extent-like Performance from a UNIX File System" (PostScript). Proceedings of USENIX winter '91. Dallas, Texas: Sun Microsystems, Inc. pp. 33–43. Retrieved 2006-12-14.
  10. 1 2 Hanselman, Scott (3 December 2014). "The real and complete story - Does Windows defragment your SSD?". Scott Hanselman's blog.
  11. Smith, Keith Arnold (January 2001). "Workload-Specific File System Benchmarks" (PDF). Cambridge, Massachusetts: Harvard University. Archived from the original (PDF) on 2004-11-17. Retrieved 2006-12-14.{{cite journal}}: Cite journal requires |journal= (help)
  12. Layton, Jeffrey (29 March 2009). "From ext3 to ext4: An Interview with Theodore Ts'o". Linux Magazine . QuinStreet. Archived from the original on April 1, 2009.{{cite journal}}: CS1 maint: unfit URL (link)
  13. Singh, Amit (May 2004). "Fragmentation in HFS Plus Volumes". Mac OS X Internals. Archived from the original on 2012-11-18. Retrieved 2009-10-27.
  14. Sweeney, Adam; Doucette, Doug; Hu, Wei; Anderson, Curtis; Nishimoto, Mike; Peck, Geoff (January 1996). "Scalability in the XFS File System" (PDF). Proceedings of the USENIX 1996 Annual Technical Conference. San Diego, California: Silicon Graphics . Retrieved 2006-12-14.
  15. Reiser, Hans (2006-02-06). "The Reiser4 Filesystem". Google TechTalks. Archived from the original on 19 May 2011. Retrieved 2006-12-14.
  16. Singh, Amit (2007). "12 The HFS Plus File System". Mac OS X Internals: A Systems Approach. Addison Wesley. ISBN   0321278542.

Further reading