In computing, file system fragmentation, sometimes called file system aging, is
the inability of a file system to lay out related data sequentially, an
inherent phenomenon in storage-backed file systems that allow in-place
modification of their contents. It is a special case of data fragmentation. File
system fragmentation increases disk head movement or seeks, which are known to
hinder throughput. The correction to existing fragmentation is to reorganize
files and free space back into contiguous areas, a process called
defragmentation. Cause
When a file system is first initialized on a partition, the partition contains
only a few small internal structures and is otherwise one contiguous block of
empty space. This means that the allocator algorithm is completely free
to place newly created files anywhere on the partition. For some time after
creation, files on the file system can be laid out near-optimally. When the
operating system and applications are installed or other archives are
unpacked, laying out separate files sequentially also means that related
files are likely to be positioned close to each other.
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. This is especially true when
the file system is more full — longer contiguous regions of free space are
less likely to occur. Note that the following is a
simplification of an otherwise complicated subject. The method which is
about to be explained has been the general practice for allocating files on
disk and other random-access storage for over 30 years. Some operating systems do
not simply allocate files one after the other, and some use various methods to
try to prevent fragmentation, but in general, sooner or later, for the
reasons explained in the following explanation, fragmentation will occur as
time goes by on any system where files are routinely deleted or expanded.
Consider the following scenario, as shown by the image on the right:
A new disk has had 5 files saved on it, named A, B, C, D and E, and each file is
using 10 blocks of space. As the free space is contiguous the files are
located one after the other). If file B is deleted, a second region of
10 blocks of free space is created, and the disk becomes fragmented. The file
system could defragment the disk immediately after a deletion, which
would incur a severe performance penalty at unpredictable times, but in general
the empty space is simply left there, marked in a table as available for later
use, then used again as needed). Now if a new file F requires 7 blocks of
space, it can be placed into the first 7 blocks of the space formerly holding the
file B, and the 3 blocks following it will remain available). If another new
file G is added, and needs only three blocks, 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:
add a new block somewhere else and indicate that F has a second extent,
move files in the way of the expansion elsewhere, to allow F to remain
contiguous; or move 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. Indeed 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 may become excessively long.
To summarize, factors that typically cause or facilitate fragmentation
include: low free space.
frequent deletion, truncation or extension of files.
overuse of sparse files. Need for fragmentation
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
resulting frustration would be greater if the user had taken the trouble to
check the free space on the disk beforehand and found free space. While
free space on the disk may exist, the fact that it was not in the place where
it was needed was not apparent without mentally analysing the numbers presented
by the disk catalog and so would escape the user's notice. In addition, DFS
users had almost without exception previously been accustomed to cassette
file storage, which does not suffer from this error. The upgrade to a floppy disk
system was expensive, but it freed users from the unreliability and terrible
slowness of the cassette system, and it was a shock to make the sudden and
unpleasant discovery that the upgrade might without warning cause data loss of
their recent work. Performance implications
File system fragmentation is projected to become more problematic with newer
hardware due to the increasing disparity between sequential access speed and
rotational latency, of consumer-grade hard disks, on which file systems are
usually placed. 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. 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, and unsurprisingly, the results
may vary heavily from real-life access patterns.
File system fragmentation has less impact upon the performance of
solid-state drives, as there is no mechanical seek time involved like with
rotating media, though additional non-sequential I/O operations impacts
system performance, and many file system architectures consume additional
internal resources when fragmentation is present.
Types of fragmentation File system fragmentation may occur on
several levels: Fragmentation within individual files
and their metadata. Free space fragmentation, making it
increasingly difficult to lay out new files contiguously.
The decrease of locality of reference between separate, but related files.
= File fragmentation = Individual file fragmentation occurs
when a single file has been broken into multiple pieces. 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 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 of free space in order
to facilitate extending nearby files. = File scattering =
File segmentation, also called related-file fragmentation, or
application-level fragmentation, refers to the lack of locality of reference
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.
To avoid related file fragmentation and improve locality of reference,
assumptions 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. Techniques for mitigating fragmentation
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 at 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 preallocate 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. 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 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.
A relatively recent technique is delayed allocation in XFS, HFS+ 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. 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, they are always read
sequentially. = 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 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.
The now obsolete Commodore Amiga Smart File System defragmented itself while
the filesystem was in use. The defragmentation process is almost
completely stateless, 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 FAT file fragmentation
Disk compression Notes and references
General Keith Smith, Margo Seltzer: File Layout
and File System Performance