Thread: Re: [PATCHES] Patch for UUID datatype (beta)

Andreas Pflug <pgadmin@pse-consulting.de> writes:
> Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
> there's a commonly accepted algorithm providing this.

Anyone who thinks UUIDs are guaranteed unique has been drinking too much
of the kool-aid.  They're at best probably unique.  Some generator
algorithms might make it more probable than others, but you simply
cannot "guarantee" it for UUIDs generated on noncommunicating machines.

One of the big reasons that I'm hesitant to put a UUID generation
function into core is the knowledge that none of them are or can be
perfect ... so people might need different ones depending on local
conditions.  I'm inclined to think that a reasonable setup would put
the datatype (with input, output, comparison and indexing support)
into core, but provide a generation function as a contrib module,
making it easily replaceable.

            regards, tom lane

Completely agreed. I can remove the function from the patch. The
temptation was just too high not to include the new_guid() in the
patch :)


On Mon, 2006-09-18 at 10:33 -0400, Tom Lane wrote:
> Andreas Pflug <pgadmin@pse-consulting.de> writes:
> > Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
> > there's a commonly accepted algorithm providing this.
>
> Anyone who thinks UUIDs are guaranteed unique has been drinking too much
> of the kool-aid.  They're at best probably unique.  Some generator
> algorithms might make it more probable than others, but you simply
> cannot "guarantee" it for UUIDs generated on noncommunicating machines.
>
> One of the big reasons that I'm hesitant to put a UUID generation
> function into core is the knowledge that none of them are or can be
> perfect ... so people might need different ones depending on local
> conditions.  I'm inclined to think that a reasonable setup would put
> the datatype (with input, output, comparison and indexing support)
> into core, but provide a generation function as a contrib module,
> making it easily replaceable.
>
>             regards, tom lane
>

On Mon, Sep 18, 2006 at 05:29:34PM +0200, Harald Armin Massa wrote:
> I would really like PostgreSQL to include an uuid-generation function
> crafted along the recommendations in rfc4122 or ISO/IEC 9834-8; so those
> UUIDs have a "ISO/IEC-defined uniqueness" or at least a "ISO/IEC-defined
> extreme likelyness to be unique"

The code to get things like the MAC address is going to be a pile of
very OS specific code, which I really don't think is in the realm of
code postgresql wants to maintain. The easier and better solution is to
include a module in contrib (at best) that calls some standard
cross-platform library to do the job.

Have a nice day,
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

"Harald Armin Massa" <haraldarminmassa@gmail.com> writes:
> They also talk about a "guaranteed differentness" - and as much as I
> understand, they are Unique as long as the MAC-Adresses of the Network-Cards
> are unique, and fall back to "extremly likely" when there is no network card
> present.

