Wie GitLab die Backup-Zeit von Repositories von 48 Stunden auf 41 Minuten verkürzt hat

 (about.gitlab.com)
5 Punkte von GN⁺ 2025-06-07 | 1 Kommentare | Auf WhatsApp teilen
  • GitLab stellte fest, dass Backups großer Repositories sehr lange dauerten, und leitete Verbesserungen ein
  • Die Hauptursache war die O(N²)-Komplexität einer 15 Jahre alten Git-Funktion; durch Algorithmus-Optimierung wurde die Leistung deutlich verbessert
  • Als Ergebnis der Optimierung sank die Backup-Zeit des größten Repositories von 48 Stunden auf 41 Minuten
  • Die verbesserte Methode bietet Ressourceneffizienz und Zuverlässigkeit und wirkt sich zugleich positiv auf andere Git-basierte Tools und die Community aus
  • Ab GitLab 18.0 können alle Nutzer diese Vorteile ohne zusätzliche Konfiguration nutzen

Die Bedeutung und die Herausforderungen von Repository-Backups

  • Repository-Backups sind ein Kernelement jeder Disaster-Recovery-Strategie
  • Mit wachsender Repository-Größe steigt die Komplexität eines zuverlässigen Backup-Prozesses
  • Das interne Rails-Repository von GitLab benötigte 48 Stunden für ein Backup, wodurch ein schwieriger Zielkonflikt zwischen Backup-Häufigkeit und Systemleistung entstand
  • Bei großen Repositories treten verschiedene Probleme auf, etwa Zeitaufwand, Ressourcenbedarf, Ausfallrisiken und Race Conditions
    • Das führt je nach Organisation zu uneinheitlichen Strategien, etwa erschwerten geplanten Backups, Abhängigkeit von externen Tools oder einer geringeren Backup-Frequenz

Analyse des Performance-Engpasses und Ursachenfindung

  • Die Backup-Funktion von GitLab erzeugt mit dem Befehl git bundle create einen Repository-Snapshot
  • Bei der Implementierung dieses Befehls trat ein Performance-Engpass auf, der mit der steigenden Zahl von References zunahm
  • In großen Repositories mit mehreren Millionen References dauerten Backups in manchen Fällen mehr als 48 Stunden

Ursachenanalyse

  • Während der Befehlsausführung wurde der Engpass per Flame-Graph-Analyse identifiziert
  • Bei 10.000 References entfielen etwa 80 % der Laufzeit auf die Funktion object_array_remove_duplicates()
  • Diese Funktion wurde 2009 in diesem Commit eingeführt, um doppelte References zu verarbeiten
    • Bei der Verwendung von git bundle create sollte verhindert werden, dass Probleme durch doppelte References entstehen
    • Die Erkennung von Duplikaten war jedoch als verschachtelte for-Schleife implementiert, wodurch eine O(N²)-Komplexität entstand
    • Je mehr References vorhanden waren, desto stärker wurde der Bottleneck

Von O(N²) zu effizientem Mapping

  • GitLab trug einen Patch zu Git bei, der statt verschachtelter Schleifen eine Map-Datenstruktur verwendet
    • Jede Reference wird zur Map hinzugefügt, wodurch Duplikate automatisch entfernt und effizient verarbeitet werden
  • Diese Änderung verbessert die Performance von git bundle create deutlich und macht das Verhalten auch bei sehr vielen References skalierbar
  • Benchmarks zeigten bei 100.000 References eine mehr als 6-fache Leistungssteigerung

Deutlich verkürzte Backup-Zeiten und ihre Auswirkungen

  • Die maximale Backup-Dauer eines Repositories sank von 48 Stunden auf 41 Minuten (auf 1,4 % des ursprünglichen Werts)
  • Dadurch ist konsistente Performance unabhängig von der Repository-Größe möglich
  • Zusätzliche Vorteile sind geringere Serverlast und eine bessere Performance bei Git-Befehlen rund um Backups
  • Der Patch wurde in upstream Git übernommen; GitLab hat ihn zugleich sofort integriert, damit Kunden schneller davon profitieren können

Konkrete Veränderungen für GitLab-Kunden

  • Unternehmenskunden können nun aufeinanderfolgende nächtliche Backups ausführen, ohne Konflikte mit Entwicklungs-Workflows zu verursachen
  • Durch den verkürzten Recovery Point Objective (RPO) sinkt das Risiko von Datenverlusten im Katastrophenfall erheblich
  • Auch der betriebliche Overhead nimmt ab, etwa bei Ressourcenverbrauch, Wartungszeit und Cloud-Kosten
  • Selbst bei weiter wachsender Repository-Größe ist kein Kompromiss mehr zwischen Backup-Häufigkeit und Systemleistung nötig
  • Nun können alle GitLab-Nutzer diese Vorteile ohne Konfigurationsänderungen nutzen

