Déduplication vs. Compression : deux approches

Selon l’institut de recherche international IDC, la quantité de données mondiale est doublée tous les deux ans environ. Dès 2020, cet univers digital devrait comprendre un volume total de 44 zettaoctets. Cela représente une production ou copie de 44 trillions de gigaoctets de données en une seule année. Ce développement a notamment des répercussions sur les techniques de stockage, les procédures de liens retour, et les systèmes de récupération de données. Ces derniers doivent être en mesure de porter l’énorme poids de données ainsi que de l’utiliser. Des méthodes sont mises en avant pour les concepts de mise en œuvre technique. Elles permettent une réduction des informations physiques ainsi que des coûts de la conservation de données. Ces méthodes s’appuient essentiellement sur deux approches : la compression de donnés et la déduplication. Tandis que la compression de données sans perte utilise la redondance au sein d’un fichier, les algorithmes de déduplication ajustent généralement les données de fichiers afin d’éviter les répétitions. La sauvegarde de données est pour cette raison le domaine central de la technique de déduplication.

Déduplication

La technique de déduplication désigne un processus de réduction de données permettant d’éviter la redondance de données sur l’espace de stockage d’un système. Une machine de déduplication est utilisée pour éliminer les fichiers ou blocs de données redondants grâce à des algorithmes spéciaux. 

Le but de la déduplication comme technique de stockage est d’écrire autant d’informations que nécessaire sur un support non volatile, afin de reconstituer un fichier sans perte. Plus il y a de duplicatas enlevés, plus la quantité de données devant être stockée et transmise est réduite. L’identification de duplicatas peut par exemple se faire sur Git ou Dropbox au niveau du fichier, mais les algorithmes qui travaillent au niveau des sous-fichiers restent plus efficaces. Les fichiers sont ainsi démontés en blocs de données qui sont dotés de sommes de contrôle ou hachages. Une base de données de suivi sert d’instance de contrôle centrale et contient toutes ces sommes de contrôle.

La méthode de déduplication basée sur la construction de blocs comporte deux variantes :

  • Déduplication avec de longs blocs solides : l’algorithme subdivise des fichiers en extraits faisant exactement la même longueur. Celui-ci s’oriente généralement vers la taille du  groupe de fichiers (cluster) ou système RAID (4 KB habituellement), mais il peut aussi être configuré manuellement. La longueur des blocs est adaptée individuellement dans ce cas et est déterminée comme standard pour tous les blocs.
  • Déduplication avec des blocs à longueur variable : aucune longueur standard n’est définie ici. Au lieu de cela, l’algorithme répartit les données en différents blocs dont la longueur varie selon le type.

Le type de répartition a une influence de plus en plus importante sur l’efficacité de la déduplication. Ceci est particulièrement important lorsque les données décalquées sont modifiées ultérieurement. Si l’on élargit un bloc de données solide avec des informations supplémentaires, le contenu de tous les blocs suivants se déplacent généralement proportionnellement vers les limites de blocs prédéfinies. Bien que la modification ne concerne qu’un bloc de données seulement, l’algorithme de déduplication classe aussi tous les segments suivants d’un fichier de nouveau en raison du décalage des limites des blocs. Il se peut aussi que les octets modifiés présentent exactement le même multiple que la longueur de bloc fixée. Étant donné que les blocs marqués comme nouveaux sont à nouveau enregistrés, une copie lors d’une déduplication de blocs de données à la longueur fixe augmente la mémoire de calcul ainsi que la charge sur la bande passante.    

Si un algorithme utilise au contraire des limites de blocs variables, les modifications sur un seul bloc ne se répercutent pas sur les segments adjacents. Au lieu de cela, seul le bloc de données modifié est modifié et enregistré. Cela décharge le réseau, car moins de données sont transmises lors d’une sauvegarde. Cette flexibilité des modifications de données est cependant coûteuse en ressources du processeur car l’algorithme doit tout d’abord trouver comment les différentes portions de données sont réparties.

L’identification de portions redondantes repose sur la supposition que les blocs de données contiennent des informations de hachage identiques. Afin de filtrer les portions redondantes, l’algorithme de déduplication n’a qu’à retransmettre les hachages et les comparer avec la base de données de suivi. S’il y trouve des sommes de contrôle identiques, les portions redondantes sont remplacées par un pointeur qui renvoie à un espace de stockage identique à celui du bloc de données. Un tel pointeur nécessite en lui-même sensiblement moins de place en comparaison avec un bloc de données. Plus ces données sont remplacées par de tels pointeurs, moins elles nécessitent d’espace de stockage. On ne peut cependant pas prédire l’efficacité de la réduction de données à travers les algorithmes de déduplication car ils dépendent fortement du fichier sortant et de sa structure de données. De plus, la déduplication ne convient qu’à des données non codées. Les redondances sont évitées de manière ciblée sur les systèmes de chiffrement, ce qui rend impossible la reconnaissance de modèle.