MAC addresses are not guaranteed unique (heck, on Apple machines they're
user-assignable, and I think you can change 'em on Linux too).  Another
unrelated-to-reality assumption in the above claim is that the local
system clock is always accurate (is never, say, set backwards).

You can have a reasonably strong probability that UUIDs generated per spec
within a single well-run network are unique, but that's about as far as
I'd care to believe it.
        regards, tom lane

On Mon, Sep 18, 2006 at 10:33:22AM -0400, Tom Lane wrote:
> Andreas Pflug <pgadmin@pse-consulting.de> writes:
> > Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
> > there's a commonly accepted algorithm providing this.
> Anyone who thinks UUIDs are guaranteed unique has been drinking too much
> of the kool-aid.  They're at best probably unique.  Some generator
> algorithms might make it more probable than others, but you simply
> cannot "guarantee" it for UUIDs generated on noncommunicating machines.

The versions that include a MAC address, time, and serial number for
the machine come pretty close, presuming that the user has not
overwritten the MAC address with something else. It's unique at
manufacturing time. If the generation is performed from a library
with the same state, on the same machine, on the off chance that you
do request multiple generations at the same exact time (from my
experience, this is already unlikely) the serial number should be
bumped for that time.

So yeah - if you set your MAC address, or if your machine time is ever
set back, or if you assume a serial number of 0 each time (generation
routine isn't shared among processes on the system), you can get overlap.
All of these can be controlled, making it possible to eliminate overlap.

> One of the big reasons that I'm hesitant to put a UUID generation
> function into core is the knowledge that none of them are or can be
> perfect ... so people might need different ones depending on local
> conditions.  I'm inclined to think that a reasonable setup would put
> the datatype (with input, output, comparison and indexing support)
> into core, but provide a generation function as a contrib module,
> making it easily replaceable.

I have UUID generation in core in my current implementation. In the
last year that I've been using it, I have already chosen twice to
generate UUIDs from my calling program. I find it faster, as it avoids
have to call out to PostgreSQL twice. Once to generate the UUID, and
once to insert the row using it. I have no strong need for UUID
generation to be in core, and believe there does exist strong reasons
not to. Performance is better when not in core. Portability of
PostgreSQL is better when not in core. Ability to control how UUID is
defined is better when not in control.

The only thing an in-core version provides is convenience for those
that do not have easy access to a UUID generation library. I don't
care for that convenience.

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   |
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

If you're going to yank it, please at least include a generator in
contrib.

Personally, I'd like to see at least some kind of generator in core,
with appropriate info/disclaimers in the docs. A simple random-number
generator is probably the best way to go in that regard. I think that
most people know that UUID generation isn't 100.00000% perfect.

BTW, at a former company we used SHA1s to identify files that had been
uploaded. We were wondering on the odds of 2 different files hashing to
the same value and found some statistical comparisons of probabilities.
I don't recall the details, but the odds of duplicating a SHA1 (1 in
2^160) are so insanely small that it's hard to find anything in the
physical world that compares. To duplicate random 256^256 numbers you'd
probably have to search until the heat-death of the universe.

On Mon, Sep 18, 2006 at 05:14:22PM +0200, Gevik Babakhani wrote:
> Completely agreed. I can remove the function from the patch. The
> temptation was just too high not to include the new_guid() in the
> patch :)
>
>
> On Mon, 2006-09-18 at 10:33 -0400, Tom Lane wrote:
> > Andreas Pflug <pgadmin@pse-consulting.de> writes:
> > > Isn't guaranteed uniqueness the very attribute that's expected? AFAIK
> > > there's a commonly accepted algorithm providing this.
> >
> > Anyone who thinks UUIDs are guaranteed unique has been drinking too much
> > of the kool-aid.  They're at best probably unique.  Some generator
> > algorithms might make it more probable than others, but you simply
> > cannot "guarantee" it for UUIDs generated on noncommunicating machines.
> >
> > One of the big reasons that I'm hesitant to put a UUID generation
> > function into core is the knowledge that none of them are or can be
> > perfect ... so people might need different ones depending on local
> > conditions.  I'm inclined to think that a reasonable setup would put
> > the datatype (with input, output, comparison and indexing support)
> > into core, but provide a generation function as a contrib module,
> > making it easily replaceable.
> >
> >             regards, tom lane
> >
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings
>

--
Jim Nasby                                    jimn@enterprisedb.com
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

On Mon, Sep 18, 2006 at 04:00:22PM -0500, Jim C. Nasby wrote:
> BTW, at a former company we used SHA1s to identify files that had been
> uploaded. We were wondering on the odds of 2 different files hashing to
> the same value and found some statistical comparisons of probabilities.
> I don't recall the details, but the odds of duplicating a SHA1 (1 in
> 2^160) are so insanely small that it's hard to find anything in the
> physical world that compares. To duplicate random 256^256 numbers you'd
> probably have to search until the heat-death of the universe.

The birthday paradox gives you about 2^80 (about 10^24) files before a
SHA1 match, which is huge enough as it is. AIUI a UUID is only 2^128
bits so that would make 2^64 (about 10^19) random strings before you
get a duplicate. Embed the time in there and the chance becomes
*really* small, because then you have to get it in the same second.

Have a nice day,
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

