http://osxbook.com/software/hfsdebug/fragmentation.htmlFragmentation in HFS Plus Volumes© Amit Singh. All Rights Reserved. Written in May 2004IntroductionFragmentation in filesystems has traditionally been an important factor affecting performance negatively. Modern filesystems are usually less prone to fragmentation than their ancestors. Numerous algorithms and schemes have been incorporated into filesystems to reduce fragmentation, and in some cases, even undo existing fragmentation. Nevertheless, fragmentation is still a cause for concern for those who design and implement filesystems, as well as for end users. The purpose of this discussion is to:
Note that I do not intend to make any claims regarding the fragmentation-resistance of HFS+. I have sampled too few a volume to generalize my "results". This discussion is more illustrative than empirical, wherein I am only suggesting a tool/method that you could use to gauge your own volumes' situation. hfsdebug
While analyzing the fragmentation issue, I created a tool called Please go to the What is Fragmentation?In a typical scenario, an operating system uses a disk drive in a mode where the drive's storage space appears as a logically contiguous sequence of blocks. The drive does read-aheads, and supports large size I/O requests for contiguous blocks. Thus, it is desirable to have data be contiguous on disk. The entire disk, or one or more of its logically contiguous subsets, may be formatted to contain volumes. Informally put, a filesystem is a scheme for arranging data on the disk, while a volume is an instance of a filesystem. It is somewhat subjective and context dependent to define fragmentation. Let us first define what lack of fragmentation is in our context: a file on a volume is unfragmented if all its content resides in contiguous blocks at the volume level. A file on HFS+ could theoretically have an arbitrary number of forks, analogous to named attributes in NTFS. At the time of this writing, Mac OS X uses only two named forks: the data fork, and the resource fork, each of which is like a traditional file, with its own content on the volume. From here onwards, instead of talking about a file's fragmentation, we shall talk about a fork's fragmentation. Let us consider a few types of fragmentation: User-level Data FragmentationEven if a file is contiguous on disk, it may contain information that is not contiguous at the user level. For example, a word processor document may be contiguous on disk, but not from the point of view of how the word processor reads it. It is both difficult, and not very worthwhile, to quantify or deal with such fragmentation, mainly because it depends on the application in question, the file format, and so on. We will not discuss this kind of fragmentation here. Internal FragmentationAn HFS+ volume allocates space to files in units called allocation blocks. An allocation block's size (for example, 4096 bytes) is usually a multiple of a disk drive's block size (for example, 512 bytes). Both these numbers are much larger than a file's fundamental unit of size: 1 byte. Suppose an HFS+ volume has an allocation block size of 4096 bytes, then a 1 byte file on it would "use" 4096 bytes. The rest of the space (4095 bytes) is wasted -- at least until the file's size grows. Such wastage is usually referred to as internal fragmentation. We shall calculate the internal fragmentation of an HFS+ volume in this discussion. BSD's UFS (also supported on Mac OS X) employs another unit of allocation besides a block: a fragment. A fragment is a fraction of a block (for example, 1/8th of a block). Fragments lead to more efficient use of space when there is a large number of small files on a volume, at the cost of more complicated logic in the filesystem's implementation. External FragmentationExternal fragmentation is what people usually mean when they refer to fragmentation. As mentioned earlier, the fundamental unit of space allocation to a fork on HFS+ is an allocation block. The primary allocation method used by HFS+ is extent-based. An extent is a chunk of contiguous allocation blocks, and is represented in HFS+ by a number pair: the starting block on the volume, and the number of blocks that follow. An allocation block is typically 4096 bytes, but does not have to
be. Assuming 4096 byte allocation blocks, a 16384 byte fork will need
four of them. These blocks could be contiguous -- all in one extent --
in which case the fork would be unfragmented. The fork's location on
the volume is specified (in HFS+ data structures) using an extent
descriptor:
the { startBlock, blockCount } pair. Our 16384 byte fork could reside
on the volume starting at block 12345, in which case its extent
descriptor would be
If the above fork were fragmented, specification of its location would
require more than one extent descriptor: in fact, as many as the number
of fragments the fork has. For example, In this discussion, we use the term "fragment" to mean the same as an extent. It should not be confused with UFS' fragments. A 100% contiguous file has exactly one extent, and each additional extent introduces one discontinuity in the file. Now, it is important to note that while an HFS+ fork may have any number of extents, only eight descriptors are resident in the file's record (roughly analogous to an inode), alongside its owning file's usual metadata. If a fork does have more than eight extents, descriptors for the ones beyond the first eight overflow to an Extents Overflow B-Tree, where they have to be looked up at some additional cost. Thus, we could classify HFS+ forks in the following manner:
We have so far implied that "contiguous is good", which is usually true. The performance of modern drives is higher when I/O requests have a larger size. More contiguity in file allocation allows for larger I/O requests (plus any CPU overheads may be amortized), leading to better sequential I/O performance. Quantifying FragmentationIt may be rather subjective to compare two fragmented files and say which is worse; such quantification will also depend on how you use the files. Consider an example:
Suppose you have two files X and Y whose extents are Rather than coming up with one consolidated fragmentation "number", we shall simply examine various aspects of the volume, and look at fragmentation in multiple ways. I analyzed five HFS+ volumes, on four computers, each used by a different person. Again, this is too small a sample to generalize from, and is only meant to be illustrative. The usage characteristics of the volumes are as follows:
Each computer has a 6+ months old Mac OS X "Panther" installation. AnalysisWe first obtain summarized usage statistics for each volume, as shown in Table 1. Most of these statistics were derived from the output of the following command line:
Note that if a fork is empty, that is, has a zero size, we do not include it in our calculations at all -- we consider a zero fork to be neither fragmented nor unfragmented. It is not fragmented for obvious reasons. We could consider it as unfragmented, but in my opinion, that would make the volume to appear less fragmented than it practically is. A typical Mac OS X installation, as we shall see, has most data forks non-zero, and most resource forks zero. There may also be a small number of empty files, with both forks zero.
In Table 1, the numbers in the rows titled "non-zero" represent the number of data and resource forks that have non-zero content, while "fragmented" represents forks that have more than one extent (forks that are not 100% contiguous). We shall refine these numbers shortly, before which let us look at the figures for internal fragmentation, in Table 2.
We get the internal fragmentation for a fork type on a volume by calculating the difference between the total space allocated to all forks of that type, and the total space used by all forks of that type. The latter is just the sum of all fork sizes. Intuitively, a larger block size would lead to higher internal fragmentation if the volume has many small files. A similar trend is seen in our volumes here. Let us determine what percentage of forks are not 100% contiguous. As shown in Table 3, this turns out to be a very small number for all volumes.
Thus, very few forks on each volume have more than one extent. Next, we examine the "fragmented" forks in more detail to find out how fragmented these are. Consider the statistics in Table 4, which were derived from the output of the following command line:
When run with the
Note that you may see one or more files under
We see that for most volumes, the majority of fragmented files are "barely fragmented", that is, they have only two extents. As mentioned earlier, the next "degree" of fragmentation happens when a fork has more than eight extents. The number of such forks is very small, particularly for "normal" volumes (unlike "G5 Ext", which has a large number of extremely large files). What do these numbers mean?Many of the numbers are "low" enough that they are worth considering, even in isolation (that is, without comparison to another filesystem). The design of HFS+, and some of its optimizations (see the next section), are aimed at reducing fragmentation. Based on the volumes I looked at, fragmentation does seem to be under control. This is not to say that HFS+ is a cutting-edge filesystem, which in turn is not say that a cutting-edge filesystem is bound to be an excellent system in real life! NTFS is more advanced than HFS+ in many respects, but real-life filesystem behavior in Windows often leaves much to be desired. Some key features found in NTFS but not in HFS+ include: resident attributes (very small files fit entirely within the file record), sparse files, transparent compression, the Encrypting File System facility, and more versatile indexing and change logging. Still, the numbers would be more meaningful if they were compared against something. Time permitting, I shall try to obtain similar statistics for a few important filesystems (say, NTFS and ReiserFS, to begin with). A challenge is to find "equivalent" volumes (same age, same usage pattern, and so on). One option would be to simulate use, and age a volume artificially. Built-in Measures in Mac OS X Against FragmentationAs stated earlier, the primary allocation method in HFS+ is extent-based, which helps in contiguity. Moreover, HFS+ uses delayed allocation: rather than allocating blocks as a file is written in memory, the filesystem can reserve (or loan) blocks, delaying actual allocation until the buffer cache is flushed to disk. Thus, several small allocations can be combined into larger, possibly contiguous, allocations. While Apple does not provide a defragmentation tool, they introduced a few HFS+ optimizations in "Panther", two of which play important roles in countering (even undoing) the fragmentation of files that are below a certain size, and are frequently accessed. On-the-fly DefragmentationWhen a file is opened on an HFS+ volume, the following conditions are tested:
If all of the above conditions are satisfied, the file is relocated -- it is defragmented on-the-fly. Hot File Clustering
This optimization is currently available only on boot volumes. Hot File
Clustering is a multi-staged clustering scheme that records "hot" files
(except journal files, and ideally quota files) on a volume, and moves
them to the "hot space" on the volume (0.5% of the total filesystem
size located at the end of the default metadata zone, which itself is
at the start of the volume). The files are also defragmented. The
various stages in this scheme are
You can use A defragmenting tool should not move a file into the hot file area, nor should it move a file out of the hot file area. Doing so might degrade performance! Poor Man's DefragmentationAs we have seen, an HFS+ volume seems to resist fragmentation rather well on Mac OS X 10.3.x, and I don't envision fragmentation to be a problem bad enough to require proactive remedies (such as a defragmenting tool).
Moving a file to a new name does not change its Catalog Node ID (CNID), and copying it back to the original name will result in the copy having a different CNID. ConclusionDefragmentation on HFS+ volumes should not be necessary at all, or worthwhile, in most cases, because the system seems to do a very good job of avoiding/countering fragmentation. It is risky to defragment anyway: What if there's a power glitch? What if the system crashes? What if the defragmenting tool has a bug? What if you inadvertently reboot? In some cases, you could make the situation worse by defragmenting. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
