Dieser Artikel ist bereits der zweite zum Thema Hochgeschwindigkeits-Datenkomprimierung. Der erste Artikel beschrieb einen Kompressor, der mit einer Geschwindigkeit von 10 GB / s arbeitet. pro Prozessorkern (minimale Komprimierung, RTT-Min).
Dieser Kompressor, der bereits in der Ausstattung von forensischen Duplikatoren für die Hochgeschwindigkeitskomprimierung von Speichermedien-Dumps implementiert ist und die Stärke der Kryptografie erhöht, kann auch zum Komprimieren von Images virtueller Maschinen und RAM-Auslagerungsdateien verwendet werden, während diese auf Hochgeschwindigkeits-SSD-Laufwerken gespeichert werden.
Der erste Artikel kündigte auch die Entwicklung eines Komprimierungsalgorithmus zum Komprimieren von Sicherungskopien von Festplatten- und SSD-Laufwerken (mittlere Komprimierung, RTT-Mid) mit erheblich verbesserten Datenkomprimierungsparametern an. Bis heute ist dieser Kompressor komplett fertig und dieser Artikel handelt von ihm.
Ein Kompressor, der den RTT-Mid-Algorithmus implementiert, bietet ein Komprimierungsverhältnis, das mit Standardarchivierern wie WinRar, 7-Zip, vergleichbar ist und im Hochgeschwindigkeitsmodus arbeitet. Darüber hinaus ist seine Geschwindigkeit mindestens eine Größenordnung höher.
Die Geschwindigkeit des Packens / Entpackens von Daten ist ein kritischer Parameter, der den Umfang der Komprimierungstechnologien bestimmt. Es ist unwahrscheinlich, dass jemand daran denkt, ein Terabyte Daten mit einer Geschwindigkeit von 10-15 Megabyte pro Sekunde zu komprimieren (dies ist die Geschwindigkeit von Archiven im Standardkomprimierungsmodus), da es fast zwanzig Stunden dauert, bis der Prozessor vollständig geladen ist ...
Auf der anderen Seite kann dasselbe Terabyte etwa zehn Minuten lang mit Geschwindigkeiten in der Größenordnung von 2-3 Gigabyte pro Sekunde kopiert werden.
Daher ist die Komprimierung von Informationen eines großen Volumens relevant, wenn sie mit einer Geschwindigkeit durchgeführt werden, die nicht niedriger als die Geschwindigkeit der tatsächlichen Eingabe / Ausgabe ist. Bei modernen Systemen sind dies mindestens 100 Megabyte pro Sekunde.
Moderne Kompressoren können solche Drehzahlen nur im „schnellen“ Modus erzeugen. In diesem aktuellen Modus vergleichen wir den RTT-Mid-Algorithmus mit herkömmlichen Kompressoren.
Vergleichstest des neuen Kompressionsalgorithmus
Der RTT-Mid Kompressor arbeitete im Rahmen eines Testprogramms. In einer echten "funktionierenden" Anwendung funktioniert es viel schneller, Multithreading wird dort korrekt verwendet und ein "normaler" Compiler wird verwendet, nicht C #.
Da die im Vergleichstest verwendeten Kompressoren auf unterschiedlichen Prinzipien beruhen und unterschiedliche Datentypen unterschiedlich komprimiert werden, haben wir für die Objektivität des Tests die Methode zur Messung der "Durchschnittstemperatur im Krankenhaus" verwendet ...
Es wurde eine Sektor-für-Sektor-Dump-Datei eines logischen Laufwerks mit dem Betriebssystem Windows 10 erstellt, bei der es sich um die natürlichste Mischung verschiedener Datenstrukturen handelt, die tatsächlich auf jedem Computer verfügbar sind. Durch die Komprimierung dieser Datei können Sie die Geschwindigkeit und den Grad der Komprimierung des neuen Algorithmus mit den fortschrittlichsten Komprimierungen vergleichen, die in modernen Archiven verwendet werden.
Hier ist die Dump-Datei:

Die Speicherauszugsdatei wurde mit PTT-Mid-WinRar-Komprimierungsprogrammen mit 7 Zip komprimiert. WinRar-Kompressor und 7-Zip wurden auf maximale Geschwindigkeit eingestellt.
7-Zip- Kompressor funktioniert:

