Re: HFS problems

[jd-wong@cs.uiuc.edu (wong james d)]

nathan@visi.com (Nathan Mates) writes:
>   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.

Actually, I did a read-only (admittedly, that's the really easy part)
implementation of HFS a few months ago).  If two frazzled grad
students can figure it out in a couple weeks, it can't be that bad... :-)

(In particular, the on-disk format was pretty straightforward: if I
recall correctly, it's just a breadth-first walk of the tree, with
each node taking up 512 bytes).

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

Of course, doing binary search doesn't have the nice locality properties
that B-trees do -- you've pretty much got to keep the whole directory
in memory..

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

It's not _quite_ true to say that the B-tree is stored in another
B-tree.  Rather, the catalog tree is just another file as far as the
file system is concerned, and its blocks (after the first three
extents) are stored in the extents overflow tree just like any other
file's.

Of course, this can lead to some interesting situations: you might,
for example, try to look up a file "foo" in the catalog tree, but find
that the particular subtree you need isn't in memory.  If the catalog
tree is sufficiently huge (it usually isn't since space is preallocated
when disks are formatted), you'll have to do a lookup in the extents
tree for the missing blocks.  Of course, the extents tree might not
be wholly in memory either, thus requiring additional lookups...

All in all, I'm not sure that the kind of overhead incurred in
this situation is any worse than having to do recursive lookups
on directories and superblocks and all that...

I suppose we'll just have to agree to disagree regarding whether
b-trees are appropriate.  I think HFS is a pretty clever application
of a very neat data structure.

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

But the larger your files are, the less you're affected by this sort
of fragmentation.  I don't want to make any wild claims, but I'd guess
that the average file size on Mac systems is considerably larger
than the typical file on a UNIX system.  Thus, you can get the same
overall utilization with larger allocation blocks if your usage patterns
are right.

That said, HFS is definitely broken in this regard.  I'm just not sure
that you absolutely, postively have to have 0.5K blocks to make
efficient use of large disks...

-- 
Jim Wong (jd-wong@uiuc.edu)