Hacker News Reader

Comment by gus_massa | Hacker News Reader

> GUID generation algorithm 4 fills the GUID with 122 random bits. The odds of two GUIDs colliding are therefore one in 2^122, which is a phenomenally small number.

Another thing to consider, is that due to the birthday paradox once you build 2.7 * 10^18 GUID, the probability that you have at lest a collision is bigger than 50%. And 2.7 * 10^18 is only 2^61.2.

View on HN

If you generated 2.7 * 10^18 GUIDs (and obviously stored them all, otherwise the birthday paradox is not relevant), you also used up 43 exabytes (=1 million terrabytes) of storage. I wonder which problem you will encounter first...

True, but that's for a 50% chance of a collision. In a single system, even a 1% chance of a collision is bad news.

I can't do the math on my phone, but getting to a 1% chance still needs an enormous unfathomable bucketload of uuids.

Note that at 128 bits per GUID (not including any storage overhead), 2.7x10^18 GUIDs would take up 43.2 exabytes of storage. That's about 10 million 4TB drives.

It's going to be a while before the birthday paradox is really going to be problematic.

Not to the NSA... ;-)

Duplicate GUID:s matter only if there is actual comparison.

There may be duplicate GUID:s used in different contexts and that's just fine. If there is single system and context where storing just GUID:s takes several exabytes we may start worrying.

Yeah, I really don't understand how they are ignoring this. It's actually very concerning to me that they don't understand this.

Are you sure they don't? Do you know how much 2^61 is?

Well, if they did understand, they would say the chance is ~1 in 2^61, not 1 in 2^122, and they would've based the math comparison to RAM failure on 2^61, which changes the comparison entirely.

In any case, I should have been more clear. I'm not necessarily worried about this case. But if you design systems and miss a factor of a square root, you tend to break things that we're all relying on to work.

Far within the bounds of modern computing. The Bitcoin network cranks out 2^61 hashes every 2 or so seconds.

Thanks for saying this. The birthday paradox calculation is far more relevant to determining collision risks. Rule of thumb: if you have N random IDs, then after sqrt(N) IDs are generated there's a 50% probability of a single collision. Fortunately the sqrt(2^122) is still 2^62, or a very large number of IDs. But 64 bit random IDs have a collision after only 2^32, or 4 billion, and that has happened in practice in several systems.

only

Reply on news.ycombinator.com