La déduplication se fait soit à l’emplacement cible du stockage, soit à la source.

Déduplication source

Si les données redondantes sont déjà enlevées avant la transmission vers l’espace de stockage cible, on parle de déduplication source. La machine de déduplication est par exemple dans ce cas intégrée au programme de sauvegarde. Les informations redondantes sont directement éliminées du système de données de la source de données. Pour cela, le programme de sauvegarde scanne les blocs de données nouvellement créés à intervalles réguliers et les compare avec les sauvegardes du serveur déjà existantes. S’il trouve un bloc de fichiers redondant, il l’exclura de la prochaine sauvegarde. Si un fichier est modifié, le programme de sauvegarde transmet seulement les modifications.

L’avantage certain de la méthode de déduplication en matière de sécurité des données est que les nouvelles informations transmises au serveur de sauvegarde permettent d’alléger la bande passante, ainsi que la capacité de l’espace de stockage cible. A l’inverse de la méthode de déduplication basée sur la cible, la déduplication source implique un investissement et des ressources du programme de sauvegardes supplémentaires. Elle n’est donc pas adaptée à tous les scénarii d’utilisation.

Déduplication cible

La réduction de données se fait en dehors des données source avec la méthode de déduplication cible. La machine de déduplication peut soit être intégrée au tableau matériel ou en tant qu’appareil indépendant. Dans les deux cas, la déduplication cible réduit la capacité mémoire nécessaire et n’a, à la différence de la déduplication source, aucune influence sur la quantité de données transmise du système source à l’espace de stockage cible via LAN ou WIFI lors d’une sauvegarde. Selon la structure de déduplication cible choisie, on différencie post-processing deduplication et inline-deduplication.

  • Post-Processing-deduplication : si le moteur de déduplication est placé dans le tableau, les données de la sauvegarde authentique sont déposées sur un support de stockage puis dédupliquées. On parle dans ce cas de post-processing-deduplication. Ce type de déduplication présente l’avantage que les données sont transmises relativement rapidement sur l’espace de stockage cible. Toutefois, ces données ne sont pas disponibles immédiatement après la transmission car le processus de sauvegarde doit d’abord être terminé avant que les redondances ne puissent être éliminées. Par conséquent, les données sont adressées 3 fois sur le disque dur avant qu’elles ne soient disponibles pour une réplication ou un retrait. Ceci augmente la charge sur le système de stockage. De plus, le système de sauvegarde doit d’abord fournir deux zones de stockages séparées : une pour les données sortantes et l’autre pour les données dédupliquées. Cela nécessite par conséquent bien plus de stockage physique qu’une déduplication inline. A la différence de cette dernière, une déduplication post-processing permet une réduction de données plus efficace, sur la base de blocs de données variables.
  • Inline-deduplication : si le moteur de déduplication se situe avant le support de stockage, il est possible d’enlever les données redondantes immédiatement pendant la transmission avant que celles-ci ne soient écrites sur le support de stockage. Cela diminue en effet le débit d’écriture et limite la déduplication de blocs de données à longueur fixe, mais aussi la mémoire physique nécessaire sur un système cible (en comparaison avec une déduplication post-processing). De plus, les données dédupliquées inline sont rapidement mises à disposition, comme lors d’une récupération ou reproduction de données par exemple.

Compression de données

Avec la compression de données, les fichiers sont transférés en une représentation alternative qui est plus efficace que l’initiale. Le but de cet encodage est de réduire non seulement la mémoire dont on a besoin, mais aussi le temps de transfert. On différencie deux approches de gain de codage :

  • Compression axée sur la redondance : lors d’une compression sans perte pour réduire une redondance de données, ces dernières peuvent être décompressées sans perte après une compression. Les données entrantes et sortantes sont ainsi identiques. Une telle compression n’est possible qu’à condition qu’une donnée contienne des informations redondantes.
  • Compression axée sur la non-pertinence : lors d’une compression avec perte, des informations insignifiantes sont enlevées pour compresser un fichier. Ceci implique dans tous les cas une perte de données. Les données d’origine ne se récupèrent que de manière approximative. Les données considérées comme non pertinentes le sont de façon subjective. Lors d’une compression audio via MP3, les modèles de fréquences considérés comme imperceptibles par des humains sont par exemple retirés.

Tandis que la compression se produit sans perte au niveau des systèmes de stockage, on constate des pertes de données dans d’autres domaines tels que l’image, la vidéo, ou la transmission audio lors de la réduction du volume d’un tel fichier.

