GUIDs are globally unique, but substrings of GUIDs aren't

re: GUIDs are globally unique, but substrings of GUIDs aren't

Adrian — Fri, 27 Jun 2008 18:29:56 GMT

Nice analysis.

I never knew about the algorithm identifier in the GUID. I remember when there was a privacy concern since GUIDs could be tracked back to the machine that generated them (by the network card address). As I understand it, the algorithm used by Windows was changed. It's neat to see that GUIDs generated by different algorithms can't collied.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Joe Enos — Fri, 27 Jun 2008 18:42:52 GMT

Wouldn't a truly random GUID generator be better suited? If all 128 bits are random, then you could take a subset of them and still be reasonably unique - not as unique as the full 128, but still pretty good.

The non-random GUID doesn't really make a lot of sense to me. If truly random, the odds of finding a duplicate are incredibly ridiculously low - if you have it based on a timestamp, network card, etc., you can run into duplicates much easier, especially as CPUs get faster, and as more and more pieces of hardware get added to the global network.

re: GUIDs are globally unique, but substrings of GUIDs aren't

.. — Fri, 27 Jun 2008 19:08:49 GMT

You basically cannot implement a truly random generator without specific hardware support.

You can always improve your 128bit UUID adding a random generated number to it (of at least 64bit itself.. remember birthday paradox); adding a second random number to an already random number will not improve the situation that much unless taken from a completely different generator.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Nate — Fri, 27 Jun 2008 19:09:43 GMT

Ok, say it with me:

"GUIDs are not defined to be random; they are defined to BE UNIQUE in space & time!"

Joe, the customer didn't ask for a random number, they asked for a unique number and more specifically about chopping a GUID in half. Raymond explained why that was a bad idea. And he gave a way to generate a CLUSTER unique number with 0 risk of a collision when taken within the customer specified spatial and temporal domains.

Also, using a pseudo-random number generator doesn't help with uniqueness if all the computers use the same seed (through the use of time or some other error of coding).

My $0.02.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Maurits — Fri, 27 Jun 2008 19:11:35 GMT

The "random" GUIDs have an "algorithm identifier" of 0100 (4), FWIW.

Don't get me started on the KSDATAFORMAT_SUBTYPE_PCM and KSDATAFORMAT_SUBTYPE_IEEE_FLOAT pseudo-GUIDs.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Josh — Fri, 27 Jun 2008 19:26:37 GMT

@Joe:

Because there is a *chance* of collision, even with pure randomness. Remember, the birthday problem (aka birthday paradox) means that the time before unacceptably high probability of collision is much lower than the number of possible options. e.g. For truly random 128 bit numbers (3.4e38 options), you'd have a 50% chance of collision after generating about 22 quintillion GUIDs (2.17e19). Problem is, this assumes we are *really* random. And generating numbers that are truly random, to the point of uniqueness, is nearly impossible. For example, one means of generating very good random numbers is having an antenna count ticks in the cosmic background radiation over time. If an odd number of ticks occur in a time frame, you get a 1, even, a 0, continue until the number is long enough. But what if two antennas are generating at the same time in close proximity? Odds of collision increase greatly. And of course, it would take a while to collect the arbitrary randomness. Virtually every form of random number generation would be in some way dependent on the time and location at which it was generated. And any less extensive randomness generator is likely to be slightly non-random, leading to collisions occurring *much* more often.

The non-random GUID, if you read the description, allows for any given machine to pump out 16 *guaranteed* unique GUIDs per second. And it even manages to conserve 6 bits that aren't part of the uniqueness, to allow for future advances in GUID design. Not bad if I say so myself. Keep in mind, this isn't "based on" a timestamp or network card, it is a time stamp and specific network card ID. You can permanently remove a whole block of GUIDs from existence by smashing network cards. No risk of duplicates, period.

