Mit Fiber Pool 1.0.0.3 ist es nun möglich, mehrere Dateien parallel zu bearbeiten – sogar mit nur einer Festplatte.
Für viele Anwendungstypen ist die Bearbeitung einer Vielzahl von Dateien ein wesentlicher Bestandteil ihres Funktionsumfangs. Virenscanner gehören beispielsweise dazu, aber auch Medienserver, Indexierungsdienste oder Bildbearbeitungsprogramme mit Stapelverarbeitung. Und wer sich mal gefragt hat, warum so manche Installation oder Deinstallation einer Anwendung so lange dauert – ja, einige Installationsprogramme gehören leider auch dazu.
Die Bearbeitung vieler Dateien ist natürlich ein langwieriger Prozess, aber bei den meisten dieser Anwendungen kriegt man das Gefühl, dass jedes Bit 10x angeschaut wird und das Ganze sehr träge bleibt, auch wenn man sie auf bessere Hardwaresysteme ausführt.
Der Grund dafür ist ein nicht-optimaler Dateiverarbeitungsalgorithmus, der nicht das verfügbare Potenzial an CPU- und I/O-Performance ausschöpft.
In diesem Artikel möchte ich Euch deswegen den in Fiber Pool implementierten Algorithmus vorstellen, von dem ich überzeugt bin, dass er eine sehr gute Performance bringt.
Zum besseren Verständnis beginne ich mit der Beschreibung eines einfachen Algorithmus, den ich mit jedem Evolutionsschritt nach und nach verändere, bis die finale Version erreicht ist. So könnt Ihr auch überprüfen, wo Ihr mit Euren Anwendungen steht.
Nun los:
1. Algorithmus: Datei erst vollständig einlesen, dann bearbeiten
Das ist der einfachste Algorithmus: Die Datei wird erst vollständig in den Speicher geladen, bevor sie bearbeitet wird.
Da zu einem Zeitpunkt entweder nur I/O oder nur CPU zum Zuge kommt, ist sowohl die I/O- als auch die CPU-Performance schwach.
Gravierend kann auch der Speicherverbrauch beim Bearbeiten von sehr großen Dateien sein. Deshalb müssen wir uns zunächst darum kümmern.
2. Algorithmus: Datei blockweise einlesen und blockweise bearbeiten
Die Dateien werden nun filetiert und in Teilen gelesen und bearbeitet.
Im Vergleich zum ersten Algorithmus ergibt sich keine Verbesserung bezüglich I/O- oder CPU-Performance. Dafür ist aber nun die Bearbeitung großer Dateien möglich, weil nur Speicher für einen Block (dessen Größe dynamisch sein kann) benötigt wird.
3. Algorithmus: Dateiblöcke asynchron einlesen
Dies ist der Standard-”Overlapped I/O”-Algorithmus: Mehrere Dateiblöcke werden asynchron eingelesen, während die CPU einen Block bearbeitet.
Durch das asynchrone Einlesen wird das gegenseitige Warten von CPU und I/O reduziert. Je nach Verarbeitungszeit profitiert die I/O-Performance mehr bei kurzer Dauer (Fall 1), während die CPU-Performance stärker bei langer Dauer steigt (Fall 2).
Der Speicherverbrauch ist nun aber höher als beim zweiten Algorithmus, da ein Puffer für die asynchron einzulesenden Dateiblöcke bereitgestellt werden muss.
4. Algorithmus: Dateiblöcke über Dateigrenzen hinaus asynchron einlesen
Das asynchrone Einlesen von Dateiblöcken wird nun so erweitert, dass gleich nach dem Lesen des letzten Blocks einer Datei der erste Block der nächsten Datei gelesen wird.
Durch Entfernen der Synchronisation zwischen zwei Dateien verbessert sich nochmals sowohl die I/O- als auch die CPU-Performance.
Für Systeme mit einem Prozessor und einer Festplatte ist dieser Algorithmus bereits optimal, da nun entweder die I/O-Performance (Fall 1) oder die CPU-Performance (Fall 2) ihr Maximum erreicht hat.
Aktuelle Systeme haben in der Regel mehr als einen Prozessor oder Kern und häufig weitere Festplatten. Um die Performance weiter zu erhöhen, kann dieses Mehr an Ressourcen in die nächsten Algorithmen einbezogen werden.
5. Algorithmus: Mehr Festplatten für Fall 1
Im Fall 1 des vorigen Algorithmus hat die I/O-Performance für eine Festplatte bereits ihr Maximum erreicht, während auf CPU-Seite noch Kapazitäten frei sind. Diese können abgerufen werden, wenn von weiteren Festplatten Dateien parallel gelesen werden können.
Durch den parallelen Zugriff auf weitere Festplatten kann die ansonsten unterbeschäftigte CPU nun besser ausgelastet werden. Naturgemäß verbessert sich auch die I/O-Performance.
Der Speicherverbrauch erhöht sich, weil für jede Festplatte, auf die parallel zugegriffen wird, ein Puffer bereitgestellt werden muss.
6. Algorithmus: Mehr Prozessoren für Fall 2
Im umgekehrten Fall 2 hat die CPU-Performance ihr Maximum erreicht, während im I/O-Bereich noch einiges möglich wäre. Stellt man mehr Prozessoren/Kerne zur Bearbeitung zur Verfügung, so kann das Potenzial durch Lesen einer weiteren Datei auf der selben Festplatte genutzt werden.
Von der Festplatte werden abwechselnd Blöcke mehrerer Dateien gelesen, um die vorhandenen Prozessoren/Kerne zu beschäftigen. Damit erhöht sich die I/O-Performance und naturgemäß die CPU-Performance.
Ähnlich wie beim 5. Algorithmus muss für jeden Prozessor/Kern ein Puffer bereitgestellt werden, was zu einem höheren Speicherverbrauch führt.
Zu guter Letzt der…
7. Algorithmus: Mehr Festplatten, mehr Prozessoren
Der letzte Schritt vereint den 5. und 6. Algorithmus, der nun sowohl maximale CPU- als auch maximale I/O-Performance erreicht.
Der Algorithmus priorisiert seine Aufgaben so, dass das Erreichen einer hohen CPU-Performance vor dem Erreichen einer hohen I/O-Performance steht. Dies kann sich in speziellen Fällen negativ auswirken, z.B. wenn man unter CPU-Volllast im Hintergrund eine Datei kopieren will. Dann erhält der Algorithmus selbst keine CPU-Zeit und kann keine I/O-Operationen ausführen.
Verwenden des Algorithmus mit Fiber Pool
Die Verwendung des Algorithmus mit Fiber Pool ist denkbar einfach:
- Sämtliche I/O-Aufgaben werden über den globalen I/O-Manager “g_ioManager” eingetragen. Dieser unterstützt zwar aktuell nur die Funktionen “Verzeichnis scannen”, “Datei in den Speicher lesen” und “Speicher in Datei schreiben”, mit der Zeit werden aber mehr dazukommen, und da er als Source Code verfügbar ist, kann er natürlich auch für eigene Zwecke erweitert werden.
- Die dazugehörigen Bearbeitungsaufgaben werden direkt über den Fiber Pool Task Scheduler eingetragen.
Beispiel: Virenscan
Sämtliche Dateien, die zum Scannen ausgewählt wurden, werden beim I/O-Manager zu Lesen eingereicht. Die dazugehörigen Scan-Operationen werden für jede Datei beim Fiber Pool Task Scheduler eingereicht. Fertig.
Damit das Ganze geordnet abläuft, erfolgt die gesamte Synchronisation zwischen I/O- und CPU-Task über das verwendete Speicherobjekt (aktuell vom Typ ISequentialVirtualMemory). Dieses blockiert den I/O-Task, wenn der gesamte Puffer aufgebraucht ist, und gibt ihn wieder frei, wenn Speicher wieder verfügbar wird. Entsprechend blockiert das Speicherobjekt den CPU-Task, wenn keine Daten zur Bearbeitung vorliegen, und gibt ihn bei Verfügbarkeit frei.
Für ein einfaches Programmierbeispiel empfehle ich, einen Blick auf das Sample “copyfile” zu werfen, das im Entwicklungspaket enthalten ist. Es bearbeitet zwar nicht viel, zeigt aber die Funktionsweise des I/O-Managers (serielles Lesen und Schreiben bei einer Festplatte, paralleles Lesen und Schreiben bei zwei Festplatten). Ein weiteres Beispiel ist in Arbeit.
Das soll es zunächst zum Thema “Parallel Dateiverarbeitung” gewesen sein. Auf Euer Feedback bin ich gespannt!