Repacking-Probleme mit Multi-Pack-Bitmaps gelöst Skalierung der Monorepo-Wartung bei GitHub

GitHub betreut einige der größten und am schnellsten wachsenden Git-Repositories der Welt. Bei Wartungsarbeiten führte dies zu Bottlenecks, die man mittlerweile in den Griff bekommen hat. Die Gründe und Gegenmaßnahmen zeigt dieser Erfahrungsbericht.

Vor etwa einem Jahr stellten wir fest, dass der Prozess, mit dem wir die größeren Git-Repositories umpacken, unsere Zeitlimits überschreitet. Selbst als wir die Limits erweiterten, waren fehlgeschlagene Wartungen die häufigste Ursache unerwartet langsamer Operationen, was sich nur schwer beheben ließ.

Heute gibt es diese Probleme nicht mehr. GitHub kann selbst die größten Repositories in einem Bruchteil der damaligen Zeit umpacken. In diesem Beitrag geht es um die Probleme, auf die wir damals gestoßen sind, welche Lösungen wir entwickelt und sicher implementiert haben und wie die Zukunft aussehen könnte.

Das Problem

Die Wartung von GitHub ist so aufwändig, weil wir uns dafür entschieden haben, die gesamten Inhalte jedes Repositorys in eine einzige Datei zu packen. Das bringt Vorteile mit sich: Man muss nicht mehrere Packs öffnen und durchsuchen, um ein Objekt zu finden.

Alle Objekte können relativ zu allen anderen delta-komprimiert werden; das Packfile-Format von Git unterstützt Pack-übergreifende Deltas, aber derzeit speichert Git diese niemals auf der Festplatte. Der größte Nachteil ist jedoch, dass die Reachability-Bitmaps, eine leistungsrelevante Datenstruktur, nur mit Single-Packs kompatibel sind.

Eine neue Funktion in Git sind daher Multi-Pack-Indizes. Sie lassen alle Objektsuchen über einen einzigen Index laufen. Zudem haben wir uns daran gemacht, eine Bitmap-Unterstützung für Multi-Pack-Indizes zu entwickeln, um die Single-Pack-Limits für Reachability-Bitmaps aufzuheben. Um Multi-Pack-Bitmaps erstellen zu können, mussten wir jedoch zunächst eine ganze Reihe von Problemen lösen.

Objekte, Packs und Fetching

Git speichert den Inhalt der Repositories als Menge von Objekten. Jedes Objekt repräsentiert einen Teil seines Repositorys: eine Datei, einen Baum, einen Commit oder ein Tag. Die Objekte können einzeln als „lose“ Objekte oder zusammen in einem Packfile gespeichert werden. Dabei können die Objekte aufeinander verweisen.

Ein Baum bezieht sich auf eine Reihe von Blobs, die Dateien entsprechen, und anderen Bäumen, die ihrerseits Unterverzeichnissen entsprechen. Ein Commit bezieht sich auf einen einzelnen Baum – die Wurzel des Repositorys – und keine oder mehrere andere Commits.

Die Verknüpfungen helfen Git herauszufinden, welche Objekte übertragen werden müssen, um eine Fetch- oder Clone-Anfrage zu erfüllen. Bei einem Fetch muss Git allerdings nicht nur die Commits senden, die zwischen denen liegen, die der Client hat und denen, die er möchte, sondern auch alle Objekte, die von diesen Commits aus erreichbar sind. Da Git nicht die Liste jedes erreichbaren Objekts speichert, kann dies teuer werden.

Heute speichert Git eine Reachability-Bitmap, die mit einigen Commits im Packfile korrespondiert. Die Idee dahinter ist simpel: Ordne die Objekte in einem Pack in einer bestimmten Reihenfolge an. Dann ist das i-te Bit in der Bitmap, die dem Commit C entspricht, 1, falls C das i-te Objekt erreichen kann, und sonst 0.

