Mailing-List: contact couchdb-user-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: couchdb-user@incubator.apache.org
Received-SPF: neutral (athena.apache.org: 209.85.198.248 is neither permitted
 nor denied by domain of ayende@ayende.com)
Message-ID: <27d8d0930810031755k346e7c9ag2365b00c12be1243@mail.gmail.com>
Date: Sat, 4 Oct 2008 03:55:56 +0300
From: "Ayende Rahien" <ayende@ayende.com>
To: couchdb-user@incubator.apache.org
Subject: Re: couch_util:new_uuid problem?
In-Reply-To: <e2111bbb0810031746q62e014bfs55b927143ba090e2@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_12852_3258547.1223081756619"
References: <27d8d0930810031649h3fa3d5deyd16f373527aae472@mail.gmail.com>
	 <e2111bbb0810031706s303f4e5ao15123630d0208783@mail.gmail.com>
	 <27d8d0930810031730w306fcc2fmfc57cd9e100091b2@mail.gmail.com>
	 <e2111bbb0810031746q62e014bfs55b927143ba090e2@mail.gmail.com>

------=_Part_12852_3258547.1223081756619
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_12852_3258547.1223081756619--