Re: Hash collision count

[David Lang <david.lang@digitalinsight.com>]

On Sat, 23 Apr 2005, 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
>
> 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.

Jeff, this can't work becouse you don't know what objects exist on other 
servers, in fact given the number of different repositories that will 
eventually exist the odds are good that when the colision occures it will 
be when object repositories get combined,

David Lang
-- 
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
  -- C.A.R. Hoare