On Mon, Sep 18, 2006 at 12:23:16PM -0400, mark@mark.mielke.cc wrote:
> I have UUID generation in core in my current implementation. In the
> last year that I've been using it, I have already chosen twice to
> generate UUIDs from my calling program. I find it faster, as it avoids
> have to call out to PostgreSQL twice. Once to generate the UUID, and
> once to insert the row using it. I have no strong need for UUID
> generation to be in core, and believe there does exist strong reasons
> not to. Performance is better when not in core. Portability of
> PostgreSQL is better when not in core. Ability to control how UUID is
> defined is better when not in control.

That's kinda short-sighted. You're assuming that the only place you'll
want to generate UUIDs is outside the database. What about a stored
procedure that's adding data to the database? How about populating a
table via a SELECT INTO? There's any number of cases where you'd want to
generate a UUID inside the database.

> The only thing an in-core version provides is convenience for those
> that do not have easy access to a UUID generation library. I don't
> care for that convenience.

It's not about access to a library, it's about how do you get to that
library from inside the database, which may not be very easy.

You may not care for that convenience, but I certainly would.
--
Jim Nasby                                    jimn@enterprisedb.com
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

On Mon, 2006-09-18 at 16:00 -0500, Jim C. Nasby wrote:
> BTW, at a former company we used SHA1s to identify files that had been
> uploaded. We were wondering on the odds of 2 different files hashing to
> the same value and found some statistical comparisons of probabilities.
> I don't recall the details, but the odds of duplicating a SHA1 (1 in
> 2^160) are so insanely small that it's hard to find anything in the
> physical world that compares. To duplicate random 256^256 numbers you'd
> probably have to search until the heat-death of the universe.

That assumes you have good random data. Usually there is some kind of
tradeoff between the randomness and the performance. If you
read /dev/random each time, that eliminates some applications that need
to generate UUIDs very quickly. If you use pseudorandom data, you are
vulnerable in the case a clock is set back or the data repeats.

Regards,
    Jeff Davis

On Mon, Sep 18, 2006 at 04:17:50PM -0500, Jim C. Nasby wrote:
> On Mon, Sep 18, 2006 at 12:23:16PM -0400, mark@mark.mielke.cc wrote:
> > I have UUID generation in core in my current implementation. In the
> > last year that I've been using it, I have already chosen twice to
> > generate UUIDs from my calling program. I find it faster, as it avoids
> > have to call out to PostgreSQL twice. Once to generate the UUID, and
> > once to insert the row using it. I have no strong need for UUID
> > generation to be in core, and believe there does exist strong reasons
> > not to. Performance is better when not in core. Portability of
> > PostgreSQL is better when not in core. Ability to control how UUID is
> > defined is better when not in control.
> That's kinda short-sighted. You're assuming that the only place you'll
> want to generate UUIDs is outside the database. What about a stored
> procedure that's adding data to the database? How about populating a
> table via a SELECT INTO? There's any number of cases where you'd want to
> generate a UUID inside the database.

contrib module.

> > The only thing an in-core version provides is convenience for those
> > that do not have easy access to a UUID generation library. I don't
> > care for that convenience.
> It's not about access to a library, it's about how do you get to that
> library from inside the database, which may not be very easy.
> You may not care for that convenience, but I certainly would.

Then load the contrib module. I do both. I'd happily reduce my contrib
module to be based upon a built-in UUID type within PostgreSQL, providing
the necessary UUID generation routines.

I would not use a 100% random number generator for a UUID value as was
suggested. I prefer inserting the MAC address and the time, to at
least allow me to control if a collision is possible. This is not easy
to do using a few lines of C code. I'd rather have a UUID type in core
with no generation routine, than no UUID type in core because the code
is too complicated to maintain, or not portable enough.

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   |
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
> I would not use a 100% random number generator for a UUID value as was
> suggested. I prefer inserting the MAC address and the time, to at
> least allow me to control if a collision is possible. This is not easy
> to do using a few lines of C code. I'd rather have a UUID type in core
> with no generation routine, than no UUID type in core because the code
> is too complicated to maintain, or not portable enough.

As others have mentioned, using MAC address doesn't remove the
possibility of a collision.