La compression nécessite autant de calcul que la décompression de fichiers. Mais cette quantité de calcul dépend de la méthode de compression utilisée. Tandis que quelques techniques sont conçues pour une représentation aussi compacte que possible des données sortantes, d’autres méthodes permettent une réduction du temps de calcul nécessaire pour la réduction de données. Le choix de la méthode de compression s’oriente toujours en fonction des exigences du domaine de mise en application en question.

Dans le cadre d’une transmission vidéo ou d’un enregistrement audio en direct, il est recommandé d’utiliser un procédé qui favorise la compression et la récupération rapide des données. Comparativement, un gain de codage plus faible et sans perte de données est aussi acceptable dans ce cas. Les données qui sont mises à disposition d’un grand nombre d’utilisateurs via un serveur de fichiers (File Server) peuvent être traitées différemment : la compression devrait prendre plus de temps et donc utiliser un algorithme de compression plus performant, permettant un fort gain de codage sans perte de qualité.

Compression de données sans perte

Tandis que l’algorithme de déduplication recherche des fichiers différents dans des extraits de données similaires et les remplace par des renvois vers la section correspondante, des procédés travaillent à la compression de données sans perte avec ce qu’on appelle les représentations. Ceci consiste à remplacer les sections qui se répètent plusieurs fois au sein d’un même fichier par une représentation sensiblement plus courte. Voici une illustration d’un tel cas de figure avec l’exemple suivant :

Texte sortant : ABCDEABCEEABCEE

Codage : ABC = 1; EE = 2

Texte comprimé : 1DE1212

Le texte sortant d’une longueur de 15 caractères peut être réduit à 7 caractères via la compression. Le gain de codage s’élève donc à plus de 50 pourcent. Les prérequis pour cela sont que le système de décodage connaisse aussi bien les techniques d’encodage que de décodage.

La plupart des procédés de compression sans perte utilisent la répétition de caractères ou de combinaisons de caractères au sein d’un fichier. Les procédés Word-Coding et Lempel-Ziv (LZ77) sont des processus de compression populaires basés sur la répétition.  

  • Word-Coding : ce processus de compression est principalement adapté pour les fichiers de texte. Son principe de base est le remplacement de mots par de courtes représentations. Pour cela, la première étape consiste à établir une liste et attribuer chaque mot du fichier à une valeur. Des textes entiers peuvent ainsi être convertis en codes numériques. 

Texte sortant : Thé ou café 

Codage : Thé = 1; ou = 2, café = 3

Texte compressé : 123

Étant donné que la liste de mots doit elle aussi être enregistrée avec ce procédé, le Word-coding se révèle avant tout efficace pour les textes contenant de nombreuses répétitions.

  • Processus Lempel-Ziv : ce procédé repose aussi sur une méthode basée sur le dictionnaire, et qui permet de comprimer des séquences de caractères sur le principe de la redondance. L’algorithme de compression utilise pour cela le contenu présenté dans les dictionnaires. Le renvoi à une série de caractères identiques est représenté via une valeur en trois parties, permettant de déterminer la position et la longueur de la partie présentant des répétitions. Le rapprochement se fait via un étage de recherche et un étage de présentation. Si aucun rapprochement n’est trouvé, on aura la valeur triple (0, 0, X), X étant le caractère correspondant. Le schéma suivant est un exemple de codage LZ77 pour le mot BANANE :

Les caractères ou les séquences de caractères sur l’étage de présentation sont comparées avec les caractères (issus du dictionnaire) de l’étage de recherche. La ligne 4 correspond au remplacement des caractères ANE via le triplé (2, 2, E). Cela se lit de la manière suivante :

2 = remplace la séquence de caractères actuelle par une séquence de caractères déjà lue en position numéro deux de l’étage de recherche (A)

2 = la substitution comprend deux signes (A et N) 

E = le premier caractère après le remplacement est E

Comme la plupart des données peuvent être compressées efficacement à l’aide du procédé LZ77, les successeurs de cet algorithme tels que LZSS sont aujourd’hui très répandus et sont entre autres utilisés pour les formats de fichiers Zip, PNG ou PDF.

En dehors des procédés de codage sans perte basés sur la répétition, on trouve des méthodes basées sur la fréquence ou la longueur, mais aussi le codage Huffman.

  • Codage basé sur la longueur : avec cette méthode, les redondances qui se succèdent sont dans le viseur. La représentation schématique d’une ligne isolée d’un graphique en noir et blanc nous permet de mieux comprendre ceci.  

Données sortantes : WWWWWSSSSWWSSWWWWWWSSSSSSWWW

Une réduction claire des données à enregistrer est possible si des caractères répétés peuvent être caractérisés en tant que valeurs couples issues du nombre de répétitions.

