Frage Welche Auswirkungen hat die Leistung auf Millionen von Dateien in einem modernen Dateisystem?


Nehmen wir an, wir verwenden ext4 (mit dir_index enabled) um 3M Dateien zu hosten (mit einer durchschnittlichen Größe von 750KB) und wir müssen entscheiden, welches Ordnerschema wir verwenden werden.

In dem erste Lösung, wenden wir eine Hash - Funktion auf die Datei an und verwenden einen Ordner mit zwei Ebenen (1 Zeichen für die erste Ebene und 2 Zeichen für die zweite Ebene) filex.for Hash ist gleich abcde1234Wir speichern es auf / Pfad /ABC/abcde1234-filex.for.

In dem zweite Lösung, wenden wir eine Hash - Funktion auf die Datei an und verwenden einen Ordner mit zwei Ebenen (2 Zeichen für die erste Ebene und 2 Zeichen für die zweite Ebene) filex.for Hash ist gleich abcde1234Wir speichern es auf / Pfad /ab / de/abcde1234-filex.for.

Für die erste Lösung haben wir das folgende Schema /path/[16 folders]/[256 folders] mit einem Durchschnitt von 732 Dateien pro Ordner (der letzte Ordner, in dem sich die Datei befindet).

Während der zweiten Lösung werden wir haben /path/[256 folders]/[256 folders] mit einem Durchschnitt von 45 Dateien pro Ordner.

Wenn wir daran denken, Dateien zu schreiben / zu entfernen / zu lesen (aber meistens gelesen) von diesem Schema viel (im Grunde das Nginx-Caching-System), Ist es leistungsbezogen sinnvoll, ob wir die eine oder andere Lösung gewählt haben?

Welche Werkzeuge könnten wir auch verwenden, um dieses Setup zu testen?


26
2017-08-13 16:53


Ursprung


Natürlich wird Benchmarking helfen. Aber ext4 ist möglicherweise das falsche Dateisystem dafür. Ich würde auf XFS schauen. - ewwhite
Ich würde nicht einfach ansehen XFS, ich würde es sofort ohne weiteres benutzen. Der B + -Baum schlägt jedes Mal die Hash-Tabelle. - Michael Hampton♦
Danke für die Tipps, Benchmarking ist ein bisschen schwer, obwohl ich versucht habe hdparm -Tt /dev/hdX aber es ist vielleicht nicht das am besten geeignete Werkzeug. - leandro moreira
Nein hdparm ist nicht das richtige Werkzeug, es ist eine Überprüfung der rohen Leistung des Blockgerätes und kein Test des Dateisystems. - HBruijn


Antworten:


Der Grund für diese Art von Verzeichnisstruktur liegt darin, dass Dateisysteme eine Datei in einem Verzeichnis finden müssen, und je größer das Verzeichnis ist, desto langsamer ist diese Operation.

Wie viel langsamer hängt vom Dateisystemdesign ab.

Das ext4 Dateisystem verwendet ein B-Baum um Verzeichniseinträge zu speichern. Ein Nachschlagen in dieser Tabelle wird erwartet O (log n) Zeit, die die meiste Zeit weniger ist als die naive lineare Tabelle, die ext3 und vorherige Dateisysteme verwendet haben (und wenn dies nicht der Fall ist, ist das Verzeichnis zu klein, um wirklich von Bedeutung zu sein).

Das XFS-Dateisystem verwendet a B + Baum stattdessen. Der Vorteil gegenüber einer Hash-Tabelle oder einem B-Baum ist, dass jeder Knoten mehrere untergeordnete Elemente haben kann b, wo in XFS b variiert und kann so hoch wie 254 (oder 19 für den Stammknoten; und diese Nummern möglicherweise veraltet sein). Dies gibt Ihnen eine zeitliche Komplexität von O (logb n), eine große Verbesserung.

Jedes dieser Dateisysteme kann Zehntausende von Dateien in einem einzigen Verzeichnis verarbeiten, wobei XFS in einem Verzeichnis mit der gleichen Anzahl von Inodes wesentlich schneller ist als ext4. Aber wahrscheinlich wollen Sie kein einziges Verzeichnis mit 3M-Inodes, da selbst bei einem B + -Baum die Suche einige Zeit dauern kann. Dies führte dazu, dass Verzeichnisse auf diese Weise überhaupt erstellt wurden.

