Warum ist der Git .git / objects / -Ordner in viele SHA-Präfix-Ordner unterteilt?

21

Git speichert intern Objekte (Blobs, Bäume) im .git/objects/Ordner. Jedes Objekt kann durch einen SHA1-Hash referenziert werden, der aus dem Inhalt des Objekts berechnet wird.

Objekte werden jedoch nicht .git/objects/direkt im Ordner gespeichert . Stattdessen wird jedes Objekt in einem Ordner gespeichert, der mit dem Präfix seines SHA1-Hash beginnt. Also würde ein Objekt mit dem Hash b7e23ec29af22b0b4e41da31e868d57226121c84bei gespeichert werden.git/objects/b7/e23ec29af22b0b4e41da31e868d57226121c84

Warum unterteilt Git seinen Objektspeicher auf diese Weise?

Die Ressourcen, die ich finden konnte, wie die Seite über Git-Interna bei git-scm, erklärten nur wie , nicht warum .

Qqwy
quelle

Antworten:

33

Es ist möglich, alle Dateien in einem Verzeichnis abzulegen, obwohl dies manchmal etwas umfangreich werden kann. Viele Dateisysteme haben ein Limit . Sie möchten ein Git-Repository auf einem FAT32-formatierten Laufwerk auf einem USB-Stick ablegen? Sie können nur 65.535 Dateien in einem einzigen Verzeichnis speichern. Dies bedeutet, dass die Verzeichnisstruktur unterteilt werden muss, damit das Füllen eines einzelnen Verzeichnisses weniger wahrscheinlich ist.

Dies würde sogar bei anderen Dateisystemen und größeren Git-Repositorys zu einem Problem werden. Ein relativ kleines Git-Repo, in dem ich rumhängen muss (ca. 360MiB) und das 181.546 Objekte für 11k-Dateien enthält. Ziehen Sie das Linux-Repo und Sie haben 4.374.054 Objekte. Wenn Sie diese alle in einem Verzeichnis ablegen würden, wäre es unmöglich, das Dateisystem auszuchecken und zum Absturz zu bringen (für eine Bedeutung von "Absturz").

So? Sie haben es byteweise aufgeteilt. Ähnliche Ansätze werden mit Anwendungen wie FireFox durchgeführt:

~/Li/Ca/Fi/Pr/7a/Cache $ ls
0/           4/           8/           C/           _CACHE_001_
1/           5/           9/           D/           _CACHE_002_
2/           6/           A/           E/           _CACHE_003_
3/           7/           B/           F/           _CACHE_MAP_

Darüber hinaus geht es auch um eine Frage der Leistung. Berücksichtigen Sie die NTFS-Leistung mit zahlreichen langen Dateinamen :

Windows NT benötigt viel Zeit, um Verzeichnisvorgänge auf NTFS-formatierten Laufwerken (Windows NT File System) auszuführen, die eine große Anzahl von Dateien mit langen Dateinamen (Namen, die nicht der 8.3-Konvention entsprechen) in einem einzelnen Verzeichnis enthalten.

Wenn NTFS Dateien in einem Verzeichnis auflistet, muss es nach den 8.3-Namen suchen, die den langen Dateinamen zugeordnet sind. Da ein NTFS-Verzeichnis in einem sortierten Zustand verwaltet wird, werden entsprechende lange Dateinamen und 8.3-Namen in der Verzeichnisliste in der Regel nicht nebeneinander angezeigt. Daher verwendet NTFS für jede vorhandene Datei eine lineare Suche im Verzeichnis. Infolgedessen steigt der Zeitaufwand für die Durchführung einer Verzeichnisliste mit dem Quadrat der Anzahl der Dateien im Verzeichnis. Für eine kleine Anzahl von Dateien (weniger als einige hundert) ist die Zeitverzögerung vernachlässigbar. Wenn sich die Anzahl der Dateien in einem Verzeichnis jedoch auf mehrere Tausend erhöht, kann sich der Zeitaufwand für eine Auflistung auf Minuten, Stunden oder sogar Tage erhöhen. Das Problem verschlimmert sich, wenn die langen Dateinamen sehr ähnlich sind - nur in den letzten Zeichen unterschiedlich.

Bei Dateien, die nach SHA1-Prüfsummen benannt sind, kann dies ein Rezept für eine Katastrophe und eine miserable Leistung sein.

Das Obige stammt aus einem technischen Hinweis von Windows NT 3.5 (und NTFS 1.2 - häufig verwendet von 1995 bis Anfang 2000). Dies kann auch in Dingen wie EXT3 festgestellt werden, bei denen Implementierungen des Dateisystems verknüpfte Listen sind, die O (n) Lookup erfordern . Und selbst mit diesem B-Tree-Wechsel:

Während der HTree-Algorithmus die Nachschlagezeiten erheblich verbesserte, konnte er bei Workloads, die readdir () verwendeten, einige Leistungseinbußen verursachen, um einige Vorgänge für alle Dateien in einem großen Verzeichnis auszuführen.
...
Eine mögliche Lösung zur Minderung dieses Leistungsproblems, das von Daniel Phillips und Andreas Dilger vorgeschlagen, aber noch nicht implementiert wurde, besteht darin, dass der Kernel freie Inodes auswählt, deren Inode-Nummern einer Eigenschaft entsprechen, die die Inodes nach ihrem Dateinamen-Hash gruppiert. Daniel und Andreas schlagen vor, den Inode aus einer Reihe von Inodes basierend auf der Größe des Verzeichnisses zuzuweisen und dann einen freien Inode aus diesem Bereich basierend auf dem Dateinamen-Hash auszuwählen. Dies sollte theoretisch die Menge an Thrashing reduzieren, die beim Zugriff auf die Inodes entsteht, auf die im Verzeichnis in readdir-Reihenfolge verwiesen wird. Insofern ist nicht klar, dass diese Strategie zu einer Beschleunigung führen wird; Tatsächlich kann dies die Gesamtzahl der Inode-Blöcke erhöhen, auf die möglicherweise verwiesen werden muss, und damit die Leistung der Workloads readdir () + stat () verschlechtern. Deutlich,