[Actually, it's 16 guaranteed unique GUIDs per 100-nanosecond interval, or 160 million unique GUIDs per second. -Raymond]

re: GUIDs are globally unique, but substrings of GUIDs aren't

Josh — Fri, 27 Jun 2008 19:39:23 GMT

Even better. Sorry, didn't know the time interval off the top of my head. :-)

[I didn't either, but I bothered to follow the link to the GUID spec. -Raymond]

re: GUIDs are globally unique, but substrings of GUIDs aren't

Nathan_works — Fri, 27 Jun 2008 19:49:52 GMT

Looks like they are up to algorithm 5, according to a newer spec than the one Raymond linked to: http://www.faqs.org/rfcs/rfc4122.html

re: GUIDs are globally unique, but substrings of GUIDs aren't

Brian — Fri, 27 Jun 2008 20:03:43 GMT

It's all fine and dandy until someone builds the 140,737,488,355,328th network card.

re: GUIDs are globally unique, but substrings of GUIDs aren't

mikeb — Fri, 27 Jun 2008 20:16:00 GMT

@josh:

"Not bad if I say so myself."

So, you're the creator of the GUID generation algorithm? :-)

re: GUIDs are globally unique, but substrings of GUIDs aren't

Ron Parker — Fri, 27 Jun 2008 20:55:07 GMT

@Josh:

Where do you get the number 16 from? That seems to come from the 4-bit clock sequence number Raymond suggested for the 64-bit cluster-unique ID. GUID algorithm 1 uses 14 bits for the clock sequence number, for 16,384 unique GUIDs per MAC address per 100ns interval, no?

(Provided, of course, that your clock never goes backward. If it does, and you're generating GUIDs at a rate of 16,384 every 100ns, your risk of collision rises to near 100%.)

re: GUIDs are globally unique, but substrings of GUIDs aren't

njkayaker — Fri, 27 Jun 2008 20:58:43 GMT

[I didn't either, but I bothered to follow the link to the GUID spec. -Raymond]

Great! A well that will never run dry!

re: GUIDs are globally unique, but substrings of GUIDs aren't

Alexandre Grigoriev — Fri, 27 Jun 2008 21:19:30 GMT

>Provided, of course, that your clock never goes backward

Stupid clock correction in Windows makes it possible, unfortunately.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Alexandre Grigoriev — Fri, 27 Jun 2008 21:21:54 GMT

>[Actually, it's 16 guaranteed unique GUIDs per 100-nanosecond interval, or 160 million unique GUIDs per second. -Raymond]

You mean your tick rate is 10 MHz? 100 ns is just kernel time unit, not actual resolution, or rate at which it changes. It only changes about 15 times per second, depending on HAL.

[If you read the GUID spec (which I linked to) you can see how you can generate timestamps with greater precision than the clock tick. -Raymond]

re: GUIDs are globally unique, but substrings of GUIDs aren't

mikeb — Fri, 27 Jun 2008 21:33:22 GMT

@Ron Parker:

The clock sequence field is not intended to be used to allow more than one GUID to be generated within a 100ns interval. The clock sequence field is specifically intended to handle the situation where the clock 'goes back in time' (due to a resetting the clock, restarting the machine or whatever).

What Raymond calls 56 bits of time stamp with 4 bits of 'uniquifier' is really a 60 bit time stamp field with 100ns resolution. What's being described as 56 bit of timestamp with 4 bits uniquifier is probably that the clock being used to get the timestamp does not have a 100ns resolution, and the implementation is using a technique like the one described in RFC 4122 section 4.2.1.2 to get up to 16 UUID's per native clock tick.

Basically with algorithm 1 (according to RFC4122) for a single generator instance, you get at most one UUID per 100ns interval. If you need more, the RFC suggests adding more MAC addresses so you can have several instances of the UUID gen going concurrently. If you can't do something like that you have to stall or return an error.

See RFC 4122 4.2.1.2.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Ron Parker — Fri, 27 Jun 2008 21:42:45 GMT

@Alexandre:

If you can get anything that runs Windows to generate 16,384 GUIDs every 100ns, tell me what the stock market looks like there in the 160+ GHz future. And where do you store them all? If you're not generating them at a sustained rate that's a significant fraction of that, the risk of collision goes way down, even if the clock goes backwards.

RFC 4122 actually has a provision for clocks that don't tick every 100ns, allowing you to use the lower bits of the timestamp as a serial number. It's not clear to me on first reading how that serial number interacts with the time sequence number, so the number of GUIDs you can generate on such a system without causing collisions might not be quite as high.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Ron Parker — Fri, 27 Jun 2008 21:50:54 GMT

@mikeb:

I see. The RFC says "If the state was available, but the saved timestamp is later than the current timestamp, increment the clock sequence value" but Raymond said "When time appears to have stood still ... or gone backward ... the uniquifier is incremented." When I read the RFC, I missed the subtle difference. So at most one GUID every 100ns it is.

re: GUIDs are globally unique, but substrings of GUIDs aren't

mikeb — Fri, 27 Jun 2008 22:02:38 GMT

[If you read the GUID spec (which I linked to) you can see how you can generate timestamps with greater precision than the clock tick. -Raymond]

But you can't generate timestamps with a higher resolution than 100ns - that's what the timestamp field is defined to be. So the spec discusses, for example, how to deal with the fact that your clock can only generate ticks with 10 microsecond resolution and you want your generator to be able to generate more than one UUID within the span of 10 microseconds.

If you need to generate more than one UUID within a 100ns span (on average), you either need to have addition MAC addresses to 'uniquify' the node ID field or you need to have your generator stall or return an error.

On the whole though, I don't think there are too many people having problems with generating too many GUIDs in too short a time period. My machine has less than a 4GHz clock - so that's fewer than 400 clock cycles per 100ns interval here (if my cipherin' is correct).

re: GUIDs are globally unique, but substrings of GUIDs aren't

Dave — Fri, 27 Jun 2008 22:30:12 GMT

some other interesting notes about GUIDs that try to use MAC addresses as unique values:

1) many network cards and devices now allow you to set the MAC address to whatever you want; some cable modems and that kind of thing rely on this functionality, apparently.

2) for a while, at least, the dummy network adaptors created by Windows for dial-up connections and the like all had the same MAC address (i think it was "DEST\0\0" or something). there were a lot of GUIDs floating around that had that decidedly non-unique value...

re: GUIDs are globally unique, but substrings of GUIDs aren't

Anonymous — Fri, 27 Jun 2008 22:38:06 GMT

A related post by Larry Osterman:

UUIDs are only unique if you generate them...

http://blogs.msdn.com/larryosterman/archive/2005/07/21/441417.aspx

re: GUIDs are globally unique, but substrings of GUIDs aren't

Thor — Fri, 27 Jun 2008 23:01:05 GMT

Beyond the specifics of the GUID generation, I love the initial problem statement. (I am fairly new to the blog and haven't finished going back and reading them all but this must be a pattern.)

The customer's basic question is-- "for this problem, there is a solution, but I want it for less".

Without changing the a basic requirement (like local uniqueness versus global uniqueness in this example), it seems the only way this would be possibile is if the original solution was suboptimal. While I frequently think that a given solution seems suboptimal, I almost always find that, no, whoever found it knew *tons* more about the problem than I had any idea existed.

Granted questioning an optimal solution is how technology improves, but in a case like this, unless you are master of the intricacies of unique number generation, the chances seem quite slim that you will achieve the requirement (unique) with fewer resources (half the byters).

So, the root of the question pattern may be-- what are the requirements on which a solution is based and can any of them be relaxed?

re: GUIDs are globally unique, but substrings of GUIDs aren't

eff Five — Fri, 27 Jun 2008 23:53:13 GMT

@Thor

Very nicely put. I’m adding “what are the requirements on which a solution is based and can any of them be relaxed” to the “words to code by” list. I especially like it because its got understanding the requirements baked in

re: GUIDs are globally unique, but substrings of GUIDs aren't

Judge Dredd — Sat, 28 Jun 2008 01:00:17 GMT

>> “never fix a bug you don’t understand” -http://www.links.org/?p=327

I disagree with the post..

Better is

Never leave ambiguous "bug-smelling" code around, at least not uncommented, and never rely on undetermined system behavior (OpenSSL relies on the memory being uninitialized.. which is a false assumption because it's not part of any contract and both OS, the loader, libc et al are free to zero-out - or something else - the uninit. memory).

If it smells like a bug, it's a bug, at least in form. Correct code should never raise a suspect.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Miles Archer — Sat, 28 Jun 2008 03:39:39 GMT

Judge Dred,

I hope you don't work on any of my projects. There's a risk to fixing any code. If you don't weigh the risk vs reward you're asking for trouble. If you worked on my project and fixed code that "smells" without justification, their would be hell to pay.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Dean Harding — Sat, 28 Jun 2008 06:21:05 GMT

"OpenSSL relies on the memory being uninitialized"

If you're referring to the "Debian incident", that is not true - OpenSSL does not rely on memory being uninitialized.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Jeff Tyrrill — Sat, 28 Jun 2008 06:30:33 GMT

I really do wish hardware random number generators were standard order in modern processors, so we didn't have to rely on these elaborate algorithms simply to guarantee uniqueness, which are riddled with privacy implications. (I realize newer algorithms are much improved from the one in this post, but the point remains that not having access to guaranteed entropic data means a slew of pragmatic assumptions must be made and carefully weighted in the development of any unique number generation algorithm.)

Using a cryptographic PRNG and guaranteed entropic source data, you don't need silly constructs like an "algorithm" counter to prevent collisions between "algorithms". The size of the bitspace (128 bits) is guarantee enough, even with arbitrarily many algorithms, as long as they all have entropic source data and are reliable CSPRNGs.

(Whatever the probability of number collision, it will be higher with a less entropic algorithm than a cryptographic PRNG anyway, so even if 128 bits isn't enough bitspace, you're still better off using a CSPRNG. A CSPRNG satisfies a greater requirement than uniqueness, but it _does_ satisfy uniqueness also.)

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

re: GUIDs are globally unique, but substrings of GUIDs aren't

Yuhong Bao — Sat, 28 Jun 2008 09:28:50 GMT

Similarly, hashing 2 7-byte values aren't as secure as hashing 1 14-byte value, as the LM hash showed.

re: GUIDs are globally unique, but substrings of GUIDs aren't

Narr — Sat, 28 Jun 2008 11:24:56 GMT

>Whatever the probability of number collision,

>it will be higher with a less entropic

>algorithm than a cryptographic PRNG anyway

Global registry? _That_ would actually guarantee uniqueness. A 1:1, one-way hashed hardware ID + timestamp comes pretty close, too.

>A CSPRNG satisfies a greater requirement than

>uniqueness, but it _does_ satisfy uniqueness also.

How? It's entirely possible for a collision to occur, so there's no guarantee, and it trivially does not satisfy. Also, what is your 'greater requirement'?

re: GUIDs are globally unique, but substrings of GUIDs aren't

Xepol — Sun, 29 Jun 2008 01:12:47 GMT

Or they could stop being data-cheap and just use a GUID....

re: GUIDs are globally unique, but substrings of GUIDs aren't

SuperKoko — Sun, 29 Jun 2008 10:28:49 GMT

From mikeb:

But you can't generate timestamps with a higher resolution than 100ns - that's what the timestamp field is defined to be.

On my computer, QueryPerformanceCounter has 10ns accuracy (the function call time itself is irrelevant). It uses the on-board clock which runs at approximatively 100Mhz.

Why would you use GetTickCount?

From Jeff Tyrrill:

I really do wish hardware random number generators were standard order in modern processors, so we didn't have to rely on these elaborate algorithms simply to guarantee uniqueness

On Linux, there's /dev/random, based on keystrokes entropy, and things like noise recorded from the sound card.

Birthday's paradoxes remain.

re: GUIDs are globally unique, but substrings of GUIDs aren't

AndyC — Sun, 29 Jun 2008 23:46:22 GMT

@Jeff Tyrrill

"I really do wish hardware random number generators were standard order in modern processors, so we didn't have to rely on these elaborate algorithms simply to guarantee uniqueness"

If your random numbers are unique, your random number generator is broken.

re: GUIDs are globally unique, but substrings of GUIDs aren't

mikeb — Mon, 30 Jun 2008 05:58:49 GMT

@SuperKoko:

>> On my computer, QueryPerformanceCounter has 10ns accuracy <<

That's nice, but it doesn't solve the theoretical problem of generating more than one UUID every 100ns (on average) - the timestamp field in the UUID is in units of 100ns.

re: GUIDs are globally unique, but substrings of GUIDs aren't

pZy — Mon, 30 Jun 2008 09:23:57 GMT

German Wikipedia says for privacy reasons newer versions of Windows would not make use of the MAC address for creating GUIDs.

Otherwise it would be possible to draw conclusions about the creator.

Unfortunatley I didn't find that statement in the english wiki.

re: GUIDs are globally unique, but substrings of GUIDs aren't

SuperKoko — Mon, 30 Jun 2008 18:22:52 GMT

That's nice, but it doesn't solve the theoretical problem of generating more than one UUID every 100ns (on average) - the timestamp field in the UUID is in units of 100ns.

That's still better than one GUID every 10 milliseconds with GetTickCount.

re: GUIDs are globally unique, but substrings of GUIDs aren't

mikeb — Mon, 30 Jun 2008 20:46:47 GMT

@SuperKoko:

>> That's still better than one GUID every 10 milliseconds with GetTickCount. <<

But you're not limited to a single UUID per 10ms tick, even if that's the hardware clock you might be stuck with. That's one of the things that section 4.2.1.2 of RFC 4122 discusses:

--------------------------------

A high resolution timestamp can be simulated by keeping a count of the number of UUIDs that have been generated with the same value of the system time, and using it to construct the low order bits of the timestamp. The count will range between zero and the number of 100-nanosecond intervals per system time interval.

--------------------------------

So you can still get a 10000 unique UUIDs per 10ms tick. But my point wasn't what timer resolution is best to use, but that by definition you can't get better resolution than 100ns resolution using Algorithm 1 to generate UUIDs. Oh, and that the clock sequence field is not intended to be used to simulate a higher resolution - it's intended to deal with clocks getting out of 'sync' (or going back in time).

Reflective Perspective - Chris Alcock » The Morning Brew #126

Reflective Perspective - Chris Alcock » The Morning Brew #126 — Tue, 01 Jul 2008 10:04:33 GMT

PingBack from http://blog.cwa.me.uk/2008/07/01/the-morning-brew-126/

The GUID Guide « SQL Dev’s Playground

The GUID Guide « SQL Dev’s Playground — Tue, 01 Jul 2008 10:46:49 GMT

PingBack from http://sqldev.wordpress.com/2008/07/01/the-guid-guide/

re: GUIDs are globally unique, but substrings of GUIDs aren't

Andy R — Thu, 03 Jul 2008 13:03:05 GMT

Your reduced GUID format is a good idea, not used often enough, but it makes one more assumption... that there is only one thread or process running on each computer.

re: GUIDs are globally unique, but substrings of GUIDs aren't

SuperKoko — Fri, 04 Jul 2008 01:29:23 GMT

Your reduced GUID format is a good idea, not used often enough, but it makes one more assumption... that there is only one thread or process running on each computer.

No. It just assumes that you use only one generator function (e.g. in a dynamic or static library). In that case, it's free to use shared variables and mutexes to safely manager GUIDs generation.

Interesting Links 7/09/2007

Matt Johnson's Technical Adventures — Wed, 09 Jul 2008 15:38:55 GMT

The list is a little longer today because of not posting last week. Enjoy! Microsoft Advanced Windows