Maybe a good compromise that would allow a generator function to go into
the backend would be to combine the current time with a random number.
That will ensure that you won't get a dupe, so long as your clock never
runs backwards.
--
Jim Nasby                                    jimn@enterprisedb.com
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

> As others have mentioned, using MAC address doesn't remove the
> possibility of a collision.
> 
> Maybe a good compromise that would allow a generator function to go into
> the backend would be to combine the current time with a random number.
> That will ensure that you won't get a dupe, so long as your clock never
> runs backwards.

I think that is a reasonable solution. I just wonder if there is a cross
platform way to get the MAC address for all OS we support.

On Tue, Sep 19, 2006 at 08:20:13AM -0500, Jim C. Nasby wrote:
> On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
> > I would not use a 100% random number generator for a UUID value as was
> > suggested. I prefer inserting the MAC address and the time, to at
> > least allow me to control if a collision is possible. This is not easy
> > to do using a few lines of C code. I'd rather have a UUID type in core
> > with no generation routine, than no UUID type in core because the code
> > is too complicated to maintain, or not portable enough.
> As others have mentioned, using MAC address doesn't remove the
> possibility of a collision.

It does, as I control the MAC address. I can choose not to overwrite it.
I can choose to ensure that any cases where it is overwritten, it is
overwritten with a unique value. Random number does not provide this
level of control.

> Maybe a good compromise that would allow a generator function to go into
> the backend would be to combine the current time with a random number.
> That will ensure that you won't get a dupe, so long as your clock never
> runs backwards.

Which standard UUID generation function would you be thinking of?
Inventing a new one doesn't seem sensible. I'll have to read over the
versions again...

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   |
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

On Tue, Sep 19, 2006 at 03:35:55PM +0200, Gevik Babakhani wrote:
> > As others have mentioned, using MAC address doesn't remove the
> > possibility of a collision.
> > 
> > Maybe a good compromise that would allow a generator function to go into
> > the backend would be to combine the current time with a random number.
> > That will ensure that you won't get a dupe, so long as your clock never
> > runs backwards.
> 
> I think that is a reasonable solution. I just wonder if there is a cross
> platform way to get the MAC address for all OS we support.

Well... how much OS-specific code do you want? :)

Another (not as good) possibility would be to use the IP address (along
with time and a random number).
-- 
Jim Nasby                                    jimn@enterprisedb.com
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

[-patches trimmed from list]

mark@mark.mielke.cc wrote:
>> As others have mentioned, using MAC address doesn't remove the
>> possibility of a collision.
>>     
>
> It does, as I control the MAC address. I can choose not to overwrite it.
> I can choose to ensure that any cases where it is overwritten, it is
> overwritten with a unique value.
>   

How do you know somebody else isn't using that MAC value?

cheers

andrew

On Tue, Sep 19, 2006 at 09:51:23AM -0400, mark@mark.mielke.cc wrote:
> On Tue, Sep 19, 2006 at 08:20:13AM -0500, Jim C. Nasby wrote:
> > On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
> > > I would not use a 100% random number generator for a UUID value as was
> > > suggested. I prefer inserting the MAC address and the time, to at
> > > least allow me to control if a collision is possible. This is not easy
> > > to do using a few lines of C code. I'd rather have a UUID type in core
> > > with no generation routine, than no UUID type in core because the code
> > > is too complicated to maintain, or not portable enough.
> > As others have mentioned, using MAC address doesn't remove the
> > possibility of a collision.
>
> It does, as I control the MAC address. I can choose not to overwrite it.
> I can choose to ensure that any cases where it is overwritten, it is
> overwritten with a unique value. Random number does not provide this
> level of control.
>
> > Maybe a good compromise that would allow a generator function to go into
> > the backend would be to combine the current time with a random number.
> > That will ensure that you won't get a dupe, so long as your clock never
> > runs backwards.
>
> Which standard UUID generation function would you be thinking of?
> Inventing a new one doesn't seem sensible. I'll have to read over the
> versions again...

