- Sur les systèmes modernes où plusieurs cœurs physiques lisent l’horloge simultanément, même les horodatages à la nanoseconde se chevauchent facilement : lors de mesures simultanées sur 4 cœurs physiques, environ 5 % de l’ensemble des échantillons entraient en collision
- Les conceptions qui utilisent des horodatages bruts comme des identifiants uniques sont risquées, et la fréquence des collisions varie selon le système d’exploitation et le mode d’exécution
time.Now()en Go enregistre à la fois l’heure absolue et un temps relatif basé sur une horloge monotone, ce qui permet de distinguer les écarts entre appels successifs des doublons d’horodatages absolus- Sous Linux avec un seul thread, le temps augmentait toujours et l’incrément minimal était de 32 ns, mais lorsque les threads étaient séparés, une même heure absolue était observée
- Sous Mac OS X, l’heure absolue a une résolution à la microseconde, ce qui entraîne beaucoup plus de collisions, et il arrive fréquemment que l’horloge monotone ne progresse pas, même avec un seul thread
Fréquence des collisions révélée par les lectures simultanées
- La question centrale est de savoir à quelle fréquence les collisions d’horodatages à la nanoseconde se produisent réellement sur les systèmes modernes
- Lorsque l’horloge est lue simultanément sur 4 cœurs physiques, environ 5 % de l’ensemble des échantillons entrent en collision
- Même en n’utilisant que 2 threads sur un système à 4 cœurs, environ 2 % des horodatages se chevauchent
- Il n’est donc pas sûr de supposer que de simples horodatages bruts à la nanoseconde suffisent à créer des ID uniques
Méthode de test et différences selon le système d’exploitation
- Le programme de test est écrit en Go
time.Now()en Go enregistre à chaque appel une heure absolue et un temps relatif basé sur une horloge monotone- Le test compare l’écart relatif entre horodatages successifs
- Il vérifie aussi les doublons de l’horodatage absolu lui-même
-
Linux
- Avec un seul thread, l’heure absolue et le temps monotone augmentent toujours
- L’incrément minimal sur le système de mesure était de 32 ns
- Entre threads, l’heure absolue était exactement identique à celle d’un autre thread dans environ 5 % des cas
-
Mac OS X
- L’heure absolue ayant une résolution à la microseconde, le même test produit de très nombreuses collisions
- Même avec un seul thread, il a souvent été observé que l’horloge monotone ne progressait pas
1 commentaires
Avis sur Hacker News
Utiliser des ID qui combinent un élément temporel et un numéro de séquence est une façon d’éviter ce genre de problème.
Par exemple, UUIDv7 contient un élément temporel à la milliseconde, un champ qui s’incrémente pour chaque événement dans la même milliseconde, ainsi que suffisamment de bits aléatoires pour rendre astronomiquement faible la probabilité de collision entre des ID générés sur des machines différentes.
Bien sûr, le nombre de bits est fini : s’il y a trop d’événements dans le même intervalle de temps, la séquence peut déborder ; des collisions entre machines peuvent réellement se produire ; et l’opération d’incrément peut nécessiter une synchronisation CPU, ce qui peut limiter le débit de génération d’événements.
Malgré tout, aux échelles rencontrées en pratique, UUIDv7 fonctionne très bien.
Je n’arrive pas vraiment à trouver sur Internet depuis quand UUIDv7 existe.
Il ne fait que consommer des bits dans l’UUID et contribue peu à l’entropie.
Ce n’est pas encore intégré au cœur, mais il existe plusieurs excellentes extensions pg qui fournissent uuidv7, en plus de l’utiliser directement au niveau applicatif.
Ce n’est pas seulement difficile à comprendre : même les distinguer visuellement les uns des autres est très pénible.
C’est pourquoi, dans certains cas, un identifiant qui ne contient aucune information ni aucun bruit au-delà du strict nécessaire peut être utile.
Un compteur incrémental qui déborde d’une manière ou d’une autre, plus quelques bits aléatoires, suffit généralement ; et avec une bonne implémentation, les deux peuvent se faire sans branchement.
À ce sujet, j’ai été autrefois program manager du journal des événements de sécurité de Windows.
Sur un système multicœur, lorsque des choses se produisent en même temps ou à des instants très proches, l’ordonnancement des threads peut fortement influencer ce que l’on observe.
Par exemple, le quantum d’un thread peut se terminer avant qu’il n’atteigne l’appel système qui récupère l’horodatage, ou avant qu’il ne transmette le tampon dans lequel mettre l’événement en file afin de l’horodater plus tard.
En pratique, sur les systèmes multiprocesseurs Windows des années 2000, il était très courant de voir des entrées du journal des événements apparaître dans le désordre, et on ne pouvait pas non plus faire une confiance trop fine à la précision des horodatages des logs.
La borne inférieure sûre était en fait d’une seconde, et je me souviens que certains composants tronquaient ou arrondissaient les horodatages.
Si vous avez besoin d’un identifiant unique, utilisez un UUID version 4, c’est-à-dire un UUID aléatoire.
La probabilité de collision est comparable à celle qu’un dinosaure adulte apparaisse soudainement dans votre chambre à cause de fluctuations quantiques.
Plus sérieusement, si c’est possible, une bonne vieille valeur incrémentale est probablement ce qu’il y a de mieux.
C’est rapide et peu coûteux, en particulier dans les bases de données, mais cela pose des problèmes de confidentialité et de sécurité, car on peut déduire des informations à partir de la valeur de l’ID.
Dans ces cas-là, ou lorsqu’on travaille avec des systèmes distribués, les UUID sont préférables.
Même si la résolution est à la nanoseconde, je me demande quelle est la précision réelle de l’horloge d’un ordinateur.
J’ai du mal à imaginer qu’elle soit réellement de l’ordre de la nanoseconde, et cela me rappelle l’époque où, en cours de travaux pratiques de physique, je répétais aux étudiants que le plus petit chiffre affiché par un instrument de mesure n’est pas la même chose que son exactitude.
Cela ne veut pas dire pour autant qu’elle soit exacte à ce niveau, et sur un système multicœur, les horloges des différents cœurs peuvent ne pas être synchronisées à ce degré.
ARMv8 garantit que l’horloge s’incrémente au moins à 1 GHz, mais avec Intel et les anciens ARM, c’est plus compliqué.
La VM BEAM d’Erlang/Elixir met très clairement cette différence en évidence. C’est la distinction entre croissance monotone et croissance strictement monotone
https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
« Dans une séquence de valeurs croissantes monotones, toute valeur ayant une valeur précédente est supérieure ou égale à cette valeur précédente »
C’est disponible via la fonction https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
https://www.erlang.org/doc/apps/erts/time_correction.html#st...
« Dans une séquence de valeurs strictement croissantes monotones, toute valeur ayant une valeur précédente est supérieure à cette valeur précédente »
Une valeur strictement monotone implique une forme de synchronisation ou de coordination, avec un coût en performances lorsqu’il y a beaucoup de processus concurrents
Cette fonctionnalité est fournie par la fonction https://www.erlang.org/doc/man/erlang.html#unique_integer-1, et la documentation avertit elle aussi que les valeurs strictement croissantes monotones sont intrinsèquement coûteuses à générer et se passent mal à l’échelle ; il ne faut donc passer le modificateur
monotonicque si c’est vraiment nécessaireAutrement dit, c’est similaire à UUIDv1 ou à https://en.wikipedia.org/wiki/Snowflake_ID
On n’a réellement besoin d’identifiants globaux strictement monotones que lorsqu’il faut immédiatement déterminer de façon cohérente le premier/dernier écrivain gagnant
Si l’on peut plutôt utiliser un premier/dernier écrivain gagnant à cohérence éventuelle, par exemple si les événements d’écriture entrent dans un journal d’événements ou une file où ils sont linéarisés par ID, et que parmi les écritures « simultanées » on peut ne garder que celle dont l’ID a la priorité la plus élevée puis jeter les autres pendant le traitement ou à la lecture, j’envisagerais d’abord une paire compacte
(nodeID, seq)Si un ordre global des événements est nécessaire, il vaut particulièrement la peine d’envisager une forme d’ID Snowflake comme
(timestampMajor, nodeID, timestampMinor, seq)FreeBSD n’a pas
CLOCK_MONOTONIC_RAW, donc je l’ai mis en commentaire et ça semble correctJe pensais que s’il y avait des collisions, certains timestamps devaient se répéter, mais je n’arrive pas à en provoquer
clock_getres(CLOCK_REALTIME, ...)=1 ns,clock_getres(CLOCK_MONOTONIC, ...)=1 ns, et même sur 30 échantillons l’écart continuait d’augmenter, grosso modo dans une plage de 29 à 71 nsAu final, j’ai l’impression qu’on finit à un moment par tomber sur un problème d’architecture de jeu d’instructions
Un CPU à 3 GHz dispose de 3 cycles d’horloge par nanoseconde
Avec les optimisations du compilateur, il paraît tout à fait possible que des appels assembleur lisant le registre d’horloge se retrouvent accolés les uns aux autres
Si des appels successifs à
time.Now()se produisent en moins de 3 cycles d’horloge, est-il vraiment raisonnable d’attendre une précision à la nanoseconde réellement unique ?Même si les collisions restent assez rares, en avoir quelques-unes par jour est bien pire que « cela n’arrive presque jamais »
Cela me rappelle une légende au sujet de Lotus Notes
Il paraît qu’autrefois, ils utilisaient comme identifiant unique des timestamps avec une résolution d’une seconde
En cas de collision, ils ajoutaient simplement 1 seconde, et les collisions sont finalement devenues si nombreuses que les éléments se sont retrouvés avec des heures dans le futur
Un temps absolument exact est un problème de sécurité
Pour empêcher une prévisibilité parfaite, les concepteurs de CPU introduisent volontairement du jitter dans l’horloge depuis très longtemps, déjà à l’époque des Alpha de DEC
Même sur x86, si l’on exécute l’opération 3 ou 4 fois, que l’on stocke les valeurs dans des registres puis qu’on les affiche à la fin, on devrait voir que les écarts de temps ne sont pas exactement identiques
Je n’arrive pas à trouver grand-chose en cherchant, et si cela inclut les premiers x86, je trouve surprenant qu’on ait identifié si tôt les problèmes de sécurité liés aux horloges exactes
Personnellement, je pense que je n’aurais pas connu ce problème avant ce millénaire, et que j’aurais supposé que le jitter d’horloge observé s’expliquait par des choses comme les interruptions
Je ne dis pas que c’est faux, j’aimerais simplement en savoir plus
J’ai vu trop de gens être surpris par des collisions de timestamps à la milliseconde ou à la microseconde
Le cas le plus mémorable, et celui que j’ai le plus détesté, était une façon d’assembler un timestamp avec deux appels système
Un appel pour les chiffres de poids fort, l’autre pour les chiffres de poids faible ; mais à cause de la préemption du processus, si les chiffres de poids faible passent de 99x à 00x après la lecture des chiffres de poids fort, on peut produire un timestamp antérieur à la cause même qui a créé une entité
Certaines portions de code cassent alors de façon spectaculaire, et j’ai vu au moins deux boucles infinies à cause de ça
Si l’on ne mémorise pas que c’est quelque chose à toujours éviter, les tests passent dans 99,5 % des cas, et il faut quelqu’un avec un très bon sens du pattern matching pour remarquer que « le même test est passé au rouge une fois par semaine pendant un mois et demi »
C’est beaucoup trop longtemps pour laisser une bombe logique survivre dans du code CI/CD avant qu’elle soit corrigée