Pour un service comme GitLab, le temps de sauvegarde des dépôts est vital pour éviter une perte de données en cas de problème. Jusqu'à présent, il fallait plus de 48 heures pour pouvoir sauvegarder les gros dépôts de la plateforme. Cependant, à mesure que la taille des dépôts augmente, la création de sauvegardes fiables devient de plus en plus complexe. Après une longue vérification, les équipes identifient le problème : "nous avons finalement identifié le problème comme issu d'une fonction Git vieille de 15 ans et présentant une complexité O(N²) et l'avons corrigé par une modification algorithmique, réduisant ainsi les temps de sauvegarde de manière exponentielle. Résultat : des coûts réduits, des risques réduits et des stratégies de sauvegarde évolutives avec votre base de code." indique le post. 

Une complexité (temporelle) O(N²) indique que le temps d'exécution d'un algorithme croît avec la taille (des données, des éléments) en entrée. Souvent, des boucles imbriquiées sont en cause et chaque élément en entrée est alors comparé aux autres. La croissance du temps d'exécution est dite quadritique. C'est à dire que ce temps est multiplié au carré, ce qui peut rapidement peser sur la bonne exécution de l'algo. 

Cette découverte a permis de réduire le temps de backup du système, passant de 48 heures à 41 minutes ! GitHub réduit les coûts, réduction des risques de pertes de données et permettre une meilleure stratégie de sauvegarde des dépôts pour les utilisateurs. 

Pour GitLab, le défi de faire un backup à l'échelle est crucial. Il s'agit de pouvoir faire un backup supportant des dépôts toujours plus nombreux et de pouvoir absorder cette croissance. GitLab a listé les défis suivants : 

- Sauvegardes chronophages : pour les référentiels très volumineux, la création d'une sauvegarde peut prendre plusieurs heures, ce qui peut entraver la planification de sauvegardes régulières.

- Intensité des ressources : les processus de sauvegarde prolongés peuvent consommer des ressources serveur (trop) importantes, ce qui peut impacter d'autres opérations.

- Fenêtres de sauvegarde : trouver des fenêtres de maintenance adéquates pour des processus aussi longs peut s'avérer difficile pour les équipes fonctionnant 24h/24 et 7j/7.

- Risque de panne accru : les processus longs sont plus sensibles aux interruptions dues à des problèmes de réseau, des redémarrages de serveur et des erreurs système, ce qui peut obliger les équipes à recommencer l'intégralité du processus de sauvegarde, très long.

- Race condition : la création d'une sauvegarde étant longue, le référentiel peut avoir subi de nombreuses modifications au cours du processus, ce qui peut entraîner la création d'une sauvegarde non valide ou l'interruption de la sauvegarde en raison de l'indisponibilité des objets.

La fonction de sauvegarde repose sur la commande git bundle create qui crée un snapshot du dépôt incluant tous les éléments et références. La commande crée alors un point de restauration pour pouvoir restaurer le dépôt si nécessaire. L'implémentation de la commande souffrait d'une mauvaise montée en charge et provoquant alors des performances médiocres. 

Pour les équipes, il a fallu tuner les performances de la commande et comprendre les blocages. Les graphs ont permis de mieux scruter le fonctionnement. Ainsi, sur un dépôt de 10 000 références, plus de 80 % du temps d'exécution sont consommés par la fonction object_array_remove_duplicates(). Cette fonction avait été introduite en 2009. "Pour comprendre ce changement, il est important de savoir que git bundle create permet aux utilisateurs de spécifier les références à inclure dans le bundle. Pour les bundles de dépôt complets, l'option --all inclut toutes les références. Cet algorithme O(N²) constitue un goulot d'étranglement important en termes de performances dans les dépôts avec un grand nombre de références, consommant un temps de traitement considérable." commente l'éditeur. 

A partir de cette analyse, les équipes ont pu fixer le problème d'exécution en remplaçant les boucles imbriquées par une structure de données de type map permettant de réaliser une unique copie de chaque référence durant le traitement de la commande. 

Ce fix permet :

- un backup réduit à 41 minutes

- une meilleure montée en charge

- une optimisation des ressources utilisées

Source : https://about.gitlab.com/blog/2025/06/05/how-we-decreased-gitlab-repo-backup-times-from-48-hours-to-41-minutes/