I don't think it exists, but I don't see how that's an issue. Let's look
at an extreme case: take the amount of random entropy used for the
random-only generation method. Append that to the current time in UTC,
and hash it. Thanks to the time component, you've now greatly reduced
the odds of a duplicate, probably by many orders of magnitude.

Ultimately, I'm OK with a generator that's only in contrib, provided
that there's at least one that will work on all OSes.
--
Jim Nasby                                    jimn@enterprisedb.com
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

On Tue, Sep 19, 2006 at 10:11:39AM -0400, Andrew Dunstan wrote:
> mark@mark.mielke.cc wrote:
> >>As others have mentioned, using MAC address doesn't remove the
> >>possibility of a collision.
> >It does, as I control the MAC address. I can choose not to overwrite it.
> >I can choose to ensure that any cases where it is overwritten, it is
> >overwritten with a unique value.
> How do you know somebody else isn't using that MAC value?

Different UUID forms can be unique within their domain. As long as I
control the MAC address assignment for all of my units, my MAC address
can be guaranteed to be unique across space and time, within the
generous range provided by a UUID. My UUIDs may not be unique in your
database, or in your domain, but they will be unique within mine.

If I use a UUID form based upon the MD5 or SHA-1 of a unique URL, there
is a great chance that it is unique. Better than that of a random number
generator, in that I control the URL.

I'm not in favour of the random number based UUID forms, as I believe
I am sacrificing control, thereby allowing for generation to result in
non-unique output. Where it is currently impossible for me to generate
the same UUID (I control the MAC address, time, and the generator uses
the clock sequence), using a random number generator turns the
impossibility into a possibility.

If you don't have control over the MAC address, time, or generator,
then yeah - random number generator might suffice.

Cheers,
mark

-- 
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada
 One ring to rule them all, one ring to find them, one ring to bring them all                      and in the darkness
bindthem...
 
                          http://mark.mielke.cc/

On 2006-09-19, mark@mark.mielke.cc <mark@mark.mielke.cc> wrote:
> Different UUID forms can be unique within their domain. As long as I
> control the MAC address assignment for all of my units, my MAC address
> can be guaranteed to be unique across space and time,

You do not know (and can never know) that no-one else is using the same
MAC address. Anyone with substantial experience in networking will tell
you that the supposed "uniqueness" of manufacturer-assigned MACs is often
a myth, with (in extreme cases) entire batches of NICs being manufactured
with the same assigned MAC.

-- 
Andrew, Supernews
http://www.supernews.com - individual and corporate NNTP services

On Tue, Sep 19, 2006 at 10:02:40PM -0000, Andrew - Supernews wrote:
> On 2006-09-19, mark@mark.mielke.cc <mark@mark.mielke.cc> wrote:
> > Different UUID forms can be unique within their domain. As long as I
> > control the MAC address assignment for all of my units, my MAC address
> > can be guaranteed to be unique across space and time,
> You do not know (and can never know) that no-one else is using the same
> MAC address. Anyone with substantial experience in networking will tell
> you that the supposed "uniqueness" of manufacturer-assigned MACs is often
> a myth, with (in extreme cases) entire batches of NICs being manufactured
> with the same assigned MAC.

I have the impression I'm not being heard.

*I* control the MAC address assignment for all of *MY* units.

Clear? :-)

Cheers,
mark

-- 
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada
 One ring to rule them all, one ring to find them, one ring to bring them all                      and in the darkness
bindthem...
 
                          http://mark.mielke.cc/

mark@mark.mielke.cc wrote:
> On Tue, Sep 19, 2006 at 08:20:13AM -0500, Jim C. Nasby wrote:
> > On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
> > > I would not use a 100% random number generator for a UUID value as was
> > > suggested. I prefer inserting the MAC address and the time, to at
> > > least allow me to control if a collision is possible. This is not easy
> > > to do using a few lines of C code. I'd rather have a UUID type in core
> > > with no generation routine, than no UUID type in core because the code
> > > is too complicated to maintain, or not portable enough.
> > As others have mentioned, using MAC address doesn't remove the
> > possibility of a collision.
>
> It does, as I control the MAC address.

