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

Ask HN: We just had an actual UUID v4 collision...

news.ycombinator.com

Post reply on HN
Print view View original

341–350 of 369 posts

Re: Ask HN: We just had an actual UUID v4 collision...

#341

Post by connorgurney »

tomjakubowski wrote: post #171
LocalH wrote: post #151

Earlier quoted context omitted.

I'd believe it. What I'd find harder to believe is that it wasn't really a table with more information than just "list of assigned UUIDs". I'd be really surprised (pleasantly!) if it was only that. I'd figure most startups would make sure that table links to customer info so that they know which customer has a specific UUID, for easy searching and crossreferencing with the main db

That sort of table can be quite handy when every entity in the business's data stew is identified with a UUID, and there is no way of telling just from looking at an identifier what kind of entity it is. Particularly when the business has disparate databases and/or microservices with their own sets of UUIDs. In such businesses, inevitably, someone will ask you to run process X for widget 8dbcd950-14c1-4877-a8b0-90c08…

Stripe handle this interestingly, with a prefix to the ID indicating the type of entity.

https://dev.to/4thzoa/designing-apis-for-humans-object-ids-3...

Re: Ask HN: We just had an actual UUID v4 collision...

#342

Post by ralferoo »

stanmancan wrote: post #252
calfuris wrote: post #249

Earlier quoted context omitted.

The inclusion of a timestamp in v7 makes collisions impossible unless the generating systems think that the time is the same down to the millisecond, which makes the temporal distance quite relevant.

Plenty of systems end up generating multiple UUID's in a single millisecond. The issue with UUIDv7 is that you also have significantly less entropy since you only have a 62 bits (sometimes less, depending on implementation) of "random" data. So while the time aspect of format lowers the chances of collisions, generating two UUIDv7's in the same millisecond (depending on implementation) have a significantly higher cha…

I answered this in another HN topic just the other day: https://news.ycombinator.com/item?id=48061098

But essentially, using UUID v7 you actually have less risk of collisions than with UUID v4.

Because of the birthday paradox, if you have N bits of randomness, you can expect a collision approximately after (2^((N/2)-1)) random numbers.

With v4, you have 122 bits of entropy over all time, so will see a collision after 2^60 allocations, approx 1.2 x 10^18.

With v7, you sacrifice 48 bits of entropy to give you 74 bits of entropy every millisecond, so you will see a collision after approximate 2^36 allocations per millisecond, approx 6.8 x 10^10 per millisecond.

You could argue that the risk of a collision is too high per millisecond because it's likely that 68 billion UUIDs are generated every millisecond. And maybe I'd agree. But the counter argument is that with v4 you'd expect a collision after 2^24 milliseconds, or 280 minutes, allocating at the same rate of 68 billion UUIDs per millisecond.

Obviously "all time" is longer than "280 minutes", so v7 is actually statistically less likely to cause collisions than v4, even though it seems counter-intuitive because it has a smaller space devoted to entropy. The key insight is that the time provides bits that are guaranteed to be unique, so only collisions within the same timestamp are significant, and every bit used to provide known-unique values is worth 2 bits of entropy.

Re: Ask HN: We just had an actual UUID v4 collision...

#343

Post by stanmancan »

ralferoo wrote: post #342
stanmancan wrote: post #252

Earlier quoted context omitted.

Plenty of systems end up generating multiple UUID's in a single millisecond. The issue with UUIDv7 is that you also have significantly less entropy since you only have a 62 bits (sometimes less, depending on implementation) of "random" data. So while the time aspect of format lowers the chances of collisions, generating two UUIDv7's in the same millisecond (depending on implementation) have a significantly higher cha…

I answered this in another HN topic just the other day: https://news.ycombinator.com/item?id=48061098 But essentially, using UUID v7 you actually have less risk of collisions than with UUID v4. Because of the birthday paradox, if you have N bits of randomness, you can expect a collision approximately after (2^((N/2)-1)) random numbers. With v4, you have 122 bits of entropy over all time, so will see a collision after…

Sorry if I worded poorly but you’re definitely less likely to run into a collision with v7, but it’s not impossible, which is what I was trying to point out.

Thanks for a more articulate answer!

Re: Ask HN: We just had an actual UUID v4 collision...

#344

Post by iberator »

jandrewrogers wrote: post #95

This is surprisingly common. The security of UUIDv4 is based on the assumption of a high-quality entropy source. This assumption is invalidated by hardware defects, normal software bugs, and developers not understanding what "high-quality entropy" actually means and that it is required for UUIDv4 to work as advertised. It is relatively expensive to detect when an entropy source is broken, so almost no one ever does.…

what else so you suggest instead of uuuid4?

Re: Ask HN: We just had an actual UUID v4 collision...

#345

Post by iberator »

wpm wrote: post #274
BSVogler wrote: post #181

Earlier quoted context omitted.

I once read that noise of camera in total darkness is apparently a good source.

Would a CRT TV tuned to channel 3 and no RF input be a good source?

better to just switch to... random channel every while :) Not perfect but something.

Re: Ask HN: We just had an actual UUID v4 collision...

#347

Post by soni96pl »

erikerikson wrote: post #247
orf wrote: post #244

Earlier quoted context omitted.

AKA centralising a decentralised identifier generator?

There are better approaches like pre -avoiding collisions but generating tends to be more expensive than checking.

UUID is used where checking is difficult, think distributed devices offline at a plantation. How could checking be easier in that case? It would require infrastructure that doesn't exist. There are many other cases where it's easier to handle collisions.

Re: Ask HN: We just had an actual UUID v4 collision...

#348

Post by tommoneytools »

erikerikson wrote: post #247
orf wrote: post #244

Earlier quoted context omitted.

AKA centralising a decentralised identifier generator?

There are better approaches like pre -avoiding collisions but generating tends to be more expensive than checking.

   Wild edge case. Curious if they ever found the root cause.

Re: Ask HN: We just had an actual UUID v4 collision...

#349

Post by Schiendelman »

tgv wrote: post #292
Schiendelman wrote: post #187

Earlier quoted context omitted.

Same! It had validation on each number before adding them. Poor design, but that's how it worked.

I find this so hard to believe, but I've nearly always worked in small groups/companies. Can you, or any of the commenters above, explain why the reasoning that leads to such a service isn't rejected by, well, common sense? Some super-special requirements?

Sure. In this case, this started as a method with two parameters; each were validated internally before addition.

The validation was long running, as it required checking two other services to confirm both of the numbers were OK.

Because of issues calling those services, instead of two nasty synchronous calls, it turned into calling a microservice asynchronously and using a callback. Then that microservice was owned by the team that owned those two other services.

Don't underestimate the power of Conway's law.

Post reply on HN