Was Ihre vorgeschlagenen Strukturen betrifft, ist die erste Option, die Sie angegeben haben, genau das, was in nginx-Beispielen gezeigt wird. Es wird auf jedem Dateisystem gut funktionieren, obwohl XFS immer noch ein bisschen von Vorteil sein wird. Die zweite Option kann etwas besser oder etwas schlechter abschneiden, wird aber wahrscheinlich sogar bei Benchmarks ziemlich nah sein.


25
2017-08-13 22:52



Und für XFS oder ext4 wird die Hardware, auf die Sie das Dateisystem setzen, einen großen Einfluss auf die Performance haben. Ein langsames SATA-Laufwerk mit 5400 U / min kann ungefähr 50 zufällige E / A-Vorgänge ausführen, ein gutes SAS-Laufwerk mit 15000 U / min kann einige hundert ausführen, und eine SSD wird wahrscheinlich bandbreitenbegrenzt sein und einige Millionen zufällige E / A-Vorgänge haben wenn nicht mehr. - Andrew Henle
Streng genommen ist $ O (\ log_b n) $ für fixes $ b $ dieselbe Komplexität wie $ O (\ log n) $. Aber für das OP wären die tatsächlichen Konstanten wichtig. - Hagen von Eitzen


Nach meiner Erfahrung ist einer der Skalierungsfaktoren die Größe der Inodes, die eine Hash-Name-Partitionierungsstrategie erhalten.

Beide vorgeschlagenen Optionen erstellen bis zu drei Inode-Einträge für jede erstellte Datei. Außerdem erzeugen 732 Dateien einen Inode, der immer noch kleiner als die üblichen 16 KB ist. Für mich bedeutet dies, dass beide Optionen dasselbe ausführen.

Ich applaudiere Ihnen auf Ihrem kurzen Hash; frühere Systeme, an denen ich gearbeitet habe, haben die sha1sum der gegebenen Datei und gespleißten Verzeichnisse basierend auf dieser Zeichenfolge genommen, ein viel schwierigeres Problem.


5
2017-08-13 22:43



Was macht die Verwendung von SHA1-Summen (und anderen, längeren Hash-Summen) "ein viel schwierigeres Problem"? Es ist für menschliche Benutzer unhandlich, ja, aber es ist das gleiche für das Betriebssystem, das Dateisystem und andere Programme. - kbolino


Sicherlich wird jede dieser Optionen dazu beitragen, die Anzahl der Dateien in einem Verzeichnis auf etwas zu reduzieren, das vernünftig erscheint, für xfs oder ext4 oder welches Dateisystem auch immer. Es ist nicht offensichtlich, welches ist besser, müsste testen, um zu erzählen.

Benchmark mit Ihrer Anwendung, die so etwas wie die tatsächliche Arbeitslast simuliert, ist ideal. Sonst sollten Sie sich etwas einfallen lassen, das speziell viele kleine Dateien simuliert. Apropos, Hier ist eine Open-Source-Datei namens Smallfile. Die Dokumentation verweist auf einige andere Tools.

hdparm Es ist nicht so sinnvoll, die I / O-Funktion zu unterstützen. Es zeigt nicht die vielen kleinen I / Os oder riesigen Verzeichniseinträge, die mit sehr vielen Dateien verbunden sind.


4
2017-08-13 22:28





Eines der Probleme besteht darin, den Ordner zu scannen.

Stellen Sie sich eine Java-Methode vor, die den Scan für den Ordner ausführt.

Es muss eine große Menge an Speicher reservieren und es in kurzer Zeit freigeben, was für die JVM sehr schwer ist.

Die beste Möglichkeit besteht darin, die Ordnerstruktur so anzuordnen, dass sich jede Datei im dedizierten Ordner befindet, z. Jahr Monat Tag.

Die Art und Weise, wie ein vollständiger Scan ausgeführt wird, besteht darin, dass für jeden Ordner ein Lauf der Funktion ausgeführt wird, so dass JVM die Funktion beendet, den RAM-Speicher freigibt und ihn erneut in einem anderen Ordner ausführt.

Dies ist nur ein Beispiel, aber einen so großen Ordner zu haben macht keinen Sinn.


0
2017-08-13 23:14



Sie gehen von Java aus und durchsuchen den Ordner. In der Frage wird keiner erwähnt, und es gibt andere Möglichkeiten, den Ordner in Java neben dem Scannen zu bearbeiten. - user207421