What happens if you have two postmaster running on the same machine?

--
Alvaro Herrera                                http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

On Tue, Sep 19, 2006 at 11:21:51PM -0400, Alvaro Herrera wrote:
> mark@mark.mielke.cc wrote:
> > On Tue, Sep 19, 2006 at 08:20:13AM -0500, Jim C. Nasby wrote:
> > > On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
> > > > I would not use a 100% random number generator for a UUID value as was
> > > > suggested. I prefer inserting the MAC address and the time, to at
> > > > least allow me to control if a collision is possible. This is not easy
> > > > to do using a few lines of C code. I'd rather have a UUID type in core
> > > > with no generation routine, than no UUID type in core because the code
> > > > is too complicated to maintain, or not portable enough.
> > > As others have mentioned, using MAC address doesn't remove the
> > > possibility of a collision.
> > It does, as I control the MAC address.
> What happens if you have two postmaster running on the same machine?

Could be bad things. :-)

For the case of two postmaster processes, I assume you mean two
different databases? If you never intend to merge the data between the
two databases, the problem is irrelevant. There is a much greater
chance that any UUID form is more unique, or can be guaranteed to be
unique, within a single application instance, than across all
application instances in existence. If you do intend to merge the
data, you may have a problem.

If I have two connections to PostgreSQL - would the plpgsql procedures
be executed from two different processes? With an in-core generation
routine, I think it is possible for it to collide unless inter-process
synchronization is used (unlikely) to ensure generation of unique
time/sequence combinations each time. I use this right now (mostly),
but as I've mentioned, it isn't my favourite. It's convenient. I don't
believe it provides the sort of guarantees that a SERIAL provides.

A model that intended to try and guarantee uniqueness would provide a
UUID generation service for the entire host, that was not specific to
any application, or database, possibly accessible via the loopback
address. It would ensure that at any given time, either the time is
new, or the sequence is new for the time. If computer time ever went
backwards, it could keep the last time issued persistent, and
increment from this point forward through the clock sequence values
until real time catches up. An alternative would be along the lines of
a /dev/uuid device, that like /dev/random, would be responsible for
outputting unique uuid values for the system. Who does this? Probably
nobody. I'm tempted to implement it, though, for my uses. :-)

Cheers,
mark

--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   |
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

mark@mark.mielke.cc writes:

> I have the impression I'm not being heard.
> 
> *I* control the MAC address assignment for all of *MY* units.

No, you're missing the point. How does that help *me* avoid collisions with
your UUIDs? UUIDs are supposed to be unique period, not just unique on your
database.

If all you want is unique number generation in your database then you can just
use sequences and they'll take a lot less space and perform much better.
(16-byte foreign keys throughout the whole database, *shudder*)

The reason to use UUIDs is when you want to have unique identifiers that you
can send outside the database and know they won't conflict with other unique
identifiers generated elsewhere.


Really this whole debate only reinforces the point that there isn't a single
way of doing UUID generation. There are multiple libraries out there each with
pros and cons. It makes more sense to have multiple pgfoundry UUID generating
modules.



-- 
greg

On Wed, 20 Sep 2006, Gregory Stark wrote:

>
> mark@mark.mielke.cc writes:
>
> > I have the impression I'm not being heard.
> >
> > *I* control the MAC address assignment for all of *MY* units.
>
> No, you're missing the point. How does that help *me* avoid collisions with
> your UUIDs? UUIDs are supposed to be unique period, not just unique on your
> database.


