Quelle est la qualité de l'UUID.randomUUID de Java?

311

Je sais que les UUID randomisés ont une probabilité de collision très, très, très faible en théorie, mais je me demande, en pratique, à quel point Java randomUUID()est bon en termes de non-collision? Quelqu'un at-il une expérience à partager?

java uuid Alvin
la source
10
D'après mon expérience, je n'ai jamais vu de collision ;-)
Thilo
4
Les algorithmes sont spécifiés dans RFC1422: ietf.org/rfc/rfc4122.txt
skaffman
8
@skaffman: le RFC ne dit absolument rien sur l'algorithme utilisé pour générer les chiffres aléatoires.
Michael Borgwardt
4
Puisqu'il s'agit d'une question plus ouverte, je suppose que je ne marquerai aucune réponse comme la bonne réponse; au lieu de cela, je donnerai un vote à chacune des réponses que je pense être bonnes :)
Alvin
5
De wikipedia: ... En d'autres termes, seulement après avoir généré 1 milliard d'UUID par seconde pendant les 100 prochaines années, la probabilité de créer un seul doublon serait d'environ 50%.
MaVRoSCy

Réponses:

168

UUID utilise java.security.SecureRandom, qui est censé être "cryptographiquement fort". Bien que l'implémentation réelle ne soit pas spécifiée et puisse varier entre les JVM (ce qui signifie que toutes les déclarations concrètes faites ne sont valables que pour une JVM spécifique), elle oblige la sortie à passer un test de générateur de nombres aléatoires statistiques.

Il est toujours possible qu'une implémentation contienne des bogues subtils qui ruinent tout cela (voir le bogue de génération de clé OpenSSH) mais je ne pense pas qu'il y ait de raison concrète de s'inquiéter du caractère aléatoire des UUID Java.

Michael Borgwardt
la source
34
"Il est toujours possible pour une implémentation de contenir des bogues subtils ..." - Ou (enfiler un chapeau en feuille d'étain) ... des défauts subtils délibérés. <:-)
Stephen C
25
La force cryptographique est totalement hors de propos pour la question des collisions.
osa
14
@osa: Ne pas produire de collisions (plus que ce à quoi on peut s'attendre d'un aléatoire parfait) est à peu près l'exigence de qualité la plus faible pour un RNG, tandis que la force cryptographique est la plus élevée. En d'autres termes, un RNG cryptographiquement fort ne produira certainement pas plus de collisions que prévu.
Michael Borgwardt
3
Il peut être utile de noter, cependant, que si vous exécutez par exemple une JVM produisant des UUID à l'intérieur de blogs.vmware.com/cto/… , vous obtiendrez probablement de très nombreuses collisions. Tous les RNG logiciels sont des PRNG, et ils ne sont finalement aussi bons que leur source d'entropie; deux PRNG qui sont définis de manière identique se comporteront également de manière identique, ce qui peut se produire de manière surprenante souvent avec des configurations de serveur et des procédures de démarrage cohérentes et en double exact.
user508633
@ user508633: Je m'attendrais en fait à obtenir un taux de collision de 100% dans ce cas spécifique, mais c'est un cas très spécifique qui va bien au-delà de "configurations de serveur et procédures de démarrage cohérentes et en double exact". Je suis sûr que vous n'obtiendrez pas de taux de collision plus élevés si vous cloniez simplement une machine virtuelle et l'utilisiez normalement. L'auto-amorçage de SecureRandom essaie assez fort d'obtenir une véritable entropie, au point de bloquer l'exécution s'il n'en trouve pas: seancassidy.me/wiggle-the-mouse-to-fix-the-test.html
Michael Borgwardt
114

Wikipedia a une très bonne réponse http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

le nombre d'UUID aléatoires de la version 4 qui doivent être générés pour avoir une probabilité de 50% d'au moins une collision est de 2,71 quintillions, calculé comme suit:

...

Ce nombre équivaut à générer 1 milliard d'UUID par seconde pendant environ 85 ans, et un fichier contenant ce nombre d'UUID, à 16 octets par UUID, serait d'environ 45 exaoctets, plusieurs fois plus grand que les plus grandes bases de données actuellement en existence, qui sont sur l'ordre de centaines de pétaoctets.

...

Ainsi, pour qu'il y ait une chance sur un milliard de duplication, 103 000 milliards d'UUID version 4 doivent être générés.

sheki
la source
56
Je citerais également cette page: "La probabilité d'un double serait d'environ 50% si chaque personne sur terre possède 600 millions d'UUID."
Jeff Axelrod
24
Cela n'est vrai que pour le vrai hasard, pas pour les nombres pseudo-aléatoires comme les UUID javas.
Markus
9
@Markus: complètement faux. La probabilité de collisions pour les bons RNG pseudo-aléatoires, en particulier cryptographiquement forts, n'est pas différente du "vrai" hasard.
Michael Borgwardt
6
@Eric - Je pense qu'il vous incombe de sauvegarder votre affirmation. FWIW, les seuls scénarios auxquels je peux penser où les UUID de type 4 entreraient en collision plus fréquemment que la théorie des probabilités dit qu'ils devraient être: 1) une mauvaise source de nombres aléatoires cryptographiques, ou 2) une bibliothèque UUID qui a été compromise.
Stephen C
13
Cela ne répond pas à la question posée. La question porte sur la qualité du caractère aléatoire dans Java UUID.randomUUID(), et non sur les chances théoriques pour un générateur de nombres aléatoires parfait donné.
kratenko
69

