4 ms·
Ever see a UUID collision?
by Waterluvian 3y ago
Ever see a UUID collision?
- mabbo 3y agoEven at a billion requests per second, 128 bit UUIDs shouldn't collide for something like a billion years. And that's if you're going completely random and not taking care to try to reduce collisions.
- Dylan16807 3y agoAre you sure about that math? A billion seconds at a billion requests per second is already 2^60 items. You'd only need a few billion seconds to have a 50:50 collision chance with 128 random bits, and even less with a real UUID that only has 122 random bits. You'd hit 1% odds of collision after less than a decade. If you actually want to go for a billion years, you need to expand that UUID by 50%.
- danielmarkbruce 3y agoThis seems off. A few billion seconds to have a 50:50 chance? Why wouldn't it be a billion seconds at a billion per second (2^60 total requests) would give a 1 in 2^68 chance (or 1 in 2^62 if its really only 122 bits)?
- Dylan16807 3y agoBirthday paradox. The number of opportunities to collide is the number of items squared. (Divided by two and a smidge)
- danielmarkbruce 3y agoLol. I must be brain dead. Yes.
- penteract 3y agoBecause we're talking about collisions, as opposed to comparing 2^64 independent pairs. With 2^128 possible values, if you've picked 2^63 distinct ones, the chance that a randomly selected value collides with one of those is 1 in 2^65. If none of your second batch of 2^63 collide with each other, that gives a 2^63/2^65 = 1/4 chance of one of them colliding with the first batch. Considering the possibility of collisions within each batch of 2^63 brings it closer to 1 in 2.
- mabbo 3y agoYou know I think I converted powers of two and powers of ten interchangeably in my calculations. You're very likely correct.
- jandrewrogers 3y agoThere have been many cases of UUIDv4 collisions because an RNG wasn’t as random as expected, due to broken RNG or developer error. It is one of those cases where practice is not as reliable as theory, and it is banned in some places as a consequence. It depends on how paranoid you need to be.
- polynomial 3y agoFacts.
- MichaelZuo 3y agoNIST standards on RNG are not as random as expected? Or do you mean certain folks intentionally chose substandard implementations for some reason?
- jandrewrogers 3y agoA significant number of implementers roll their own UUIDv4. It seems so easy so why not? Most UUIDs are used in contexts where the devs are not that sophisticated so it isn’t that surprising that naive mistakes happen. If you are using it for distributed UUID generation, it just takes one person making a mistake to create havoc. UUIDv4 is banned in many high security environments primarily because it is easy for people to screw up in practice and it is difficult to detect when those mistakes are made. 128-bits doesn’t leave much room for mistakes using probabilistic uniqueness.
- lazide 3y agoShouldn’t != never happens. All sorts of weird implementation issues can cause problems.
- cmckn 3y agoEh, UUID’s are usually not truly global anyway; so you’d need a collision in the context of a single region, cell, user, resource, etc. for it to matter.
- deleted 3y ago[deleted]
- kortilla 3y agoHow did you know it was a double bit flip and not just BGP bug or an in memory bit flip before being sent to the socket?
- abwizz 3y ago> two bit flips in the same tcp packet cancel each other out and cause the checksum to pass checksum != parity check not sure if there even exists a chance for this to happen
- raverbashing 3y agoWow this is at the level of Homer Simpson "Cereal with Milk catching fire" But yeah, mathematically possible (in AWS scale, but still) so of course it will happen once in a lifetime.