LessFs: la déduplication en ligne sous Linux (1/3)

Il faut se faire une raison! Le volume de données généré par la vie d’une entreprise ou d’un particulier ne cesse de croitre.

La politique du “zéro papier” y contribue. Par exemple,un email ou un document non imprimé est souvent conservé “pour archivage et références ultérieures”. Comme le travail est devenu massivement collaboratif et que de plus en plus de réactivité à l’information est attendue de chacun, ce peut être trente copies d’un même email qui sont ainsi conservées par les différents interlocuteurs qui ont contribués à son élaboration.

Le nomadisme pousse également les employés à conserver une copie de leurs fichiers importants sur leur PC portable, plutôt que centralisés sur un serveur.

La virtualisation de serveurs contribue aussi à cette tendance. Au fond, une fois que l’on a déduit l’OS et les applications standards, quel pourcentage d’un disque dur fait vraiment la différence entre un serveur et un autre? Bien peu!

Certes, le coût des disques baisse. Aujourd’hui un disque SATA d’un Teraoctets coute à peine une centaine d’euros. Mais ce qui coute cher, ce sont les technologies requises pour consolider et administrer Teraoctets après Teraoctets après Teraoctets.

Cela ne veut pas dire que tous ces fichiers qui encombrent au final nos serveurs et nos baies de stockage ne doivent pas être sauvegardés ou qu’il faut changer nos habitudes de travail. Cela nous invite simplement à reconsidérer la nécessité de stocker deux versions d’un même fichier dont le contenu ne diffère que de quelques fractions de pourcentage.

La déduplication de données est une solution à cette problématique. Il s’agit de réduire le volume requis pour stocker un volume de données. Certes, il existe déjà de nombreux algorithmes d’archivage et de compression pour cela. Tous les algorithmes de compression comme gzip, tar, 7zip… répondent tous au même algorithme de base: remplacer des blocs de données souvent répétés dans un fichier par un code arbitraire. Ce code est la référence du bloc de données redondants dans un dictionnaire.

La déduplication de données reprend la même logique. Les algorithmes mis en œuvre sont bien moins raffinés que pour la compression de données car le défi que s’est donné la déduplication de données est de garder les fichiers accessibles et modifiables en temps réels. Pas besoin de faire intervenir un administrateur de sauvegardes pour restaurer un document.

De telles fonctionnalités existent d’ors et déjà dans les solutions de stockage des marques de références: NetAPP, EMC, HP… mais ce sont des options très onéreuses.

Depuis décembre 2009, la build 128 de OpenSolaris ajoute la déduplication comme option au système de fichier ZFS.

Dans le monde Linux, il existait déjà des systèmes de fichiers (attachés au noyau par FUSE) où les données sont stockées dans une archive ZIP.

Depuis peu, un projet extrêmement actif (trois mises à jour durant la semaine qui m’a été nécessaire pour rédiger cet article) nommé LessFS apporte la déduplication de donnée au monde du logiciel Libre.

LessFS

LessFS est une application écrite en C disponible sous licence GNU GPLv3.

Elle s’appuie d’une part sur le moteur de base de données “TokyoCabinet” (toutefois, les dernières versions de LessFS peuvent fonctionner sans cette base de données) et FUSE – FileSystem inUser Space – d’autre part.

LessFS est fourni sous la forme d’un paquet RPM pour les distribution basées sur les technologie RedHat ou de fichiers sources.

LessFS détermine si un bloc de données est redondant en calculant une clef de hashage unique à partir des données que contient le bloc. Cette clef est d’une longueur de 20 à 32 octets et est calculée soit par l’algorithme “Blue Midnight Whish hash” ou “tiger hash”. Le choix de l’algorithme influe sur les performances de la déduplication mais aussi sur les risques de collisions.

Une collision de “hash” se produit quand 2 blocs de données différents produisent la même clef. La probabilité est extrêmement faible mais elle existe.

Par exemple, un « Tiger hash » de 24 octets à une longueur de 192 bits ce qui représente 2^192 = 6277101735386680763835789423207666416102355444464034512896 combinaisons possibles. Si l’on considère un volume de 1024 PB de données soit 10^18 = 1000000000000000000 octets et que l’on utilise des bloc d’une taille de 4 KiloOctets pour dé-dupliquer ce volume, cela représente 1000000000000000000/4096 = 244140625000000 blocs. Le probabilité de collision est donc de 244140625000000/ 6277101735386680763835789423207666416102355444464034512896 soit 1:25711008708143844408671393477458.

LessFS permet de régler la taille du bloc de données. Typiquement, elle est comprise entre 4K et 128K. Plus la taille du bloc de données est petite, plus la probabilité de voir un bloc se répéter est grande et donc plus l’effet de déduplication sera effectif.. Toutefois, comme la clef de hachage a la même taille quelque soit la taille du bloc de données, plus le bloc est petit, plus le “overhead” de stockage (c’est à dire la ratio “hash size”/”block size”) est important ce qui nuit considérablement à l’action de dé-duplication. De plus, le temps requis pour “dé-dupliquer” un fichier sera important si la taille de bloc est très petite.

Les paires (“clef de hachage”,”bloc de données”) sont organisées dans une base de données afin d’en faciliter le référencement. Depuis sa création, LessFs utilise TokyoCabinet. Depuis la version 7.4, il est possible de stocker les blocs dans un fichier “à plat”. Cette approche a l’avantage d’être moins gourmande en mémoire.

Avant d’être stocké sur disque, chaque bloc de données est compressé.

