Déduplication : bloc fixe VS bloc variable

Intérêt de la dé-duplication

J’ai testé il y a quelques temps le filesystem lessfs (site officiel du projet). C’est un filesystem très simple à mettre en place, de type Fuse (donc en user space) qui permet de monter un espace de dé-duplication à la volée.  Cette fonctionnalité permet de gagner une place considérable lorsque l’on a des données qui se ressemble fortement.

Elle est complémentaire de la compression. Là où vous aller gagner sur un fichier avec la compression, si vous en avez deux, vous aller stocker deux fois la taille compressée. Avec une passe de dé-duplication avant, vous n’aurez qu’une fois chaque bloc, puis vous pouvez compresser ce qui reste.

Deux méthodes : bloc de taille fixe ou variable

Taille fixe

Les blocs justement. Dans lessfs, ce sont des blocs de taille fixe. Donc on applique un algorithme très simple :

• on coupe la donnée en bloc de NKo (prenons 4Ko)
• on fait un hash de chaque bloc
• si on a déjà un hash, on change le bloc par un simple pointeur vers le bloc déjà sauvegardé
• sinon on sauvegarde le bloc et son hash

Simple. Efficace? Pas si sûr. Bien entendu, si vous faites une copie d’un fichier, celle-ci ne va quasiment rien vous coûter. Mais faire des copies intactes de vos fichiers arrive parfois avec des sauvegardes, et encore…

Taille variable

Si l’on veut être plus efficace, il faut faire une recherche dans les données d’un bloc déjà vu. Mais là où avant on cherchait avec un début de bloc tous les 4Ko, là on cherche pour tous les octets. En effet, si vos blocs ne sont pas parfaitement alignés, vous ne reconnaîtrez pas votre bloc, car il a pris un simple offset de quelques octets!

Bien sûr, ce genre de recherche est bien plus couteux en terme de CPU, 4K calculs fois plus. (En fait u peu moins, dès que vous raccrochez un wagon de blocs déjà connu, un seul calcul suffit).

Exemple de gain

Un exemple?

J’ai codé rapidement un petit script en Python qui réalise ces deux types de dé-duplications :

• recherche des mêmes blocs de 4Ko avec recherche par fenêtre glissante
• recherche brut de frondrie, bloc de 4k

Voici les résultats sur un répertoire plein de fichiers de type office and co:

****** Stats Varible: Deplicated 342756761/465877423 = 73.00% Dedup+compress 426510002 =91.00%
****** Stats Fix: Deplicated 59596755/465877423 = 12.00% Dedup+compress 68349038 =14.00%

On a donc 73% de gain avec des tailles de blocs variables, 91% si on les compresse par dessus. La méthode fixe bourrine n’arrive elle qu’à un faible 12%.

Bon bah il faut demander à lessfs d’appliquer cet algo? Pas si simple, de un c’est ultra consommateur en CPU, donc il faut le faire en post-process, pas à la volée. Et surtout l’algo utilisé semble avoir été breveté par EMC… Et après ça qu’on vienne encore me sortir que les brevets sont fait pour protéger l’innovation…. l’investissement oui, l’innovation non…

Pour ceux qui ont la chance de ne pas habiter dans ce merveilleux pays des brevets logiciels, vous pouvez tester le script là.