Re: Hash collision count

From: Ray Heasman <lists@mythral.org>
Date: Apr 23, 2005, 23:00 UTC
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:

Show 13 quoted lines

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

Show 12 quoted lines

> 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