File system fragmentation: Difference between revisions

Revision as of 06:25, 14 December 2006

Revision as of 07:07, 14 December 2006

Line 3:

In computing, '''[[file system]] [[fragmentation (computer)|fragmentation]]''', sometimes called '''file system aging''' is the inability of a file system to lay out related data sequentially (contiguously), an inherent phenomena in [[computer storage|storage]]-backed file systems that allow in-place modification of their contents. It is a special case of [[fragmentation (computer)#Data fragmentation|data fragmentation]].

File system fragmentation is projected to become more problematic with time,newer hardware due to the increasing disparity ofbetween 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 |accessdate=2006-12-14 }}</ref> which file systems are usually placed on. Thus, fragmentation is a 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 on its implementation.

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 ran on empty file systems, and unsuprisingly, 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 |accessdate=2006-12-14 }}</ref>

File system fragmentation may occur on several levels:

* Fragmentation within individual [[computer file|file]]s 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.

==Types of fragmentation==

====File fragmentation====

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

====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 (sometimes called "bubbles") of free space in order to facilitate extending nearby files (see [[#Proactive techniques|proactive techniques]] below).

====Related file fragmentation====

Unlike the previous two types of fragmentation, related file fragmentation is a much more vague concept, as it heavily depends on the access pattern of related files. 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.{{fact}}

==Techniques for mitigating fragmentation==

Line 22 ⟶ 27:

====Proactive techniques====

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.

A recent technique is [[allocate-on-flush]] in [[XFS]] and [[ZFS]], also called delayed allocation in [[reiser4]] and [[ext4]].

====Retroactive techniques====

Line 32 ⟶ 39:

==References==

<references />

* {{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 |accessdate=2006-12-14 }}

{{compu-storage-stub}}

[[Category:Computer file systems]]

[[Category:Computer storage devices]]

[[Category:Disk file systems]]