Fichier compressé : 5W4S2W2S6W6S3W

Le codage basé sur la longueur est mis en œuvre lors de la compression d’images, mais perd en efficacité plus il y a de couleurs à coder. Tandis que les esquisses en noir et blanc peuvent être représentées avec deux couleurs, on a déjà besoin de 256 tons de gris pour des images de gris 8 bits. La probabilité que plus de deux pixels consécutifs représentent la même valeur de couleur diminue clairement avec des images complexes dotées de dégradés de couleur fins. Comme l’encodage s’appuie sur des couples de valeur de deux chiffres dans cet exemple, un gain de codage se produit déjà ici, si au moins trois mêmes caractères se succèdent. La forme modifiée d’un codage basé sur la longueur fait partie du processus de compression très populaire JPEG.

  • Encodage Huffman : lors d’une compression selon la méthode Huffman, c’est avant tout la fréquence de tous les caractères qui est déterminée. L’étape suivante consiste à interpréter les caractères en une suite d’unités Bit, avec lesquelles la longueur de la représentation varie selon la fréquence. Voici un exemple permettant de comprendre ce processus de codage :

Caractères

Espace

a

e

f

h

i

m

n

s

t

l

o

p

r

u

x

Fréquence

7

4

4

3

2

2

2

2

2

2

1

1

1

1

1

1

Le codage binaire d’un caractère résulte du chemin de la racine à la feuille d’un arbre. Les renvois vers la gauches sont codés avec un  0 et ceux vers la droite avec un 1.

Pour les caractères de l’exemple, le code suivant se présente :

Espace

a

e

f

h

i

m

n

111

010

000

1101

1010

1000

0111

0010

s

t

l

o

p

r

u

x

1011

0110

11001

00110

10011

11000

00111

10010

Tandis que des caractères tels que l’espace, le A et le E se laissent coder avec seulement 3 bits dans cet exemple, des caractères plus rares comme le R, le U ou le X exigent 5 bits. En comparaison, la police de caractères ASCII utilise par exemple 7 bits par caractère. Avec les polices de caractères compatibles avec SCII telles que UTF-8 ou ISO 8859-1 (Latin-1), on y ajoute encore un huitième bit que les ordinateurs actuels peuvent traiter avec 8, 16, 32 ou 64 bits. L’encodage Huffman permet de stocker du texte de manière très compacte

La suite de caractères suivante montre l’exemple de cet arbre humain comme conséquence binaire selon Huffman :

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

En comparaison avec cette série de Bits, voici le même contenu avec un codage ASCII avec un huitième bit :

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101

Selon la répartition de la fréquence de caractères, les données codées avec Huffman peuvent être réduites à un tiers de leur taille d’origine. On doit cependant tenir compte du fait que la racine de l’arbre doit aussi être stockée lors du décodage suivant.

Un encodage Huffman ne met pas seulement en œuvre la compression de fichiers texte.  Cette méthode est en partie celle utilisée pour la compression d’images JPEG et les formatsZip, qui représentent une combinaison de LZSS et Huffman.

Compression à perte

Tandis que la compression de données sans perte est seulement possible si les redondances se trouvent au sein d’un même fichier, la compression de données avec perte est en principe toujours possible sur la base d’une compression en fonction de la pertinence. Il faut ici accepter une perte de données potentielle avec cette méthode. Une compression de données à perte comporte donc toujours une part de chance de perdre des données originales. On parle de la théorie de Rate-Distortion-Theorie comme limite maximale de compression, décrivant le rapport entre compression et qualité de signal.

Les méthodes de compression à perte sont en général orientées sur la perception humaine. La compression de fichiers audio via MP3, AAC ou WMA par exemple supprime les données qui sont en dehors de la zone d’audibilité humaine. Un exemple courant de la réduction d’éléments non pertinents dans le processus JPEG décrit combine les méthodes de compression sans perte et avec perte.

Déduplication et compression de données en comparaison

Pour réaliser des procédures de sauvegarde ou optimiser le stockage standard de systèmes de données, les entreprises recourent généralement à la déduplication. Cela s’explique notamment par l’extrême efficacité des systèmes de déduplication lorsque des données identiques doivent être classées.

Les processus de compression de données  sont au contraire liés à un volume de calcul plus élevé et nécessitent des plateformes plus onéreuses. Le plus efficace est d’utiliser une combinaison des deux procédés de réduction de données sur un système de stockage. Les redondances sont ainsi éliminées des fichiers stockés et les données restantes sont compressées par la suite.


Attendez ! Nous avons quelque chose pour vous !
Votre messagerie professionnelle

Créez une adresse personnalisée
Affichez votre sérieux sur Internet
Nom de domaine inclus
À partir d' 1 € TTC/mois
Conseiller personnel inclus !