Der Prozessor wird zu 100% geladen, während die durchschnittliche Lesegeschwindigkeit des Original-Dumps etwa 60 Megabyte / s beträgt.
WinRar Kompressor funktioniert:

Ähnlich ist die Situation, die Prozessorauslastung liegt bei fast 100%, die durchschnittliche Lesegeschwindigkeit des Dumps liegt bei ca. 125 Megabyte / Sek.
Wie im vorherigen Fall ist die Geschwindigkeit des Archivierers durch die Fähigkeiten des Prozessors begrenzt.
Das
RTT-Mid Kompressor Testprogramm funktioniert jetzt:

Der Screenshot zeigt, dass der Prozessor zu 50% ausgelastet ist und die restliche Zeit im Leerlauf ist, da die komprimierten Daten nirgendwo heruntergeladen werden können. Die Datenübertragungsdiskette (Disk 0) ist fast vollständig geladen. Die Lesegeschwindigkeit von Daten (Datenträger 1) springt stark an, beträgt jedoch im Durchschnitt mehr als 200 Megabyte / s.
Die Kompressordrehzahl ist in diesem Fall durch die Fähigkeit begrenzt, komprimierte Daten auf die Festplatte 0 zu schreiben.
Nun das Kompressionsverhältnis der resultierenden Archive:



Es ist zu sehen, dass der RTT-Mid-Kompressor die Komprimierung besser handhabte als jeder andere. 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 Reißverschlüsse - 26 Minuten 10 Sekunden;
- WinRar - 17 Minuten 40 Sekunden;
- RTT-Mid - 7 Minuten 30 Sekunden.
So konnte selbst ein nicht optimiertes Testprogramm mit dem RTT-Mid-Algorithmus ein Archiv mehr als zweieinhalb Mal schneller erstellen, während sich herausstellte, dass das Archiv erheblich kleiner war als das der Wettbewerber ...
Diejenigen, die den Screenshots nicht glauben, können ihre Richtigkeit selbst überprüfen. Das Testprogramm ist
hier verfügbar, herunterladen und prüfen.
Aber nur auf Prozessoren mit Unterstützung für AVX-2, ohne Unterstützung für diese Anweisungen, funktioniert der Kompressor nicht und testet den Algorithmus nicht auf älteren AMD-Prozessoren. Sie sind hinsichtlich der Ausführung von AVX-Befehlen langsam ...
Komprimierungsmethode verwendet
Der Algorithmus verwendet die Methode zur Indizierung sich wiederholender Textfragmente bei der Byte-Granulation. Diese Komprimierungsmethode ist seit langem bekannt, wurde jedoch nicht angewendet, da die Übereinstimmungssuche im Hinblick auf die erforderlichen Ressourcen sehr teuer war und viel mehr Zeit in Anspruch nahm als die Erstellung 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 Hochgeschwindigkeitsscanner zum Auffinden von Übereinstimmungen. Er war es, der den Kompressionsprozess beschleunigen konnte. Ein selbst hergestellter Scanner, es ist "mein Charme ...", "es ist ein beachtlicher Preis, weil es komplett handgemacht ist" (in Assembler geschrieben).
Der Übereinstimmungssuchscanner basiert auf einem zweistufigen Wahrscheinlichkeitsschema. Das Vorhandensein eines "Zeichens" einer Übereinstimmung wird zuerst gescannt, und erst nachdem das "Zeichen" an dieser Stelle erkannt wurde, beginnt die Prozedur zum Erkennen einer echten Übereinstimmung.
Das Übereinstimmungssuchfenster hat eine unvorhersehbare Größe, abhängig vom Entropiegrad im verarbeiteten Datenblock. Für völlig zufällige (inkomprimierbare) Daten hat es eine Größe von Megabyte, für Daten mit Wiederholungen hat es immer eine Größe von mehr als einem Megabyte.
Viele moderne Datenformate sind jedoch inkompressibel und das „Ansteuern“ eines ressourcenintensiven Scanners ist nutzlos und verschwenderisch. Daher verwendet der Scanner zwei Betriebsmodi. Zunächst werden Abschnitte des Quelltextes mit möglichen Wiederholungen durchsucht, diese Operation wird ebenfalls nach der probabilistischen Methode durchgeführt und erfolgt sehr schnell (mit einer Geschwindigkeit von 4-6 Gigabyte / s). Dann werden Bereiche mit möglichen Übereinstimmungen vom Hauptscanner verarbeitet.
Die Indexkomprimierung ist nicht sehr effizient. Sie müssen sich wiederholende Fragmente durch Indizes ersetzen, und das Indexarray verringert die Komprimierungsrate erheblich.
Um die Komprimierungsrate zu erhöhen, werden nicht nur vollständige Übereinstimmungen von Bytefolgen indiziert, sondern auch teilweise Übereinstimmungen, wenn die Zeichenfolge übereinstimmende und nicht übereinstimmende Bytes enthält. Zu diesem Zweck wird das Indexmaskenfeld in das Indexformat aufgenommen, das die übereinstimmenden Bytes von zwei Blöcken angibt. Für eine noch stärkere Komprimierung wird die Indizierung mit der Überlappung mehrerer teilweise übereinstimmender Blöcke auf dem aktuellen Block verwendet.
All dies ermöglichte es, ein Kompressionsverhältnis im PTT-Mid-Kompressor zu erzielen, das mit Kompressoren vergleichbar ist, die nach der Dictionary-Methode hergestellt wurden, jedoch viel schneller arbeiten.
Die Geschwindigkeit des neuen Komprimierungsalgorithmus
Wenn der Kompressor ausschließlich mit dem Speichercache arbeitet (4 Megabyte pro Stream sind erforderlich), variiert die Geschwindigkeit zwischen 700 und 2000 Megabyte / Sek. Je Prozessorkern, abhängig von der Art der zu komprimierenden Daten und wenig abhängig von der Betriebsfrequenz des Prozessors.
Bei der Multithread-Implementierung des Kompressors wird die effektive Skalierbarkeit durch das Volumen des Cache-Speichers der dritten Ebene bestimmt. Wenn beispielsweise 9 Megabyte Cache-Speicher „an Bord“ sind, ist es nicht sinnvoll, mehr als zwei Komprimierungsströme auszuführen. Die Geschwindigkeit wird dadurch nicht erhöht. Mit einem Cache von 20 Megabyte können Sie jedoch bereits fünf Komprimierungsströme ausführen.
Auch die Latenz des RAM wird zu einem wesentlichen Parameter, der die Geschwindigkeit des Kompressors bestimmt. Der Algorithmus verwendet zufällige Zugriffe auf das OP, von denen einige nicht in den Cache-Speicher gelangen (ca. 10%) und muss im Leerlauf auf Daten vom OP warten, was die Arbeitsgeschwindigkeit verringert.
Beeinflusst maßgeblich die Drehzahl des Kompressors und den Betrieb des Dateneingabe- / Ausgabesystems. Anforderungen an das OP von E / A blockieren Datenanforderungen von der CPU, wodurch sich auch die Komprimierungsrate verringert. Dieses Problem ist für Laptops und Desktops erheblich, für Server aufgrund der fortschrittlicheren Zugriffskontrolleinheit für den Systembus und den Mehrkanal-RAM weniger bedeutend.
Überall im Text bezieht sich der Artikel auf Komprimierung. Die Dekomprimierung würde den Rahmen dieses Artikels sprengen, da dort alles in Schokolade ist. Die Dekomprimierung ist viel schneller und wird durch die E / A-Geschwindigkeit begrenzt. Ein physischer Kern in einem Thread sorgt in aller Ruhe für Dekomprimierungsgeschwindigkeiten von 3-4 Gigabyte / s.
Dies ist darauf zurückzuführen, dass während des Entpackens keine Übereinstimmungssuche durchgeführt wird, die den Hauptprozessor und die Cache-Ressourcen während der Komprimierung "verschlingt".
Zuverlässige Speicherung komprimierter Daten
Wie der Name der gesamten Klasse von Softwaretools mit Datenkomprimierung (Archiven) impliziert, sind sie für die langfristige Speicherung von Informationen konzipiert, nicht für Jahre, sondern für Jahrhunderte und Jahrtausende ...
Während der Speicherung verlieren Speichermedien einen Teil der Daten. Hier ein Beispiel:

Dieses "analoge" Speichermedium ist eintausend Jahre alt, einige Fragmente sind verloren gegangen, aber im Allgemeinen sind die Informationen "lesbar" ...
Keiner der für sie verantwortlichen Hersteller moderner digitaler Speichersysteme und digitaler Medien garantiert seit mehr als 75 Jahren vollständige Datensicherheit.
Und das ist ein Problem, aber das Problem wird verschoben, unsere Nachkommen werden es lösen ...
Digitale Datenspeichersysteme können nicht nur nach 75 Jahren Daten verlieren, Datenfehler können jederzeit auftreten, auch während ihrer Aufzeichnung versuchen sie diese Verzerrungen durch Verwendung von Redundanz- und Fehlerkorrektursystemen zu minimieren. Redundanz- und Korrektursysteme können nicht immer verlorene Informationen wiederherstellen. Wenn sie wiederhergestellt werden, kann keine Garantie dafür übernommen werden, dass der Wiederherstellungsvorgang korrekt war.
Und das ist auch ein großes Problem, aber kein verzögertes, sondern das aktuelle.
Moderne Kompressoren für die Archivierung digitaler Daten basieren auf verschiedenen Modifikationen der Dictionary-Methode. Für solche Archive ist der Verlust einer Information ein schwerwiegendes Ereignis. Es gibt sogar einen festgelegten Begriff für eine solche Situation - ein "kaputtes" Archiv ...
Die geringe Zuverlässigkeit der Informationsspeicherung in Archiven mit Wörterbuchkomprimierung hängt mit der Struktur komprimierter Daten zusammen. Die Informationen in einem solchen Archiv enthalten nicht den Quelltext, die Anzahl der Einträge im Wörterbuch wird dort gespeichert, das Wörterbuch selbst wird durch den aktuellen komprimierbaren Text dynamisch geändert. Wenn ein Fragment des Archivs verloren geht oder verzerrt ist, können alle nachfolgenden Archiveinträge weder durch den Inhalt noch durch die Länge der Einträge im Wörterbuch identifiziert werden, da nicht klar ist, wie die Nummer des Wörterbucheintrags lautet.
Es ist unmöglich, Informationen aus einem solchen "kaputten" Archiv wiederherzustellen.
Der RTT-Algorithmus basiert auf einer zuverlässigeren Methode zum Speichern komprimierter Daten. Es wird die Indexmethode verwendet, mit der sich wiederholende Fragmente berücksichtigt werden. Ein derartiger Komprimierungsansatz ermöglicht die Minimierung der Folgen von Informationsverzerrungen auf dem Medium und in vielen Fällen die automatische Korrektur von während der Speicherung von Informationen auftretenden Verzerrungen.
Dies liegt daran, dass die Archivdatei bei der Indexkomprimierung zwei Felder enthält:
- Quelltextfeld mit entfernten Wiederholungsabschnitten;
- Indexfeld.
Das für die Datenwiederherstellung wichtige Indexfeld ist nicht groß und kann für eine zuverlässige Datenspeicherung dupliziert werden. Selbst wenn ein Fragment des Quelltextes oder des Index-Arrays verloren geht, werden daher alle anderen Informationen problemlos wiederhergestellt, wie im Bild mit dem „analogen“ Informationsträger.
Algorithmus Mängel
Vorteile existieren nicht ohne Nachteile. Die Indexkomprimierungsmethode komprimiert keine sich wiederholenden kurzen 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 mit einer kleineren Größe als der Index auftritt, der sie beschreibt, wird sie nicht berücksichtigt, jedoch werden solche Wiederholungen häufig in einer komprimierbaren Datei erkannt.
Die traditionelle Vokabularkomprimierungsmethode komprimiert mehrere kurze Wiederholungen effektiv und erzielt daher ein höheres Komprimierungsverhältnis als die Indexkomprimierung. Dies wird zwar aufgrund der hohen Arbeitsbelastung des Zentralprozessors erreicht, sodass die Vokabularmethode beginnt, Daten effizienter zu komprimieren als die Indexmethode. Bei realen Computerinstallationen mit voller CPU-Auslastung muss die Datenverarbeitungsgeschwindigkeit auf 10 bis 20 Megabyte pro Sekunde reduziert werden.
Solche niedrigen Geschwindigkeiten sind für moderne Datenspeichersysteme nicht akzeptabel und von "akademischem" Interesse als praktisch.
Der Grad der Informationskomprimierung wird in der nächsten Modifikation des PTT-Algorithmus (RTT-Max) deutlich erhöht, der bereits in Entwicklung ist.
Also wie immer weitermachen ...