I must jump in with my amusement at this whole conversation.  I just
looked up the standard (http://www.ietf.org/rfc/rfc4122.txt) and it
includes this abstract:

Abstract
  This specification defines a Uniform Resource Name namespace for  UUIDs (Universally Unique IDentifier), also known
asGUIDs (Globally  Unique IDentifier).  A UUID is 128 bits long, and can guarantee  uniqueness across space and time.
UUIDswere originally used in the  Apollo Network Computing System and later in the Open Software  Foundation's (OSF)
DistributedComputing Environment (DCE), and then  in Microsoft Windows platforms.
 


It then goes on to detail multiple versions of them which are generated in
various ways.  But they are all called UUID, and thus should all be
UNIVERSALLY unique, and the statement "can guarantee uniqueness across
space and time" should apply equally to all versions, as it is an absolute
statement.  So perhaps the ietf have been drinking the kool-aid (or
whatever), or perhaps you plan to use your databases in multiple
universes.  But the standard seems to make the whole discussion moot by
guaranteeing all UUIDs to be unique across space and time.  Or am I
misreading that?

So I guess I am just ROFL at the fact that people can't seem to get their
definition of "universe" quite straight.  Either the UUID is misnamed, or
some people here are vastly underestimating the scope of the universe, or
perhaps both.  Or perhaps it's just that it's 3am and this thing seems
extraordiarily funny to me right now ;)


-- 
Menu, n.:A list of dishes which the restaurant has just run out of.

Hi, Mark,

mark@mark.mielke.cc wrote:

> The versions that include a MAC address, time, and serial number for
> the machine come pretty close, presuming that the user has not
> overwritten the MAC address with something else. It's unique at
> manufacturing time.

Not even that is guaranteed. I remember that, about 8 years ago, me and
a co-student bought a cheap "network starting kit" each, containing two
network kards and a crossover cable.

Now, it turned out, that the first cards in both packages had the same
mac address, and the second cards as well, so we could not network
together using proper cabling and a hub.

Luckily, the mac address was flashable in an eeprom, and so my friend
"fixed" his hards with those from two 10 MBit Coax cards we had
abandoned in favour of the new twisted pair network.

AFAIR, in the end it turned out that the whole charge of cards was
manufactured this way. Officially, it was a bug in the eeprom content
generating software, but there were rumours that the manufacturer wanted
to avoid paying the registration fees for the mac address ranges...


Just gettin' off topic,
Markus
--
Markus Schaber | Logical Tracking&Tracing International AG
Dipl. Inf.     | Software Development GIS

Fight against software patents in Europe! www.ffii.org
www.nosoftwarepatents.org

On Wed, Sep 20, 2006 at 05:04:00AM -0400, Gregory Stark wrote:
> mark@mark.mielke.cc writes:
> > I have the impression I'm not being heard.
> > *I* control the MAC address assignment for all of *MY* units.
> No, you're missing the point. How does that help *me* avoid collisions with
> your UUIDs? UUIDs are supposed to be unique period, not just unique on your
> database.

As you already said, they can't be. I don't see how random is better than
unique by intent (MAC address).

> If all you want is unique number generation in your database then
> you can just use sequences and they'll take a lot less space and
> perform much better.  (16-byte foreign keys throughout the whole
> database, *shudder*)

I want unique number generation from several separate databases, and
I don't like the idea of maintaining complicated SERIAL ranges, or using
one of the increment by X, offset Y techniques. Too hard.

> The reason to use UUIDs is when you want to have unique identifiers that you
> can send outside the database and know they won't conflict with other unique
> identifiers generated elsewhere.

If you don't control the factors that influence the UUID generation, this
is a cross your fingers type of merge. Random numbers might collide.
Shared MAC address might collide. Not controlling the time source might
collide. Although it will probably work, if I know my domain, if I know
what will need to be merged, I can ensure that they can be merged.

> Really this whole debate only reinforces the point that there isn't
> a single way of doing UUID generation. There are multiple libraries
> out there each with pros and cons. It makes more sense to have
> multiple pgfoundry UUID generating modules.

Exactly. If I lead you to the impression that I want UUIDv1 in core, this
was not the intent. What I intend to say is that different people want
different implementations, and one of the most useful versions, in my
opinion, is difficult to implement portably.

Cheers,
mark

-- 
mark@mielke.cc / markm@ncf.ca / markm@nortel.com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada
 One ring to rule them all, one ring to find them, one ring to bring them all                      and in the darkness
bindthem...
 
                          http://mark.mielke.cc/