Quelqu'un at-il une expérience à partager?

Il existe 2^122des valeurs possibles pour un UUID de type 4. (La spécification indique que vous perdez 2 bits pour le type et 4 bits supplémentaires pour un numéro de version.)

En supposant que vous deviez générer 1 million d'UUID aléatoires par seconde, les chances qu'un doublon se produise au cours de votre vie seraient extrêmement faibles. Et pour détecter le doublon, vous devez résoudre le problème de la comparaison de 1 million de nouveaux UUID par seconde avec tous les UUID que vous avez précédemment générés 1 !

Les chances que quiconque ait connu (c'est-à-dire réellement remarqué ) un doublon dans la vie réelle soient encore plus petites que minuscules ... en raison de la difficulté pratique de rechercher des collisions.

Maintenant, bien sûr, vous utiliserez généralement un générateur de nombres pseudo-aléatoires, pas une source de nombres vraiment aléatoires. Mais je pense que nous pouvons être convaincus que si vous utilisez un fournisseur crédible pour vos nombres aléatoires de force cryptographique, alors ce sera la force cryptographique, et la probabilité de répétitions sera la même que pour un générateur de nombres aléatoires idéal (non biaisé) .

Cependant, si vous deviez utiliser une machine virtuelle Java avec un générateur de nombres aléatoires cryptés "cassé", tous les paris sont désactivés. (Et cela pourrait inclure certaines des solutions de contournement pour les problèmes de «pénurie d'entropie» sur certains systèmes. Ou la possibilité que quelqu'un ait bricolé avec votre JRE, soit sur votre système, soit en amont.)

1 - En supposant que vous avez utilisé "une sorte de btree binaire" comme proposé par un commentateur anonyme, chaque UUID va avoir besoin de O(NlogN)bits de mémoire RAM pour représenter Ndes UUID distincts en supposant une faible densité et une distribution aléatoire des bits. Multipliez maintenant cela par 1 000 000 et le nombre de secondes pendant lesquelles vous allez exécuter l'expérience. Je ne pense pas que ce soit pratique pour la durée nécessaire pour tester les collisions d'un RNG de haute qualité. Pas même avec des représentations intelligentes (hypothétiques).

Stephen C
la source
4
"(Et pour détecter le doublon, vous devrez résoudre le problème de la comparaison de 1 million de nouveaux UUID par seconde avec tous les UUID que vous avez déjà générés!)" - cette partie est relativement simple en supposant que vous avez stocké vos uuids dans certains sorte de structure d'arbre binaire, ce ne serait qu'une descente d'arbre par nouvel uuide. Vous n'auriez pas besoin de le comparer individuellement à tous les uuids générés précédemment.
user467257
20

Je ne suis pas un expert, mais je suppose que suffisamment de gens intelligents ont regardé le générateur de nombres aléatoires de Java au fil des ans. Par conséquent, je suppose également que les UUID aléatoires sont bons. Donc, vous devriez vraiment avoir la probabilité de collision théorique (qui est d'environ 1: 3 × 10 ^ 38 pour tous les UUID possibles. Quelqu'un sait-il comment cela change pour les UUID aléatoires uniquement? Est-ce 1/(16*4)de ce qui précède?)

D'après mon expérience pratique, je n'ai jamais vu de collision jusqu'à présent. J'aurai probablement une barbe étonnamment longue le jour où j'aurai ma première;)

sfussenegger
la source
10
De wikipedia: ... En d'autres termes, seulement après avoir généré 1 milliard d'UUID par seconde pendant les 100 prochaines années, la probabilité de créer un seul doublon serait d'environ 50%.
MaVRoSCy
1
En fait, Wikipédia dit que c'est pour les 85 prochaines années ... Je dis ne comptez pas dessus, quelqu'un quelque part a généré le même UUID que vous
smac89
12

Chez un ancien employeur, nous avions une colonne unique qui contenait un uuid aléatoire. Nous avons eu une collision la première semaine après son déploiement. Bien sûr, les chances sont faibles mais elles ne sont pas nulles. C'est pourquoi Log4j 2 contient UuidUtil.getTimeBasedUuid. Il générera un UUID unique pendant 8 925 ans tant que vous ne générerez pas plus de 10 000 UUID / milliseconde sur un seul serveur.

voyous
la source
2
Oui. Mais la question porte sur les UUID aléatoires (c'est-à-dire de type 4).
Stephen C
1
Il pose la question de la probabilité d'une collision. L'implication est qu'il veut être sûr de les éviter.
rgoers
1
(La collision était probablement due à une source aléatoire de hasard pour l'ensemencement des PRNG. Je pensais qu'il était possible qu'elle soit due au pur hasard.)
Stephen C
9

Le schéma de génération original pour les UUID consistait à concaténer la version de l'UUID avec l'adresse MAC de l'ordinateur qui génère l'UUID et avec le nombre d'intervalles de 100 nanosecondes depuis l'adoption du calendrier grégorien en Occident. En représentant un seul point dans l'espace (l'ordinateur) et le temps (le nombre d'intervalles), le risque de collision de valeurs est effectivement nul.

Alex2Ustas
la source
1
Cette explication me rend optimiste de ne pas voir de collisions dans la pratique. Pouvez-vous indiquer une référence pour cette déclaration (du code source serait encore mieux)?
Dragan Marjanović
Trouvé dans les spécifications ietf.org/rfc/rfc4122.txt . Ce serait néanmoins formidable de voir la mise en œuvre.
Dragan Marjanović
1
Ce schéma n'est cependant pas ce que Java implémente. Java implémente l'UUID de type 4, qui est purement aléatoire et n'inclut pas l'adresse MAC ni l'heure. Soit dit en passant, puisqu'il existe maintenant de nombreux périphériques physiques et virtuels où vous pouvez choisir votre adresse MAC, l'algorithme d'origine ne garantit pas l'unicité.
Søren Boisen
8

De nombreuses réponses discutent du nombre d'UUID qui devraient être générés pour atteindre 50% de chances de collision. Mais un risque de collision de 50%, 25% ou même 1% ne vaut rien pour une application où la collision doit être (pratiquement) impossible.

Les programmeurs rejettent-ils régulièrement comme «impossibles» les autres événements qui peuvent et se produisent?

Lorsque nous écrivons des données sur un disque ou une mémoire et les relisons, nous tenons pour acquis que les données sont correctes. Nous comptons sur la correction d'erreur de l'appareil pour détecter toute corruption. Mais le risque d'erreurs non détectées se situe en réalité autour de 2 à 50 .

Ne serait-il pas logique d'appliquer une norme similaire à des UUID aléatoires? Si vous le faites, vous constaterez qu'une collision "impossible" est possible dans une collection d'environ 100 milliards d'UUID aléatoires (2 36,5 ).

Il s'agit d'un nombre astronomique, mais des applications telles que la facturation détaillée dans un système de santé national ou l'enregistrement de données de capteurs haute fréquence sur un large éventail d'appareils pourraient définitivement se heurter à ces limites. Si vous écrivez le prochain guide de l'auto-stoppeur sur la galaxie, n'essayez pas d'attribuer des UUID à chaque article!

erickson
la source
À titre de comparaison, les chances de gagner un jackpot Powerball sont de 1 sur 300 millions, mais les ventes de 10 à 20 millions de billets sont typiques. Le fait est que beaucoup de gens définissent «impossible» comme quelque chose de moins d'une chance sur des centaines de millions.
erickson
4

Comme la plupart des réponses se sont concentrées sur la théorie, je pense que je peux ajouter quelque chose à la discussion en donnant un test pratique que j'ai fait. Dans ma base de données, j'ai environ 4,5 millions d'UUID générés à l'aide de Java 8 UUID.randomUUID (). Les suivants sont quelques-uns que j'ai découvert:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb


b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64


4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

S'il était vraiment aléatoire, la probabilité d'avoir ce type d'UUID similaires serait considérablement faible (voir modifier), car nous ne considérons que 4,5 millions d'entrées. Donc, bien que cette fonction soit bonne, en termes de non collision, pour moi elle ne semble pas aussi bonne qu'elle le serait en théorie.

Modifier :

Beaucoup de gens semblent ne pas comprendre cette réponse, je vais donc clarifier mon point: je sais que les similitudes sont "petites" et loin d'une collision complète. Cependant, je voulais juste comparer l'UUID.randomUUID () de Java avec un véritable générateur de nombres aléatoires, ce qui est la vraie question.

Dans un véritable générateur de nombres aléatoires, la probabilité que le dernier cas se produise serait d'environ = 0,007%. Par conséquent, je pense que ma conclusion est valable.

La formule est expliquée dans cet article wiki en.wikipedia.org/wiki/Birthday_problem

André Pinheiro
la source
6
Ce n'est pas vrai. Ce genre de similitudes se produirait même avec un véritable générateur de nombres aléatoires sur des uuides de 4,5M. Les similitudes entre les UUID que vous avez données sont petites et éloignées, oh si loin d'une collision complète.
user3711864
Je suis entièrement d'accord avec vous que les similitudes sont "petites" et loin d'être une collision complète. Cependant, je voulais juste comparer l'UUID.randomUUID () de Java avec un véritable générateur de nombres aléatoires (c'est la question). Avec certains calculs, nous pouvons voir que, dans un véritable générateur de nombres aléatoires, la probabilité que le dernier cas se produise serait d'environ 1-e ^ (- 4500000 ^ 2 / (2 * 36 ^ 11)) = 0,007% = 1 dans un 13k. Il faudrait que je sois très chanceux :)
André Pinheiro
1
Avec 4,5 millions d'objets et 1 chance sur 13 000, une collision partielle comme celle-ci ne serait-elle pas attendue 346 fois?
Ben Lee
Non @BenLee, j'ai calculé la probabilité que cet événement se produise étant donné que nous avons 4,5 millions d'articles. Ce n'est pas une chance sur 13k de se produire pour chaque élément. La formule que j'ai utilisée se trouve dans cet article wiki en.wikipedia.org/wiki/Birthday_problem
André Pinheiro
2
Quelle était votre attente? Semblable n'est pas pareil, n'est-ce pas?
Koray Tugay
3

Je joue à la loterie l'année dernière, et je n'ai jamais gagné ... mais il semble que la loterie ait des gagnants ...

doc: http://tools.ietf.org/html/rfc4122

Type 1: non implémenté. la collision est possible si l'uuid est généré au même moment. impl peut être synchronisé artificiellement afin de contourner ce problème.

Type 2: ne voyez jamais d'implémentation.

Type 3: hachage md5: collision possible (128 bits-2 octets techniques)

Type 4: aléatoire: collision possible (comme loterie). notez que l'impl jdk6 n'utilise pas un "vrai" aléatoire sécurisé car l'algorithme PRNG n'est pas choisi par le développeur et vous pouvez forcer le système à utiliser un algo PRNG "pauvre". Votre UUID est donc prévisible.

Type 5: hachage sha1: non implémenté: collision possible (160 octets techniques 2 bits)

Giher
la source
4
La probabilité de gagner à la loterie est peut-être de 1 sur 10 ou 100 millions (10 ^ 7 ou 10 ^ 8) ou quelque chose comme ça. La probabilité d'une collision avec un nombre aléatoire de 128 bits est de 3,4 * 10 ^ 28. Donnez-moi un billet de loterie à tout moment!
Stephen C
0

Nous utilisons l'UUID aléatoire de Java dans notre application depuis plus d'un an et cela très largement. Mais nous ne rencontrons jamais de collision.

Afsar
la source