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.
gitdas "Pack" -System mindert viele dieser Probleme. Theoretischgitkö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.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.
quelle
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.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.
quelle
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.
quelle