mark@mark.mielke.cc wrote:
>> Really this whole debate only reinforces the point that there isn't
>> a single way of doing UUID generation. There are multiple libraries
>> out there each with pros and cons. It makes more sense to have
>> multiple pgfoundry UUID generating modules.
> 
> Exactly. If I lead you to the impression that I want UUIDv1 in core, this
> was not the intent. What I intend to say is that different people want
> different implementations, and one of the most useful versions, in my
> opinion, is difficult to implement portably.

Actually, you could do it very portably, at the cost of a minute or so's 
worth of configuration. Simply have a GUC variable called, say, 
uuid_mac_address. Then the person who gets a box of dud NICs or who, 
like me, has a virtual server somewhere without a true ethernet port 
visible to the operating system, can easily set it. No cross-platform 
code, no requirement to build a third party module in contrib (at least 
not for v1 uuids).

I actually DO think that we should have at least one default generation 
routine in core, even if the above idea doesn't float and it's just v4 
random numbers. If we advertise that we have uuids, people will not 
expect to have to install a contrib module just to get some values 
generated. The SQL server function newsequentialid() which gives v1 
uuids, sort of, is ONLY available as a default value for a column, you 
can't use it in normal expressions (figure that out). So people clearly 
will expect to be able to generate these at the database level.

Using either v1s as configured above or v4s, there's no portability 
issue. Indeed MS SQL Server has a both available (newsequentialid() and 
newid()). And sufficient documentation should allow people to make their 
minds up regarding what their needs are. If they really want funky v3 
namespace ones then they can install a contrib, no problem with that.

Cheers

Tom

Jeremy Drake <pgsql@jdrake.com> writes:
> I must jump in with my amusement at this whole conversation.  I just
> looked up the standard (http://www.ietf.org/rfc/rfc4122.txt) and it
> includes this abstract:

>    A UUID is 128 bits long, and can guarantee
>    uniqueness across space and time.

The only meaningful word in that claim is "can".   Which boils down to
"if everybody always follows best practices and no failures ever occur,
maybe they're really unique".  We already know that two of the more
critical assumptions embedded in those best practices (unique MAC
addresses and always-correct system clocks) are seriously flawed in
the real world.

To see just how much of the kool-aid that RFC's authors have been
drinking, note that their "sample implementation" in Appendix A
implements the unique node identifier as ... a random number.
So much for guaranteed uniqueness.
        regards, tom lane

mark@mark.mielke.cc wrote:
> On Tue, Sep 19, 2006 at 11:21:51PM -0400, Alvaro Herrera wrote:
>> mark@mark.mielke.cc wrote:
>>> On Tue, Sep 19, 2006 at 08:20:13AM -0500, Jim C. Nasby wrote:
>>>> On Mon, Sep 18, 2006 at 07:45:07PM -0400, mark@mark.mielke.cc wrote:
>>>>> I would not use a 100% random number generator for a UUID value as was
>>>>> suggested. I prefer inserting the MAC address and the time, to at
>>>>> least allow me to control if a collision is possible. This is not easy
>>>>> to do using a few lines of C code. I'd rather have a UUID type in core
>>>>> with no generation routine, than no UUID type in core because the code
>>>>> is too complicated to maintain, or not portable enough.
>>>> As others have mentioned, using MAC address doesn't remove the
>>>> possibility of a collision.
>>> It does, as I control the MAC address.
>> What happens if you have two postmaster running on the same machine?
> 
> Could be bad things. :-)
> 
> For the case of two postmaster processes, I assume you mean two
> different databases? If you never intend to merge the data between the
> two databases, the problem is irrelevant. There is a much greater
> chance that any UUID form is more unique, or can be guaranteed to be
> unique, within a single application instance, than across all
> application instances in existence. If you do intend to merge the
> data, you may have a problem.
> 
You may. But it's not very likely. Since a) there is a 13-bit random number in addition to 
the MAC address (the clock sequence) and b) the timestamp has a granularity of 100 nanosec. 
An implementation could be made to prevent clock-sequence collisions on the same machine and 
thereby avoid this altogether.

Kind Regards,
Thomas Hallgren