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

241–250 of 369 posts

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

#241

Post by nubinetwork »

AntiUSAbah wrote: post #18
mittermayr wrote: post #4

I fully agree. It makes no sense. Yet... The only guesses I'm having is that we originally generated UUIDv4s on a user's phone before sending it to the database, and the UUID generated this morning that collided was created on an Ubuntu server. I don't fully know how UUIDv4s are generated and what (if anything) about the machine it's being generated on is part of the algorithm, but that's really the only change I can…

You let users generate a UUID? To be honest, the chance that you are doing something weird is probably higher than you experiencing a real UUID conflict. How did your database 'flag' that conflict?

The smart way would be to check if the id is in use, and generate a new one... Repeat a few times if you're extremely unlucky, and bail out with an error if you have the absolute worst rng. It also works for locally generated ids as well.

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

#243

Post by QuercusMax »

I lost all confidence in the infallability of software RNG when I was working on an assignment for Data Structures a million years ago (2000?). The assignment was simple: simulate a 2D random walk where you randomly go NSEW, and run 100 cases, collecting stats as to how long it takes to return to the origin.

Super easy assignment, wrote it up probably in C++ (maybe just C?), and ran it on my linux box (probably Debian potato). It finished super quick and gave me an average of like 5.6 steps to return to the origin or something. Cool!

I copied it over to my account on the department's HP-UX machines where I was supposed to run and submit it to my instructor. Compiled fine. And then it... just ran forever. I was doing rand() % 4 or something, and the HP-SUX RNG had crazy bias in its last 2 bits, and it just walked away forever, never returning to the origin. Well crap!

Got an A for my writeup, though!

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

#244

Post by orf »

erikerikson wrote: post #239
jandrewrogers wrote: post #201

Earlier quoted context omitted.

A collision is simple to detect but it requires you to actually check, which is expensive at scale. The entire point of UUIDv4 is that you don't have to check for collisions because it should never happen. But if you don't check and it does happen you are in UB territory which is generally very bad. A risk of collision before it happens is non-trivial to detect but this is really what you'd want.

Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.

AKA centralising a decentralised identifier generator?

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

#245

Post by jandrewrogers »

erikerikson wrote: post #239
jandrewrogers wrote: post #201

Earlier quoted context omitted.

A collision is simple to detect but it requires you to actually check, which is expensive at scale. The entire point of UUIDv4 is that you don't have to check for collisions because it should never happen. But if you don't check and it does happen you are in UB territory which is generally very bad. A risk of collision before it happens is non-trivial to detect but this is really what you'd want.

Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.

You must have missed the “at scale” part. There is nothing inexpensive about extra network hops, cache misses, and page faults implied by your solution. Indexing at scale is almost always lossy for performance reasons. The location where you insert a new record is frequently not the same location as where you have to search for an existing record.

It is resource amplification all the way down. In a lot of systems that index these keys the cost of that check is several times that of doing a blind insert.

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

#246

Post by erikerikson »

jandrewrogers wrote: post #245
erikerikson wrote: post #239

Earlier quoted context omitted.

Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.

You must have missed the “at scale” part. There is nothing inexpensive about extra network hops, cache misses, and page faults implied by your solution. Indexing at scale is almost always lossy for performance reasons. The location where you insert a new record is frequently not the same location as where you have to search for an existing record. It is resource amplification all the way down. In a lot of systems tha…

No I didn't miss it.

DynamoDb works fine, using CQRS if necessary.

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

#247

Post by erikerikson »

orf wrote: post #244
erikerikson wrote: post #239

Earlier quoted context omitted.

Only expensive if you have unsorted keys or lack an index. Neither of which are unscalable.

AKA centralising a decentralised identifier generator?

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

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

#248

Post by orf »

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.

In what world is generating a UUID more expensive than checking for duplicates? at any scale?

Walk me through that please

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

#249

Post by calfuris »

ffsm8 wrote: post #173
ryanmonroe wrote: post #169

Earlier quoted context omitted.

The scenario in this post is that the first uuid was created one year before the duplicate uuid. That isn’t possible with v7

You're heavily leaning on "collision like this" to relate to the exact time stamps for your statement to be true. It's equality possible to interpret the "like this" to the collision itself, without a focus on the 1 year distance between the creation dates. So I guess both views are valid.

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.

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

#250

Post by erikerikson »

orf wrote: post #248
erikerikson wrote: post #247

Earlier quoted context omitted.

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

In what world is generating a UUID more expensive than checking for duplicates? at any scale ? Walk me through that please

Yeah, that was a little sloppy but it's generating is more expensive than not generating. In more words, generating an id and validating uniqueness is more expensive than only validating uniqueness.
Post reply on HN