Re: Hash collision count

From: Jeff Garzik <jgarzik@pobox.com>
Date: Apr 23, 2005, 23:20 UTC
Message-ID: <426AD835.5070404@pobox.com>
In-Reply-To: <1114297231.10264.12.camel@maze.mythral.org>

Ray Heasman wrote:

Show 21 quoted lines

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

First, there is no 32-bit limit. git stores keys (aka hashes) as strings. As it should.

Second, in your scenario, it's highly unlikely you would get 4 billion sha1 hash collisions, even if you had the disk space to store such a git database.

Show 19 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.

First, the hash is NOT unique.

Second, you lose data if you pretend it is unique. I don't like losing data.

Third, a data check only occurs in the highly unlikely case that a hash already exists -- a collision. Rather than "trillions of times", more like "one in a trillion chance."

	Jeff