Re: [9fans] Qid path generation

[David Presotto <presotto@closedmind.org>]

[-- Attachment #1: Type: text/plain, Size: 1375 bytes --]

Actually I'm glad you asked since its made me think a
bit more about it.

I wanted something that would
notice a file being created, deleted, and a new one created
with the same name.  Making the qid.version the modification time
might be good enough.  However, in the case of files being
used only for appends, I wanted to distinguish a new version of
the same file from one that just had something appended to
it.  Hence I used the creation time as part of the qid.path.

Of course, that means that there's more likelyhood for the
qid.paths of two files created in the same second to collide.

If you assume we're using a sha1-like hash, the likelyhood of a
collision between 2 randomly chosen files using a 64 bit hash
is about 2^-32; using a 32 bit hash, 2^-16.  That means that we're
making it 65000 times more likely of a collision between two
random files created the same second.

I've now convinced myself that I'ld be better off taking
64 bits of the sha1 hash of the full path appended to the
creation time.  Then the likelyhood of any two files colliding
is still < 2^-32 and I still distinguish two files created
with the same path but at different times.  Then I can also
use the full 64 bit time available in NTFS.

Of course, SHA1 is a lot slower than the hash I currently use
but processors are getting pretty damned fast anyways.

[-- Attachment #2: Type: message/rfc822, Size: 1927 bytes --]

From: "Andrew Simmons" <andrew.simmons@monitorbm.co.nz>
To: <9fans@cse.psu.edu>
Subject: Re: [9fans] Qid path generation
Date: Tue, 6 May 2003 13:23:23 +1200
Message-ID: <01c901c3136e$16616dc0$3f00a8c0@MERCURY>


> By the way, here's my hash function.  I pass it the full path
> name and creation time:
>

Thanks, I'll give that a go. I don't know much about the theory of hash
keys. Does the addition of the creation date to the path significantly
reduce the likelihood of collisions?