Der Anfängerleitfaden zum „reftable“-Format von Git

Bis vor Kurzem war das „files“-Format die einzige Möglichkeit in Git, Referenzen zu speichern. Mit der Version Git 2.45.0 kann Git nun Referenzen im „reftable“-Format speichern. Dieses neue Format ist ein Binärformat, das deutlich komplexer als das alte “files” Format ist. Diese Komplexität ermöglicht es jedoch, einige Mängel des „files“-Formats zu beheben. Die Entwicklungsziele des „reftable“-Formats sind unter anderem folgende:

• Die Suche nach einzelnen Referenzen und die Iterationen über zahlreichen Referenzen soll so effizient und schnell wie möglich sein.
• Das konsistente Lesen von Referenzen soll unterstützt werden, sodass Git nie einen Zwischenzustand liest, wenn ein Update an mehreren Referenzen nur teilweise angewendet wurde.
• Atomares Schreiben soll unterstützt werden, sodass die Aktualisierung von mehreren Referenzen nur entweder vollständig oder gar nicht möglich ist.
• Effiziente Speicherung von Referenzen und Reflog-Einträgen.

In diesem Artikel kommen wir allen Feinheiten des „reftable“-Formats auf die Schliche und sehen uns genau an, wie es funktioniert.

So speichert Git Referenzen

Bevor wir uns die Details des „reftable“-Formats ansehen, fassen wir nochmals kurz zusammen, wie Git in der Vergangenheit Referenzen gespeichert hat. Wenn du damit bereits vertraut bist, kannst du gleich zum nächsten Abschnitt springen.

Ein Git-Repository enthält zwei wesentliche Datenstrukturen:

• Objekte, die die eigentlichen Daten deines Repositorys enthalten. Dazu gehören Commits, die Verzeichnisstruktur und die Blobs, die deinen Quellcode enthalten. Objekte verweisen aufeinander und bilden so einen Objektgraphen. Außerdem hat jedes Objekt eine Objekt-ID, durch die es eindeutig identifiziert wird.

• Referenzen wie Branches und Tags sind Wegweiser im Objektgraphen, sodass du Objekten Namen geben kannst, die einfacher zu merken sind, und verschiedene Wege deines Entwicklungsverlaufs nachverfolgen kannst. Ein Repository kann zum Beispiel einen main-Branch enthalten, der eine Referenz mit dem Namen refs/heads/main ist und auf einen bestimmten Commit zeigt.

Referenzen werden in der Referenzdatenbank gespeichert. Bis Git 2.45.0 gab es nur das Datenbankformat „files“. In diesem Format wird jede Referenz als einfache Datei gespeichert, die eines der folgenden Elemente enthält:

• Eine normale Referenz, die die Objekt-ID des Commits enthält, auf den sie zeigt.
• Eine symbolische Referenz, die den Namen einer anderen Referenz enthält. Dies ist ähnlich wie ein symbolischer Link, der auf eine andere Datei zeigt.

In regelmäßigen Abständen werden diese Referenzen in eine einzige packed-refs-Datei komprimiert, damit Referenzen effizienter durchsucht werden können.

Die folgenden Beispiele sollen eine Vorstellung davon geben, wie das „files“-Format funktioniert:

$ git init .
$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 6917c17] Initial commit

# HEAD ist eine symbolische Referenz, die auf refs/heads/main zeigt.
$ cat .git/HEAD
ref: refs/heads/main

# refs/heads/main ist eine normal Referenz, die auf einen Commit zeigt.
$ cat .git/refs/heads/main
6917c178cfc3c50215a82cf959204e9934af24c8

# git-pack-refs(1) komprimiert diese Referenzen in eine packed-refs Datei.
$ git pack-refs --all
$ cat .git/packed-refs
# pack-refs with: peeled fully-peeled sorted
6917c178cfc3c50215a82cf959204e9934af24c8 refs/heads/main

Hochrangige Struktur von reftables