Übrigens war dieses Stück, wie man die Leistung verbessert, von 2005 an das gleiche Jahr, in dem git veröffentlicht wurde.

Wie bei Firefox und vielen anderen Anwendungen, die viele zwischengespeicherte Hash-Dateien haben, ist das Design das Aufteilen des Caches nach Byte. Es hat vernachlässigbare Leistungskosten, und wenn es plattformübergreifend mit Systemen verwendet wird, die möglicherweise etwas altmodisch sind, kann dies durchaus den Unterschied zwischen dem funktionierenden Programm und dem nicht funktionierenden Programm ausmachen.

Gemeinschaft
quelle
1
Sie haben bemerkt, dass der von Ihnen zitierte Artikel zur NTFS-Leistung für NT 3.5 von 1994 gilt, oder?
Avner Shahar-Kashtan
1
@ AvnerShahar-Kashtan yep. Git wurde 2005 veröffentlicht. Ich weiß, dass ich NTFS 1.2-basierte Dateisysteme in einer Unternehmensumgebung bis in die frühen 2000er Jahre (bei einem Technologieunternehmen) verwendet habe. Es gibt sicherlich eine Überschneidung zwischen den Anforderungen von git und den Dateisystemen auf derzeit allgemein verfügbaren Systemen.
Vielleicht wäre es klarer, wenn Sie angeben würden, dass dies ein historisches Artefakt des Standes der Technik bei der Einführung von git sein könnte, da für eine im Jahr 2015 gestellte Frage eine 20 Jahre alte technische Einschränkung angeführt wird (was die Antwort auf diese Frage aufgreift) ) scheint verwirrend.
Avner Shahar-Kashtan
Um fair zu sein, gitdas "Pack" -System mindert viele dieser Probleme. Theoretisch gitkönnte man nur ein einziges Verzeichnis verwenden und nur neu packen, wenn die Anzahl der Dateien in diesem Verzeichnis eine bestimmte (möglicherweise FS-abhängige) Grenze überschreitet.
Nneonneo
5
@ AvnerShahar-Kashtan Wenn Sie den verknüpften SO-Artikel lesen, werden Sie feststellen, dass der Umgang mit Verzeichnissen, die eine große Anzahl von Dateien enthalten, auf mehreren Dateisystemen und Betriebssystemen problematisch ist, nicht nur auf NT 3.5. Abgesehen von den Dateibeschränkungen kann bereits das Auflisten der Dateien einen hohen Overhead verursachen.
8

Dies ist aus zwei Gründen wünschenswert.

Verzeichnisse können nicht beliebig groß sein. Zum Beispiel sind einige (recht moderne!) Dateisysteme auf 32000 Einträge in einem einzigen Verzeichnis beschränkt. Die Anzahl der Commits im Linux-Kernel liegt in dieser Größenordnung. Durch Unterteilen der Festschreibungen durch die ersten beiden Hexadezimalstellen wird die Größe der obersten Ebene auf 256 Einträge begrenzt. Die Unterverzeichnisse werden für typische Git-Repos viel kleiner sein.

Verzeichnisse werden linear gescannt. In einigen Dateisystemen (z. B. der Ext * -Familie) ist ein Verzeichnis eine verknüpfte Liste oder Tabelle von Einträgen. Um eine Datei nachzuschlagen, wird die gesamte Liste durchsucht, bis ein passender Dateiname gefunden wurde. Dies ist natürlich für die Leistung unerwünscht. Viele moderne Dateisysteme verwenden zusätzlich Hash-Tabellen oder B-Bäume für die schnelle Suche, aber möglicherweise hat nicht jeder diese. Jedes Verzeichnis klein zu halten bedeutet schnelle Zugriffszeiten.

amon
quelle
1
"Einige (einigermaßen moderne!) Dateisysteme sind auf 32000 Einträge in einem einzigen Verzeichnis beschränkt." Wenn das die strengste Einschränkung ist, die Git zu erfüllen hat, wäre es dann nicht besser, wenn Git die ersten drei Zeichen des Hashes anstelle der ersten beiden verwendet hätte ? Dies würde bedeuten, dass das objectsVerzeichnis bis zu 4096 Unterverzeichnisse enthalten könnte, anstatt auf 256 beschränkt zu sein, was die obige Anforderung erfüllt, aber mit dem zusätzlichen Vorteil, dass diese Unterverzeichnisse 16x weniger wahrscheinlich wären,> 32000 Dateien selbst zu enthalten.
Sampablokuper
1

Mit diesem 256-Bucket kann git größere Repositorys auf Dateisystemen speichern, die die Anzahl der Dateien in einem Verzeichnis begrenzen, und Abstiegsleistung auf Dateisystemen bereitstellen, die mit Verzeichnissen mit vielen Dateien langsamer werden.

Kasper van den Berg
quelle
1

Es gibt einige Dateisystem- und / oder Dateisystemimplementierungen und / oder Libc-Implementierungen, bei denen die Leistung durch eine große Anzahl von Verzeichniseinträgen beeinträchtigt wird.

Jörg W. Mittag
quelle