Déduplication : bloc fixe VS bloc variable

Posted in Programmation by Nap on March 14, 2010 7 Comments

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.

Related Posts:

Comments
  • AP:

    Certains brevets logiciels sont liés au procédé de déduplication. Typiquement, ce qui pose problème, c’est de déclarer identiques des blocs dont les sommes de contrôle s’avèrent identiques. Le moyen typique de contourner le projet et de réaliser une comparaison bit à bit des blocs à fusionner.

    Exemple d’un projet qui doit contourner soigneusement les brevets : le projet KSM (kernel shared memory), qui consiste en un patch visant à fusionner les blocs de mémoire identiques. Très intéressant avec tout ce qui touche à la virtualisation.
    http://lwn.net/Articles/330589/

    Cela-dit ce lessfs semble trrrrrrrrès intéressant. Je vais creuser ça… en attendant que btrfs (dont j’attends beaucoup) ne gère nativement la déduplication. :)

    • Nap:

      C’est vrai qu’ils utilisent un arbre binaire il me semble. Je n’ai toujours pas pris le temps de voir comment ça permettait d’éviter le hash (brevet VMware…) des pages mémoires, mais en effet ici ça permettrait de faire la même chose au final.

      D’après ton lien, le replacement du hash est bien une simple comparaison bit à bit (”Placement in the tree is determined by a simple memcmp()”) ce qui au final est peu être plus efficace qu’un hash!

      Pour Btrfs oui, il semble prometteur. Mais j’espère qu’il fera du bloc fixe (ça ok, ça va être géré), mais aussi du variable, quitte à le faire en background, car les gains ne sont pas les mêmes :p

      Pour l’instant lessfs permet déjà de bien s’amuser :)

      Je sens bien que la dédup+compression va être un standard dans l’avenir des espaces de backups, et que ça va remplacer nos chères commandes gzip et bzip2 car de-dupliquer du compressé, c’est inefficace au possible :)

      • Cyril:

        Nous utilisons ZFS sur Opensolaris (également dispo sur BSD) qui intègre également déduplication et compression, très très concluant, les gains se cumulent et le système de fichier reste performant (et en + quota, snapshots instantanés de file system, export et import de snapshot… bref tout le confort)

        Existe en version partielle sur Linux via Fuse il me semble (ZFS est opensource mais la licence n’est pas compatible avec la GPL du noyau Linux, ce qui est fort dommage)

        • Nap:

          Je vais essayer de le monter et de voir les gains entre lessfs et ZFS question déduplication/compression.

          Tu sais si ZFS fait de la taille fixe ou variable? (Il me semble que c’est du fixe car il se base sur ton hash interne pour la corruption de données, donc taille fixe a priori).

          Donc quid du gain sur un fichier qui se prends un petit offset dès le début?

  • AP:

    “de contourner le brevet” … pas “le projet”.
    Grrr, on ne se relit jamais assez.

    • Nap:

      Ne m’en parle pas…

      PS : y a pas edit de dispo? (mon compte là car il est authentifié, mais pour le autres je ne sais pas)

  • Nap:

    Bon j’ai réussi à tuner un peu le script en :
    *bypassant le hash (et donc en évitant le brevet héhéhé), mais en mettant tout simplement les pages en mémoires au lieu du hash. La comparaison est un poil plus lente, mais vu qu’on n’a plus de hash, on y gagne.
    *ne faisant la comparaison complète de du bloc que si ses 128 premiers octets étaient dans une seconde table remplie en même temps que la table principale. On perd en consommation mémoire, mais on booste le temps de comparaison.

    Temps final : 4m39 pour dé-dupliquer 460Mo, soit 1.6Mo/s. Bon c’est lent soit, mais bon faut être pas clair si vous voulez un filesystem en Python aussi :)