Wenn du nun Git 2.45.0 oder eine neuere Version installiert hast, kannst du ein Repository mit dem „reftable“-Format erstellen, indem du den Switch --ref-format=reftable verwendest:

$ git init --ref-format=reftable .Initialized empty Git repository in /tmp/repo/.git/
$ git rev-parse --show-ref-format
reftable

# Irrelevante Dateien wurden für ein einfacheres Verständnis entfernt.
$ tree .git
.git
├── config
├── HEAD
├── index
├── objects
├── refs
│   └── heads
└── reftable
	├── 0x000000000001-0x000000000002-40a482a9.ref
	└── tables.list

4 directories, 6 files

Sieh dir zunächst die Repository-Konfiguration an. Du wirst feststellen, dass sie den Schlüssel extension.refstorage enthält:

$ cat .git/config
[core]
    repositoryformatversion = 1
    filemode = true
    bare = false
    logallrefupdates = true
[extensions]
    refstorage = reftable

Diese Konfiguration teilt Git mit, dass das Repository mit dem „reftable“-Format initialisiert wurde und gibt an, dass Git das „reftable“-Backend nutzen muss, um darauf zuzugreifen.

Seltsamerweise enthält das Repository immer noch einige Dateien, die aussehen, als würde das „files“-Backend verwendet werden:

• HEAD würde normalerweise eine symbolische Referenz sein, die auf deinen derzeit ausgecheckten Branch zeigt. Obwohl es nicht vom „reftable“-Backend verwendet wird, ist es für Git-Clients erforderlich, um das Verzeichnis als Git-Verzeichnis zu erkennen. Wenn du also das „reftable“-Format verwendest, ist HEAD ein Stub mit dem Inhalt ref: refs/heads/.invalid.

• refs/heads ist eine Datei mit dem Inhalt this repository uses the reftable format. Git-Clients, die das Format „reftable“ nicht kennen, würden normalerweise erwarten, dass dieser Pfad ein Verzeichnis ist. Wenn du also diesen Pfad bewusst als Datei erstellst, führt dies dazu, dass ältere Git-Clients fehlschlagen, wenn sie versuchen, mit dem „files“-Backend auf das Repository zuzugreifen.

Die tatsächlichen Referenzen werden im Verzeichnis reftable/ gespeichert:

$ tree .git/reftable
.git/reftable/
├──0x000000000001-0x000000000001-794bd722.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000001-794bd722.ref

Es gibt hier zwei Dateien:

• 0x000000000001-0x000000000001-794bd722.ref ist eine Tabelle mit Referenzen und den Reflog-Einträgen in einem Binärformat.

• tables.list ist eine Liste von Tabellen. Im aktuellen Status des Repositorys enthält die Datei eine Zeile, die der Name der Tabelle ist. Diese Datei verfolgt den aktuellen Satz aktiver Tabellen in der „reftable“-Datenbank und wird aktualisiert, wenn neue Tabellen zum Repository hinzugefügt werden.

Wenn du eine Referenz aktualisierst, wird eine neue Tabelle erstellt:

$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 1472a58] Initial commit

$ tree .git/reftable
.git/reftable/
├──0x000000000001-0x000000000002-eb87d12b.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000002-eb87d12b.ref

Wie du sehen kannst, wurde die vorherige Tabelle durch eine neue ersetzt. Darüber hinaus wurde die Datei tables.list aktualisiert und enthält nun die neue Tabelle.

Die Struktur einer Tabelle

Wie bereits erwähnt, sind die eigentlichen Daten der Referenzdatenbank in Tabellen enthalten. Grob gesagt ist eine Tabelle in mehrere Abschnitte unterteilt:

