Cet article est déjà le deuxième sur le thème de la compression de données à haut débit. Le premier article décrivait un compresseur fonctionnant à une vitesse de 10 Go/sec. par cœur de processeur (compression minimale, RTT-Min).
Ce compresseur a déjà été implémenté dans l'équipement des duplicateurs médico-légaux pour la compression à grande vitesse des dumps de supports de stockage et pour améliorer la force de la cryptographie ; il peut également être utilisé pour compresser les images des machines virtuelles et les fichiers d'échange de RAM lors de leur sauvegarde à haute vitesse. Disques SSD.
Le premier article annonçait également le développement d'un algorithme de compression pour compresser les copies de sauvegarde des disques durs et SSD (compression moyenne, RTT-Mid) avec des paramètres de compression de données considérablement améliorés. À présent, ce compresseur est complètement prêt et cet article en parle.
Un compresseur qui implémente l'algorithme RTT-Mid fournit un taux de compression comparable aux archiveurs standards tels que WinRar, 7-Zip, fonctionnant en mode haute vitesse. Dans le même temps, sa vitesse de fonctionnement est au moins d'un ordre de grandeur supérieure.
La vitesse de compression/décompression des données est un paramètre critique qui détermine le champ d’application des technologies de compression. Il est peu probable que quiconque pense à compresser un téraoctet de données à une vitesse de 10 à 15 mégaoctets par seconde (c'est exactement la vitesse des archiveurs en mode de compression standard), car cela prendrait près de vingt heures avec une charge complète du processeur. .
D’un autre côté, le même téraoctet peut être copié à des vitesses de l’ordre de 2 à 3 Go par seconde en une dizaine de minutes.
Par conséquent, la compression d’informations volumineuses est importante si elle est effectuée à une vitesse non inférieure à la vitesse d’entrée/sortie réelle. 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 avec les compresseurs traditionnels.
Test comparatif d'un nouvel algorithme de compression
Le compresseur RTT-Mid a fonctionné dans le cadre du programme de test. Dans une vraie application « fonctionnelle », cela fonctionne beaucoup plus rapidement, il utilise judicieusement le multithreading et utilise un compilateur « normal », pas C#.
Étant donné que les compresseurs utilisés dans le test comparatif sont construits sur des principes différents et que différents types de données sont compressés différemment, pour l'objectivité du test, la méthode de mesure de la « température moyenne à l'hôpital » a été utilisée...
Un fichier de dump secteur par secteur d'un disque 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 actuellement 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 dump :
Le fichier de vidage a été compressé à l'aide des compresseurs PTT-Mid, 7-zip et WinRar. Le compresseur WinRar et 7-zip ont été réglés à la vitesse maximale.
Compresseur en marche 7-zip:
Il charge le processeur à 100 %, tandis que la vitesse moyenne de lecture du dump original est d'environ 60 mégaoctets/s.
Compresseur en marche WinRAR:
La situation est similaire, la charge du processeur est presque à 100 %, la vitesse moyenne de lecture du dump est d'environ 125 mégaoctets/s.
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 est en cours RTT-Mid:
La capture d'écran montre que le processeur est chargé à 50 % et reste 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 de données (Disque 0) est presque entièrement chargé. La vitesse de lecture des données (disque 1) varie considérablement, mais en moyenne supérieure à 200 mégaoctets/s.
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 fait le meilleur travail de compression ; l'archive qu'il a créée était 1,3 Go plus petite que l'archive WinRar et 2,1 Go plus petite que l'archive 7z.
Temps passé à créer 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 rapidement, alors que l'archive s'est avérée nettement plus petite que celle de ses concurrents...
Ceux qui ne croient pas aux captures d’écran peuvent vérifier eux-mêmes leur authenticité. Le programme des tests est disponible sur , 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 testez pas l'algorithme sur les anciens processeurs AMD, ils sont lents en termes d'exécution des instructions AVX...
Méthode de compression utilisée
L'algorithme utilise une méthode d'indexation des fragments de texte répétés avec une granularité en octets. Cette méthode de compression est connue depuis longtemps, mais n'a pas été utilisée car l'opération de mise en 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 de « retour vers le futur »…
Le compresseur PTT utilise un scanner de recherche de correspondances à haute vitesse unique, ce qui nous permet d'accélérer le processus de compression. Un scanner fait maison, c'est "mon charme...", "c'est assez cher, car c'est entièrement fait main" (écrit en assembleur).
Le scanner de recherche de correspondance est réalisé selon un schéma probabiliste à deux niveaux : d'abord, la présence d'un « signe » d'une correspondance est analysée, et seulement après que le « signe » a été identifié à cet endroit, la procédure de détection d'une correspondance réelle a démarré.
La fenêtre de recherche de correspondance a une taille imprévisible, en fonction du degré d'entropie dans le bloc de données traité. Pour les données complètement aléatoires (incompressibles), sa taille est de mégaoctets, pour les données répétitives, elle est toujours supérieure à un mégaoctet.
Mais de nombreux formats de données modernes sont incompressibles et exécuter un scanner gourmand en ressources est inutile et inutile, le scanner utilise donc deux modes de fonctionnement. Tout d'abord, les sections du texte source avec des répétitions possibles sont recherchées ; cette opération est également effectuée selon une méthode probabiliste et est effectuée très rapidement (à une vitesse de 4 à 6 gigaoctets/s). Les zones présentant des correspondances possibles sont ensuite traitées par le scanner principal.
La compression d'index n'est pas très efficace, vous devez remplacer les fragments en double 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 également les correspondances partielles, lorsque la chaîne contient des octets correspondants et sans correspondance. Pour ce faire, le format d'index comprend un champ de masque de correspondance qui indique les octets correspondants de deux blocs. Pour une compression encore plus importante, l'indexation est utilisée pour superposer plusieurs blocs partiellement correspondants au bloc actuel.
Tout cela a permis d'obtenir dans le compresseur PTT-Mid un taux de compression comparable aux compresseurs réalisés selon la méthode du dictionnaire, mais fonctionnant beaucoup plus rapidement.
Vitesse du nouvel algorithme de compression
Si le compresseur fonctionne avec l'utilisation exclusive de la mémoire cache (4 mégaoctets sont requis par thread), la vitesse de fonctionnement varie de 700 à 2000 XNUMX mégaoctets/s. par cœur de processeur, en fonction du type de données compressées et dépend peu de la fréquence de fonctionnement du processeur.
Avec une implémentation multithread du compresseur, l'évolutivité efficace est déterminée par la taille du cache de troisième niveau. Par exemple, avec 9 mégaoctets de mémoire cache « embarqués », cela n'a aucun sens de lancer plus de deux threads de compression, la vitesse n'augmentera pas à partir de là. Mais avec un cache de 20 Mo, vous pouvez déjà exécuter cinq threads de compression.
De plus, la latence de la RAM devient un paramètre important qui détermine la vitesse du compresseur. L'algorithme utilise un accès aléatoire à l'OP, dont une partie ne pénètre pas dans la mémoire cache (environ 10 %) et doit rester inactif, en attendant les données de l'OP, ce qui réduit la vitesse de fonctionnement.
Affecte de manière significative la vitesse du compresseur et le fonctionnement du système d'entrée/sortie de données. Les requêtes adressées à l'OP depuis le bloc d'E/S demandent des données au CPU, ce qui réduit également la vitesse de compression. Ce problème est important pour les ordinateurs portables et de bureau ; pour les serveurs, il est moins important en raison d'une unité de contrôle d'accès au bus système plus avancée et d'une RAM multicanal.
Tout au long du texte de l'article nous parlons de compression ; la décompression reste en dehors du cadre de cet article puisque « tout est recouvert de chocolat ». La décompression est beaucoup plus rapide et est limitée par la vitesse des E/S. Un cœur physique dans un thread fournit facilement des vitesses de déballage de 3 à 4 Go/s.
Cela est dû à l'absence d'opération de recherche de correspondance pendant le processus de décompression, qui « consomme » les principales ressources du processeur et de la mémoire cache lors de la compression.
Fiabilité du stockage des données compressées
Comme le suggère le nom de toute la classe de logiciels utilisant la compression de données (archiveurs), ils sont conçus pour le stockage à long terme des informations, non pas pendant des années, mais pendant des siècles et des millénaires...
Lors du stockage, les supports de stockage perdent certaines données, voici un exemple :
Ce support d'information « 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 de données numériques modernes et de supports numériques correspondants ne garantit une sécurité totale des données depuis plus de 75 ans.
Et c'est un problème, mais un problème reporté, nos descendants le résoudront...
Les systèmes de stockage de données numériques peuvent perdre des données non seulement après 75 ans, mais des erreurs dans les données peuvent apparaître à tout moment, même pendant leur enregistrement, ils essaient de minimiser ces distorsions en utilisant la redondance et en les corrigeant avec des systèmes de correction d'erreurs. Les systèmes de redondance et de correction ne peuvent pas toujours restaurer les informations perdues, et s'ils le font, il n'y a aucune garantie que l'opération de restauration se soit déroulée correctement.
Et c’est aussi un gros problème, mais pas différé, mais 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 par dictionnaire est associée à la structure des données compressées. Les informations contenues dans une telle archive ne contiennent pas le texte source, le nombre d'entrées dans le dictionnaire y est stocké et le dictionnaire lui-même est modifié dynamiquement par le texte compressé actuel. Si un fragment d'archive est perdu ou corrompu, toutes les entrées d'archive ultérieures ne peuvent être identifiées ni par le contenu ni par la longueur de l'entrée dans le dictionnaire, car il n'est pas clair à quoi correspond le numéro de l'entrée du dictionnaire.
Il est impossible de restaurer les informations d'une archive aussi « 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'indexation pour comptabiliser les fragments répétitifs. Cette approche de la compression vous permet de minimiser les conséquences de la distorsion des informations sur le support de stockage et, dans de nombreux cas, de corriger automatiquement les distorsions survenues lors du stockage des informations.
Cela est dû au fait que le fichier archive dans le cas de la compression d'index contient deux champs :
- un champ de texte source dont les sections de répétition ont été supprimées ;
- champ d'indexation.
Le champ d'index, essentiel à la récupération des informations, 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 un support de stockage « analogique ».
Inconvénients de l'algorithme
Il n’y a pas d’avantages sans inconvénients. La méthode de compression d’index ne compresse pas les courtes séquences répétitives. Cela est dû aux limites de la méthode d'indexation. Les index ont une taille d'au moins 3 octets et peuvent atteindre 12 octets. Si une répétition est rencontrée avec une taille inférieure à l'index la décrivant, alors elle n'est pas prise en compte, quelle que soit la fréquence à laquelle de telles répétitions sont détectées dans le fichier compressé.
La méthode traditionnelle de compression par dictionnaire compresse efficacement plusieurs répétitions de courte durée et permet donc d'obtenir un taux de compression plus élevé que la compression d'index. Certes, cela est dû à la charge élevée du processeur central : pour que la méthode du dictionnaire commence à compresser les données plus efficacement que la méthode de l'index, elle doit réduire la vitesse de traitement des données à 10-20 mégaoctets par seconde en temps réel. installations informatiques avec une charge CPU complète.
Des vitesses aussi faibles 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é dans la prochaine modification de l'algorithme RTT (RTT-Max), déjà en développement.
Alors, comme toujours, à suivre...
Source: habr.com