Slashdot Mirror
Measuring Fragmentation in HFS+
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."
As mentioned in the article, HFS+ does defragging on the fly when files are opened if they are less than 20MB. The source code for this is available here, as is a discussion about it that contains input from some Darwin developers.
Ext2/3 and reiserfs both have inbuilt defragmentation capabilities. This can be seen, for instance, when you boot an ext2 system after an unclean shutdown and it checks the integrity of the filesystem. Ext3 and reiserfs are both journaling filesystems, which also helps with this problem. This is often strange for new Linux users, as they're used to worrying about their Windows NTFS/FAT32 filesystems. In Linux, it's just not necessary (nor in any Unix derivative such as AIX or BSD that uses those filesystems).
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.
I write in my journal
i believe the topic at hand is fragmentation, not how well it works as a filesystem. in that regard, FAT32 and NTFS do have horrible problems with fragmentation, while HFS+ defragments on the fly.
Ntfs does not fragment that strongly as long as you dont hit the 90% full mark of your disk, once you reach that, see the files becoming fragmented in no time. NTFS uses the open space for write access and then probably relocates the files in time, once it hits 90% the open space usage algorithm does not seem to work anymore.
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
Fun. Free. Online. RPG. BattleMaster.
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.
Buzzsaw and Dirms -- I admit, the site looks a little seedy, but I've used both of these programs on several machines for upwards of a year and they've done a superb job of keeping my NTFS disks defragmented.
Jaguar (10.2) has journaled support as well, but you had to enable it as it was not a default option.
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.
http://docs.info.apple.com/article.html?artnum=256 68
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:
For proof, check out this. This drive was defragged about a week ago, and although it does go through heavy use, the current low disk space causes massive fragmentation.
The most significant display I've ever seen for the benefits of defragmentation was on a 386 box that had Win 3.11 in 1992. The boot time was cut from two minutes down to 40 seconds and response was very noticeable. I didn't defrag due to any outside encouragement; I happened to find the utility in some drawer on a job site and gave it a try.
... presuming that Win 9x actually performs.
Fragmentation is a performance killer for Win 9x on older machines
m.mmm..myyy
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 has some more info on the subject.
There are a couple things that you have to consider. For one, if part of the disk corrupts, how will you identify a header? Or for that matter, how would you identify the header space vs. file space in a non-corrupted file system?
/usr/local/bin/mybinary
/usr (10) /usr/local (9) /usr/local/bin (72)
/usr/X11R6/include/X11
/usr/local/bin/mybinary, we get 34+10+9+72 = 134 operations.
:-)
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.
Javascript + Nintendo DSi = DSiCade
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.
No, it doesn't take much to outdo NTFS.
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.
There are so many comments already posted to this topic that seem to not grasp the following point, that I think the best way to deal with it is to start a completely new thread. I'm sorry if it seems more than a little obvious to some of you:
:-), such as until you would need to perform disk maintenace anyway for lots of other reasons in any 'reasonable' file system. A typical media file is probably Type 1 in 99%+ of cases.
.txt format, while it is stll being edited by its creator. (type 2). (That same document may behave as effectively Type 1 once it is finished, only to revert to type 2 when a second edition is created from it.)
.doc file, that may become longer for obvious reasons like more text, but may also become longer for less obvious reasons (such as the hidden characters created when you make some text italic or underlined). (These are reasons that are not obvious to most end users, and often not predictable in detail even to people who understand them better). The default configuration for a Windows swap file is type 2a. It is likely to be hard for an automated system to predict the final size of Type 2a files, as that would imply a software system of near human level intelligence to detect patterns that are not obvious and invariant to a normal human mind. It may be possible to predict in some cases only because many users are unlikely to make certain mistakes, (i.e. cutting and pasting an entire second copy of a text file into itself is unusual, while duplicating a single sentence or word isn't).
.bmp, which will only get larger or smaller if the user changes the color depth or size of the image, and not if he just draws something else on the existing one.). A good portion of users (not all by any means) will learn
.zip) is hopefully a 3b, but only until it is run, then the contents may be of any type. A typical Microsoft patch is a 3a (it will somehow always end up longer overall, but you never know just what parts will vary or why).
:-).
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
Who is John Cabal?
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 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
Editor, A1-AAA AmeriCaptions
How many ways are there do define fragmented files? If I can read the file starting from the byte address of the first byte of the file sequentially all the way to the EOF, it isn't fragmented. Otherwise, every time I have to jump to a non-sequential byte address, that's another fragment. Am I missing something?
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.
Coming soon - pyrogyra