• Der „Header“ enthält Metadaten zur Tabelle. Dazu gehören unter anderem die Version des Formats, die Blockgröße und die vom Repository verwendete Hash-Funktion (z. B. SHA1 oder SHA256).
• Der Abschnitt „Ref“ enthält deine Referenzen. Diese Datensätze haben einen Schlüssel, der dem Referenznamen entspricht und entweder auf eine Objekt-ID für reguläre Referenzen oder auf eine andere Referenz für symbolische Referenzen zeigt.
• Der Abschnitt „Obj“ enthält die umgekehrte Zuordnung von Objekt-IDs zu den Referenzen, die auf diese Objekt-IDs zeigen. Diese ermöglichen es Git, effizient zu suchen, welche Referenzen auf eine bestimmte Objekt-ID zeigen.
• Der Abschnitt „Log“ enthält deine Reflog-Einträge. Diese Datensätze haben einen Schlüssel, der dem Referenznamen entspricht, sowie einen Index, der die Nummer des Reflog-Eintrags darstellt. Außerdem enthalten sie die alten und neuen Objekt-IDs sowie die Nachricht für diesen Reflog-Eintrag.
• Der „Footer“ enthält Zeiger zu den verschiedenen Abschnitten.

Die Abschnittstypen sind alle ähnlich strukturiert. Abschnitte enthalten eine Reihe von Datensätzen, die nach den Schlüsseln der einzelnen Datensätze sortiert sind. Wenn du zum Beispiel zwei Ref-Datensätze refs/heads/aaaaa und refs/heads/bbb hast, hast du zwei Ref-Datensätze mit diesen Referenznamen als jeweiligen Schlüssel, weshalb refs/heads/aaaaa vor refs/heads/bbb kommt.

Darüber hinaus ist jeder Abschnitt in Blöcke mit einer festen Länge unterteilt. Diese Blocklänge ist im Header codiert und dient zwei Zwecken:

• Da sie den Anfang des Abschnitts markieren und die Blockgröße angeben, weiß der bzw. die Leser(in) implizit, wo jeder der Blöcke beginnt. Dadurch kann Git gleich in die Mitte des Abschnitts springen, ohne vorherige Blocks lesen zu müssen. So kann die binäre Suche in Blöcken das Durchsuchen von Datensätzen beschleunigen.
• Sie stellt sicher, dass Git weiß, wie viele Daten gleichzeitig von der Festplatte gelesen werden sollen. Folglich ist die Blockgröße standardmäßig auf 4 KiB eingestellt, was die häufigste Sektorgröße für Festplatten ist. Die maximale Blockgröße beträgt 16 MB.

Wenn wir zum Beispiel in einen „ref“-Abschnitt schauen, sieht er ungefähr wie die folgende Grafik aus. Achte darauf, wie die Datensätze lexikografisch in den Blocks, aber auch blockübergreifend sortiert sind.

Mit diesem Wissen können wir nun einen Datensatz finden, indem wir die folgenden Schritte befolgen:

1. Führe eine Binärsuche über die Blocks durch, indem du dir die Schlüssel der jeweiligen ersten Datensätze ansiehst und den Block identifizierst, der unseren Datensatz enthalten muss.

2. Führe eine lineare Suche in den Datensätzen dieses Blocks durch.

Beide Schritte sind immer noch recht ineffizient. Wenn wir viele Blöcke haben, müssen wir logarithmisch viele davon in unserer Binärsuche lesen, um den gewünschten Block zu finden. Und wenn Blöcke viele Datensätze enthalten, müssen wir vielleicht bei der linearen Suche alle davon lesen.

Das „reftable“-Format verfügt über zusätzliche integrierte Mechanismen, um diese Leistungsbedenken auszuräumen. Wir gehen in den nächsten Abschnitten darauf ein.

Präfix-Komprimierung

Wie du vielleicht bemerkt hast, haben alle Datensatzschlüssel das gleiche Präfix refs/. Dies ist häufig so in Git:

• Alle Branches beginnen mit refs/heads/.
• Alle Tags beginnen mit refs/tags/.

Daher gehen wir davon aus, dass nachfolgende Datensätze höchstwahrscheinlich einen signifikanten Anteil ihres Schlüssels gemeinsam haben. Dies ist eine gute Gelegenheit, um wertvollen Speicherplatz zu sparen. Da wir wissen, dass die meisten Schlüssel ein gemeinsames Präfix haben, ist es sinnvoll, dies zu optimieren.