Les performances en terme de réduction de données dépendent grandement du type de fichiers. Il est inutile de perdre du temps à dé-dupliquer des fichiers MP3 ou DIVX. Hormis les doublons, il n’y à rien à gagner à traiter ces fichiers qui dont déjà hautement compressés . Par contre, des images BMP, des fichiers bureautiques ou des disques de machines virtuelles sont de très bons candidats. Un choix astucieux de la taille des blocs de données assurera un excellent ratio performance/réduction d’espace. Globalement, plus on dé-duplique de fichiers, plus la probabilité d’y rencontrer des blocs déjà référencés est grande et donc plus la déduplication sera efficace.

A titre d’illustration, considérons 2 fichiers dont voici le contenu:

Fichier 1: AAABBBABABBBAAAAAABBBABABBBAAA (taille = 30 octets)

Fichier 2: BBBAAAABABBBAAA AAABBBABABBBAAA (taille = 30 octets)

Tout d’abord, cherchons à compresser ces deux fichiers. Une analyse du contenu des 2 fichiers suggère le dictionnaire listé dans le tableau 1.

Tableau 1: dictionnaire de compression (taille = 16 octets)

En utilisant ce dictionnaire, il est possible de retranscrire les deux fichiers de la façons suivante:

Fichier 1: 434435

Fichier 2: 535435

Les 2 fichiers, une fois compressés n’occuperaient plus que 12 octets. Par conséquent, la compression de ces deux fichiers réduit de 53% l’espace requis pour les stocker.

Avant compression: taille = 30 + 30 = 60 octets

Après compression: taille= 16 + 12 = 28 octets

La création du dictionnaire est assez longue et requière beaucoup de mémoire et de CPU. Selon les algorithmes, plusieurs lectures des fichiers à compresser peuvent être requises (« plusieurs passes »).

Maintenant, on applique la déduplication à ces deux fichiers avec une taille de bloc de 3 octets.

La base de données de déduplication va contenir des informations décrivant de façon unique le contenu de chaque bloc (« clef de hachage »). Ce dictionnaire est construit au fur et à mesure de la lecture des fichiers (une seule passe requise). Les blocs sont remplacés par la clef correspondante dès que celle-ci est présente dans le dictionnaire listé dans le tableau 2.

Dictionnaire (taille = 12)

Tableau 2: Dictionnaire de déduplication (taille = 12)

Si l’on remplace les blocs de données par leurs index dans la base de blocs, on obtient le descriptif de contenu suivant:

Fichier 1: 1232112321

Fichier 2: 2132112321

Par conséquent, la déduplication de ces deux fichiers réduit de 47% l’espace requis pour les stocker.

Avant déduplication: taille = 30 + 30 = 60 octets

Après déduplication: taille= 12 + 20 = 32 octets

Certes le taux de compression est inférieur à celui obtenu avec la compression mais les traitements requis pour l’obtenir sont beaucoup plus légers.

La fiabilité des supports de stockage est primordiale lorsqu’on utilise la déduplication de données. Parce que les blocs de données ne sont stockés qu’une seule et unique fois, toute défaillance, même partielle, d’un disque dur peut avoir des conséquences dramatique. Archiver ne veut pas dire sauvegarder! Il s’agit plutôt de réduire le coût de stockage de données peu actives. LessFS propose d’ailleurs un mécanisme permettant de geler le système de fichier système le temps de sa sauvegarde.

LessFS fourni également un utilitaire permettant de dé-fragmenter la base de données de blocs.

Comme LessFS utilise FUSE, il simule un répertoire Linux “normal”. Tous les fichiers qui y seront écrit seront automatiquement dé-dupliqués en temps réel. Les fichiers peuvent être édités de façon totalement transparente par l’utilisateur.

TokyoCabinet

TokyoCabinet est un jeu de librairie permettant de gérer une base de donnée. La base de données est un simple fichier dans lequel sont stockés des paires (clef primaire,données). Chaque entrée est un flux de taille variable. Les clef et les données peuvent être de type texte ou binaire. Il n’y a pas de concept de table ou de type de données dans TokyoCabinet. Les enregistrements sont organisés grâce à un algorithme de type B+ tree.

Tokyo Cabinet est présenté comme une alternative aux SGDB traditionnels comme MySQL. Il s’agit d’un jeu de librairie qui s’intègre au plus près du programme et stocke directement les données sur le disque. Il n’y a pas de serveur de base de données intermédiaire. Ainsi, on obtient des fonctions de base de données simple à utiliser, rapides et économes en mémoire et en espace disque

Tokyo Cabinet est écrit en C mais il existe des interfaces en Perl, Ruby, Java… TokyoCabinet est conforme à la norme POSIX et est disponible sous licence GNU Lesser General Public License.

FUSE

FUSE signifie «  Filesystem in Userspace”. Il s’agit d’un module, disponible pour les noyaux 2.4 et 2.6, grâce auquel il est possible d’implémenter toutes les fonctionnalités d’un système de fichier dans un espace utilisateur. Ces fonctionnalités incluent :

• une API de librairie simple ;
• une installation simple (pas besoin de patcher ou recompiler le noyau) ;
• une implémentation sécurisée ;
• utilisable dans l’espace utilisateur.

Yves Brissaud a écrit un article sur FUSE intitulé « FUSE, Ruby et DigiKam » paru dans l’édition de septembre 2008 de Linux+.

Aujourd’hui, pour monter un système de fichier, il faut être administrateur ou que celui-ci l’ait prévu dans « /etc/fstab » avec des informations en dur.

FUSE permet à un utilisateur de monter lui-même un système de fichier.

Pour profiter de FUSE, il faut des programmes qui exploitent sa bibliothèque et ces programmes sont nombreux. Vous trouverez ci-dessous quelques exemples des systèmes de fichiers compatibles avec FUSE: la liste complète est disponible dans le wiki: http://fuse.sourceforge.net/wiki/index.php/FileSystem.

Tableau 3: Quelques systèmes de fichiers disponible par FUSE