Measuring Fragmentation in HFS+ 417
keyblob8K writes "Amit Singh takes a look at fragmentation in HFS+. The author provides numbers from his experiments on several HFS+ disks, and more interestingly he also provides the program he developed for this purpose. From his own limited testing, Apple's filesystem seems pretty solid in the fragmentation avoidance department. I gave hfsdebug a whirl on my 8-month-old iMac and the disk seems to be in good shape. I don't have much idea about ext2/3 or reiser, but I know that my NTFS disks are way more fragmented than this after similar amount of use."
HFS+ defrag source (Score:5, Informative)
Re:Anonymous (Score:3, Informative)
Measuring fragmentation in NTFS (Score:2, Informative)
This was my PhD Thesis.
My stats (Score:5, Informative)
I've got a G4 with an 80 GB root drive which I use all day, every day. Well, almost. It's never had anything done to it, filesystem-maintenance-wise, since I last did an OS upgrade last fall, about eight months ago.Not too shabby, methinks.
Re:Give it a rest (Score:4, Informative)
Re:NTFS is not so bad (Score:3, Informative)
Re:NTFS is not so bad (Score:5, Informative)
Re:HFS+ defrag source (Score:5, Informative)
Good luck
Re:HFS+ defrag source (Score:5, Informative)
Bzzt! Nope. Close, though! (Score:4, Informative)
That's not quite correct. In Panther (Mac OS X 10.3, for the uninitiated), journaling is enabled by default: that is, when you first install Panther, it will add journaling to your existing HFS+ disk, and if you're reformatting, it will default to HFS+ (Journaled). However, prior to Panther, there was no journaling support in HFS+, to my knowledge.
Dan Aris
Re:NTFS is not so bad (Score:1, Informative)
Re:HFS Filesystem vs. ReiserFS (apple bug) (Score:1, Informative)
Re:HFS Filesystem vs. ReiserFS (Score:2, Informative)
Re:Huh? (Score:5, Informative)
My own experience, using a small tool I wrote to analyze NTFS fragmentation:
NTFS is pretty good at avoiding fragmentation when creating new files if the size of the file is set before it is written. In other words, if the file is created, the EOF set, and then the file data is written, NTFS does a good job of finding a set of contiguous clusters for the file data.
NTFS does a poor job of avoiding fragmentation for files written sequentially. Consider a file retrieved with wget. An empty file is created, then the contents are written sequentially as it is read from the net. Odds are, the file data will be scattered all over the disk.
Here's a concrete example. Today, I downloaded Andrew Morton's 2.6.6-mm4.tar.bz2 patch set. (Yes, I run WinXP on my Toshiba laptop -- deal with it.) Anyway, the file is less than 2.5MB, but it is allocated in 19 separate fragments. I copied it to another file, and that file is unfragmented. Since the copy command sets EOF before writing the data, NTFS can try ot allocate a contiguous run of clusters.
Note - This was done on uncompressed NTFS. My feeling is that compressed NTFS is even worse about fragmentation, but I don't have any numbers to back that up.
On-the-fly defragmentation for NTFS disks in WinNT (Score:3, Informative)
Re:Bzzt! Nope. Close, though! (Score:5, Informative)
Even in 10.3 it's optional, not required, but it's the new default for new disks. Probably because Apple decided that their code was solid enough to put into production. After testing it on 10.2 I agree with them.
Re:Big frag issues under EXT2 too (Score:5, Informative)
Apple updated their stand recently (Score:5, Informative)
Mac OS X: About Disk Optimization
Do I need to optimize?
You probably won't need to optimize at all if you use Mac OS X. Here's why:
Re:NTFS is not so bad (Score:5, Informative)
Re:Anonymous (Score:3, Informative)
Fragmentation is a performance killer for Win 9x on older machines
Re:Anonymous (Score:4, Informative)
What are you talking about?
No, they don't. But since they borrow their design from BSD's FFS they don't need it either.
Erm, that's fsck. fsck doesn't do defragmentation.
It's true, however performance is severely degraded when disk usage reaches around 90% for classic FFS-like filesystems. While the BSDs can mount ext2 partitions none of them uses ext[23] as default. AIX uses a JFS version that's a bit different from the one you see in Linux, which was based on OS/2's code. I think you're mixing up filesystem integrity with fragmentation. In classic BSD UFS/FFS data is stored in datablocks, which are partitioned in fragments, usually 1/4th of the datablock size. A fragmented file is a file that's stored in non-contiguous fragments. Just that. The performance impact of fragmented files vs the time needed to reorganize the data shows that it's not worth running a defrag program on FFS filesystems.
This paper [harvard.edu] has some more info on the subject.
Re:HFS+ defrag source (Score:4, Informative)
So therefore it might be a part of the operating system's filesystem. That's the system that deals with files. But that's not what was asked. What was asked was whether it was an inherent feature of HFS+, and that's not possible, since HFS+ doesn't tell the OS what to do when a file is opened, only how the stuff is stored on the disk.
Perhaps you didn't understand the dual nature of the word filesystem: it can be the subsystem of the OS that handles files, or it can be the physical representation of the data on to the hard drive. If you assume it's only the first, your explanation makes sense. If you assume the second one (which would be the usage intended and understood by most people given the fact that the question and response were about HFS+ (physical filesystem) compared to Panther (OS filesystem)), then you'd be wrong.
And I've been trolled, but who cares.
Re:File allocation Table (Score:5, Informative)
You're probably thinking "just store the size of the file", This is perfectly valid, but it does have certain implications. You see, in Comp-Sci, we refer to a list like this as a "linked list". The concept basically being that each item in the list has information (i.e. a "link") that helps identify the next item in the list. Such a data structure has a worst case access time of O(n). Or in other words, if your item is at the end of the list,and you have you have 2000 files, you'll have to check through all two thousand headers before finding your file.
Popular file systems circumvent this by using what's called a Tree structure. A tree is similar to a linked list, but allows for multiple links that point to children of the node. A node that has no children is referred to as a "leaf node". In a file system the directories and files are nodes of a tree, with files being leaf nodes. This configuration gives us two performance characteristics that we must calculate for:
1. The maximum number of children in a node.
2. The maximum depth of the tree.
Let's call them "c" for children and "d" for depth. Our performance formula is now O(c*d) and is irrespective of the number of items in the data structure. Let's make up and example to run this calculation against:
Path:
Nodes:
/ (34)
Longest path:
Plugging the above numbers (72 for c, 4 for d) we get a worst case of 72*4 = 288 operations. Thus our worst case is much better than the linked list. And if we calculate the real case to access
Hope this helps.
Re:Panther Defrag (Score:3, Informative)
Re:HFS+ defrag source (Score:5, Informative)
I believe the actual sequence is this:
In other words, it defrangments after the file has been returned to the program needing it, as a background process. The buffer to memory is a pre-existing optimization, so the only real trade off is the background processor usage goes up. If you aren't doing major work at the time, you'll never notice. (And if you are doing major work, you probably are using files larger than 20MB in size anyway.)
Files larger than 20MB just aren't defragmented, unless you have another tool to do it.
Re:HFS+ defrag source (Score:2, Informative)
The real advantage is that it will speed up things immediately for the 2nd time the file is read. Though you can still defrag your disk overnight if you like that.
Re:How to determine fragmentation... (Score:5, Informative)
NTFS is horrible. on a system installed less than a week ago, and a few programs (nwn, firefox, avg, itunes, aa, nvdvd, windows updates, and a couple more programs, it has 9.3GB used, and it is reported that it has "Total Fragmentation: 22%, File Fragmentation: 45%"
So yes there are various methods of calculating file fragmentation. (2 I can think of: (# of files with fragments)/(total number of files) = 0 for a totally defragemented hd (& gives nice percentages) & (# of file fragments)/(total number of files) = 1 for a perfectly defragmented hd. or variations on those, and I haven't been able to find what calculations Windows, & e2fstools use, so I can't tell.
Re:Anonymous (Score:2, Informative)
Re:NTFS is not so bad (Score:4, Informative)
NTFS fragments _very_ fast on me, after a few months of use, it is in the 20% or more range.
Same user (i.e. me), so same usage pattern, on my HPFS disks (yes, HPFS, that would be OS/2, not OS X), the fragmentation after 3 _years_ is less than 2% on ALL of my HPFS disks.
Re:HFS+ defrag source (Score:3, Informative)
Journalling didn't show up until one of the Jaguar updates, where it could be enabled via the command line on clients and via disk utility on Server.
HPFS fragments could be good (Score:3, Informative)
Defrag utils for OS/2 had options to only defrag if there were more than 3 extents, to avoid nullifying this effect.
funny, years after the death of OS/2, it still kicks ass on much what we use now.
Re:HFS+ defrag source (Score:4, Informative)
If you ever wondered why there is a "soft limit" on FFS filesystems, the reason why is that its allocator's effectiveness breaks down at about the point where the filesystem is 90% full. So they sacrifice 10% of the filesystem space so that they can avoid fragmentation problems. It's not a bad tradeoff, particularly these days.
I didn't know that HFS+ used an after-the-fact defragmentation system, but they've been around for awhile too. Significant research was done into such things as part of log-based filesystem research in the early 1990s (reference BSF LFS and Sprite). You had to have a "cleaner" process with those filesystems anyway (to pick up abandoned fragments of the log and return them to the free pool) so it made sense to have it also perform some optimization features.
Re:Defrag = placebo? (Score:3, Informative)
If you need to save a 100kb file, it will take 10ms (1/100th of a second) to seek to the first block, and then, assuming everything is perfect, it will take 100MB/sec / 100kb = 1/1000th of a second to write the file... so, seeking to the start of the file took 10 times as long as writing it!
This gross simplification actually trivializes the real effect. The 10ms seek figure is an average track-to-track seek delay between adjacent tracks. The farther apart the tracks are the longer a seek takes (it's more or less linear although there is a per-seek overhead). You also don't deal with the fact that you're going to have to perform seeks on larger files no matter what.
I note that there is a similar latency issue with head switches.
There is a big difference between the delay necessary to pull a sector off of a track adjacent to where the heads currently are and one 1000 tracks away -- the delay can be an appreciable fraction of a second just for that single seek.
The problem with simplistic filesystem block allocators is they do not weight their block allocations according to seek time. Usually they just pick whatever's first in the free list. This results, over time, to random block placement and therefore seek times that will on average approach 50% of worst case. I'd have to look closely to give a good figure with today's drives, but order-of-magnitude degredation is certainly possible. What you would prefer is blocks placed such that they're within a few percent of best case if at all possible.
This is not hard to do, and to my knowledge BSD FFS was the first to attempt it -- and it was wildly successful at it.
As an aside, I've never seen a fragmentation analysis program that took noncontiguous-but-well-placed into account. It's entirely possible to create a block layout that those programs think is awful that is within 90% of optimum. I think, actually, that BSD FFS would typically show up that way although I never investigated.
I also note that smart block allocation makes a defragmenter's job a heck of a lot easier.
Re:HFS+ defrag source (Score:5, Informative)
And the person who came up with this idea was a genius. This is far far better than what most other operating systems do (refuse to mount the volume.)
If I boot MS-DOS on a machine that has FAT-32 or NTFS volumes, I simply don't find any volume. I can't tell the difference between an unsupported file system and an unformatted partition. If the file system would create a FAT-compatible read-only stub (like HFS+ does), it would be much better for the user. Instead of thinking you have a corrupt drive, you'd know that there is a file system that your OS can't read.
Re:Defrag = placebo? (Score:3, Informative)
Head seek and rotational latency is still much slower than contiguous blocks. True, modern systems deal with it better, partially due to b-tree and other file indexing strategies and partially due to having plenty of RAM for metadata caching and predictive caching. But fragmentation is still a major issue for me on multiuser Windows PCs and periodic disk cleanup and defragmentation is necessary for reasonable operation speed.
<MS gripe>
In particular, the hidden "Content.IE5" cache of IE on 20-100 user PCs fills up hard drives in a big hurry, and I haven't found a way of controlling this except for periodically deleting with the following batch file I made for Win2k. (Limiting the cache size doesn't seem to affect these files.)This needs to be done preventatively, though. In addition to fragmenting data, 20-100 user PCs with large numbes of files (and Content.IE5 is my killer in my situation) fill up the MFT and then fragment it, and once you get the MFT fragmented you're basically screwed.
</MS gripe>
Admittedly the biggest problem PCs have disks less than 12G and I don't have as much of a problem with 20G+ systems. But have you ever run defrag after a clean install, even with an enormous hard drive? You'd think it could at least install itself without severe fragmentation. Oh well.
Re:Huh? (Score:2, Informative)
When you download a file with internet explorer, it downloads to a temporary directory, and then copies it to the location you selected in the "Save" dialog (using Windows copy facilities). According to your logic, the file that you downloaded should not be fragmented, at all.
Care to explain yourself?
Re:fragmentation and dimension (Score:3, Informative)
File types and fragnentation (Score:5, Informative)
There are fundamentally only a few types of files when it comes to fragmentation.
1. There are files that simply never change size, and once written don't get overwritten. (Type 1). Most programs are actually type 1, if you use sufficiently small values of never
2. There are files that will often shorten or lengthen in use, for example a word processor document in
Of type 2, there are files of type 2a. Files that may get either longer or shorter with use, on a (relatively) random basis. (as a relatively simple case, a
Then there are files of type 2b. Files that get longer or shorter only for predictable reasons, (such as a Windows
what to expect for these files, which suggests a well-written defragger could theoretically also auto-predict the consequences of the changes a user is making).
3. Then there are type 3 files, which only get longer. These too have predictable and unpredictable subtypes. Most log files for example, are set up to keep getting longer on a predictable basis when their associated program is run (type 3b). Anything that has been compressed (i.e.
4. Type 4 would be files that always get smaller, but there are no known examples of this type
These types are basic in any system, as they are implied by fundamental physical constraints. However, many defrag programs use other types instead of starting from this model, often with poor results.
In analyizing what happens with various defrag methods, such as reserving space for predicted expansion or defragging in the background/on the fly methods, the reader should try these various types (at least 1 through 3), and see what will happen when that method is used on each type. Then consider how many of those type files will be involved in the overall process, and how often.
For example, Some versions of Microsoft Windows (tm) FAT32 defragger move files that have been accessed more than a certain number of times (typically f
Re:Defragging XP now... (Score:4, Informative)
With the latest versions of ntfsresize, fairly safe. I did it on a machine at work with very important data on it (yes, I backed it up first), and had no trouble at all. However, all ntfsresize can do is truncate an NTFS partition's free space. In other words, it won't relocate blocks to other free areas of the disk. So the most you can shrink it is by however much free space you have at the end of the partition. ((After Googling around a bit, I've learned that the most recent versions of ntfsresize [rulez.org] will now move datablocks around, so apparently that restriction is now gone. I have not personally tested this, however.))
Incidentally, ntfsresize is part of Knoppix, and gets run through QTPartEd, a partition editing tool. It is an older, non-relocating version, however.
Schwab
Re:Not Exciting (Score:2, Informative)
actually, Darwin/OS X has a really nifty feature called BootCache that collects information at boot time and primes the read-ahead on subsequent boots to smooth things out... everyone found out the hard way when it was mildly broken in an update to 10.2 exactly how much difference it makes (it knocks about 2/3 off the boot time of my PowerBook).
see Amit Singh's excellent article [kernelthread.com] for more info, there's a chunk on BootCache at the bottom of this page [kernelthread.com].
Re:Bzzt! Nope. Close, though! (Score:2, Informative)
Re:How to determine fragmentation... (Score:4, Informative)
As an example, look up the docs on ext2. Note that file fragments are not necessarily the same as fragmented files. Also note that people use the "file fragment" number as an indicator of how fragmented their ext2 partition is - which is wrong.
Re:HPFS fragments could be good (Score:3, Informative)
Vendors used to do interleaving with the format/fdisk commands I recall. The idea was that writing the sectors in a continuous stream was not very efficient as the drives of the time could not move data to or from the disk so quickly. You'd read sector 1, and by the time you were ready to read sector two, sector 3 was under the head, so you had to wait almost an entire disk revolution to find sector 2 again.
The interleave told the OS to skip X physical disk sectors for each 1 logical sector.
For example, assume a disk with 12 sectors on a track such that when stationary the disk's sectors align with the hours on a clock face. With interleave of 3 the OS would put sector 1 at 1:00, sector 2 at 4:00, sector 3 at 7:00, sector 4 at 10:00, sector 5 at 2:00, and so on. The OS would occasionally skip more than the "interleave" number of sectors in order to not overwrite previous sectors. This meant that by the time that logical sector 1 was read and transferred to the computer, logical sector 2 would just about be under the heads for reading, thus eliminating or at least minimizing the rotational latency.
Another big advantage was placing the directory structures in the middle tracks of the drive. This minimized the longest seek that would have to be performed. Unless a single file was very large or in just the wrong spot, it would usually be positioned completely on the inside or outside half of the tracks. After reading, the head only had to move at most half way across the disk to locate the next file or cluster/fragment to read or write; the again at most 1/2 the disk to perform the next operation.
Most of today's file systems start placing directory/catalog information at the start of the disk, this effectively doubling average seek times to the data stored on the disk.
As others mentioned, on some "faster" drives, there were filesystems that essentially treated the platters in a drive as individual units and managed then like a RAID 0, a RAIP so to speak (Redundant Array of Independent Platters).
File fragmentation in today's fast, large buffer drives is, I think, the least of our worries. Fragmented or not we need more optimization of data structures on the drive. I'd rather have related files fragmented and near-by each other than contiguous and spread evenly across the drive.
Re:Bring on the browser stats! (Score:2, Informative)
What's not too obvious is that a lot of Windows administration tools are instances of one executable (though I imagine it executing different things), so they all get lumped under one entry on my taskbar too.
Re:Offtopic (Score:3, Informative)
You are forgetting two embassies in Africa and an American Warship. All of those are American soil. So it is not an attack every eight years.
Fast! (Score:3, Informative)
It might be the way they've 'frobbed' UFS for use with OS Server, but UFS really gives high priority to disk ops with GUI ops taking the back seat, and yet HFS+ is in comparison blazingly fast.
I believe in a good clean machine like anyone, and I do see the probability DiskWarrior will be needed now and again, but the speed alone is quite a pedigree for HFS+ IMHO.