Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Guid Smash

guidsmash.com

Post reply on HN
Print view View original

61–70 of 72 posts

Re: Guid Smash

#61

Post by e1g »

sgentle wrote: post #37
e1g wrote: post #8

Earlier quoted context omitted.

You need to be generating >100M of them within the same millisecond before even remembering that collisions can theoretically happen.

Apparently there's 500 hours of video uploaded to YouTube every minute (30 seconds every millisecond). Assuming 4K@60fps, that works out to 14,929,920,000 pixels per millisecond. If YouTube wanted to give every incoming pixel its own UUIDv7, they'd see a collision rate just under 0.6%.

Excellent example. And at that scale, you are generating 100TB/s in UUIDs so if you need to store them, you have much bigger problems than collisions.

Re: Guid Smash

#62

Post by 8organicbits »

Zambyte wrote: post #55
kaoD wrote: post #52

Earlier quoted context omitted.

Good observation. Could you share the math even if you don't trust it? I don't have pen and paper here and I'm curious. After thinking it more, I have the feeling (against my initial intuition) that v4 might dominate either way unless you consistently generate tons of UUIDs for an impractical number of years.

I ran some numbers by GPT-5[0], and for the scenario of generating 10k UUIDs in one ms every 10ms, over three years, it came up with a 0.0025% chance of collision for UUIDv7, and a 0.000000084% chance for collision with UUIDv4. [0] https://kagi.com/assistant/dd7d8c48-44e4-499b-9f2f-33663d125...

I checked against my notes, I see about the same numbers using the `n**2` taylor series approximation. I missed that the probability of `>=1` collision is about the same as exactly one collision, but I suspect that's quite reasonable as this scale.

Re: Guid Smash

#63

Post by vbezhenar »

habibur wrote: post #36
twiss wrote: post #5

> The chances of generating two GUIDs that are the same is astronomically small. > The odds are 1 in 2^122 — that’s approximately 1 in 5,000,000,000,000,000,000,000,000,000,000,000,00. This is true if you only generate two GUIDs, but if you generate very many GUIDs, the chance of generating two identical ones between any of them increases. E.g. if you generate 2^61 GUIDs, you have about a 1 in 2 chance of a collision…

The birthday paradox simplified : if you generate n bits of random data, you can at most generate n/2 bits of random numbers before clashes start to occur. That's square root of number's range. So if you need 1000 random numbers, generate from 1 to 1 million.

> So if you need 1000 random numbers, generate from 1 to 1 million.

If you don't check for clashes, the 50% chance of failure is too much. Probably even 0.1% is too much, so you'd need more elaborate approach.

If you do check for clashes, you can generate from 1 to 2000 with little overhead.

Re: Guid Smash

#64

Post by Xelynega »

avar wrote: post #46
sgentle wrote: post #37

Earlier quoted context omitted.

Apparently there's 500 hours of video uploaded to YouTube every minute (30 seconds every millisecond). Assuming 4K@60fps, that works out to 14,929,920,000 pixels per millisecond. If YouTube wanted to give every incoming pixel its own UUIDv7, they'd see a collision rate just under 0.6%.

> Assuming 4K@60fps [...] they'd see a collision rate just under 0.6% This doesn't detract from your point of collisions like that being viable at that scale, but assuming an average of 4K@60fps is assuming a lot. The average video upload there is probably south of 1080p@30fps.

You're glossing over the fact that they assumed youtube would want to assign a UUID to each pixel in a 4k@60fps video as the use case that this would fail for...

Re: Guid Smash

#65

Post by Xelynega »

charcircuit wrote: post #29
tonyhart7 wrote: post #26

Earlier quoted context omitted.

Your app is must be popular to be having an entire universe "amount" of users lol joke aside all of this is theorical, in practical application its literally impossible to hit it that it doesn't matters if its possible or not since you are not google scale anyway

It's not just your app. It's any other app or data provider that you may now or in the future interact with.

That's not how namespacing works though, is it?

Getting UUID 'A' from app 'X' is easily distinguishable from UUID 'A' from app 'Y'.

Re: Guid Smash

#67

Post by vlovich123 »

Retr0id wrote: post #44
vlovich123 wrote: post #17

Earlier quoted context omitted.

Depends on what “isn’t even that large means”. A modern 6ghz machine would probably need 12 years of 24/7 operation to count that high. To me that seems like a lot.

That's assuming 1 IPC, and no parallelism. A desktop-class zen5 CPU has 32 threads, with AVX512. Pipelining gets you up to 2048 bits of SIMD throughput per core per clock cycle: https://www.numberworld.org/blogs/2024_8_7_zen5_avx512_teard... So assuming you use 64-bit counters, you can divide those 12 years by 1024 to get 4 days. And that's not even considering what you could do on a GPU. Edit: I might be off by a fa…

Well UUID generation isn’t going to be quite as SIMDable as counting so the analogy breaks down there partially because of that. And += 1 isn’t a very SIMDable operation? Unless I guess you create a mask of +1, +2, +3, +4 and add that to your base number to generate those offsets (which only works with avx512 - avx2 can only do 2 increments since these are 64bit integers)

Then your 32 HT threads aren’t really going to give you full access to the underlying SIMD registers which are going to be per core which is where I assume you realized the 2x difference might show up?

And to do += 1 multithreaded you have to partition the range or you won’t get any speed up - if you don’t amortize the cost of atomic synchronization across threads you’re going to be going slower than a non-SIMD increment.

Re: Guid Smash

#68

Post by charcircuit »

Xelynega wrote: post #65
charcircuit wrote: post #29

Earlier quoted context omitted.

It's not just your app. It's any other app or data provider that you may now or in the future interact with.

That's not how namespacing works though, is it? Getting UUID 'A' from app 'X' is easily distinguishable from UUID 'A' from app 'Y'.

The point of the first U in UUID, universal, is that you don't need to use namespacing.

Re: Guid Smash

#69

Post by tonyhart7 »

charcircuit wrote: post #68
Xelynega wrote: post #65

Earlier quoted context omitted.

That's not how namespacing works though, is it? Getting UUID 'A' from app 'X' is easily distinguishable from UUID 'A' from app 'Y'.

The point of the first U in UUID, universal, is that you don't need to use namespacing.

Universal mean unique that uid wouldn't be used anyone else in any point in history or just universal available in one app????

because you just overreach at this point, if you can develop a better one. be my guest

Re: Guid Smash

#70

Post by whyever »

vbezhenar wrote: post #63
habibur wrote: post #36

Earlier quoted context omitted.

The birthday paradox simplified : if you generate n bits of random data, you can at most generate n/2 bits of random numbers before clashes start to occur. That's square root of number's range. So if you need 1000 random numbers, generate from 1 to 1 million.

> So if you need 1000 random numbers, generate from 1 to 1 million. If you don't check for clashes, the 50% chance of failure is too much. Probably even 0.1% is too much, so you'd need more elaborate approach. If you do check for clashes, you can generate from 1 to 2000 with little overhead.

You can also look at the expected number of collisions instead, which is approximately the number of random numbers squared, divided by the size of the space of random numbers.

Then you can choose how many collisions to accept on average. (If the answer is zero, then it makes more sense to look at the probability of one or more collisions.)

Post reply on HN