The Book

The Book — Extras

Software

Meta

About

elsewhere

Fragmentation in HFS Plus Volumes

Introduction

Fragmentation 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:

• Introduce hfsdebug, a tool for exploring internals of HFS+ volumes.
• Describe a procedure for quantifying fragmentation in HFS+ volumes, and list the results of applying this procedure to a few volumes.

hfsdebug

While analyzing the fragmentation issue, I created a tool called hfsdebug, which may be thought of as a read-only HFS+ filesystem debugger. hfsdebug has several other features besides displaying fragmentation statistics. I expect it to be a useful tool for studying the design of HFS+. All statistics mentioned directly or indirectly in this discussion were obtained using this tool.

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.

Let us consider a few types of fragmentation:

User-level Data Fragmentation

Even 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 Fragmentation

An 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.

External Fragmentation

External 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 { 12345, 4 }.

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, [ { 12345, 2 }, { 23456, 2 } ] means that the fork has two contiguous blocks starting at volume block 12345, and two other contiguous blocks starting at volume block 23456.

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:

• Those that are unfragmented (that is, have exactly one extent).
• Those that have at least two, and at most eight extents.
• Those that have more than eight extents.

Quantifying Fragmentation

It 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 [ { x1, 500 }, { x2, 500 } ] and [ { y1, 999 }, { y2, 1 } ], respectively. Both files have two fragments (a single discontinuity), and both have 1000 blocks. Which is more fragmented? If you were to sequentially read both X and Y in their entirety, you would have to hit one discontinuity for each, so they are equally "bad". If you were to read N contiguous blocks randomly, however, then Y is better than X, because there's a higher probability that the N contiguous blocks would fall in the 999 block wide contiguous region in Y than one of the smaller 500 block regions in X. Then again, the maximum allowable size of an I/O request may change things!

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:

• iBook — Used everyday by a non-technical/non-power user, for browsing, email, messaging, music, occasional word processing and graphics work.
• PB15 — Used everyday by a technical/power-user at work, for browsing, email, messaging, development, ...
• PB17 — Used by me everyday at home, for browsing, email, messaging, music, word processing, graphics work, movie editing, development, ...
• G5 — Used everyday by a technical/power-user at home, for similar purposes as PB17.
• G5 Ext — An external drive connected to the G5; holds music, movies, backup, ...

Each computer has a 6+ months old Mac OS X "Panther" installation.

Analysis

We 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:

# hfsdebug -d /dev/rdiskN -s -t 5

N is the appropriate disk (and slice, if necessary) specified. For example, the root volume on a default Mac OS X installation would have /dev/rdisk0s9 as its raw device. Note however, that you do not have to specify a volume explicitly in case of the root volume: hfsdebug -s -t 5 would be sufficient.

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:

# hfsdebug -d /dev/rdiskN -f -t 5

When run with the -f option, hfsdebug lists all forks with more than one extent on the volume. For each fork, the output consists of the following entities (some of which are redundant, as they could be calculated from others; they are included to make post-processing easier):

• The owning file's Catalog node ID
• The fork's type
• A "map" of the fork's layout on disk. For example, for a fork that has 3 extents, containing 10, 20, and 30 blocks, respectively, the map would be :10:20:30:
• The size of the fork in bytes
• The fork's total number of allocation blocks
• The fork's total number of extents
• The fork's average blocks per extent
• The owning file's POSIX path

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.

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 Fragmentation

As 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 Defragmentation

When a file is opened on an HFS+ volume, the following conditions are tested:

• If the file is less than 20 MB in size
• If the file is not already busy
• If the file is not read-only
• If the file has more than eight extents
• If the system has been up for at least three minutes

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 DISABLED, IDLE, BUSY, RECORDING, EVALUATION, EVICTION, and ADOPTION. At most 5000 files, and only files less than 10 MB in size are "adopted" under this scheme.

You can use hfsdebug to explore the working of Hot File Clustering.

Poor Man's Defragmentation

As 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).

hfsdebug can list all fragmented files (forks) on a volume, and can also sort them based on the number of extents each has. Although it would depend on a number of factors (such as a file's size, free space on the volume, and so on), if you simply moved (as a backup) a file with a highly fragmented fork to a new name, and copied it to the original name, the new copy might have lesser, or even no fragmentation, which you may check using hfsdebug. Please understand that I do not recommend that you do this! If you are really bent upon defragmenting your HFS+ volume, a more appropriate way would be to write your own defragmentation tool. The Carbon File Manager has functions that let you allocate contiguous space on a volume.

Conclusion

Defragmentation 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.

All contents of this site, unless otherwise noted, are ©1994-2010 Amit Singh. All Rights Reserved. Terms of Use