Version 1 UUIDs only use a random number (16 bits) in the case of an uninitialized clock sequence (a case which, ideally, should only occur the first time a device generates a UUID). Version 1 UUIDs especially avoid using random numbers; they are also not a shortening of longer input.
In short, version 1 UUIDs are not a PRNG scheme, nor are they the same as hash functions. I'm not a mathematician, and it's been a while since I've read the relevant RFC, but I believe collisions in a proper, strict implementation of V1 UUIDs are impossible by design until either a) the 60-bit timestamp overflows, or b) the MAC address namespace is exhausted. It's not a matter of probability, and it's only "a certainty" after the end of their design lifetime. Of course, UUIDs being of finite size, they will eventually be exhausted, and a single machine may only generate 65536 identifiers in a 100-nanosecond span of time. They will not, however, collide. On November 24, 2017 8:58:02 PM EST, Jean-Christophe Deschamps <j...@antichoc.net> wrote: > >At 23:49 24/11/2017, you wrote: > >>On 11/24/17 5:26 PM, Jean-Christophe Deschamps wrote: >> >>>At 22:38 24/11/2017, you wrote: >>>>One proof of the falsehood of your assertion is that we CAN fill a >>>>database with some data using UIDs, and we will almost certainly not > >>>>get a collision, while you assertion we will. >> >>>This is an attempt at "proof by example". Keith is perfectly right >>>--mathematically speaking-- and your "proof" doesn't hold water, I >>>mean as a formal proof. The best proof that your "proof" isn't a >>>proof is that you feel obliged to add "almost certainly". >> >>DISproof by example is a perfectly valid method. If someone makes a >>claim that something is ALWAYS true, ONE counter example IS a >>disproof. I said almost certainly as the chance of a collision isn't 0 > >>(to be able to say with certainty) but is most defintely less than the > >>100% claimed. > >You're confusing one mathematical theorem and one practical statement. >The first is the _mathematical_ fact that any PRNG (using any fixed >number of random bits, which is what xUIDs are) will provide an >infinite number of collisions with probability 1. This is definitely >true. Of course here, the number of samples is implicitely infinite. > >Your practical statement is that you can "most certainly" ignore the >possibility of collision when feeding 2^N xUIDs into a unique column >without loosing sleep. That's good enough in practice. The issue with >your "demonstration" is that 2^N is bounded, whatever finite N you >choose. Hence you don't contradict what Keith said, you just say >something different applying to restricted cases. You're speaking about > >practice, while Keith told about math. You're both right, each from his > >own point of view. But you can't claim to disproof a trivially true >theorem this way, by changing its premices. > >An event with probability 10^-100000...000 (any finite number of >zeroes) will occur at least once, provided you run enough tries. It'll >occur an infinite number of times if you run an infinite number of >tries. Else its probability would be zero. >Your "disproof" amounts to say that 10^-100000...000 = 0 > >And neither Keith nor I ever said that an xUID collision will occur >with probability 1 after 2^64 samples. That would be false and that's >why people feel free to use xUIDs _AND_ sleep quietly. > >JcD > >_______________________________________________ >sqlite-users mailing list >sqlite-users@mailinglists.sqlite.org >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users -- Sent from my Android device with K-9 Mail. Please excuse my brevity. _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
