Les risques des clés primaires UUID dans SQLite

 (andersmurphy.com)
1 points par GN⁺ 4 시간 전 | 1 commentaires | Partager sur WhatsApp
  • L’implémentation des clés primaires dans SQLite produit un ordre de stockage physique différent entre les tables rowid classiques et les tables WITHOUT ROWID, et l’utilisation de UUID4 aléatoires comme index clusterisé entraîne un rééquilibrage du B-tree et des coûts de pagination supplémentaires
  • La référence avec un rowid entier atteint environ 1 million d’insertions par seconde par lots de 1 million de lignes, tandis que UUID4 WITHOUT ROWID enregistre des temps d’insertion 14 à 16 fois plus lents
  • Le caractère non ordonné d’UUID4 provoque des insertions de lignes aléatoires dans le B-tree, et le profilage montre davantage de temps passé à l’équilibrage de l’arbre ainsi qu’aux lectures et écritures
  • UUID7 WITHOUT ROWID réduit les problèmes de tri d’UUID4 grâce à son ordre temporel et affiche des temps d’insertion plus raisonnables, mais reste plus lent qu’une clé entière de 8 octets car la clé BLOB fait 16 octets
  • UUID4 WITH ROWID profite du caractère séquentiel du rowid caché, mais l’amplification d’écriture due aux deux index et le coût des insertions aléatoires dans l’index demeurent, ce qui le rend moins performant que UUID7 WITHOUT ROWID

Qu’est-ce qu’un index clusterisé ?

  • Un index clusterisé détermine l’ordre de stockage physique des lignes d’une table
  • Comme les lignes ne peuvent être physiquement triées que d’une seule manière, chaque table ne peut avoir qu’un seul index clusterisé
  • L’index clusterisé est la table elle-même, tandis qu’un index non clusterisé ne stocke que les colonnes indexées et un pointeur vers l’emplacement des données réelles

Rowid

  • Toutes les tables SQLite classiques possèdent une clé primaire entière implicite sur 64 bits appelée rowid
  • Les données de la table sont stockées dans une structure B-tree avec une entrée par ligne, en utilisant la valeur rowid comme clé
  • En pratique, rowid est l’index clusterisé de SQLite, et l’ordre de stockage physique des lignes suit l’ordre des rowid
Publicité

WITHOUT ROWID

  • SQLite prend en charge les tables WITHOUT ROWID, qui n’ont pas de rowid implicite
  • Dans une table WITHOUT ROWID, la clé primaire déclarée joue le rôle d’index clusterisé
  • Les tables SQLite rowid sont implémentées sous forme de B*-tree où tout le contenu est stocké dans les feuilles, tandis que les tables WITHOUT ROWID utilisent un B-tree classique qui stocke du contenu à la fois dans les feuilles et dans les nœuds intermédiaires

Référence : clé primaire entière rowid

  • La référence mesure le temps d’insertion par lots de 1 million de lignes dans une table rowid classique de structure id INTEGER PRIMARY KEY, data BLOB
  • Le tableau de résultats couvre un total de 10 millions à 100 millions de lignes, avec des temps mesurés allant de 692 ms à 838 ms
  • La performance de référence se situe autour d’environ 1 million d’insertions par seconde

UUID4 WITHOUT ROWID

  • Le test UUID4 insère des valeurs random-uuid4-bytes comme clé primaire dans une table WITHOUT ROWID de structure id BLOB PRIMARY KEY, data BLOB
  • Dans le tableau de résultats, le temps mesuré est de 2649 ms à 10 millions de lignes et de 12586 ms à 100 millions de lignes
  • Les performances d’insertion sont 14 à 16 fois plus lentes que la référence avec rowid entier

