English ▾ Themen ▾ Neueste Version ▾ multi-pack-index zuletzt aktualisiert in 2.50.0

Das Git-Objektverzeichnis enthält ein Verzeichnis pack, das Packdateien (mit der Endung ".pack") und Pack-Indizes (mit der Endung ".idx") enthält. Die Pack-Indizes bieten eine Möglichkeit, Objekte nachzuschlagen und zu ihrem Offset innerhalb des Packs zu navigieren, aber diese müssen mit den Packdateien ein Paar bilden. Diese Paarung hängt von den Dateinamen ab, da sich der Pack-Index nur in der Endung von seiner Packdatei unterscheidet. Während die Pack-Indizes eine schnelle Suche pro Packdatei ermöglichen, verschlechtert sich diese Leistung mit zunehmender Anzahl von Packdateien, da Abkürzungen jede Packdatei inspizieren müssen und wir mit höherer Wahrscheinlichkeit einen Treffer bei unserer zuletzt verwendeten Packdatei haben. Für einige große Repositories ist das Repacking in eine einzige Packdatei aufgrund von Speicherplatz oder übermäßigen Repack-Zeiten nicht praktikabel.

Der Multi-Pack-Index (kurz MIDX) speichert eine Liste von Objekten und ihre Offsets in mehreren Packdateien. Er enthält

  • Eine Liste von Packdateinamen.

  • Eine sortierte Liste von Objekt-IDs.

  • Eine Liste von Metadaten für die i-te Objekt-ID, einschließlich

    • Ein Wert j, der sich auf die j-te Packdatei bezieht.

    • Ein Offset innerhalb der j-ten Packdatei für das Objekt.

  • Wenn große Offsets benötigt werden, verwenden wir eine weitere Liste von großen Offsets, ähnlich wie bei Version 2 der Pack-Indizes.

    • Eine optionale Liste von Objekten in Pseudo-Pack-Reihenfolge (wird mit MIDX-Bitmaps verwendet).

Somit können wir eine O(log N) Suchzeit für eine beliebige Anzahl von Packdateien bieten.

Design-Details

  • Die MIDX wird in einer Datei namens multi-pack-index im Verzeichnis .git/objects/pack gespeichert. Diese könnte im Packverzeichnis eines Alternativen gespeichert werden. Sie bezieht sich nur auf Packdateien in demselben Verzeichnis.

  • Die Konfigurationseinstellung core.multiPackIndex muss aktiviert sein (was der Standard ist), um MIDX-Dateien zu verbrauchen. Wenn sie auf false gesetzt wird, verhindert dies, dass Git eine MIDX-Datei liest, auch wenn eine vorhanden ist.

  • Das Dateiformat enthält Parameter für die Hash-Funktion der Objekt-ID, sodass eine zukünftige Änderung des Hash-Algorithmus keine Änderung des Formats erfordert.

  • Die MIDX speichert nur einen Datensatz pro Objekt-ID. Wenn ein Objekt in mehreren Packdateien vorkommt, wählt die MIDX die Kopie in der bevorzugten Packdatei aus, andernfalls wird aus der zuletzt geänderten Packdatei ausgewählt.

  • Wenn im Packverzeichnis Packdateien vorhanden sind, die nicht in der MIDX registriert sind, werden diese Packdateien in die packed_git-Liste und den packed_git_mru-Cache geladen.

  • Die Pack-Indizes (.idx-Dateien) verbleiben im Packverzeichnis, damit wir die MIDX-Datei löschen, core.midx auf false setzen oder herabstufen können, ohne Informationsverluste.

  • Das MIDX-Dateiformat verwendet einen auf Chunks basierenden Ansatz (ähnlich der Commit-Graph-Datei), der das Hinzufügen optionaler Daten ermöglicht.

Inkrementelle Multi-Pack-Indizes

Wenn Repositories größer werden, wird es teurer, einen Multi-Pack-Index (MIDX) zu schreiben, der alle Packdateien enthält. Um dem Rechnung zu tragen, ermöglicht die Funktion "inkrementelle Multi-Pack-Indizes" die Kombination einer "Kette" von Multi-Pack-Indizes.

Jede einzelne Komponente der Kette muss nur eine kleine Anzahl von Packdateien enthalten. Das Anhängen an die Kette macht frühere Teile der Kette nicht ungültig, sodass Repositories steuern können, wie viel Zeit für die Aktualisierung der MIDX-Kette aufgewendet wird, indem sie die Anzahl der Packs in jeder Schicht der MIDX-Kette bestimmen.

Design-Status