Die Optimierung verwendet Präfix-Komprimierung. Jeder Datensatz kodiert eine Präfixlänge, die den Leser(innen) mitteilt, wie viele Bytes des Schlüssels des vorhergehenden Datensatzes wiederverwendet werden sollen. Wenn wir zwei Datensätze haben, refs/heads/a und refs/heads/b, kann letzterer kodiert werden, indem man eine Präfixlänge von 11 angibt und dann nur das Suffix b speichert. Die Leser(innen) nehmen dann die ersten 11 Bytes von refs/heads/a, was refs/heads/ ist, und fügen das Suffix b hinzu.

Neustart-Punkte

Wie bereits erklärt, ist eine lineare Suche der beste Weg, mit unserem derzeitigen Wissen über das „reftable“-Format in einem Block nach einer Referenz zu suchen. Der Grund dafür ist, dass die Datensätze keine fixe Länge haben. Daher können wir nicht feststellen, wo Datensätze beginnen, ohne von Anfang an den Block zu durchsuchen. Auch wenn Datensätze eine fixe Länge hätten, könnten wir nicht in der Mitte eines Blocks suchen, da die Präfix-Kompression erfordert, dass wir auch die vorhergehenden Datensätze lesen.

Eine lineare Suche wäre ziemlich ineffizient, da Blöcke Hunderte oder sogar Tausende von Datensätzen enthalten können. Um dieses Problem zu beheben, codiert das „reftable“-Format sogenannte Neustart-Punkte in jeden Block. Neustart-Punkte sind unkomprimierte Datensätze, bei denen keine Präfix-Komprimierung verwendet wird. Folglich enthalten Datensätze an Neustart-Punkten immer ihren vollständigen Schlüssel, und es wird möglich, den Datensatz direkt zu suchen und zu lesen, ohne die vorhergehenden Datensätze lesen zu müssen. Diese Neustart-Punkte sind in der Fußzeile jedes Blocks aufgeführt.

Mit diesen Informationen können wir eine lineare Suche über den Block vermeiden. Stattdessen können wir jetzt eine Binärsuche über die Neustart-Punkte durchführen, bei der wir nach dem ersten Neustart-Punkt mit einem Schlüssel suchen, der lexikographisch größer ist als der gesuchte Schlüssel. Daraus folgt, dass sich der gewünschte Datensatz in dem Abschnitt befinden muss, der sich vom vorhergehenden Neustart-Punkt bis zum identifizierten Neustart-Punkt erstreckt.

Daher ist unser erstes Vorgehen bei der Suche nach einem Datensatz (Binärsuche nach dem Block, Linearsuche nach dem Datensatz) nun wie folgt:

1. Führe eine Binärsuche über die Blocks durch und finde den Block, der unseren Datensatz enthalten muss.

2. Führe eine Binärsuche über die Neustart-Punkte durch und identifiziere den Unterabschnitt des Blocks, der unseren Datensatz enthalten muss.

3. Führe eine lineare Suche in den Datensätzen dieses Unterabschnitts.

Indizes

Die Suche nach Datensätzen in einem Block wäre nun einigermaßen effizient. Es ist aber weiterhin ineffizient, den Block selbst zu finden. Eine Binärsuche kann bei ein paar Blöcken funktionieren, aber Repositories mit Millionen von Referenzen können Hunderte oder sogar Tausende von Blöcken haben. Ohne zusätzliche Datenstruktur würde dies durchschnittlich logarithmisch viele Festplattenzugriffe verursachen. Um dies zu vermeiden, kann auf jeden Abschnitt ein Indexabschnitt folgen, der eine effiziente Möglichkeit bietet, einen Block nachzuschlagen. Jeder Indexdatensatz enthält die folgenden Informationen:

• Die Position des Blocks, den er indiziert.
• Der Schlüssel des letzten Datensatzes des Blocks, den er indiziert.

Bei drei oder weniger Blöcken erfordert eine Binärsuche immer höchstens zwei Festplattenlesevorgänge, um den gewünschten Zielblock zu finden. Dies ist die gleiche Anzahl von Lesevorgängen, die wir mit einem Index hätten: einen, um den Index selbst zu lesen, und einen, um den gewünschten Block zu lesen. Folglich werden Indizes nur geschrieben, wenn sie tatsächlich einige Lesevorgänge einsparen würden, was ab vier indizierten Blöcken der Fall ist.

Nun stellt sich die Frage: Was passiert, wenn der Index selbst so groß wird, dass er sich über mehrere Blöcke erstreckt? Du hast es vielleicht erraten: Wir schreiben einen weiteren Index, der den Index indiziert. Diese mehrstufigen Indizes werden erst dann wirklich notwendig, wenn du Repositories mit hunderttausenden von Referenzen hast.

Mit diesen Indizes können wir jetzt das Verfahren zum Nachschlagen von Datensätzen noch effizienter machen:

1. Finde heraus, ob es einen Index gibt, indem du dir die Fußzeile der Tabelle ansiehst.
   • Wenn es einen gibt, führe eine Binärsuche über den Index durch, um den gewünschten Block zu finden. Dieser Block kann selbst auf einen Indexblock verweisen. In diesem Fall müssen wir diesen Schritt wiederholen, bis wir einen Datensatz des gewünschten Typs finden.
   • Ansonsten führe eine Binärsuche über die Blöcke durch, wie wir es zuvor getan haben.
2. Führe eine Binärsuche über die Neustart-Punkte durch und identifiziere den Unterabschnitt des Blocks, der unseren Datensatz enthalten muss.
3. Führe eine lineare Suche in den Datensätzen dieses Unterabschnitts durch.

Mehrere Tabellen

Bis jetzt haben wir nur besprochen, wie man eine einzelne Tabelle liest. Aber wie der Name tables.list schon sagt, kannst du tatsächlich eine Liste von Tabellen in deiner „reftable“-Datenbank haben.

Jedes Mal, wenn du eine Referenz in deinem Repository aktualisierst, wird eine neue Tabelle geschrieben und an tables.list angehängt. So hast du schließlich mehrere Tabellen:

$ tree .git/reftable/
.git/reftable/
├──0x0000000000000001-0x000000000007-8dcd8a77.ref
├── 0x000000000008-0x000000000008-30e0f6f6.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000007-8dcd8a77.ref
0x000000000008-0x000000000008-30e0f6f6.ref

Um den tatsächlichen Status eines Repositorys zu lesen, müssen wir diese mehreren Tabellen zu einer einzigen virtuellen Tabelle zusammenführen.

Du fragst dich vielleicht: Wenn für jede Referenzaktualisierung eine Tabelle geschrieben wird und dieselbe Referenz mehrmals aktualisiert wird, woher kennt das „reftable“-Format den aktuellsten Wert einer bestimmten Referenz? Intuitiv könnte man davon ausgehen, dass der Wert derjenige aus der neuesten Tabelle ist, die die Referenz enthält.

Tatsächlich hat jeder einzelne Datensatz einen sogenannten Aktualisierungsindex, der die „Priorität“ eines Datensatzes kodiert. Wenn beispielsweise zwei Ref-Datensätze mit demselben Namen existieren, überschreibt derjenige mit dem höheren Aktualisierungsindex denjenigen mit dem niedrigeren Aktualisierungsindex.

Diese Aktualisierungsindizes sind in der obigen Dateistruktur sichtbar. Die langen Hex-Zeichenfolgen (z. B. 0x000000000001) sind die Aktualisierungsindizes, wobei die linke Seite des Tabellennamens der minimale Aktualisierungsindex ist, der in der Tabelle enthalten ist, und die rechte Seite der maximale Aktualisierungsindex ist.

