Dieser Artikel ist bereits der zweite in der Reihe über schnelle Datenkompression. Im ersten Artikel wurde ein Kompressor beschrieben, der mit einer Geschwindigkeit von 10 GB/s pro Prozessorkern (minimale Kompression, RTT-Min) arbeitet.
Dieser Kompressor ist bereits in die Ausrüstung forensischer Duplikatoren integriert, um schnelle Kompression von Datenabbildern zu ermöglichen und die Widerstandsfähigkeit der Kryptografie zu erhöhen. Er kann auch zur Kompression von Bildern virtueller Maschinen und Swap-Dateien des Arbeitsspeichers verwendet werden, während diese auf schnelleren SSD-Laufwerken gespeichert werden.
Im ersten Artikel wurde auch die Entwicklung eines Kompressionsalgorithmus zur Kompression von Backups von HDD- und SSD-Laufwerken (mittlere Kompression, RTT-Mid) mit erheblich verbesserten Datenkompressionsparametern angekündigt. Inzwischen ist dieser Kompressor vollständig fertiggestellt, und dieser Artikel handelt genau davon.
Der Kompressor, der den RTT-Mid-Algorithmus implementiert, bietet eine Kompressionsrate, die mit Standardarchivierungsprogrammen wie WinRar und 7-Zip vergleichbar ist, die im Schnellmodus arbeiten. Dabei liegt seine Geschwindigkeit mindestens um eine Größenordnung höher.
Die Geschwindigkeit der Datenkompression/ -dekompression ist ein kritischer Parameter, der den Anwendungsbereich von Kompressionstechnologien bestimmt. Es kommt kaum jemand auf die Idee, ein Terabyte Daten mit einer Geschwindigkeit von 10-15 Megabyte pro Sekunde zu komprimieren (genau diese Geschwindigkeit haben Archivierungsprogramme im Standardkompressionsmodus), denn das würde fast zwanzig Stunden in Anspruch nehmen, bei vollständiger Auslastung der CPU...
Andererseits kann das gleiche Terabyte mit Geschwindigkeiten von etwa 2-3 Gigabyte pro Sekunde in etwa zehn Minuten kopiert werden.
Daher ist die Kompression großer Informationsmengen nur dann von Bedeutung, wenn sie mit einer Geschwindigkeit von mindestens der realen Eingabe-/Ausgabe-Geschwindigkeit durchgeführt wird. Für moderne Systeme beträgt dies mindestens 100 Megabyte pro Sekunde.
Solche Geschwindigkeiten können moderne Kompressoren nur im "Schnell"-Modus erreichen. Gerade in diesem relevanten Modus werden wir den RTT-Mid-Algorithmus mit herkömmlichen Kompressoren vergleichen.
Vergleichende Tests des neuen Kompressionsalgorithmus
Der RTT-Mid-Kompressor arbeitete innerhalb eines Testprogramms. In einer realen "Arbeits"-Anwendung arbeitet er deutlich schneller, da dort Multithreading sinnvoll genutzt wird und ein "normaler" Compiler zum Einsatz kommt, nicht C#.
Da die im Vergleichstest verwendeten Kompressoren auf unterschiedlichen Prinzipien basieren und verschiedene Datentypen unterschiedlich komprimieren, wurde zur Objektivität des Tests die Methode der „durchschnittlichen Temperatur im Krankenhaus“ verwendet…
Eine Datei mit sektoralem Dump der logischen Festplatte mit dem Betriebssystem Windows 10 wurde erstellt. Dies ist die natürlichste Mischung aus verschiedenen Datenstrukturen, die auf jedem Computer tatsächlich vorhanden ist. Die Komprimierung dieser Datei ermöglicht es, die Geschwindigkeit und den Kompressionsgrad des neuen Algorithmus mit den fortschrittlichsten Kompressoren zu vergleichen, die in modernen Archivierungsprogrammen verwendet werden.
Hier ist diese Dump-Datei:
Die Dump-Datei wurde von den Kompressoren RTT-Mid, 7-zip, WinRar komprimiert. Die Kompressoren WinRar und 7-zip waren auf maximale Geschwindigkeit eingestellt.
Der Kompressor arbeitet 7-zip:
Er belastet die CPU zu 100 %, während die durchschnittliche Lesegeschwindigkeit des ursprünglichen Dumps bei etwa 60 Megabyte/Sekunde liegt.
Der Kompressor arbeitet WinRar:
Die Situation ist ähnlich, die CPU-Auslastung liegt nahezu bei 100 %, die durchschnittliche Lesegeschwindigkeit des Dumps beträgt etwa 125 Megabyte/Sekunde.
Wie im vorherigen Fall ist die Arbeitsgeschwindigkeit des Archivers durch die Möglichkeiten der CPU begrenzt.
Jetzt läuft die Testanwendung des Kompressors RTT-Mid:
Der Screenshot zeigt, dass die CPU zu 50 % ausgelastet ist und die restliche Zeit untätig ist, da es keinen Ort gibt, um die komprimierten Daten zu entladen. Die Zielplatte (Platte 0) ist nahezu vollständig ausgelastet. Die Datenlesegeschwindigkeit (Platte 1) schwankt stark, liegt jedoch im Durchschnitt über 200 Megabyte/Sekunde.
Die Arbeitsgeschwindigkeit des Kompressors wird in diesem Fall durch die Möglichkeit begrenzt, die komprimierten Daten auf Platte 0 zu schreiben.
Jetzt die Kompressionsrate der resultierenden Archive:
Es ist zu sehen, dass der Kompressor RTT-Mid die beste Kompression erreicht hat. Das von ihm erstellte Archiv ist 1,3 Gigabyte kleiner als das von WinRar und 2,1 Gigabyte kleiner als das von 7z.
Zeit, die für die Erstellung des Archivs aufgewendet wurde:
- 7-zip – 26 Minuten 10 Sekunden;
- WinRar – 17 Minuten 40 Sekunden;
- RTT-Mid – 7 Minuten 30 Sekunden.
Somit konnte selbst die Testanwendung, die nicht optimiert ist und den Algorithmus RTT-Mid verwendet, ein archiv über zweieinhalb mal schneller erstellen, wobei das Archiv wesentlich kleiner ist als bei den Mitbewerbern…
Diejenigen, die den Screenshots nicht glauben, können ihre Richtigkeit selbst überprüfen. Die Testanwendung ist verfügbar unter , laden Sie herunter und überprüfen Sie es.
Aber nur auf Prozessoren mit AVX-2-Unterstützung, ohne die Unterstützung dieser Instruktionen funktioniert der Kompressor nicht und testen Sie den Algorithmus nicht auf alten AMD-Prozessoren, sie sind langsam bei der Ausführung von AVX-Befehlen…
Verwendete Komprimierungsmethode
Im Algorithmus wird eine Methode zur Indizierung wiederkehrender Textfragmente in bytebasierten Granularitäten verwendet. Diese Kompressionsmethode ist schon lange bekannt, wurde jedoch nicht genutzt, da die Übereinstimmungssuche sehr ressourcenintensiv war und viel mehr Zeit in Anspruch nahm als der Aufbau eines Wörterbuchs. Daher ist der Algorithmus RTT-Mid ein klassisches Beispiel für eine Rückkehr in die Zukunft…
Im RTT-Kompressor wird ein einzigartiger schneller Suchscanner für Übereinstimmungen verwendet, der es ermöglicht hat, den Kompressionsprozess zu beschleunigen. Der Scanner ist ein Eigenbau, er ist „mein Schatz…“, „kostet nicht wenig, da er vollständig handgefertigt ist“ (in Assembler geschrieben).
Der Übereinstimmungssuche-Scanner ist nach einem zweistufigen probabilistischen Schema gebaut, zuerst wird die Anwesenheit eines „Signals“ für Übereinstimmung gescannt, und erst nach Feststellung des „Signals“ an dieser Stelle wird das Verfahren zur Erkennung der tatsächlichen Übereinstimmung gestartet.
Das Suchfenster für Übereinstimmungen hat eine unvorhersehbare Größe, die von der Entropiestufe im verarbeiteten Datenblock abhängt. Für vollständig zufällige (nicht komprimierbare) Daten hat es eine Größe im Megabyte-Bereich, für Daten mit Wiederholungen hat es immer eine Größe von mehr als einem Megabyte.
Aber viele moderne Datenformate sind nicht komprimierbar, und es ist nutzlos und verschwenderisch, einen ressourcenintensiven Scanner darauf zu laufen, deshalb verwendet der Scanner zwei Betriebsmodi. Zuerst werden Abschnitte des Quelltextes mit möglichen Wiederholungen gesucht, und diese Operation erfolgt auch nach einem probabilistischen Verfahren und wird sehr schnell (mit 4-6 Gigabyte/Sekunde) durchgeführt. Danach werden die Abschnitte mit möglichen Übereinstimmungen vom Hauptscanner verarbeitet.
Die indexbasierte Kompression ist nicht sehr effektiv, da wiederkehrende Fragmente durch Indizes ersetzt werden müssen, und das Index-Array senkt den Kompressionsfaktor erheblich.
Um den Kompressionsgrad zu erhöhen, werden nicht nur vollständige Übereinstimmungen von Byte-Strings indexiert, sondern auch teilweise, wenn in der Zeichenfolge übereinstimmende und nicht übereinstimmende Bytes vorhanden sind. Zu diesem Zweck ist im Indexformat ein Feld für Übereinstimmungsmasken enthalten, das auf die übereinstimmenden Bytes von zwei Blöcken hinweist. Für eine noch größere Kompression wird die Indizierung mit Überlappungen mehrerer teilweise übereinstimmender Blöcke auf den aktuellen Block verwendet.
All dies hat es ermöglicht, im Kompressor RTT-Mid einen Kompressionsgrad zu erzielen, der mit Kompressoren vergleichbar ist, die nach dem Wörterbuchverfahren arbeiten, jedoch wesentlich schneller.
Die Arbeitsgeschwindigkeit des neuen Kompressionsalgorithmus
Wenn der Kompressor mit ausschließlicher Nutzung des Cache-Speichers arbeitet (für einen Thread sind 4 Megabyte erforderlich), schwankt die Arbeitsgeschwindigkeit im Bereich von 700-2000 Megabyte/Sek. pro CPU-Kern, abhängig von der Art der komprimierten Daten, und ist nur minimal abhängig von der Arbeitsfrequenz des Prozessors.
Bei der Multi-Thread-Implementierung des Kompressors wird die effektive Skalierbarkeit durch das Volumen des Level-3-Cache-Speichers bestimmt. Zum Beispiel macht es wenig Sinn, mehr als zwei Kompressionsströme zu starten, wenn man «an Bord» 9 Megabyte Cache-Speicher hat, da die Geschwindigkeit dadurch nicht steigt. Bei einem Cache von 20 Megabyte kann man jedoch bereits fünf Kompressionsströme starten.
Ein weiterer wesentlicher Parameter, der die Geschwindigkeit des Kompressors beeinflusst, ist die Latenz des Arbeitsspeichers. Der Algorithmus verwendet zufällige Zugriffe auf den RAM, von denen ein Teil (etwa 10%) nicht im Cache-Speicher landet, und muss auf Daten aus dem RAM warten, was die Arbeitsgeschwindigkeit verringert.
Die Geschwindigkeit des Kompressors wird auch durch die Arbeit des Daten-Eingangs-/Ausgangssystems beeinflusst. Anfragen an den RAM von Ein-/Ausgabe blockieren die Zugriffe auf Daten seitens der CPU, was ebenfalls die Kompressionsgeschwindigkeit verringert. Dieses Problem ist für Laptops und Desktops erheblich. Server Für sie ist es weniger erheblich, dank eines fortschrittlicheren Zugriffssteuerblocks auf den Systembus und dem Mehrkanal-Arbeitsspeicher.
In dem gesamten Artikel wird von Kompression gesprochen, während Dekompression in diesem Artikel nicht behandelt wird, da dort "alles in Ordnung ist". Die Dekompression erfolgt erheblich schneller und wird durch die Eingabe-/Ausgabe-Geschwindigkeit begrenzt. Ein physisches Kern pro Thread ermöglicht mühelos Entpackungsraten von 3-4 Gigabyte/Sekunde.
Das liegt daran, dass im Dekompressionsprozess keine Übereinstimmungsfindung stattfindet, die "die Hauptressourcen der CPU und des Cache" während der Kompression verschlingt.
Zuverlässigkeit der Speicherung komprimierter Daten
Wie der Name der gesamten Klasse von Software-Tools, die Datenkompression verwenden (Komprimierungssoftware), bereits andeutet, sind sie für die langfristige Speicherung von Informationen ausgelegt, nicht für Jahre, sondern für Jahrhunderte und Jahrtausende…
Im Laufe der Lagerung verlieren Speicherträger einen Teil der Daten, hier ist ein Beispiel:
Dieser "analoge" Informationsspeicher ist tausend Jahre alt, einige Fragmente sind verloren, aber insgesamt ist die Information "lesbar"…
Keiner der verantwortlichen Hersteller moderner digitaler Datenspeichersysteme und der digitalen Träger gibt eine Garantie für die vollständige Datenintegrität von mehr als 75 Jahren.
Und das ist ein Problem, aber ein aufgeschobenes Problem, das unsere Nachkommen lösen werden…
Digitale Datenspeichersysteme können Daten nicht nur nach 75 Jahren verlieren, Datenfehler können jederzeit auftreten, selbst während der Aufzeichnung; diese Verzerrungen versuchen, mithilfe von Redundanz und Fehlerkorrektursystemen zu minimieren. Redundanz und Fehlerkorrektursysteme können nicht immer verlorene Informationen wiederherstellen, und selbst wenn sie wiederhergestellt werden, gibt es keine Garantie, dass der Wiederherstellungsvorgang korrekt war.
Und das ist auch ein großes Problem, aber kein aufgeschobenes, sondern ein aktuelles.
Moderne Kompressionssoftware, die für die Archivierung digitaler Daten verwendet wird, basiert auf verschiedenen Modifikationen des Wörterbuchverfahrens. Für solche Archive wäre der Verlust eines Informationsfragmentes ein fataler Vorfall; es gibt sogar einen etablierten Begriff für eine solche Situation – "beschädigtes" Archiv…
Die geringe Zuverlässigkeit der Informationsspeicherung in Archiven mit Wörterbuchkompression hängt mit der Struktur der komprimierten Daten zusammen. Informationen in einem solchen Archiv enthalten keinen ursprünglichen Text; stattdessen werden die Nummern der Wörterbucheinträge gespeichert, wobei das Wörterbuch dynamisch durch den aktuell komprimierten Text modifiziert wird. Im Falle des Verlusts oder der Verfälschung eines Fragmentes des Archivs ist es unmöglich, alle folgenden Archivdatensätze weder anhand des Inhalts noch der Länge des Eintrags im Wörterbuch zu identifizieren, da unklar ist, welcher nummerierten Wörterbucheintrag entspricht.
Es ist unmöglich, Informationen aus einem solchen 'beschädigten' Archiv wiederherzustellen.
Der RTT-Algorithmus basiert auf einer zuverlässigeren Methode zur Speicherung komprimierter Daten. Dabei wird eine indexbasierte Methode zur Erfassung wiederkehrender Fragmente verwendet. Dieser Ansatz zur Kompression minimiert die Auswirkungen von Informationsverzerrungen auf dem Träger und ermöglicht es in vielen Fällen, die während der Speicherung von Informationen entstandenen Verzerrungen automatisch zu korrigieren.
Dies liegt daran, dass die Archivdatei bei indexbasierter Kompression zwei Felder enthält:
- ein Feld mit dem ursprünglichen Text, aus dem wiederholte Abschnitte entfernt wurden;
- ein Feld der Indizes.
Das für die Informationswiederherstellung kritische Feld der Indizes ist nicht groß und kann zur Sicherung der Datenspeicherung dupliziert werden. Daher wird, selbst wenn ein Fragment des ursprünglichen Textes oder des Indexarrays verloren geht, die restliche Information problemlos wiederhergestellt, wie auf dem Bild mit einem 'analogen' Informationsträger.
Nachteile des Algorithmus
Vorteile gibt es niemals ohne Nachteile. Die indexbasierte Kompressionsmethode komprimiert wiederkehrende Sequenzen geringer Länge nicht. Dies hängt mit den Beschränkungen der indexbasierten Methode zusammen. Indizes haben eine Größe von mindestens 3 Bytes und können bis zu 12 Bytes groß sein. Wenn eine Wiederholung auftritt, die kleiner ist als die beschreibende Indexgröße, wird sie nicht berücksichtigt, egal wie oft solche Wiederholungen in der zu komprimierenden Datei festgestellt werden.
Die traditionelle, lexikalische Komprimierungsmethode komprimiert effektiv multiple kurze Wiederholungen und erzielt daher eine höhere Kompressionsrate als die indexbasierte Kompression. Allerdings wird dies auf Kosten einer hohen Auslastung der zentralen Verarbeitungseinheit erreicht, sodass die lexikalische Methode, um Daten effektiver als die indexbasierte Methode zu komprimieren, die Verarbeitungsgeschwindigkeit auf 10-20 Megabyte pro Sekunde in realen Berechnungssystemen bei voller CPU-Auslastung senken muss.
Solch niedrige Geschwindigkeiten sind für moderne Datenspeichersysteme unakzeptabel und haben eher akademisches als praktisches Interesse.
Der Kompressionsgrad der Informationen wird in der nächsten Modifikation des RTT-Algorithmus (RTT-Max) erheblich erhöht, der sich bereits in der Entwicklung befindet.
Also wie immer, Fortsetzung folgt…
Quelle: habr.com