Nächste Schritte und Bedeutung

  • Diese Verbesserung ist Teil der kontinuierlichen Bemühungen von GitLab, eine hochskalierbare Git-Infrastruktur auf Enterprise-Niveau aufzubauen
  • Die von GitLab beigetragenen Änderungen wurden auch in das Upstream-Git-Projekt übernommen und entfalten damit positive Wirkung auf die gesamte Branche und die Open-Source-Community
  • Solche Infrastrukturverbesserungen dienen inzwischen als Modell für weitere zentrale Performance-Optimierungen

Eine ausführlichere Darstellung von GitLabs Performance-Ansatz gibt es beim virtuellen Launch-Event zu GitLab 18

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-07
Hacker-News-Kommentare

  • Hinweis, dass der von GitLab zu Git beigesteuerte Performance-Verbesserungscode in v2.50.0 veröffentlicht werden soll Link zum relevanten Commit

  • Aus eigener Erfahrung wird betont, dass das Entfernen von n^2-Operationen im selbst geschriebenen Code immer die richtige Entscheidung war. Es sei überraschend, wie leicht sich das Problem schon bei sehr kleinen n-Werten zeigt, auch ohne spezielle Algorithmen zu schreiben.

    • Zitat von Bruce Dawsons erstem Gesetz des Computings: O(n^2) ist der Punkt, an dem die schlimmsten Skalierungsprobleme entstehen. In der Produktion ist es zunächst schnell genug, und sobald es ausgerollt wird, kommt es zu fatalen Performance-Einbrüchen Link zum relevanten Beitrag

    • Persönliche Erfahrung, O(N^2)-Zeitkomplexität in Tests oft schnell wirken zu sehen, während sie in der Produktion mehrfach ernsthafte Probleme verursacht hat

    • Nach eigener Erfahrung ist es bei den meisten Problemen (80–90 %) ein Signal, dass das Datenmodell selbst nicht korrekt ist, wenn ein komplexer Algorithmus nötig wird. Nur in einigen besonderen Fällen wie Compiler, DB-Interna oder Pfadplanung seien komplexe Algorithmen grundsätzlich erforderlich.

    • Als Ausnahme werden Fälle mit kleiner Hardware und n unter 10 genannt (etwa CAN-Schnittstellen). Falls n ohne Hardwaretausch wachsen kann, sollte man n^2-Operationen unbedingt vermeiden und entweder die Begrenzung im Design fest verankern oder frühzeitig erkennen, dass eine Neugestaltung nötig ist.

    • Es wird Frust darüber geäußert, dass bei n^3-Operationen bereits bei nur 10.000 Elementen ein Flaschenhals entsteht und bisher noch keine Lösung gefunden wurde.

  • Als interessante Entdeckung bewertet, zugleich aber bedauert, dass der Text auch mit einem Zehntel der Länge ausreichend effektiv kommuniziert hätte. Positiv wird immerhin erwähnt, dass es kein Videoinhalt war und sich daher leicht überfliegen ließ.

    • Für Leute, die den Artikel noch nicht gelesen haben, der Tipp, bis zur Erwähnung des Flame Graphs und vor dem Backporting zu lesen und dort aufzuhören, da das für das Verständnis des Kerns am effizientesten sei

    • Eindruck, der gesamte Stil des Artikels sei so langatmig gewesen, dass er wirkte, als wäre er von einem LLM (Large Language Model) erzeugt worden; gerade das sei in Erinnerung geblieben

    • Meinung, dass auch ein noch längerer Artikel in Ordnung gewesen wäre, während weiterhin unklar bleibt, warum das Backup-Bundle mit zwei refs erstellt wurde

  • Es wird angemerkt, dass schon 48 Stunden zum Komprimieren eines Git-Ordners von mehreren GB sehr lang seien und selbst 41 Minuten noch viel Zeit seien. Es wird gefragt, warum nicht einfach das gesamte git repo als Snapshot/Archiv gesichert wird und warum man eigens git bundle verwendet. Unklar sei, welchen Vorteil git bundle gegenüber häufigen ZFS-Backups habe.

    • Laut offizieller Git-FAQ ist ein solcher Ansatz riskant, weil er die üblichen Integritätsprüfungen von Git umgeht. In solchen Fällen werde git fsck empfohlen, um die Integrität der Sammlung zu prüfen. Für den privaten Einsatz seien Syncthing und Btrfs-Snapshots allein bereits schnell und zuverlässig genug. Relevantes Dokument

    • Es wird erwähnt, dass ZFS-Snapshots für Offsite-Backups auf nicht ZFS-basierten Zielen wie S3 Einschränkungen haben. Als weniger bekannte Funktion von git bundle könne bei git clone --bundle-uri ein Ort angegeben werden; wenn der Server dem Client den Bundle-Speicherort mitteilt, kann der Client das Bundle laden, schnell entpacken und dann nur noch Delta-Updates vom Server beziehen, was die Last beim Klonen großer Repos stark reduziert.

    • Bewertung, dass letztlich wohl Caching dort ergänzt wurde, wo Caching nötig war. Es wird die Frage gestellt, ob man Git-Repos aufgrund ihres Charakters als verteiltes System nicht einfach auf ein anderes Repository spiegeln und mit Filesystem-Snapshot-/Backup-Tools verwalten sollte. Entscheidend sei, dass die wichtigen Versionsverwaltungsinformationen selbst verteilt vorliegen.

  • Nicht viel Erfahrung mit Git-Backups, aber Verwunderung darüber, warum beim direkten Erstellen eines Backups aus einem lokalen Repo heraus eine Race Condition entstehen sollte

  • Wenn es wegen eines Datenprotokolls höherer Ebene so kompliziert wird, wird gefragt, warum man nicht stattdessen Block-Level-Snapshots verwendet. Dass Git kein WAL (Write Ahead Logging) wie SQLite habe, sei zwar ein Hindernis, aber bei SQLite werde in realen Service-Umgebungen durch das Hinzufügen des WAL-Modus problemlos auf Block-Snapshots gesetzt. Mit einer ähnlichen Architektur in Git wären deutlich stabilere Backup-Strategien möglich.

    • Zustimmung, dass das Problem aus dem Fehlen eines WAL-ähnlichen Mechanismus in Git entsteht; es wird eine kritische Erfahrung geschildert, bei der ein nur auf Snapshots vertrauendes Backup beim Wiederherstellen zu einem beschädigten Repository führte. Die Reparatur sei möglich, aber sehr mühsam.

    • Hinweis, dass es bei SQLite inzwischen mit sqlite3_rsync eine bessere Lösung gibt

    • Erläuterung der GitLab-Perspektive: GitLab ist nicht nur ein einfacher Managed Service, sondern ein Produkt, das man selbst installieren und in verschiedensten Umgebungen nutzen kann. Daher unterscheiden sich je nach Nutzer Dateisystem, Snapshot-Unterstützung und Betriebssystembedingungen. GitLab wolle also ein eigenständiges Backup-System, das in allen Umgebungen allgemein funktioniert.

  • Beim Ausdruck „die Backup-Zeit durch eine Algorithmusänderung exponentiell reduziert“ wird hinterfragt, ob das bedeuten solle, dass man von O(n^2) auf O(n^2/2^n) gekommen sei. Vermutet wird, dass das in Wirklichkeit kaum gemeint sein kann.

    • Erklärung, dass die Algorithmuskomplexität der geänderten Funktion tatsächlich sechsmal schneller wurde und im gesamten Nutzungskontext die Laufzeit sogar auf 1 % sank; in diesem Fall sei „exponentielle Verbesserung“ aus Marketing-Sicht vertretbar. Die exakte Komplexitätsbezeichnung sei hier weniger wichtig.

    • Es wird klargestellt, dass „exponential“ in alltäglichen Gesprächen nicht mathematisch präzise verwendet werde, sondern eher bildlich im Sinne von „massiv verbessert“

    • Nach eigener Interpretation könnte n auf log(n) reduziert worden sein. Erwähnt wird eine ähnliche Ausdrucksweise beim Quanten-Fourier-Transform, der oft als exponentiell schneller als die klassische DFT beschrieben wird, sowie ein Fall, in dem sich die Komplexität von n^2 auf nlogn ändert.

    • Wenn ein n^2-Algorithmus durch eine log(n)-Lookup-Methode ersetzt wird, sei es korrekt, von einer exponentiellen Beschleunigung zu sprechen; tatsächlich lande man aber oft sogar bei O(1), etwa durch Hashmap-Lookups, und damit sei es noch schneller.

    • Die Ansicht, dass diese ganze Debatte selbst unproduktive Haarspalterei sei

  • Meinung, dass in C geschrieben zu sein nicht automatisch hohe Performance bedeutet und dass Datenstrukturen und Algorithmen wichtiger sind; dies sei ein gutes Beispiel dafür

    • Da es in C ausgesprochen schwierig sei, geeignete Container zu implementieren, träten solche Performance-Probleme dort häufiger auf. In C++ oder Rust würden Entwickler dank eingebauter Datenstrukturen wie unordered_set/HashSet eher nicht einfach mit einer for-Schleife weitermachen, sondern natürlicher optimieren. In diesem Fall gebe es auch in Git ein String-Set, aber da es nicht standardmäßig sei, habe der ursprüngliche Autor möglicherweise nichts davon gewusst.

  • Es wird als Lehre erwähnt, dass man ein Gleichgewicht zwischen voreiliger Optimierung und vorausschauender Optimierung braucht. Im Allgemeinen solle man premature optimization zwar vermeiden, doch bei sehr häufig aufgerufenen Funktionen sei es sinnvoll, offensichtliche und einfache Optimierungen vorab einzubauen.

    • Vermutung, dass der ursprüngliche Entwickler eine solche Optimierung leicht eingebaut hätte, wenn die Quellsprache ein set-of-strings eingebaut gehabt hätte. Letztlich sei das Problem also Ausdruck der strukturellen Grenzen einer containerarmen Sprache wie C.

  • Direkter Hinweis auf den relevanten Commit mit den Algorithmusverbesserungen Link zum relevanten Commit

    • Hinweis, dass sich darüber die zugehörige Einreichung und der Diskussions-Thread auf der Kernel-Mailingliste finden ließen Link zur relevanten Diskussion