15

I am working on a project where I need to generate approximately 1 billion GUIDs.

I know GUIDs are not guaranteed to be unique but are unique almost all of the time.

If I generated a billion GUIDs, what is the probability that there will be a match?

Diskdrive
  • 18,107
  • 27
  • 101
  • 167
  • possible duplicate of [Are GUID collisions possible?](http://stackoverflow.com/questions/184869/are-guid-collisions-possible) – tanascius Jun 29 '10 at 06:45
  • Over how long a period of time are you going to be generating the GUIDs? – overslacked Jun 29 '10 at 07:05
  • it will all be done in one batch, so however long it takes to do that – Diskdrive Jun 29 '10 at 07:07
  • You'll need to ensure that enough time passes between each GUID generation to allow the time to become unique again. I don't know how long that is, that's your only concern. I'd recommend multiple computers working on this in parallel! – overslacked Jun 29 '10 at 07:10
  • @overslacked the time stamp value has a resolution of 100ns, so assuming it is got from a timer with similar resolution it should be OK, as you aren't going to generate more than 2^14 GUIDs between time stamp increments on current conventional hardware (a quad core at 4GHz would need to be able to create a GUID for a quarter a cpu cycle; so an increment, an or, two moves probably need 64 cores to start getting close). – Pete Kirkham Jun 29 '10 at 08:11

3 Answers3

15

Blogpost: GUIDs are globally unique, but substrings of GUIDs aren’t

The .NET GUID consists of

  • 60 bits of timestamp,
  • 48 bits of computer identifier,
  • 14 bits of uniquifier, and
  • six bits are fixed

So the UUID probability quoted by Oscar does not work here. But if you create all your 1 billion GUIDs from one computer, there is no chance to get a duplicate (except you are playing with the clock ;-)

Hinek
  • 9,519
  • 12
  • 52
  • 74
5

If you are creating the GUIds from the same machine and using the same algorithm then you will not get a collision.

Robin Day
  • 100,552
  • 23
  • 116
  • 167
2

http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

n probability

68,719,476,736 = 2^36 = 0.0000000000000004 = 4 × 10^−16)

2,199,023,255,552 = 2^41 = 0.0000000000004 = (4 × 10^−13)

70,368,744,177,664 = 2^46 = 0.0000000004 = (4 × 10^−10)

sbi
  • 219,715
  • 46
  • 258
  • 445
Oscar Cabrero
  • 4,168
  • 8
  • 29
  • 49
  • He's talking about .NET GUIDs, they are not entirely random, like assumed in the article. There are parts caused by time and processor id(?) ... still the chance of getting a duplicate in 1 billion GUIDs is very unlikely on the same machine it may be even impossible. – Hinek Jun 29 '10 at 06:55