Eine Eins-zu-eins-Entsprechung zwischen Objekt und Bitposition bringt ein paar interessante Eigenschaften mit sich: Das Abgreifen erreichbarer Objekte zwischen Commits entspricht einer einfachen ODER-Verknüpfung ihrer Bitmaps, und das der Differenz einer einfachen Kombination aus AND und NOT.

Wenn also eine Bitmap vorhanden ist, kann Git die Objektaushandlung immens beschleunigen; da alle Reachability-Infos direkt in den Bitmaps kodiert sind, spart dies Zeit, zumal das Öffnen und Parsen von Objekten entfallen. Das Durchlaufen aller Objekte im Linux-Kernel-Repository dauerte ohne Bitmaps mehr als 33 Sekunden, mit Bitmaps jedoch nur 1,57 Sekunden.

Die Reihenfolge der Bitpositionen ist allerdings von einem Pack vorgegeben, weshalb Bitmaps an die Existenz eines einzigen Packfiles gekoppelt sind. Alle Objekte, die sich außerhalb des Bitmap-Packs ansammeln, profitieren also nicht von den gleichen Geschwindigkeitsvorteilen.

Um dies zu beheben, packen wir regelmäßig den gesamten Inhalt des Repositorys in ein einziges Pack um und erzeugen eine neue Reachability-Bitmap. Das macht Erreichbarkeitsabfragen in neueren Teilen der Historie des Projektarchivs schneller. Aber größere Projektarchive brauchen länger, um umgepackt zu werden und wachsen schneller, was bedeutet, dass sie öfter gewartet werden müssen.

Multi-Pack-Indizes

Sehen wir uns daher eine neue Funktion von Git an: Multi-Pack-Indizes. Wenn Git ein Objekt nach seinem Namen in einem einzelnen Pack suchen möchte, verwendet es die Indexdatei (.idx) dieses Packs, die eine binär durchsuchbare Liste der Objektpositionen enthält.

Multi-Pack-Indizes funktionieren ähnlich, aber die von ihnen angegebene Position enthält sowohl das Pack, welches wiederum das Objekt enthält, als auch die Information, wo das Objekt in diesem Pack zu finden ist. Die Objekte werden zunächst danach gruppiert, in welchem Packfile sie vorkommen, und die Packs werden nach dem Multi-Pack-Index geordnet.

Wir wissen aber nicht, wie viele eindeutige Objekte, die vom Multi-Pack-Index ausgewählt werden, in jedem Pack erscheinen, und wir wissen auch nicht, welche nicht eindeutigen Objekte fehlen. Um dieses Problem zu lösen, haben wir Reverse-Indizes eingeführt. Auf die gleiche Weise, wie der Pack-Index dem Objektnamen den Objektort zuordnet, ordnet der Reverse-Index den Ort eines Objekts seinem Namen zu.

Zusätzlich zum Inhalt des Packs (gespeichert in einer .pack-Datei) und dem Index (gespeichert in einer .idx-Datei) schreiben wir ein Zahlen-Array, die den Reverse-Index bilden und in einer neuen .rev-Datei gespeichert werden. Diese Zahlen erlauben die Zuordnung zwischen der Position eines Objekts in der Pack-Reihenfolge und seiner Position in der lexikographischen Ordnung. Der Reverse-Index erlaubt es uns, schnell von Offsets im Packfile auf die Objektpositionen zu schließen, denen sie entsprechen.

Multi-Pack Bitmaps

Da wir nun ein Format für .rev-Dateien haben, können wir es zum Erstellen von Multi-Pack-Bitmaps nutzen. Anstatt von Positionen relativ zu einer Pack-.idx-Datei geht ein Multi-Pack-Reverse-Index von Positionen aus, die relativ zu einer Multi-Pack-Index-Datei sind.

Anhand ihres Dateinamens weiß jede Bitmap, ob sie zu einem Pack (und wenn ja, zu welchem) oder zu einem Multi-Pack-Index gehört oder nicht. Und basierend auf dieser Information kann sie ihre Objektsuche relativ zu einer Packdatei oder zum Multi-Pack-Index über ihren Reverse-Index durchführen.

