couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Damien Katz <dam...@apache.org>
Subject Re: couch_util:new_uuid problem?
Date Sat, 04 Oct 2008 01:33:41 GMT
Given the probability of collision, it's a fair assumption that a  
crypto strength random UUID is unique. But if you are that worried  
about collisions, we do welcome patches. Also, you are encouraged to  
generate your own doc ids client side, using whatever scheme you want.

-Damien

On Oct 3, 2008, at 8:55 PM, Ayende Rahien wrote:

> The problem is that you assume that random is unique.UUID != random.
> A sequential UUID is perfectly fine, as long as you make sure to  
> unique the
> result per machine.
> But random has no non repeating guarantees.
>
> On Sat, Oct 4, 2008 at 3:46 AM, Paul Davis <paul.joseph.davis@gmail.com 
> >wrote:
>
>> The following quote from wikipedia assumes a reliable source of
>> randomness. I'm gonna guess the OpenSSL team is pretty good at what
>> they do. And even if not, it becomes painfully obvious when things  
>> are
>> wrong. (For instance the SSH key brouhaha)
>>
>> Quoting wikipedia:
>>
>> [In] perspective, one's annual risk of being hit by a meteorite is
>> estimated to be one chance in 17 billion [15], that means the
>> probability is about 0.00000000006 (6 x 10-11), equivalent to the  
>> odds
>> of creating a few tens of trillions of UUIDs in a year and having one
>> duplicate.
>>
>> Found at:
>> http://en.wikipedia.org/wiki/Universally_Unique_Identifier#Random_UUID_probability_of_duplicates
>>
>> These numbers are huge. If you have collisions, its because
>> something's broken. If something like this breaks, the internet  
>> breaks
>> and it gets fixed pronto.
>>
>> The only alternative that I could say would be better would be to  
>> read
>> /dev/urandom directly but that would break on machines that don't  
>> have
>> a native source of randomness.
>>
>> HTH,
>> Paul
>>
>> On Fri, Oct 3, 2008 at 8:30 PM, Ayende Rahien <ayende@ayende.com>  
>> wrote:
>>> The problem is with the guarantees that the method does.
>>> This is a valid implementation for random number generator:
>>> http://xkcd.com/221/
>>>
>>> A UUID isn't going to be duplicated, because it is unique to the  
>>> machine
>> and
>>> time it was generated, and there is care taken to ensure that even  
>>> if you
>>> have two thread creating the a guid on the same micro second,  
>>> you'll get
>> two
>>> different guids.
>>> There is no such guarantees for random numbers.
>>>
>>> On Sat, Oct 4, 2008 at 3:06 AM, Paul Davis <paul.joseph.davis@gmail.com
>>> wrote:
>>>
>>>> Ayende,
>>>>
>>>> Perhaps I'm missing something, but I don't see the problem.
>>>>
>>>> I suppose you could technically claim that we're not setting the
>>>> version bits properly but that seems rather not important given  
>>>> that
>>>> we have the revision protection. Also unless I'm mistaken this  
>>>> would
>>>> only be a problem if someone is using an external UUID generation
>>>> scheme that happens to be extremely not random. Which while  
>>>> possible,
>>>> would still send up red flags on constant collisions on document
>>>> creation.
>>>>
>>>> Paul
>>>>
>>>> On Fri, Oct 3, 2008 at 7:49 PM, Ayende Rahien <ayende@ayende.com>
>> wrote:
>>>>> Looking at the method implementation, it looks like there might  
>>>>> be a
>>>> problem
>>>>> here.
>>>>>
>>>>> new_uuid() ->
>>>>>   list_to_binary(to_hex(crypto:rand_bytes(16))).
>>>>>
>>>>> In particular, we aren't actually guaranteed to have a unique  
>>>>> value.
>>>>> You can read more about what needs to be done to get unique guids:
>> here:
>>>>> http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx
>>>>>
>>>>
>>>
>>


Mime
View raw message