Comment GitLab a réduit le temps de sauvegarde des dépôts de 48 heures à 41 minutes

 (about.gitlab.com)
5 points par GN⁺ 2025-06-07 | 1 commentaires | Partager sur WhatsApp
  • GitLab a identifié un problème de lenteur lors de la sauvegarde de dépôts volumineux et a mené un travail d’amélioration
  • La cause principale était la complexité O(N²) d’une fonction Git vieille de 15 ans, et l’optimisation de l’algorithme a permis d’améliorer fortement les performances
  • Après optimisation, le temps de sauvegarde du plus gros dépôt est passé de 48 heures à 41 minutes
  • Cette approche améliorée apporte efficacité des ressources et fiabilité, tout en ayant un impact positif sur d’autres outils basés sur Git et sur la communauté
  • À partir de GitLab 18.0, tous les utilisateurs peuvent bénéficier de ces avantages sans configuration supplémentaire

Importance et défis de la sauvegarde des dépôts

  • La sauvegarde des dépôts est un élément clé d’une stratégie de reprise après incident
  • Plus la taille des dépôts augmente, plus la complexité d’un processus de sauvegarde fiable s’accroît
  • Le dépôt Rails interne de GitLab nécessitait 48 heures de sauvegarde, ce qui obligeait à arbitrer difficilement entre fréquence des sauvegardes et performances système
  • Les grands dépôts cumulent divers problèmes liés au temps, aux ressources, au risque d’échec et aux race conditions
    • Il en résulte, selon les organisations, des stratégies peu homogènes : sauvegardes planifiées difficiles, dépendance à des outils externes ou réduction du nombre de sauvegardes

Analyse du goulot d’étranglement et identification de la cause

  • La fonctionnalité de sauvegarde de GitLab crée des instantanés de dépôts avec la commande git bundle create
  • Lors de l’implémentation de cette commande, un goulot d’étranglement apparaissait à mesure que le nombre de références augmentait
  • Dans certains grands dépôts comptant plusieurs millions de références, une sauvegarde pouvait prendre plus de 48 heures

Analyse de la cause

  • Une analyse par Flame Graph pendant l’exécution de la commande a permis d’identifier la zone bloquante
  • Avec 10 000 références, environ 80 % du temps d’exécution était consommé par la fonction object_array_remove_duplicates()
  • Cette fonction a été introduite en 2009 via ce commit pour gérer les références en double
    • Elle évitait les problèmes lorsque des références dupliquées étaient incluses dans git bundle create
    • Mais la détection des doublons reposait sur des boucles for imbriquées, entraînant une complexité en O(N²)
    • Plus le nombre de références augmentait, plus le goulot d’étranglement s’aggravait

Passage de O(N²) à un mappage efficace

  • GitLab a contribué à Git un patch utilisant une structure de données de type map à la place des boucles imbriquées
    • Chaque référence est ajoutée à la map, ce qui supprime automatiquement les doublons et permet un traitement efficace
  • Ce changement améliore considérablement les performances de git bundle create et permet de mieux passer à l’échelle dans les environnements avec un grand nombre de références
  • Les benchmarks montrent, avec 100 000 références, une amélioration de performances de plus de 6 fois

Temps de sauvegarde drastiquement réduits et effets obtenus

  • Le temps maximal de sauvegarde d’un dépôt est passé de 48 heures à 41 minutes (soit 1,4 % du temps initial)
  • Il devient possible d’offrir des performances constantes quelle que soit la taille du dépôt
  • Des bénéfices supplémentaires ont été obtenus : baisse de la charge serveur, amélioration des performances de l’ensemble des commandes Git basées sur les sauvegardes, etc.
  • Le patch a été intégré à Git en amont, et GitLab l’a appliqué immédiatement afin que ses clients puissent en profiter rapidement

Ce que cela change concrètement pour les clients GitLab

  • Les grands comptes peuvent désormais exécuter des sauvegardes nocturnes successives sans conflit avec les workflows de développement
  • Grâce à la réduction du RPO (Recovery Point Objective), le risque de perte de données en cas de sinistre diminue fortement
  • La consommation de ressources, le temps de maintenance et les coûts cloud liés à l’exploitation diminuent également
  • Même si la taille des dépôts augmente, il n’est plus nécessaire d’hésiter entre fréquence des sauvegardes et performances système
  • Tous les utilisateurs de GitLab peuvent désormais bénéficier de ces avantages sans modifier leur configuration