Derzeit fehlen der inkrementellen Multi-Pack-Indizes-Funktion zwei wichtige Komponenten

  • Die Fähigkeit, frühere Teile der MIDX-Kette neu zu schreiben (d. h. eine Sammlung benachbarter MIDX-Schichten zu einem einzigen MIDX zu "komprimieren"). Derzeit ist die einzige unterstützte Methode zum Verkleinern einer MIDX-Kette, die gesamte Kette von Grund auf neu zu schreiben, ohne das Flag --split.

    Es gibt keine grundlegenden Einschränkungen, die der Implementierung dieser Funktion im Wege stehen. Sie wurde in der anfänglichen Implementierung weggelassen, um die Komplexität zu reduzieren, wird aber später hinzugefügt.

  • Unterstützung für Erreichbarkeits-Bitmaps. Die klassische einzelne MIDX-Implementierung unterstützt Erreichbarkeits-Bitmaps (siehe den Abschnitt "multi-pack-index reverse indexes" in gitformat-pack[5] für weitere Details).

    Wie oben erwähnt, gibt es keine grundlegenden Einschränkungen, die der Erweiterung des inkrementellen MIDX-Formats zur Unterstützung von Erreichbarkeits-Bitmaps im Wege stehen. Das nachstehende Design berücksichtigt dies ausdrücklich, und die Unterstützung für Erreichbarkeits-Bitmaps wird in einer zukünftigen Patch-Serie hinzugefügt. Sie wurde aus demselben Grund wie oben aus der aktuellen Implementierung weggelassen.

    Kurz gesagt, um Erreichbarkeits-Bitmaps mit der inkrementellen MIDX-Funktion zu unterstützen, wird das Konzept der Pseudo-Pack-Reihenfolge über jede Schicht der inkrementellen MIDX-Kette erweitert, um eine verkettete Pseudo-Pack-Reihenfolge zu bilden. Diese Verkettung erfolgt in derselben Reihenfolge wie die Kette selbst (mit anderen Worten, die verkettete Pseudo-Pack-Reihenfolge für eine Kette {$H1, $H2, $H3} wäre die Pseudo-Pack-Reihenfolge für $H1, gefolgt von der Pseudo-Pack-Reihenfolge für $H2, gefolgt von der Pseudo-Pack-Reihenfolge für $H3).

    Das Layout wird dann erweitert, sodass jede Schicht der inkrementellen MIDX-Kette eine *.bitmap-Datei schreiben kann. Die Objekte in der Bitmap jeder Schicht sind um die Anzahl der Objekte in den vorherigen Schichten der Kette versetzt.

Dateilayout

Anstatt einer einzigen multi-pack-index-Datei (mit einer optionalen Erweiterung .rev und .bitmap) in $GIT_DIR/objects/pack zu speichern, werden inkrementelle MIDXs im folgenden Layout gespeichert

$GIT_DIR/objects/pack/multi-pack-index.d/
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-chain
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H1.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H2.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H3.midx

Die Datei multi-pack-index-chain enthält eine Liste der inkrementellen MIDX-Dateien in der Kette, in Reihenfolge. Das obige Beispiel zeigt eine Kette, deren multi-pack-index-chain-Datei die folgenden Zeilen enthalten würde

$H1
$H2
$H3

Die Datei multi-pack-index-$H1.midx enthält die erste Schicht der Multi-Pack-Index-Kette. Die Datei multi-pack-index-$H2.midx enthält die zweite Schicht der Kette und so weiter.

Wenn sowohl eine inkrementelle als auch eine nicht-inkrementelle MIDX vorhanden sind, wird die nicht-inkrementelle MIDX immer zuerst gelesen.

Objektpositionen für inkrementelle MIDXs

Im ursprünglichen Multi-Pack-Index-Design verweisen wir auf Objekte über ihre lexikografische Position (nach Objekt-IDs) innerhalb des einzigen Multi-Pack-Index des Repositories. Im inkrementellen Multi-Pack-Index-Design verweisen wir auf Objekte über ihren Index in einer verketteten lexikografischen Ordnung aller Komponenten in der MIDX-Kette.

Wenn objects_nr() eine Funktion ist, die die Anzahl der Objekte in einer gegebenen MIDX-Schicht zurückgibt, dann ist der Index eines Objekts an der lexikografischen Position i innerhalb, sagen wir, $H3 definiert als

objects_nr($H2) + objects_nr($H1) + i

(In der C-Implementierung wird dies oft als i + m->num_objects_in_base berechnet).

Pseudo-Pack-Reihenfolge für inkrementelle MIDXs

Die ursprüngliche Implementierung von Multi-Pack-Erreichbarkeits-Bitmaps definierte die Pseudo-Pack-Reihenfolge in gitformat-pack[5] (siehe den Abschnitt "multi-pack-index reverse indexes") ungefähr wie folgt

Kurz gesagt, eine MIDX-Pseudo-Pack-Datei ist die deduplizierte Verkettung von Objekten in Packs, die von der MIDX gespeichert werden, angeordnet in Pack-Reihenfolge, und die Packs sind in MIDX-Reihenfolge angeordnet (wobei das bevorzugte Pack zuerst kommt).