Da wir die Ordnung sorgfältig gewählt haben, komprimieren diese Multi-Pack-Bitmaps genauso gut wie ihre Single-Pack-Pendants. Und sie entkoppeln die Bitmaps von den einzelnen Packs. Ein Repository kann also immer noch höchstens eine Bitmap haben, aber diese Bitmap kann nun mehreren Packs entsprechen.

Geometrisches Umpacken

Da nun in einer einzigen Bitmap mehrere Packs enthalten sein können: Was wäre der beste Weg, ein Repository während der Wartung umzupacken? Wir haben uns für eine Variante entschieden, die sicherstellt, dass die Packs in einem Repository eine geometrische Progression nach Objektgröße bilden.

Insbesondere wenn die Packs nach der Anzahl der Objekte geordnet werden – wobei das erste Pack die meisten und das letzte Pack die wenigsten Objekte enthält – wird jedes Pack mindestens doppelt so viele Objekte enthalten wie das folgende. Wir haben dafür git repack einen neuen „--geometric=“-Modus beigebracht.

Das hat zur Folge, dass die Anzahl der Packs mit der Zeit logarithmisch wächst, so dass ein Repository nie zu viele Packs an einer Stelle haben wird. Zudem werden ältere Objekte tendenziell in die größeren Pakete geschoben, weshalb sie mit der Zeit weniger häufig umgepackt werden.

Dieser Ansatz führt dazu, dass die Zeit für das Repacking proportional zur Anzahl der neuen Objekte und nicht zur Anzahl der Objekte insgesamt ist. Wichtig dabei ist: Obwohl die klassischen Repacks immer noch langsam sind, sind wir nicht gezwungen, sie jedes Mal auszuführen, wenn wir ein Repository umpacken wollen.

Nachdem wir unseren neuen Repacking-Ansatz mit Multi-Pack-Bitmaps ausgerollt haben, sparen wir im Vergleich zum alten Ansatz durchschnittlich 5,67 CPU-Tage pro Stunde. Ebenso sank die durchschnittliche Zeit für das Umpacken eines einzelnen Repositorys erheblich. Im Durchschnitt sank die Zeit für das Repacking eines Repositorys von etwa einer Minute auf nur 15 Sekunden.

Ausblick

Es gibt zwei Herausforderungen, die wir angehen möchten, um weitere Leistungsverbesserungen zu ermöglichen. Eine ist die Bitmap-Berechnung selbst. Der Bitmap-Generierungscode von Git kann vorhandene Bitmaps wiederverwenden, indem er ihre Bits in eine neue Ordnung bringt, aber dieser Vorgang kann immer noch Zeit in Anspruch nehmen, die proportional zur Größe des Repositorys ist.

Eine Möglichkeit, dies zu lösen, wäre, Bitmaps inkrementell zu speichern, wobei nur die neuen Objekte, die seit dem letzten Speichern einer Bitmap eingeführt wurden, durchlaufen werden. Dieses Problem ist knifflig, weil es nicht nur voraussetzt, dass die Bitmap-Datei inkrementell gespeichert werden kann, sondern auch, dass die von uns gewählte Objektordnung stabil ist: das heißt, dass die Einführung neuer Bitmaps die vorhandenen nicht bedeutungslos macht.

Eine weitere Herausforderung ist die Pack-Struktur. Das Erstellen von Packs, die eine geometrische Sequenz bilden, ist ein vielversprechender Schritt nach vorn, der es uns erlaubt, zwischen vollständigen und partiellen Repacks abzuwägen. Aber einige Repositories sind so groß, dass das Repacking des gesamten Repositorys nicht machbar, geschweige denn wünschenswert ist. Die Entwicklung eines Ansatzes, der die Packs mit den ältesten Objekten in der Historie eines Repositorys „einfriert”, wird es uns ermöglichen, in Zukunft noch größere Repositories zu unterstützen.

* Taylor Blau ist Senior Software Engineer bei GitHub.

(ID:47531718)