Prochaines étapes et portée de cette amélioration

  • Cette amélioration s’inscrit dans les efforts continus de GitLab pour construire une infrastructure Git d’entreprise hautement scalable
  • Les changements apportés par GitLab ont également été intégrés au projet Git en amont, avec des retombées positives pour l’ensemble du secteur et la communauté open source
  • Ce type d’amélioration d’infrastructure sert de modèle pour d’autres travaux clés d’optimisation des performances

Un aperçu plus approfondi de l’approche de GitLab en matière de performance sera présenté lors du GitLab 18 Virtual Launch Event

À lire aussi

1 commentaires

 
GN⁺ 2025-06-07
Avis Hacker News

  • Partage d’information indiquant que le code d’amélioration des performances que GitLab a contribué à Git est prévu pour la version v2.50.0 lien vers le commit correspondant

  • À partir de son expérience directe, quelqu’un souligne que supprimer les opérations en n^2 dans le code qu’il écrit s’est toujours révélé être le bon choix. Il se dit surpris de voir à quel point le problème apparaît facilement, même pour des valeurs de n très faibles, sans qu’il soit nécessaire d’écrire un algorithme particulier

    • Citation de la première loi de l’informatique de Bruce Dawson : O(n^2) est le point où apparaissent les pires problèmes de passage à l’échelle. En production, cela semble suffisamment rapide, puis une fois déployé, cela provoque une dégradation de performances fatale lien vers le billet correspondant

    • Partage d’une expérience personnelle : il a vu à de nombreuses reprises des cas où une complexité temporelle en O(N^2) semblait rapide en test, puis causait de graves problèmes en production

    • D’après son expérience, dans la majorité des cas (80 à 90 %), si un algorithme complexe est nécessaire, c’est le signe que le modèle de données lui-même n’est pas correct. Il estime que seuls quelques cas particuliers, comme les compilateurs, l’intérieur des bases de données ou la planification de trajectoires, exigent intrinsèquement des algorithmes complexes

    • Une exception est mentionnée pour les cas limités à du matériel de petite taille avec n inférieur à 10 (interfaces CAN, etc.). Mais si n peut augmenter sans changement matériel, il faut impérativement éviter les opérations en n^2 ; il recommande soit de limiter cela dès la conception, soit de le détecter à l’avance afin de reconnaître qu’une refonte est nécessaire

    • Il exprime sa frustration face à un goulot d’étranglement qui apparaît dès 10 000 éléments à cause d’opérations en n^3, sans avoir encore trouvé de solution

  • Tout en jugeant la découverte intéressante, quelqu’un regrette que l’article aurait pu communiquer aussi efficacement en ne faisant qu’un dixième de sa longueur. Il note néanmoins un point positif : comme ce n’était pas du contenu vidéo, il était facile à parcourir rapidement

    • Conseil pour ceux qui n’ont pas lu l’article : pour saisir l’essentiel avec le plus d’efficacité, il suffit de lire jusqu’au passage après le flame graph et de s’arrêter avant la mention du backport

    • Impression que le style général de l’article donnait l’impression d’un texte généré par un LLM (grand modèle de langage), notamment à cause de sa longueur, et que c’est ce qui lui est resté en mémoire

    • Il pense qu’un article encore plus long ne l’aurait pas dérangé, tout en se demandant toujours pourquoi le bundle de sauvegarde a été créé en deux refs

  • Le fait qu’il faille 48 heures pour compresser un dossier git de plusieurs Go, et même 41 minutes, lui paraît très long. Il se demande pourquoi ne pas simplement snapshotter ou archiver tout le repo git, au lieu d’utiliser spécifiquement git bundle. Il s’interroge sur les avantages de git bundle par rapport à des sauvegardes ZFS fréquentes

    • La FAQ officielle de git indique que ce type d’approche est risqué, car elle contourne les procédures normales de vérification d’intégrité de Git. Dans ce cas, git fsck est recommandé pour vérifier l’intégrité de l’ensemble. À titre individuel, Syncthing et les snapshots Btrfs sont déjà suffisamment rapides et fiables. documentation liée

    • Il est mentionné qu’il existe des limites pour faire une sauvegarde hors site de snapshots ZFS vers une base non ZFS comme S3. Une fonctionnalité moins connue de git bundle permet de spécifier un emplacement avec git clone --bundle-uri ; si le serveur indique au client où se trouve le bundle, le client peut le récupérer, l’extraire rapidement, puis ne recevoir du serveur que les mises à jour delta, ce qui réduit fortement la charge liée au clonage de grands repos

    • En fin de compte, cela ressemble à l’ajout de cache là où il en fallait. En général, du fait de la nature distribuée des repos git, on pourrait simplement les mirrorer vers un autre dépôt et les gérer avec des outils de snapshot ou de sauvegarde du système de fichiers. L’idée centrale est que les informations importantes de gestion de versions elles-mêmes doivent être distribuées

  • Sans avoir énormément d’expérience en matière de sauvegarde git, quelqu’un dit se demander pourquoi la création d’une sauvegarde directement depuis un repo local provoquerait une race condition

  • Si c’est à ce point compliqué à cause du protocole de données de couche supérieure, quelqu’un se demande pourquoi ne pas utiliser plutôt des snapshots au niveau bloc. L’absence d’un WAL (Write Ahead Logging) dans Git semble être l’obstacle, mais il explique qu’en ajoutant simplement le mode WAL à SQLite, il utilise en production une stratégie de snapshot bloc sans difficulté. Il pense qu’une architecture de ce type appliquée à Git permettrait une stratégie de sauvegarde bien plus fiable

    • Quelqu’un dit comprendre le problème lié à l’absence dans Git d’un mécanisme comparable au WAL, et partage une expérience où le fait de se reposer uniquement sur des snapshots pour les sauvegardes a conduit à un problème critique : le dépôt était corrompu à la restauration. Il ajoute que la récupération est possible, mais très fastidieuse

    • Partage d’une astuce : une solution plus récente et meilleure existe côté SQLite avec sqlite3_rsync

    • Il est expliqué que GitLab n’est pas seulement un service managé, mais aussi un produit que l’on peut installer soi-même dans des environnements variés. Les utilisateurs ont donc chacun des systèmes de fichiers, des mécanismes de snapshot et des contraintes de système d’exploitation différents. Du point de vue de GitLab, ils veulent donc un système de sauvegarde autonome qui fonctionne universellement dans tous les environnements

  • En voyant l’expression « réduction exponentielle du temps de sauvegarde grâce à un changement d’algorithme », quelqu’un se demande si cela signifie une baisse de O(n^2) à O(n^2/2^n). Il suppose que ce n’est évidemment pas le cas

    • Il est expliqué que la complexité algorithmique de la fonction modifiée est devenue 6 fois plus rapide, et que dans son contexte d’utilisation, le temps d’exécution total a été ramené à 1 %, ce qui donne un résultat spectaculaire. Dans ce cas, parler d’« amélioration exponentielle » est jugé acceptable d’un point de vue marketing. La qualification exacte de la complexité n’a pas beaucoup d’importance ici

    • Il est précisé que dans la conversation courante, « exponential » n’a pas toujours un sens mathématique strict, mais sert plutôt d’image pour dire « amélioration énorme »

    • Selon son interprétation, cela pourrait signifier que n a été réduit jusqu’à log(n). Il cite un cas analogue où l’on dit souvent que la transformée de Fourier quantique est exponentiellement plus rapide que la DFT classique, de la même façon qu’un passage de n^2 à nlogn

    • Remplacer un algorithme en n^2 par une recherche en log(n) correspond bien à une amélioration exponentielle en vitesse, mais dans la pratique, on arrive souvent jusqu’à O(1), par exemple avec une recherche via table de hachage, ce qui est encore plus rapide

    • Quelqu’un estime que tout ce débat relève d’un pinaillage improductif

  • Avis selon lequel écrire en C ne garantit pas automatiquement de bonnes performances, et que les structures de données et les algorithmes priment. C’est présenté comme un bon exemple

    • En C, il est tellement difficile d’implémenter des conteneurs adaptés que ce type de problème de performance survient plus souvent. En C++ ou en Rust, grâce à des structures intégrées comme unordered_set ou HashSet, les développeurs ont davantage tendance à optimiser naturellement au lieu de laisser passer un simple for loop. Dans ce cas aussi, Git dispose d’un string set, mais comme ce n’est pas standard, il est probable que l’auteur d’origine n’en avait pas connaissance

  • Mention d’une leçon sur l’équilibre à trouver entre optimisation prématurée et optimisation anticipée. En général, on met en garde contre l’optimisation prématurée, mais il propose comme règle d’appliquer à l’avance les optimisations évidentes et simples lorsqu’une fonction est appelée très fréquemment

    • Supposition que si le langage source utilisé à l’implémentation avait intégré nativement un set de chaînes, le développeur d’origine aurait probablement appliqué facilement cette optimisation. Selon cette opinion, ce type de problème provient au fond des limites structurelles de langages pauvres en conteneurs comme le C

  • Transmission directe du lien vers le commit correspondant (amélioration algorithmique) lien vers le commit correspondant