Profilage

  • Le diffgraph normalisé compare les instantanés de profilage de INTEGER et UUID4, et affiche les différences sous forme de flamegraph
  • La vue normalisée ajuste le nombre total d’échantillons des deux profils pour visualiser les écarts relatifs en pourcentage
  • Les cadres bleus indiquent que, dans le second profil UUID4, le temps passé dans la fonction correspondante a diminué par rapport à INTEGER, tandis que les cadres rouges indiquent qu’il a augmenté dans UUID4
  • L’intensité de la couleur représente la variation relative du nombre d’échantillons du cadre lui-même, c’est-à-dire la variation du self time
  • Le diffgraph montre davantage de temps consacré au rééquilibrage de l’arbre ainsi qu’aux lectures et écritures
  • En raison du caractère non ordonné d’UUID4, les clés sont disposées dans un ordre aléatoire, ce qui oblige SQLite à rééquilibrer en permanence le B-tree
Publicité

UUID7 WITHOUT ROWID

  • UUID7 est un UUID ordonné dans le temps, ce qui permet d’éliminer les problèmes de tri d’UUID4
  • Le test UUID7 est lui aussi exécuté sur une table WITHOUT ROWID de structure id BLOB PRIMARY KEY, data BLOB
  • Dans le tableau de résultats, le temps mesuré est de 1372 ms à 10 millions de lignes et de 1258 ms à 100 millions de lignes
  • UUID7 WITHOUT ROWID revient à des valeurs plus raisonnables qu’UUID4 WITHOUT ROWID, mais reste malgré tout plus lent que la référence
  • Une clé primaire UUID en BLOB fait 16 octets, contre 8 octets pour une clé primaire entière

UUID4 WITH ROWID

  • Le test UUID4 WITH ROWID utilise une table id BLOB PRIMARY KEY, data BLOB sans WITHOUT ROWID
  • Dans cette configuration, le rowid caché est l’index clusterisé, et son avantage est d’être séquentiel
  • L’inconvénient est que la table se retrouve avec deux index, d’où une amplification d’écriture
  • Dans le tableau de résultats, le temps mesuré est de 2003 ms à 10 millions de lignes et de 7119 ms à 100 millions de lignes
  • UUID4 WITH ROWID n’est pas aussi performant que UUID7 WITHOUT ROWID, car même sans être l’index clusterisé, l’index doit toujours être construit via des insertions aléatoires

Conclusion

  • Dans SQLite, les clés primaires UUID sont un choix dont l’impact sur les performances d’insertion peut fortement varier selon l’index clusterisé et l’ordonnancement des clés
  • Le problème des UUID aléatoires ne se limite pas à SQLite et s’étend aussi à d’autres bases de données utilisant des index clusterisés
  • L’ensemble du code du benchmark est disponible dans le dépôt GitHub

À lire aussi

