From: Ray Heasman <lists@mythral.org>
Date: Sat, 23 Apr 2005 23:00:31 GMT
Subject: Re: Hash collision count
Message-ID: <1114297231.10264.12.camel@maze.mythral.org>
In-Reply-To: <426AAFC3.800@pobox.com>

On Sat, 2005-04-23 at 16:27 -0400, Jeff Garzik wrote:
> Ideally a hash + collision-count pair would make the best key, rather 
> than just hash alone.
> 
> A collision -will- occur eventually, and it is trivial to avoid this 
> problem:
> 
> 	$n = 0
> 	attempt to store as $hash-$n
> 	if $hash-$n exists (unlikely)
> 		$n++
> 		goto restart
> 	key = $hash-$n
> 

Great. So what have you done here? Suppose you have 32 bits of counter
for n. Whoopee, you just added 32 bits to your hash, using a two stage
algorithm. So, you have a 192 bit hash assuming you started with the 160
bit SHA. And, one day your 32 bit counter won't be enough. Then what?

> Tangent-as-the-reason-I-bring-this-up:
> 
> One of my long-term projects is an archive service, somewhat like 
> Plan9's venti:  a multi-server key-value database, with sha1 hash as the 
> key.
> 
> However, as the database grows into the terabyte (possibly petabyte) 
> range, the likelihood of a collision transitions rapidly from unlikely 
> -> possible -> likely.
> 
> Since it is -so- simple to guarantee that you avoid collisions, I'm 
> hoping git will do so before the key structure is too ingrained.

You aren't solving anything. You're just putting it off, and doing it in
a way that breaks all the wonderful semantics possible by just assuming
that the hash is unique. All of a sudden we are doing checks of data
that we never did before, and we have to do the check trillions of times
before the CPU time spent pays off.

If you want to use a bigger hash then use a bigger hash, but don't fool
yourself into thinking that isn't what you are doing.

Ciao,
Ray