From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: From: David Presotto To: 9fans@cse.psu.edu Subject: Re: [9fans] Qid path generation In-Reply-To: <01c901c3136e$16616dc0$3f00a8c0@MERCURY> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="upas-coaqznasllkgunhzhwgxpmbofo" Date: Mon, 5 May 2003 22:29:25 -0400 Topicbox-Message-UUID: 9ecfe8b6-eacb-11e9-9e20-41e7f4b1d025 This is a multi-part message in MIME format. --upas-coaqznasllkgunhzhwgxpmbofo Content-Disposition: inline Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit 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. --upas-coaqznasllkgunhzhwgxpmbofo Content-Type: message/rfc822 Content-Disposition: inline Received: from plan9.cs.bell-labs.com ([135.104.9.2]) by plan9; Mon May 5 21:21:18 EDT 2003 Received: from mail.cse.psu.edu ([130.203.4.6]) by plan9; Mon May 5 21:21:16 EDT 2003 Received: from psuvax1.cse.psu.edu (psuvax1.cse.psu.edu [130.203.23.6]) by mail.cse.psu.edu (CSE Mail Server) with ESMTP id 13DDE19AD8; Mon, 5 May 2003 21:21:06 -0400 (EDT) Delivered-To: 9fans@cse.psu.edu Received: from mail.monitorbm.co.nz (frontdoor.mbmnz.co.nz [203.167.201.38]) by mail.cse.psu.edu (CSE Mail Server) with SMTP id A185619ADE for <9fans@cse.psu.edu>; Mon, 5 May 2003 21:20:46 -0400 (EDT) Received: (qmail 28451 invoked from network); 6 May 2003 01:20:44 -0000 Received: from mercury.mbmnz.co.nz (HELO MERCURY) (192.168.0.63) by mail.monitorbm.co.nz with SMTP; 6 May 2003 01:20:44 -0000 Message-ID: <01c901c3136e$16616dc0$3f00a8c0@MERCURY> From: "Andrew Simmons" To: <9fans@cse.psu.edu> References: <1b899d420ced031fb566de867397fc17@plan9.bell-labs.com> Subject: Re: [9fans] Qid path generation MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Sender: 9fans-admin@cse.psu.edu Errors-To: 9fans-admin@cse.psu.edu X-BeenThere: 9fans@cse.psu.edu X-Mailman-Version: 2.0.11 Precedence: bulk Reply-To: 9fans@cse.psu.edu List-Id: Fans of the OS Plan 9 from Bell Labs <9fans.cse.psu.edu> List-Archive: Date: Tue, 6 May 2003 13:23:23 +1200 > 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? --upas-coaqznasllkgunhzhwgxpmbofo--