Dieser Artikel ist bereits der zweite zum Thema Hochgeschwindigkeits-Datenkomprimierung. Im ersten Artikel wurde ein Kompressor beschrieben, der mit einer Geschwindigkeit von 10 GB/Sek. arbeitet. pro Prozessorkern (minimale Komprimierung, RTT-Min).
Dieser Kompressor wurde bereits in der Ausrüstung forensischer Duplikatoren zur Hochgeschwindigkeitskomprimierung von Speichermedien-Dumps und zur Verbesserung der Stärke der Kryptographie implementiert; er kann auch zum Komprimieren von Bildern virtueller Maschinen und RAM-Auslagerungsdateien beim Speichern mit hoher Geschwindigkeit verwendet werden SSD-Laufwerke.
Im ersten Artikel wurde außerdem die Entwicklung eines Komprimierungsalgorithmus zur Komprimierung von Sicherungskopien von HDD- und SSD-Festplattenlaufwerken (mittlere Komprimierung, RTT-Mid) mit deutlich verbesserten Datenkomprimierungsparametern angekündigt. Mittlerweile ist dieser Kompressor komplett fertig und in diesem Artikel geht es darum.
Ein Kompressor, der den RTT-Mid-Algorithmus implementiert, bietet eine Komprimierungsrate, die mit Standardarchivierern wie WinRar, 7-Zip vergleichbar ist und im Hochgeschwindigkeitsmodus arbeitet. Gleichzeitig ist seine Arbeitsgeschwindigkeit um mindestens eine Größenordnung höher.
Die Geschwindigkeit des Datenpackens/-entpackens ist ein kritischer Parameter, der den Anwendungsbereich von Komprimierungstechnologien bestimmt. Es ist unwahrscheinlich, dass irgendjemand auf die Idee kommt, ein Terabyte Daten mit einer Geschwindigkeit von 10-15 Megabyte pro Sekunde zu komprimieren (dies ist genau die Geschwindigkeit von Archivierern im Standardkomprimierungsmodus), da dies bei voller Prozessorauslastung fast zwanzig Stunden dauern würde. .
Andererseits kann das gleiche Terabyte mit Geschwindigkeiten in der Größenordnung von 2–3 Gigabyte pro Sekunde in etwa zehn Minuten kopiert werden.
Daher ist die Komprimierung großvolumiger Informationen wichtig, wenn sie mit einer Geschwindigkeit durchgeführt wird, die nicht geringer ist als die Geschwindigkeit der tatsächlichen Ein-/Ausgabe. Bei modernen Systemen sind es mindestens 100 Megabyte pro Sekunde.
Moderne Kompressoren können solche Geschwindigkeiten nur im „Schnell“-Modus erzeugen. In diesem aktuellen Modus vergleichen wir den RTT-Mid-Algorithmus mit herkömmlichen Kompressoren.
Vergleichende Tests eines neuen Komprimierungsalgorithmus
Im Rahmen des Testprogramms funktionierte der RTT-Mid-Kompressor. In einer echten „funktionierenden“ Anwendung arbeitet es viel schneller, nutzt Multithreading sinnvoll und verwendet einen „normalen“ Compiler, nicht C#.
Da die im Vergleichstest verwendeten Kompressoren auf unterschiedlichen Prinzipien aufgebaut sind und unterschiedliche Datentypen unterschiedlich komprimieren, wurde zur Objektivität des Tests die Methode der Messung der „Durchschnittstemperatur im Krankenhaus“ verwendet...
Es wurde eine Sektor-für-Sektor-Dump-Datei einer logischen Festplatte mit dem Betriebssystem Windows 10 erstellt; dies ist die natürlichste Mischung verschiedener Datenstrukturen, die tatsächlich auf jedem Computer verfügbar ist. Durch die Komprimierung dieser Datei können Sie die Geschwindigkeit und den Grad der Komprimierung des neuen Algorithmus mit den fortschrittlichsten Kompressoren vergleichen, die in modernen Archivierungsprogrammen verwendet werden.
Hier ist die Dump-Datei:
Die Dump-Datei wurde mit den Kompressoren PTT-Mid, 7-zip und WinRar komprimiert. Der WinRar- und 7-zip-Kompressor wurde auf maximale Geschwindigkeit eingestellt.
Kompressor läuft 7-zip:
Es belastet den Prozessor um 100 %, während die durchschnittliche Geschwindigkeit beim Lesen des Original-Dumps etwa 60 Megabyte/Sek. beträgt.
Kompressor läuft WinRAR:
Die Situation ist ähnlich, die Prozessorauslastung beträgt fast 100 %, die durchschnittliche Dump-Lesegeschwindigkeit beträgt etwa 125 Megabyte/Sek.
Wie im vorherigen Fall wird die Geschwindigkeit des Archivers durch die Leistungsfähigkeit des Prozessors begrenzt.
Das Kompressortestprogramm läuft jetzt RTT-Mitte:
Der Screenshot zeigt, dass der Prozessor zu 50 % ausgelastet ist und die restliche Zeit im Leerlauf ist, da die komprimierten Daten nirgendwo hochgeladen werden können. Der Daten-Upload-Datenträger (Datenträger 0) ist fast vollständig geladen. Die Datenlesegeschwindigkeit (Festplatte 1) variiert stark, liegt aber im Durchschnitt bei über 200 Megabyte/Sek.
Die Geschwindigkeit des Kompressors wird in diesem Fall durch die Fähigkeit begrenzt, komprimierte Daten auf Datenträger 0 zu schreiben.
Nun das Komprimierungsverhältnis der resultierenden Archive:
Es ist ersichtlich, dass der RTT-Mid-Kompressor die beste Komprimierungsleistung erbracht hat; das von ihm erstellte Archiv war 1,3 GigaByte kleiner als das WinRar-Archiv und 2,1 GigaByte kleiner als das 7z-Archiv.
Zeitaufwand für die Erstellung des Archivs:
- 7-zip – 26 Minuten 10 Sekunden;
- WinRar – 17 Minuten 40 Sekunden;
- RTT-Mitte – 7 Minuten 30 Sekunden.
So konnte selbst ein nicht optimiertes Testprogramm mit dem RTT-Mid-Algorithmus ein Archiv mehr als zweieinhalb Mal schneller erstellen, wobei das Archiv deutlich kleiner ausfiel als das seiner Konkurrenten...
Wer den Screenshots nicht glaubt, kann deren Echtheit selbst überprüfen. Das Testprogramm finden Sie unter , herunterladen und prüfen.
Aber nur auf Prozessoren mit AVX-2-Unterstützung. Ohne Unterstützung dieser Anweisungen funktioniert der Kompressor nicht. Testen Sie den Algorithmus nicht auf älteren AMD-Prozessoren, diese sind langsam bei der Ausführung von AVX-Anweisungen ...
Verwendete Komprimierungsmethode
Der Algorithmus verwendet eine Methode zur Indizierung wiederholter Textfragmente in Byte-Granularität. Diese Komprimierungsmethode ist seit langem bekannt, wurde jedoch nicht eingesetzt, da der Matching-Vorgang hinsichtlich der erforderlichen Ressourcen sehr aufwändig war und viel mehr Zeit in Anspruch nahm als der Aufbau eines Wörterbuchs. Der RTT-Mid-Algorithmus ist also ein klassisches Beispiel für die Bewegung „zurück in die Zukunft“ ...
Der PTT-Kompressor verwendet einen einzigartigen Hochgeschwindigkeits-Match-Suchscanner, der es uns ermöglicht, den Komprimierungsprozess zu beschleunigen. Ein selbstgebauter Scanner, das ist „mein Charme…“, „er ist ziemlich teuer, weil er komplett handgefertigt ist“ (in Assembler geschrieben).
Der Übereinstimmungssuchscanner basiert auf einem zweistufigen Wahrscheinlichkeitsschema: Zuerst wird das Vorhandensein eines „Zeichens“ einer Übereinstimmung gescannt, und erst nachdem das „Zeichen“ an dieser Stelle identifiziert wurde, wird das Verfahren zur Erkennung einer echten Übereinstimmung durchgeführt ist gestartet.
Das Match-Suchfenster hat eine unvorhersehbare Größe, abhängig vom Grad der Entropie im verarbeiteten Datenblock. Bei völlig zufälligen (inkompressiblen) Daten hat sie eine Größe von Megabyte, bei Daten mit Wiederholungen ist sie immer größer als ein Megabyte.
Da viele moderne Datenformate jedoch nicht komprimierbar sind, ist es nutzlos und verschwenderisch, einen ressourcenintensiven Scanner über sie laufen zu lassen. Daher verwendet der Scanner zwei Betriebsmodi. Zunächst werden Abschnitte des Quelltextes mit möglichen Wiederholungen durchsucht; auch dieser Vorgang erfolgt mithilfe einer probabilistischen Methode und erfolgt sehr schnell (mit einer Geschwindigkeit von 4-6 GigaBytes/Sek.). Die Bereiche mit möglichen Übereinstimmungen werden dann vom Hauptscanner verarbeitet.
Die Indexkomprimierung ist nicht sehr effizient, Sie müssen doppelte Fragmente durch Indizes ersetzen und das Indexarray verringert die Komprimierungsrate erheblich.
Um das Komprimierungsverhältnis zu erhöhen, werden nicht nur vollständige Übereinstimmungen von Byte-Strings indiziert, sondern auch teilweise, wenn der String übereinstimmende und nicht übereinstimmende Bytes enthält. Zu diesem Zweck enthält das Indexformat ein Match-Maskenfeld, das die übereinstimmenden Bytes zweier Blöcke angibt. Für eine noch stärkere Komprimierung wird die Indizierung verwendet, um mehrere teilweise übereinstimmende Blöcke über den aktuellen Block zu legen.
All dies ermöglichte es, im PTT-Mid-Kompressor ein Komprimierungsverhältnis zu erreichen, das mit Kompressoren vergleichbar ist, die mit der Wörterbuchmethode erstellt wurden, aber viel schneller arbeiten.
Geschwindigkeit des neuen Komprimierungsalgorithmus
Wenn der Kompressor ausschließlich mit Cache-Speicher arbeitet (pro Thread sind 4 Megabyte erforderlich), liegt die Betriebsgeschwindigkeit zwischen 700 und 2000 Megabyte/Sek. pro Prozessorkern, abhängig von der Art der zu komprimierenden Daten und hängt kaum von der Betriebsfrequenz des Prozessors ab.
Bei einer Multithread-Implementierung des Kompressors wird die effektive Skalierbarkeit durch die Größe des Caches der dritten Ebene bestimmt. Wenn beispielsweise 9 Megabyte Cache-Speicher „an Bord“ sind, macht es keinen Sinn, mehr als zwei Komprimierungsthreads zu starten; die Geschwindigkeit erhöht sich dadurch nicht. Aber mit einem Cache von 20 Megabyte können Sie bereits fünf Komprimierungsthreads ausführen.
Außerdem wird die Latenz des RAM zu einem wichtigen Parameter, der die Geschwindigkeit des Kompressors bestimmt. Der Algorithmus verwendet Direktzugriffe auf das OP, von denen einige nicht in den Cache-Speicher gelangen (ca. 10 %), und er muss im Leerlauf auf Daten vom OP warten, was die Betriebsgeschwindigkeit verringert.
Beeinflusst erheblich die Geschwindigkeit des Kompressors und den Betrieb des Dateneingabe-/-ausgabesystems. Anfragen an das OP von I/O blockieren Anfragen nach Daten von der CPU, wodurch sich auch die Komprimierungsgeschwindigkeit verringert. Dieses Problem ist bei Laptops und Desktops von Bedeutung; bei Servern ist es aufgrund einer fortschrittlicheren Systembus-Zugriffskontrolleinheit und eines Mehrkanal-RAM weniger schwerwiegend.
Im gesamten Text des Artikels sprechen wir von Komprimierung; Dekomprimierung bleibt jedoch außerhalb des Rahmens dieses Artikels, da „alles mit Schokolade überzogen ist“. Die Dekomprimierung ist viel schneller und wird durch die E/A-Geschwindigkeit begrenzt. Ein physischer Kern in einem Thread ermöglicht problemlos Entpackgeschwindigkeiten von 3–4 GB/Sek.
Dies ist auf das Fehlen einer Übereinstimmungssuchoperation während des Dekomprimierungsprozesses zurückzuführen, was während der Komprimierung die Hauptressourcen des Prozessors und des Cache-Speichers „auffrisst“.
Zuverlässigkeit der komprimierten Datenspeicherung
Wie der Name der gesamten Klasse von Software, die Datenkomprimierung verwendet (Archiver), vermuten lässt, sind sie für die langfristige Speicherung von Informationen konzipiert, und zwar nicht für Jahre, sondern für Jahrhunderte und Jahrtausende ...
Beim Speichern verlieren Speichermedien einige Daten, hier ein Beispiel:
Dieser „analoge“ Informationsträger ist tausend Jahre alt, einige Fragmente sind verloren gegangen, aber im Großen und Ganzen sind die Informationen „lesbar“...
Keiner der verantwortlichen Hersteller moderner digitaler Datenspeichersysteme und digitaler Medien dafür bietet Garantien für vollständige Datensicherheit über mehr als 75 Jahre.
Und das ist ein Problem, aber ein aufgeschobenes Problem, unsere Nachkommen werden es lösen ...
Digitale Datenspeichersysteme können Daten nicht erst nach 75 Jahren verlieren, Fehler in den Daten können jederzeit auftreten, auch während der Aufzeichnung. Sie versuchen, diese Verzerrungen durch den Einsatz von Redundanz zu minimieren und sie mit Fehlerkorrektursystemen zu korrigieren. Redundanz- und Korrektursysteme können verlorene Informationen nicht immer wiederherstellen, und wenn doch, gibt es keine Garantie dafür, dass der Wiederherstellungsvorgang korrekt abgeschlossen wurde.
Und das ist auch ein großes Problem, aber kein verzögertes, sondern ein aktuelles.
Moderne Kompressoren zur Archivierung digitaler Daten basieren auf verschiedenen Modifikationen der Wörterbuchmethode, und für solche Archive ist der Verlust einer Information ein fatales Ereignis; es gibt sogar einen etablierten Begriff für eine solche Situation – ein „kaputtes“ Archiv ...
Die geringe Zuverlässigkeit der Speicherung von Informationen in Archiven mit Wörterbuchkomprimierung hängt mit der Struktur der komprimierten Daten zusammen. Die Informationen in einem solchen Archiv enthalten nicht den Quelltext, die Anzahl der Einträge im Wörterbuch werden dort gespeichert und das Wörterbuch selbst wird durch den aktuell komprimierten Text dynamisch verändert. Wenn ein Archivfragment verloren geht oder beschädigt ist, können alle nachfolgenden Archiveinträge weder anhand des Inhalts noch anhand der Länge des Eintrags im Wörterbuch identifiziert werden, da nicht klar ist, welcher Wörterbucheintragsnummer entspricht.
Es ist unmöglich, Informationen aus einem so „kaputten“ Archiv wiederherzustellen.
Der RTT-Algorithmus basiert auf einer zuverlässigeren Methode zum Speichern komprimierter Daten. Es verwendet die Indexmethode zur Berücksichtigung sich wiederholender Fragmente. Dieser Komprimierungsansatz ermöglicht es Ihnen, die Folgen einer Verzerrung von Informationen auf dem Speichermedium zu minimieren und in vielen Fällen Verzerrungen, die während der Informationsspeicherung entstanden sind, automatisch zu korrigieren.
Dies liegt daran, dass die Archivdatei bei Indexkomprimierung zwei Felder enthält:
- ein Quelltextfeld, aus dem Wiederholungsabschnitte entfernt wurden;
- Indexfeld.
Das für die Informationswiederherstellung wichtige Indexfeld ist nicht groß und kann für eine zuverlässige Datenspeicherung dupliziert werden. Selbst wenn daher ein Fragment des Quelltextes oder des Indexarrays verloren geht, werden alle anderen Informationen problemlos wiederhergestellt, wie im Bild mit einem „analogen“ Speichermedium.
Nachteile des Algorithmus
Es gibt keine Vorteile ohne Nachteile. Die Indexkomprimierungsmethode komprimiert keine kurzen, sich wiederholenden Sequenzen. Dies liegt an den Einschränkungen der Indexmethode. Indizes sind mindestens 3 Byte groß und können bis zu 12 Byte groß sein. Wenn eine Wiederholung auftritt, deren Größe kleiner ist als der sie beschreibende Index, wird sie nicht berücksichtigt, unabhängig davon, wie oft solche Wiederholungen in der komprimierten Datei erkannt werden.
Die herkömmliche Wörterbuchkomprimierungsmethode komprimiert effektiv mehrere Wiederholungen kurzer Länge und erreicht daher ein höheres Komprimierungsverhältnis als die Indexkomprimierung. Dies wird zwar durch die hohe Belastung des Zentralprozessors erreicht; damit die Wörterbuchmethode beginnt, Daten effizienter zu komprimieren als die Indexmethode, muss sie die Datenverarbeitungsgeschwindigkeit auf reale 10-20 Megabyte pro Sekunde reduzieren Rechenanlagen mit voller CPU-Auslastung.
Solch niedrige Geschwindigkeiten sind für moderne Datenspeichersysteme inakzeptabel und eher von „akademischem“ als praktischem Interesse.
Der Grad der Informationskomprimierung wird in der nächsten Modifikation des RTT-Algorithmus (RTT-Max), die sich bereits in der Entwicklung befindet, deutlich erhöht.
Also, wie immer, Fortsetzung folgt...
Source: habr.com