Das Zusammenführen der Tabellen erfolgt dann über eine Vorrangwarteschlange, die nach dem Schlüssel des Ref-Datensatzes sowie dem Aktualisierungsindex geordnet ist. Angenommen, wir möchten alle Ref-Datensätze durchsuchen, würden wir wie folgt vorgehen:

1. Füge für jede Tabelle ihren ersten Datensatz zur Vorrangwarteschlange hinzu.

2. Liefere den Kopf der Vorrangwarteschlange. Da die Warteschlange nach Aktualisierungsindex geordnet ist, muss sie die aktuellste Version sein. Füge das nächste Element aus dessen Tabelle zur Vorrangwarteschlange hinzu.

3. Ziehe alle Datensätze aus der Warteschlange, die den gleichen Namen haben. Diese Datensätze werden verschattet, was bedeutet, dass sie nicht angezeigt werden. Füge für jede Tabelle, für die wir Datensätze ablegen, den nächsten Datensatz zur Vorrangwarteschlange hinzu.

Jetzt können wir bereinigen und den Vorgang wiederholen, um Datensätze für andere Schlüssel zu lesen.

Tabellen können spezielle „tombstone“-Datensätze enthalten, die einen Datensatz als gelöscht markieren. So können wir Datensätze löschen, ohne den jeweiligen Datensatz aus allen Tabellen löschen zu müssen.

Autokomprimierung

Während die Idee hinter der Vorrangwarteschlange zwar einfach ist, wäre es allerdings eher ineffizient, Hunderte oder sogar nur Dutzende von Tabellen auf diese Weise zusammenzuführen. Es stimmt, dass jede Aktualisierung an deinen Referenzen eine neue Tabelle an deine tables.list-Datei anhängt. Das ist jedoch nur ein Teil der Wahrheit.

Der andere Teil ist die Autokomprimierung: Nachdem eine neue Tabelle an die Liste der Tabellen angehängt wurde, überprüft das „reftable“-Backend, ob manche der Tabellen zusammengeführt werden sollen. Dies erfolgt durch eine einfache Heuristik. Wir überprüfen, ob die Liste der Tabellen eine geometrische Folge der Dateigrößen bildet. Jede Tabelle n muss mindestens doppelt so groß sein wie die nächstletzte Tabelle n + 1. Wenn gegen diese geometrische Folge verstoßen wird, komprimiert das Backend die Tabellen, sodass die geometrische Folge wiederhergestellt wird.

Im Laufe der Zeit führt dies zu Strukturen, die wie folgt aussehen:

$ du --apparent-size .git/reftable/*
429    .git/reftable/0x000000000001-0x00000000bd7c-d9819000.ref
101    .git/reftable/0x00000000bd7d-0x00000000c5ac-c34b88a4.ref
32    .git/reftable/0x00000000c5ad-0x00000000cc6c-60391f53.ref
8    .git/reftable/0x00000000cc6d-0x00000000cdc1-61c30db1.ref
3    .git/reftable/0x00000000cdc2-0x00000000ce67-d9b55a96.ref
1    .git/reftable/0x00000000ce68-0x00000000ce6b-44721696.ref
1    .git/reftable/tables.list

Beachte, wie für jede einzelne Tabelle die Eigenschaft size(n) > size(n+1) * 2 gilt.

Eine der Folgen der Autokomprimierung ist, dass sich das „reftable“-Backend selbst erhält. Wir müssen somit nicht mehr den Befehl git pack-refs zum Optimieren der Referenzen ausführen.

Möchtest du mehr erfahren?

Du solltest jetzt ein gutes Verständnis dafür haben, wie das neue „reftable“-Format im Detail funktioniert. Wenn du noch tiefer in das Format eintauchen möchtest, kannst du dir dessen technische Dokumentation des Git-Projekts ansehen.

Lies dir unsere Zusammenfassung von Git 2.45.0 durch, um herauszufinden, was sonst noch in dieser Version von Git auf dich wartet.