Outils de développement · Générateur UUID
Aléatoire UUID Clés primaires et fragmentation des arbres B : ce qui se passe réellement
· Pourquoi c'est important
uuid cryptographie API du navigateur
Des clés aléatoires v4 sont insérées dans des pages d'index aléatoires et les index clusterisés paient pour cela. Cet article explique le mécanisme, le coût de stockage du texte par rapport au binaire et les domaines dans lesquels les UUID ordonnés dans le temps changent la donne.
Les insertions ralentissent à mesure que la table s'agrandit : le symptôme qui incite les administrateurs de base de données à examiner leur choix de clé.
L'insertion d'une ligne avec un UUID aléatoire comme clé primaire dans une base de données avec un index clusterisé entraîne l'insertion par la base de données de la nouvelle ligne à un emplacement aléatoire dans la structure B-tree. Les clés séquentielles s'ajoutent à la page feuille la plus à droite, conservant toutes les insertions dans une petite zone résidant dans le cache. Des clés aléatoires dispersent les insertions sur l'ensemble de l'index, obligeant la base de données à parcourir et modifier des pages très éloignées les unes des autres dans le stockage physique. À mesure que la table s'agrandit et que l'arborescence s'approfondit, chaque insertion touche plus de pages et provoque davantage d'opérations I/O. L’opération qui paraissait bon marché au millier de lignes devient coûteuse au million. Il ne s'agit pas d'un problème théorique ; cela se manifeste par une dégradation mesurable du débit d’insertion.
Comment se remplit un arbre B groupé : les clés séquentielles s'ajoutent à la dernière page ; des touches aléatoires touchent des pages dans tout l'index
Le mécanisme est fondamental pour le fonctionnement des arbres B car ils maintiennent l'ordre des clés triées dans les pages feuilles. Lorsque vous insérez une ligne avec la clé 10,001 dans une table qui a déjà stocké les clés 1 à 10,000, la base de données sait où appartient cette ligne : à la fin, dans la page existante la plus à droite s'il y a de l'espace, ou dans une nouvelle page ajoutée à droite. Lorsque vous insérez une ligne avec un UUID aléatoire comme 7524fae2-7dec-11d0-a765-00a0c91e6bf6 dans la même table, la base de données doit parcourir l'arborescence pour trouver la page feuille contenant les clés dans cette plage UUID, localiser la position exacte dans cette page et insérer la ligne. Si cette page est pleine, elle est divisée, déplaçant la moitié de son contenu vers une nouvelle page et mettant à jour le nœud parent.
Divisions de pages et pression du cache : pourquoi l'insertion aléatoire coûte plus cher I/O et pourquoi l'effet augmente avec la taille de la table
Les clés aléatoires créent un modèle d'insertion dans le pire des cas, car chaque insertion atterrit à une position aléatoire dans l'arborescence au lieu de s'ajouter à la page la plus à droite. La base de données doit rechercher la bonne page, ce qui coûte généralement plusieurs lectures de page, une par niveau de l'arborescence. Ensuite, il doit modifier cette page, ce qui pourrait déclencher une scission qui se propage dans l'arborescence. Plus de pages sont modifiées, plus d'écritures ont lieu et le pool de mémoire tampon se remplit de pages provenant de différentes régions de l'arborescence plutôt que de rester concentré sur le point d'insertion actif. Les échecs de cache augmentent et I/O devient le goulot d'étranglement, le taux d'insertion se stabilisant à mesure que la table s'étend à des échelles plus grandes.
Texte ou binaire — Chaînes de caractères 36 par rapport aux colonnes uuid ou binaires natives de 16 octets (16) et effet sur la taille de l'index
Le coût n'est pas uniforme selon les moteurs de base de données, car différents systèmes optimisent différemment la gestion des pages. Les bases de données avec une compression agressive, des pages de petite taille ou un fonctionnement en mémoire peuvent présenter des différences de performances plus faibles entre les clés séquentielles et aléatoires. Les bases de données comportant des pages volumineuses, des disques mécaniques ou des limites de mémoire strictes connaîtront une dégradation spectaculaire. Le problème est observable et mesurable : mesurez les taux d'insertion sur 1,000 lignes, 100,000 lignes et 1,000,000 lignes. Si le taux par seconde chute fortement à des échelles plus grandes, vous subissez une pénalité d'insertion aléatoire avec votre matériel spécifique et votre configuration de base de données.
Alternatives ordonnées dans le temps : comment UUIDv7 et ULID conservent leur unicité lors de l'insertion à la fin de l'index Les
UUID sous forme de chaînes consomment 36 caractères sous forme de texte ou 16 octets sous forme de type binaire UUID en fonction du format de stockage choisi. Une chaîne de caractères 36 dans une colonne UTF-8 ou ASCII représente 36 octets, contre 8 octets pour un entier 64 bits. L'index d'une colonne string-UUID est trois fois plus grand qu'un index d'une colonne entière, en supposant qu'aucune technique de compression n'est appliquée. Des index plus grands signifient que moins de pages d'index tiennent dans le pool de mémoire tampon, ce qui signifie moins d'accès au cache lors du parcours de l'arborescence. Un index plus petit qui tient dans la RAM fonctionne mieux qu'un index volumineux qui doit être lu à partir du disque à chaque requête, quels que soient l'ordre d'insertion ou les modèles de charge de travail.
Exemple concret — la même charge de travail d'insertion décrite pour une clé aléatoire et une table de clés ordonnées dans le temps, qualitativement, sans références inventées
La différence de stockage est importante pour les index primaires et secondaires, car chaque index secondaire qui inclut la clé primaire doit stocker la valeur 36 complète du caractère UUID ou la valeur binaire 16 octets UUID. Cela rend les index secondaires considérablement plus grands que les index utilisant une clé entière pour les recherches de clé primaire. La réplication, les sauvegardes et les ensembles de résultats de requêtes augmentent tous proportionnellement à la taille de l'index. Le générateur ToolAcre UUID produit des valeurs compatibles binaires ; les stocker sous forme de types binaires (16) ou GUID en fonction de la base de données permet d'économiser de l'espace par rapport à varchar (36) et améliore l'efficacité du cache à tous les niveaux. Cette optimisation du stockage est essentielle pour les systèmes à grande échelle.
Ce que cela ne couvre pas : tables et bases de données organisées en tas où la clé primaire n'est pas clusterisée, où l'effet est moindre
Une optimisation courante consiste à stocker le UUID sous forme binaire en interne et à l'afficher sous forme de chaîne uniquement lorsque cela est nécessaire pour les API ou les interfaces utilisateur. Les opérations d'indexation et de jointure fonctionnent sous la forme binaire compacte ; la réponse API ou le code d'application est converti en représentation sous forme de chaîne. Certaines bases de données proposent des types GUID ou UUID intégrés qui gèrent automatiquement cette conversion. D'autres nécessitent des opérations de casting explicites. La différence de performances entre les colonnes 36-byte et 16-byte est réelle : une table avec un million de lignes et une clé de colonne 36-byte contre 16-byte UUID diffère de 20 MB par niveau d'index, ce qui peut faire la différence entre un index placé dans le cache L3 et nécessitant une récupération de mémoire.
À retenir : connaissez votre index avant de choisir une version – le générateur ToolAcre produit des UUID aléatoires ; utilisez le message pour décider si cela correspond à votre moteur de stockage
Le compromis entre les performances d'insertion, la taille de l'index et les caractéristiques des requêtes nécessite des décisions architecturales basées sur des modèles de charge de travail. Une clé de chaîne séquentielle pourrait être rapide à insérer si les chaînes sont ascendantes, par exemple des chaînes basées sur un horodatage, mais consommerait le même espace que des UUID aléatoires et divulguerait des informations temporelles. Un UUID aléatoire est sémantiquement plus propre et n'a aucun composant d'horodatage à fuir, mais est plus lent à insérer dans un index clusterisé et plus volumineux en termes de stockage global. Les alternatives ordonnées dans le temps comme UUIDv7 combinent les avantages en conservant la localité d'insertion tout en évitant les fuites d'horodatage dans les identifiants aléatoires de la version 4.