Im inkrementellen MIDX-Design erweitern wir diese Definition, um Objekte aus mehreren Schichten der MIDX-Kette einzuschließen. Die Pseudo-Pack-Reihenfolge für inkrementelle MIDXs wird bestimmt, indem die Pseudo-Pack-Reihenfolge für jede Schicht der MIDX-Kette der Reihe nach verkettet wird. Formal werden zwei Objekte o1 und o2 wie folgt verglichen

  1. Wenn o1 in einer früheren Schicht der MIDX-Kette als o2 vorkommt, sortiert sich o1 vor o2.

  2. Andernfalls, wenn o1 und o2 in derselben MIDX-Schicht vorkommen und diese MIDX-Schicht keine Basis hat, dann sortiert sich das bevorzugte, wenn eines von pack(o1) und pack(o2) bevorzugt ist und das andere nicht, vor dem nicht bevorzugten. Wenn es eine Basisschicht gibt (d. h. die MIDX-Schicht ist nicht die erste Schicht in der Kette), dann sortiert sich o1 vor o2, wenn pack(o1) in der Pack-Reihenfolge dieser MIDX-Schicht früher vorkommt. Ebenso, wenn pack(o2) früher vorkommt, gilt das Gegenteil.

  3. Andernfalls kommen o1 und o2 im selben Pack vor und somit in derselben MIDX-Schicht. Sortieren Sie o1 und o2 nach ihrem Offset innerhalb ihrer enthaltenden Packdatei.

Beachten Sie, dass die bevorzugte Packdatei eine Eigenschaft der MIDX-Kette ist und nicht der einzelnen Schichten selbst. Grundsätzlich könnten wir eine bevorzugte Packdatei pro Schicht einführen, aber das ist jetzt weniger relevant, da wir die Wiederverwendung von Multi-Packs über die Menge der Packs in einer MIDX durchführen können.

Erreichbarkeits-Bitmaps und inkrementelle MIDXs

Jede Schicht einer inkrementellen MIDX-Kette kann ihre Objekte (und die Objekte aus jeder vorherigen Schicht derselben MIDX-Kette) in ihrer eigenen *.bitmap-Datei darstellen.

Die Struktur einer *.bitmap-Datei, die zu einer inkrementellen MIDX-Kette gehört, ist identisch mit der einer nicht-inkrementellen MIDX-Bitmap oder einer klassischen Einzel-Pack-Bitmap. Da Objekte am Ende der inkrementellen MIDX-Pseudo-Pack-Reihenfolge hinzugefügt werden (siehe oben), ist es möglich, eine Bitmap zu erweitern, wenn am Ende einer MIDX-Kette angehängt wird.

(Hinweis: Es ist ebenso möglich, eine zusammenhängende Sequenz von inkrementellen MIDX-Schichten und ihre *.bitmap-Dateien in einer einzigen Schicht und *.bitmap zu komprimieren, dies ist jedoch noch nicht implementiert.)

Die verwendeten Objektpositionen sind global innerhalb der Pseudo-Pack-Reihenfolge, sodass nachfolgende Schichten beispielsweise m->num_objects_in_base 0er Bits in jeder ihrer vier Typ-Bitmaps haben. Dies liegt daran, dass wir Typ-Bitmap-Einträge nur für Objekte schreiben, die in der Schicht vorhanden sind, die der Bitmap unmittelbar entspricht).

Beachten Sie auch, dass nur die Bitmap, die der neuesten Schicht in einer inkrementellen MIDX-Kette entspricht, zur Speicherung von Erreichbarkeitsinformationen über die interessanten und uninteressanten Objekte in einer Erreichbarkeitsabfrage verwendet wird. Frühere Bitmap-Schichten werden nur zum Nachschlagen von Commit- und Pseudo-Merge-Bitmaps aus dieser Schicht sowie den Typ-Level-Bitmaps für Objekte in dieser Schicht verwendet.

Um die Implementierung zu vereinfachen, werden Typ-Level-Bitmaps gleichzeitig iteriert und ihre Ergebnisse OR-verknüpft, um eine rekursive Aufrufung interner Bitmap-Funktionen zu vermeiden.

Zukünftige Arbeiten

  • Wenn die Multi-Pack-Index erweitert wird, um eine "stabile Objektordnung" (eine Funktion Order(hash) = Integer, die für einen gegebenen Hash konstant ist, auch wenn der Multi-Pack-Index aktualisiert wird) zu speichern, könnten MIDX-Bitmaps unabhängig von der MIDX aktualisiert werden.

  • Packdateien können als "speziell" markiert werden, indem leere Dateien verwendet werden, die den Anfangsnamen teilen, aber ".pack" durch ".keep" oder ".promisor" ersetzen. Wir können einen optionalen Datenblock zur Multi-Pack-Index hinzufügen, der Flags mit Informationen über die Packdateien speichert. Dies ermöglicht neue Zustände, wie z. B. repacked oder redeltified, die bei der Packwartung in einer Multi-Pack-Umgebung helfen können. Es kann auch hilfreich sein, Packdateien nach Objekttyp (Commit, Tree, Blob usw.) zu organisieren und diese Metadaten zur Wartung zu verwenden.

Verwandte Links

[0] https://bugs.chromium.org/p/git/issues/detail?id=6 Chromium-Arbeitselement für: Multi-Pack Index (MIDX)

[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/ Ein früherer RFC für die Multi-Pack-Index-Funktion

[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ Git Merge 2018 Contributor’s Summit Notizen (enthält Diskussionen über MIDX)