1 commentaires

 
GN⁺ 4 시간 전
Avis sur Lobste.rs

  • Bien. Il serait aussi intéressant de voir les chiffres quand, dans une table rowid, la clé entière n'est pas monotone croissante mais aléatoire
    Un point important manquant dans l'article est que l'index primaire d'une table rowid est un arbre B+, alors qu'une table without rowid utilise un arbre B
    Donc, en général, dès que la taille moyenne des enregistrements dépasse un certain seuil, la seconde option n'est pas idéale. En effet, les nœuds internes de l'index stockent l'enregistrement complet et, si je me souviens bien, le manuel de SQLite donne comme règle empirique 1/20 de la taille de page

  • Ils ont mis tant d'efforts à mesurer les performances des UUID, mais ils n'ont pas pris en compte les clés naturelles
    Qu'il s'agisse d'entiers, d'UUID ou d'une autre forme, les clés de substitution ajoutent de la complexité, n'apportent aucune information et masquent des erreurs de normalisation
    L'auteur dit qu'il utilise des UUID pour « éviter les doublons », mais ce n'est pas une raison. Dans toute base de données, chaque ligne de chaque table doit avoir au moins une clé, c'est-à-dire un ensemble de colonnes qui identifie cette ligne de manière unique
    Une base de données sans une telle clé contient des informations dupliquées et est vulnérable aux incohérences logiques. Si cette clé existe déjà, il n'y a pas besoin de clé de substitution. Si une clé naturelle existe déjà et est bien imposée, l'argument « il en faut pour les performances » implique un coût supplémentaire et une complexité inutile, donc il doit être démontré

    • Je manque peut-être d'imagination, mais quand on traite des données issues du monde réel, il est en général difficile de trouver une vraie clé naturelle
      Une valeur qui semble unique à première vue ne l'est souvent pas autant qu'on l'espérait, ou bien une valeur qu'on pensait immuable doit finalement changer
      À l'inverse, avec une clé de substitution, je peux définir l'identité à l'intérieur de mon système sans dépendre de la manière dont quelqu'un d'autre a défini l'identifiabilité, ou plus souvent ne l'a pas vraiment définie
      Il y a des exceptions. Si je définis moi-même tout le modèle et que les données ne viennent pas de ce qu'on appelle le monde réel, une clé naturelle a plus de sens. Mais quand on conçoit un schéma pour des données réelles qui n'ont probablement jamais été totalement normalisées, les clés de substitution sont souvent utiles
    • Une clé de substitution entière monotone croissante a une utilité pratique immédiate non négligeable
      Le simple fait de pouvoir référencer n'importe quelle ligne par un entier simplifie énormément l'accès, et c'est plus facile à mémoriser pour les humains comme à utiliser dans les requêtes
      Si elle est monotone croissante, elle contient aussi une information en elle-même. C'est une information redondante, mais c'est un fait
      Les performances en lecture sont également optimisées. C'est presque le cas idéal pour l'indexation avec des arbres B, des bitmaps, etc.
      À mon avis, si les gens utilisent surtout des UUID, c'est en grande partie par confusion. En général, l'idée est d'obfusquer la clé et de la rendre imprévisible, mais j'ai renoncé à comprendre pourquoi ils pensent qu'il faut imposer cela jusqu'à la clé primaire, au lieu d'utiliser un identifiant séparé pour cet objectif
    • L'expression « éviter les doublons » n'apparaît pas dans le billet de blog. En réalité, il n'explique même pas du tout pourquoi il utilise des UUID

  • UUID version 7 contient un horodatage de 48 bits au début, donc il ne présente pas ce type de distribution aléatoire. Cela devrait donc aussi réduire la pagination excessive et les rééquilibrages

    • Exact. L'article traite bien d'UUID7

  • Les gens utilisent vraiment des UUID comme clés primaires ? Quand un UUID est nécessaire, quel est l'avantage à faire cela plutôt que d'en faire une clé secondaire ?

    • Pour le passage à l'échelle. Si l'on veut générer des identifiants uniques de façon distribuée, à grande vitesse, sur de nombreuses machines et dans plusieurs centres de données à travers le monde, comme pour des uploads S3, on n'a pas envie de verrouiller un entier incrémental unique. Les verrous sont lents à synchroniser à l'échelle mondiale
      Les GUID et les UUID résolvent structurellement ce problème
      Les v1 et v6 encodent un identifiant de machine et un horodatage, donc ils se rapprochent d'entiers auto-incrémentés avec un espace de noms par machine
      Une grande partie de la confusion vient du fait que beaucoup supposent qu'un UUID est aléatoire. Ce n'est vrai que pour la v4 et, malheureusement, choisir la v4 a un coût
      On a souvent besoin d'un certain degré de déterminisme, avec des versions comme v3, v5 ou v7, pour aider à organiser les données ou pour des garanties de performance et de collision
    • Même si l'on met un UUID aléatoire ou une valeur aléatoire uniformément distribuée en clé secondaire, les insertions restent plus lentes. Même si ce n'est pas un index clusterisé, il y a quand même des insertions aléatoires dans l'arbre B de cet index