Re: HFS problems

[nathan@visi.com (Nathan Mates)]

In article <51061q$o5d@vixen.cso.uiuc.edu>,
wong james d <jd-wong@cs.uiuc.edu> wrote:
>nathan@visi.com (Nathan Mates) writes:
>>   My gut feeling on it is that someone had _way_ too much academic
>>background and required fancy data structures when they designed
>>it. Or, it was designed by committee. In any case, it is NOT a model
>>for simple, understandable, and reliable data structures. Even a
>>sorted linear list of files would have provided 90% of the performance
>>(you have to update the directory on disk _anyways_ when writing;
>>moving a list around in memory to insert a filename is dirt cheap, and
>>writing a few directory blocks is trivial) at a HUGE savings.

>There's nothing particularly complex, incomprehensible, or unreliable
>about B*-Trees as used in HFS; they can provide _significant_
>performance advantages over simple lists for large amounts of
>data (O(n) vs. O(lg n)).  In fact, several modern high-performance
>file systems use B-trees or similar data structures; SGI's XFS
>comes to mind immediately.

   A simple B-Tree can be read quickly, yes. However, you seem to have
missed a few parts of my earlier articles, and never looked at how
non-simple the HFS use of B-Trees are. First off, they're not a simple
btree of all files; they're btrees with crosslinks between various
sections, and they're stored in a similarly whacked b-tree on
disk.

   When it takes on the order of 25 pages to document (I have the
printouts) just the way a data structure is arranged internally and on
disk, then there is a serious problem with data structures too complex
and too insane for the task. 

   For reading, a sorted linear list (which is what I proposed-- did
you notice that?) is only slightly slower than a btree. If you're
using O(n) searches on a sorted list, that's pretty pointless. You can
get O(log n) searches with a _binary_ search on a linear sorted list
fairly trivially. Insertion and deletion are a O(log n) search plus an
O(n) memory copy. If these operations are not done at the rate of several
thousand per second (such as can be done on commercial Unices), the
slightly slower memory speed may be wirth a tradeoff for a much cleaner
design.

  Writing the HFS's B-tree to disk is far more complicated than
writing a linear chunk of memory-- the B-tree is stored in another
b-tree. As memory access speeds are far greater than disk i/o speeds
(especially for large linear read/werites on modern caching HDs),
blowing your directory all over the disk by default is a performance
hit. 

  B-Trees may be nice when in memory, but when you hit the real world
of disk i/o, it's almost better to optimize for the slowest part,
the disk, than memory. Just because another system may have a similar,
but probably much saner design doesn't mean that one system is fine.

>Don't condemn b-trees based on GS/OS's flawed implementation.
>Sophisticated data structures will become more and more important as
>the amount of data machines need to manage grows.  In this regard,
>HFS was ahead of its time.

   You seem to have missed my criticisms of its insane features. It's
not GS/OS's implementation that's my main problem, it's that the design
is crazy from the beginning.

>>   Another thing they did wrong was the 32MB per partition
>>problem. Sure, they get around it by having large blocks, but on a 1GB
>>drive, the smallest file eats 32K of disk space. Ouch. Macs had
>>processors very capable of 32-bit math from the start, and when they
>>got around to making HFS, drives >32MB were either available or very
>>much on the horizon. Using 32-bit block numbers and 0.5K or 1.0K
>>blocks would have been the far better solution for the long run.

>1) You're assuming UNIX-like utilization of the file system (ie, a
>multitude of very small files).  It's not clear that this sort of
>model holds for personal computers in general, let alone Macs.  With
>that in mind, it's not necessarily true that relatively large block
>sizes (2-4K, perhaps) are the show-stopper they are in the UNIX world.

   It doesn't matter if you've got a lot of small files; you've still
got a lot of wasted space if your block size is not an exact multiple
of the average file size. A 33K file will require 2 32K blocks on disk
if that's all that's available. With 4K blocks, you could use 9 of
them for only 3K wasted space; 1K blocks would have no wasted
space.

   Basically, if you assume files are of a random size, the last block
of a file will be, on average, 50% empty. Thus, a quick estimate of
the space wastage is roughly 0.5* block size * number of files. Thus,
a 1GB disk (32K chunks) and 3000 files will likely have 48MB wasted,
or roughly 5% of the drive. That formula is related to only the block
size and number of files; lots of files in general causes wastage, NOT
merely small files.

   Turning a blind eye or saying "buy a larger HD" is not a problem.
[MS-DOG FAT has identical problems; block unutilization is just as
much a problem for my Pentium's 1280MB HD]

Nathan Mates
--
<*> Nathan Mates http://www.visi.com/~nathan/      <*>
# What are the facts? Again and again and again-- what are the _facts_?
# Shun wishful thinking, avoid opinion, care not what the neighbors
# think-- what are the facts, and to how many decimal places?  -R.A. Heinlein