HEADS UP - HAMMER work

Matthew Dillon dillon at apollo.backplane.com
Thu Nov 13 07:52:22 PST 2008


:Just curious what the new directory hash will be. Is it "just" a 
:different, improved hash-function with less collisions, or something 
:completely different.
:
:And in general (for my personal understanding of how things work),
:how does hashing work together with the b-tree? There is no hash-table 
:at all, I guess. What you do is to compare a 64-bit hash-key instead of 
:doing a string-comparison of the file name. Is that correct?
:
:Regards,
:
:   Michael

    It's a hash with semi-sorted characteristics.

    I'll post it as soon as I hear back from an expert I emailed it
    to, unless he shoots it down in which case it will never see the
    light of day :-)

    The current HAMMER hash key is just a crc, which means it is essentially
    a random number with no sorting relationship to the filename.  If you
    have a very large directory which does not fit in cache and you are
    stat()ing it in sorted order the current hash will cause inefficient
    seeks on every lookup.  This is still better then UFS (UFS has to scan
    nearly the whole directory to find a filename if it blows out its
    dirhash cache), but not as good as it could be.

    I still have some work to do on it.  There is a lookup-miss case which
    I am not handling properly which I have to fix.

					-Matt
					Matthew Dillon 
					<dillon at backplane.com>





More information about the Kernel mailing list