Pourquoi les UUID n'entrent presque jamais en collision (même sans vérification)

Un UUID aléatoire standard est généré de façon indépendante, par un nombre quelconque de systèmes totalement non coordonnés entre eux, sans la moindre autorité centrale distribuant le prochain identifiant disponible et sans aucune vérification par rapport à une liste d'identifiants déjà utilisés — et malgré cela, les collisions sont, en pratique, quelque chose qui n'arrive jamais. C'est une affirmation véritablement audacieuse, qui repose entièrement sur la probabilité plutôt que sur la coordination, et comprendre pourquoi elle tient la route demande le même raisonnement mathématique contre-intuitif qui explique une énigme bien plus célèbre : combien de personnes faut-il réunir dans une pièce avant qu'il devienne probable que deux d'entre elles partagent la même date d'anniversaire.

Le paradoxe classique des anniversaires demande combien de personnes doivent se réunir dans une pièce avant qu'il y ait plus d'une chance sur deux que deux d'entre elles partagent leur date de naissance, et la réponse — seulement 23 personnes, contre 365 dates d'anniversaire possibles — surprend la plupart des gens, qui s'attendent intuitivement à un nombre bien plus proche de 365. La raison pour laquelle la véritable réponse est aussi petite tient au fait que la comparaison pertinente n'est pas « telle personne précise partage-t-elle mon anniversaire » mais « une paire quelconque, parmi toutes les paires possibles dans la pièce, partage-t-elle un anniversaire » — et le nombre de paires possibles croît bien plus vite que le nombre de personnes, puisqu'avec 23 personnes il existe déjà 253 paires distinctes, chacune constituant une occasion indépendante de coïncidence. Ce schéma mathématique précis — le nombre d'occasions de comparaison croissant de façon quadratique tandis que le nombre d'éléments ne croît que de façon linéaire — porte le nom de problème des anniversaires, et il s'applique directement à toute situation impliquant des valeurs aléatoires tirées d'un espace fixe et vérifiées pour détecter des doublons, les UUID en faisant tout à fait partie.

Un UUID aléatoire standard (version 4) puise dans un espace de 122 bits véritablement aléatoires — une poignée des 128 bits totaux sont fixés par la spécification même du format pour identifier la version — ce qui signifie que le nombre total de valeurs possibles est 2 puissance 122, un nombre presque incompréhensiblement grand. En appliquant le même raisonnement issu du paradoxe des anniversaires que pour l'exemple des 365 jours, mais à l'échelle de cet espace bien plus vaste, on obtient le point où une collision devient probable : il faudrait générer environ 2,7 trillions d'UUID avant que la probabilité qu'au moins deux d'entre eux entrent en collision atteigne environ 50 % — pour donner une idée de l'échelle, cela représente plus d'UUID qu'il n'y a de grains de sable estimés sur l'ensemble des plages de la Terre. Un seul système, ou même un grand nombre de systèmes combinés, générant des UUID à n'importe quel rythme réaliste, mettrait un temps dépassant très largement l'âge de l'univers pour approcher ce seuil, ce qui constitue la véritable base mathématique justifiant de traiter les collisions d'UUID comme quelque chose qui n'a pas besoin d'être vérifié en pratique.

L'UUID version 7, normalisé plus récemment spécifiquement pour produire des identifiants qui se trient dans un ordre à peu près chronologique, y parvient en plaçant un horodatage précis à la milliseconde dans les premiers bits de l'identifiant, plutôt que de remplir toute la valeur de données aléatoires comme le fait la version 4. Cela pourrait sembler affaiblir la garantie de résistance aux collisions, puisqu'une partie de la valeur est désormais prévisible plutôt qu'aléatoire — mais les bits restants continuent d'être remplis avec la même quantité de données véritablement aléatoires qu'auparavant, et comme deux UUID générés à la même milliseconde exacte ont quand même besoin que leur reste aléatoire coïncide parfaitement pour entrer en collision, la résistance pratique aux collisions demeure comparable à celle de la version 4 pour tout rythme de génération réaliste. Ce que la v7 change réellement, c'est une propriété différente et sans rapport — l'ordre de tri — et non les mathématiques de collision évoquées ici ; il vaut la peine de garder les deux notions bien distinctes : l'unicité provient de la simple taille de l'espace aléatoire, tandis que la triabilité provient de l'emplacement de l'horodatage au sein de la valeur.

Parce que la probabilité de collision est réellement, et pas seulement superficiellement, négligeable, des systèmes peuvent générer des identifiants de façon totalement indépendante — une application mobile fonctionnant hors ligne sans connexion réseau, une fonction serverless qui démarre et disparaît en quelques millisecondes, un millier d'instances de microservices s'exécutant en parallèle simultanément — sans la moindre coordination entre eux et sans aucun registre central suivant ce qui a déjà été émis, tout en conservant une attente mathématiquement solide qu'aucun de ces identifiants n'entrera jamais en collision avec un autre. C'est précisément la propriété qu'un identifiant séquentiel émis de façon centralisée ne pourrait jamais offrir sans qu'une autorité de coordination partagée ne ralentisse tout, et c'est l'entière raison pour laquelle les UUID aléatoires sont devenus le choix par défaut pour les systèmes distribués ayant besoin d'identifiants à un rythme qu'aucune étape de coordination ne pourrait suivre.