Cet article est déjà le deuxième sur le sujet de la compression de données à haute vitesse. Le premier article décrit un compresseur fonctionnant à une vitesse de 10 Go / s. par cœur de processeur (compression minimale, RTT-Min).
Ce compresseur a déjà été introduit dans l'équipement des duplicateurs médico-légaux pour la compression à grande vitesse des vidages de supports de stockage et pour augmenter la force de la cryptographie, il peut également être utilisé pour compresser des images de machines virtuelles et échanger des fichiers RAM tout en les stockant sur des disques SSD à haute vitesse.
Le premier article a également annoncé le développement d'un algorithme de compression pour compresser les copies de sauvegarde des disques durs HDD et SSD (compression moyenne, RTT-Mid) avec des paramètres de compression des données considérablement améliorés. À ce jour, ce compresseur est complètement prêt et cet article parle de lui.
Un compresseur qui implémente l'algorithme RTT-Mid fournit un taux de compression comparable aux archiveurs standard tels que WinRar, 7-Zip, fonctionnant en mode haute vitesse. De plus, sa vitesse est supérieure d'au moins un ordre de grandeur.
La vitesse de compression / décompression des données est un paramètre critique déterminant la portée des technologies de compression. Il est peu probable que quelqu'un pense à compresser un téraoctet de données à une vitesse de 10 à 15 mégaoctets par seconde (c'est la vitesse des archiveurs en mode de compression standard), car il faudra près de vingt heures pour charger complètement le processeur ...
En revanche, le même téraoctet peut être copié à des vitesses de l'ordre de 2 à 3 gigaoctets par seconde pendant une dizaine de minutes.
Par conséquent, la compression des informations d'un grand volume est pertinente si elle est effectuée à une vitesse non inférieure à la vitesse des entrées / sorties réelles. Pour les systèmes modernes, cela représente au moins 100 mégaoctets par seconde.
Les compresseurs modernes ne peuvent produire de telles vitesses qu'en mode «rapide». C'est dans ce mode actuel que nous comparerons l'algorithme RTT-Mid aux compresseurs traditionnels.
Test comparatif du nouvel algorithme de compression
Le compresseur RTT-Mid a fonctionné dans le cadre d'un programme de test. Dans une vraie application "fonctionnelle", cela fonctionne beaucoup plus rapidement, le multithreading y est correctement utilisé, et un compilateur "normal" est utilisé, pas C #.
Étant donné que les compresseurs utilisés dans le test comparatif sont construits sur différents principes et différents types de données sont compressés différemment, pour l'objectivité du test, nous avons utilisé la méthode de mesure de la "température moyenne à l'hôpital" ...
Un fichier de vidage secteur par secteur d'un lecteur logique avec le système d'exploitation Windows 10 a été créé; il s'agit du mélange le plus naturel de diverses structures de données réellement disponibles sur chaque ordinateur. La compression de ce fichier vous permettra de comparer la vitesse et le degré de compression du nouvel algorithme avec les compresseurs les plus avancés utilisés dans les archiveurs modernes.
Voici le fichier de vidage:
Le fichier de vidage a été compressé par des compresseurs PTT-Mid, 7-zip, WinRar. Le compresseur WinRar et le 7-zip ont été réglés sur la vitesse maximale.
Le compresseur
7 zip fonctionne:
Il charge le processeur à 100%, tandis que la vitesse de lecture moyenne du vidage d'origine est d'environ 60 mégaoctets / sec.
Le compresseur
WinRar fonctionne:
La situation est similaire, la charge du processeur est proche de 100%, la vitesse de lecture moyenne du vidage est d'environ 125 mégaoctets / sec.
Comme dans le cas précédent, la vitesse de l'archiveur est limitée par les capacités du processeur.
Le programme de test du compresseur
RTT-Mid fonctionne désormais:
La capture d'écran montre que le processeur est chargé à 50% et qu'il est inactif le reste du temps, car il n'y a nulle part où télécharger les données compressées. Le disque de téléchargement des données (disque 0) est chargé presque complètement. La vitesse de lecture des données (disque 1) saute beaucoup, mais en moyenne plus de 200 mégaoctets / sec.
La vitesse du compresseur est limitée dans ce cas par la possibilité d'écrire des données compressées sur le disque 0.
Maintenant, le taux de compression des archives résultantes:
On peut voir que le compresseur RTT-Mid a géré la compression mieux que quiconque, l'archive qu'il a créée était 1,3 gigaoctets plus petite que l'archive WinRar et 2,1 gigaoctets plus petite que l'archive 7z.
Temps consacré à la création de l'archive:
- 7-zip - 26 minutes 10 secondes;
- WinRar - 17 minutes 40 secondes;
- RTT-Mid - 7 minutes 30 secondes.
Ainsi, même un programme de test, non optimisé, utilisant l'algorithme RTT-Mid, a pu créer une archive plus de deux fois et demie plus vite, alors que l'archive s'est avérée être beaucoup plus petite que celle des concurrents ...
Ceux qui ne croient pas aux captures d'écran peuvent vérifier leur précision par eux-mêmes. Le programme de test est disponible
ici , téléchargez et vérifiez.
Mais uniquement sur les processeurs prenant en charge AVX-2, sans prise en charge de ces instructions, le compresseur ne fonctionne pas, et ne teste pas l'algorithme sur les anciens processeurs AMD, ils sont lents en termes d'exécution des commandes AVX ...
Méthode de compression utilisée
L'algorithme utilise la méthode d'indexation des fragments de texte répétés dans la granulation d'octets. Cette méthode de compression est connue depuis longtemps, mais n'a pas été utilisée, car l'opération de recherche de correspondance était très coûteuse en termes de ressources nécessaires et nécessitait beaucoup plus de temps que la construction d'un dictionnaire. L'algorithme RTT-Mid est donc un exemple classique du mouvement "retour vers le futur" ...
Le compresseur PTT utilise un scanner haute vitesse unique pour trouver les correspondances, c'est lui qui a permis d'accélérer le processus de compression. Un scanner fait maison, c'est "mon charme ...", "c'est un prix considérable, car il est entièrement fait à la main" (écrit en assembleur).
Le scanner de recherche de correspondance est basé sur un schéma probabiliste à deux niveaux, la présence d'un «signe» d'une correspondance est d'abord analysée, et ce n'est qu'après que le «signe» est détecté à cet endroit que la procédure de détection d'une correspondance réelle commence.
La fenêtre de recherche de correspondance a une taille imprévisible, selon le degré d'entropie dans le bloc de données en cours de traitement. Pour les données complètement aléatoires (incompressibles), il a une taille de mégaoctets, pour les données avec répétitions, il a toujours une taille supérieure à un mégaoctet.
Mais de nombreux formats de données modernes sont incompressibles et «piloter» un scanner gourmand en ressources sur eux est inutile et inutile, par conséquent, le scanner utilise deux modes de fonctionnement. Tout d'abord, des sections du texte source avec des répétitions possibles sont recherchées, cette opération est également effectuée par la méthode probabiliste et est effectuée très rapidement (à une vitesse de 4-6 gigaoctets / sec). Ensuite, les zones avec des correspondances possibles sont traitées par le scanner principal.
La compression d'index n'est pas très efficace, vous devez remplacer les fragments répétitifs par des index et le tableau d'index réduit considérablement le taux de compression.
Pour augmenter le taux de compression, non seulement les correspondances complètes des chaînes d'octets sont indexées, mais aussi les correspondances partielles lorsqu'il y a des octets correspondants et non correspondants dans la chaîne. Pour ce faire, le champ de masque d'index est inclus dans le format d'index, qui indique les octets coïncidents de deux blocs. Pour une compression encore plus grande, l'indexation est utilisée avec le chevauchement de plusieurs blocs partiellement correspondants sur le bloc actuel.
Tout cela a permis d'obtenir un taux de compression dans le compresseur PTT-Mid, comparable aux compresseurs fabriqués selon la méthode du dictionnaire, mais fonctionnant beaucoup plus rapidement.
La vitesse du nouvel algorithme de compression
Si le compresseur fonctionne avec une utilisation exclusive du cache mémoire (4 mégaoctets sont nécessaires par flux), la vitesse varie de 700 à 2000 mégaoctets / sec. par cœur de processeur, selon le type de données compressées et peu dépend de la fréquence de fonctionnement du processeur.
Avec l'implémentation multi-thread du compresseur, l'évolutivité effective est déterminée par le volume de la mémoire cache du troisième niveau. Par exemple, ayant 9 Mo de mémoire cache «embarquée», cela n'a aucun sens d'exécuter plus de deux flux de compression, la vitesse n'augmentera pas à partir de cela. Mais avec un cache de 20 mégaoctets, vous pouvez déjà exécuter cinq flux de compression.
De plus, la latence de la RAM devient un paramètre essentiel déterminant la vitesse du compresseur. L'algorithme utilise des accès aléatoires à l'OP, dont certains n'entrent pas dans la mémoire cache (environ 10%) et il doit rester inactif, en attendant les données de l'OP, ce qui réduit la vitesse de travail.
Affecte de manière significative la vitesse du compresseur et le fonctionnement du système d'entrée / sortie de données. Les demandes à l'OP à partir des demandes de données de bloc d'E / S de la CPU, ce qui réduit également le taux de compression. Ce problème est important pour les ordinateurs portables et les ordinateurs de bureau, pour les serveurs, il est moins important en raison de l'unité de contrôle d'accès plus avancée pour le bus système et la RAM multicanaux.
Partout dans le texte, l'article fait référence à la compression, la décompression sort du cadre de cet article car tout y est en chocolat. La décompression est beaucoup plus rapide et est limitée par la vitesse d'E / S. Un noyau physique dans un thread fournit calmement des vitesses de décompression au niveau de 3-4 Gigaoctets / sec.
Cela est dû à l'absence d'une opération de recherche de correspondance pendant le processus de décompression, qui «consomme» les ressources du processeur principal et du cache pendant la compression.
Stockage fiable des données compressées
Comme l'indique le nom de toute la classe d'outils logiciels utilisant la compression de données (archiveurs), ils sont conçus pour un stockage à long terme des informations, non pas pendant des années, mais pendant des siècles et des millénaires ...
Pendant le stockage, les supports de stockage perdent certaines des données, voici un exemple:
Ce support de stockage "analogique" a mille ans, certains fragments ont été perdus, mais en général l'information est "lisible" ...
Aucun des fabricants responsables de systèmes de stockage numérique modernes et de supports numériques pour eux ne garantit une sécurité complète des données depuis plus de 75 ans.
Et c'est un problème, mais le problème est reporté, nos descendants vont le résoudre ...
Les systèmes de stockage de données numériques peuvent perdre des données non seulement après 75 ans, des erreurs de données peuvent apparaître à tout moment, même pendant leur enregistrement, ils essaient de minimiser ces distorsions en utilisant des systèmes de redondance et de correction des erreurs. Les systèmes de redondance et de correction ne peuvent pas toujours restaurer les informations perdues et s'ils sont restaurés, il n'y a aucune garantie que l'opération de récupération était correcte.
Et c'est aussi un gros problème, mais pas un retard, mais le problème actuel.
Les compresseurs modernes utilisés pour l'archivage des données numériques sont construits sur diverses modifications de la méthode du dictionnaire, et pour de telles archives, la perte d'une information sera un événement fatal, il existe même un terme établi pour une telle situation - une archive "cassée" ...
La faible fiabilité du stockage des informations dans les archives avec compression de dictionnaire est associée à la structure des données compressées. Les informations contenues dans une telle archive ne contiennent pas le texte source, les nombres d'entrées dans le dictionnaire y sont stockés, le dictionnaire lui-même est modifié dynamiquement par le texte compressible actuel. Si un fragment de l'archive est perdu ou déformé, toutes les entrées d'archive suivantes ne peuvent être identifiées ni par le contenu ni par la longueur des entrées dans le dictionnaire, car on ne sait pas à quoi correspond le numéro de l'entrée de dictionnaire.
Il est impossible de récupérer des informations d'une telle archive «cassée».
L'algorithme RTT est basé sur une méthode plus fiable de stockage des données compressées. Il utilise la méthode d'index pour rendre compte des fragments répétés. Une telle approche de la compression permet de minimiser les conséquences de la distorsion des informations sur le support et, dans de nombreux cas, de corriger automatiquement les distorsions survenant lors du stockage des informations.
Cela est dû au fait que le fichier d'archive dans le cas de la compression d'index contient deux champs:
- champ de texte source avec des sections répétées supprimées;
- champ d'index.
Le champ d'index critique pour la récupération de données n'est pas de grande taille et peut être dupliqué pour un stockage fiable des données. Par conséquent, même si un fragment du texte source ou du tableau d'index est perdu, toutes les autres informations seront restaurées sans problème, comme dans l'image avec le support d'informations «analogique».
Lacunes de l'algorithme
Les avantages n'existent pas sans inconvénients. La méthode de compression d'index ne comprime pas les séquences courtes répétitives. Cela est dû aux limitations de la méthode d'indexation. La taille des index est d'au moins 3 octets et peut aller jusqu'à 12 octets. Si une répétition se produit avec une taille plus petite que l'index la décrivant, alors elle n'est pas prise en compte, cependant souvent de telles répétitions sont détectées dans un fichier compressible.
La méthode de compression de vocabulaire traditionnelle comprime efficacement plusieurs répétitions courtes et atteint donc un taux de compression plus élevé que la compression d'index. Certes, cela est dû à la charge de travail élevée du processeur central, de sorte que la méthode de vocabulaire commence à compresser les données plus efficacement que la méthode d'indexation, elle doit réduire la vitesse de traitement des données à 10-20 mégaoctets par seconde sur les installations informatiques réelles avec une utilisation complète du processeur.
Ces faibles vitesses sont inacceptables pour les systèmes de stockage de données modernes et présentent un intérêt plus "académique" que pratique.
Le degré de compression des informations sera considérablement augmenté lors de la prochaine modification de l'algorithme PTT (RTT-Max), il est déjà en développement.
Alors, comme toujours, à suivre ...