Hash collision

[Bill Barry]

Matt Mackall wrote:
> On Wed, 2009-04-29 at 12:29 -0600, Bill Barry wrote:
>   
>> Brian Mearns wrote:
>>     
>>> Thanks for the thorough feedback. I'll set up a script to commit every
>>> second, and once the age of the Universe has reached about 10^31 times
>>> what it is now, I should get my moment in the sun!
>>>   
>>>       
>> I think it'd actually be quite humorous if someone wrote a script that 
>> did something like this:
>>
>> hg pull
>> hg merge
>> hg ci -m "scripted merge"
>> hg push
>> hg id > servername.txt
>> hg ci -m "servername commit"
>>
>>
>> and then ran it as a cronjob every second against some centralized repo 
>> from a hundred machines or so.
>>
>> At one point I thought there was a bug in the local commit numbers code 
>> which would prevent you from having a revision number > 2^32
>>
>> We could bet on how long the repository would keep getting new revisions.
>>
>> all things running smoothly:
>> 2^31 revisions would be hit in 125 days (possible problem point where 
>> signed 32 bit integers roll over)
>>     
>
> 2^31 seconds = 68 years? Compare to Unix time_t.
>   
Yes but I didn't say 2^31 seconds.

I said 2^31 revisions. These would be generated 2 per second per machine 
in a 100 machine network:
http://www.google.com/search?&q=%282^31+%2F+100+%2F+2%29+seconds+in+days

> I can probably avoid dealing with that limit until after the
> singularity. Though we'll probably need another layout change before
> that, so..
>
>   
>> 2^64 = 2.9*10^9 years (unsigned 64 bit integers: read never gonna happen)
>>     
>
> 5.8e11 years (42 times the current age of the universe)
>   
http://www.google.com/search?&q=%282^64+%2F+100+%2F+2%29+seconds+in+years

Regardless though, the point of the exercise would be to use a network 
of machines for the sole purpose of breaking Mercurial. These numbers 
are completely out of range for us humans (how many developers would it 
take to be creating 2000 meaningful revisions a second continuously for 
a whole year, and what would a project like that look like?). 68 years 
is much more likely (but even that is way out of bounds for just about 
everyone, averaging 1 second per commit, come on...).

I'd guess that all but the largest development shops wouldn't be capable 
of more than 100 sustained commits a day. At that rate it would take 
almost 60,000 years to hit 2^31 revisions.

My coworkers and I have on average created 8 new revisions a day since 
we started; that puts us at 700,000 years for the 2 billion mark 
(http://www.google.com/search?hl=en&q=%282^31+%2F+8%29+days+in+years&btnG=Search)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://selenic.com/pipermail/mercurial/attachments/20090429/638aaaae/attachment.htm