Soutenance mémoire
Le nombre d’appareils interconnectés par Internet augmente de manière exponentielle. En 2003, ce nombre était largement inférieur au nombre d’habitant dans le monde (0.08 appareils par habitant en moyenne). Dans son rapport sur l’évolution d’Internet, Evans estime que ce nombre sera porté à plus de six appareils par habitant (6, 58) d’ici 2020 [Eva11]. Si cette estimation s’avère juste, le nombre total d’appareils connectés atteindra les 50 milliards. L’analyse menée par le cabinet de conseil IDC, auprès d’EMC (leader mondial des solutions de stockage), présente deux facteurs permettant d’expliquer cette augmentation [GR12] : (i) l’extension d’Internet aux objets du quotidien, désignée par le terme « Internet des objets » (IoT pour Internet of Things) ; (ii) l’émergence de nouveaux marchés numériques (Chine, Brésil, Inde, Russie, Mexique). Afin de supporter cette croissance, Internet s’adapte : évolution des protocoles (e.g. le passage à IPv6) et des infrastructures (e.g. construction de centres de données). Les utilisateurs aussi s’adaptent et découvrent de nouvelles applications (e.g. informatique en nuage, fouille de données). Dans ce contexte, le rôle des systèmes de stockage de données est crucial puisque cette évolution importante du nombre d’appareils s’accompagne d’une augmentation exponentielle des données générées et stockées. En particulier, le rapport d’IDC estime que la quantité de données stockées dans le monde correspondra à 44 zettaoctets (i.e. 10²¹ octets) d’ici 2020 [GR12]. Parmi cette quantité massive de données, on notera que 27% seront générées par des objets connectés issus de l’IoT. La conception d’un système de stockage nécessite de considérer différents critères (e.g. capacité de stockage, tolérance aux pannes, mise à l’échelle, débits des lectures et écritures). Les systèmes centralisés (composés d’un seul serveur) présentent des limites, notamment en ce qui concerne la mise à l’échelle (les ressources du serveur sont limitées) et la tolérance aux pannes (perte de la totalité des données stockées sur le serveur). Pour satisfaire ces critères, il est en conséquence nécessaire d’utiliser des systèmes de stockage distribués. Un système distribué est défini par Tanenbaum et Steen [TS06] comme « un ensemble de serveurs indépendants, dont les utilisateurs ont une vision cohérente d’un système unique ». Les systèmes de stockage distribués offrent donc une représentation cohérente d’un volume de stockage dont les données sont réparties sur plusieurs serveurs. Dans la suite, nous utiliserons le terme « Networked Distributed Storage System » (NDSS) défini par Oggier et Datta [OD12] pour insister sur l’interconnexion des supports de stockage à travers un réseau (e.g. bus, ethernet). En fonction de l’application qui travaille sur les données du NDSS, certains critères ont besoin d’être favorisés (pour des raisons économiques). Ainsi, nous allons voir quatre exemples importants d’application qui nécessitent de grands volumes de stockage :
• les services multimédias tels que la vidéo à la demande nécessitent de grandes quantité de données. Par exemple, Netflix dispose pas moins de 40 pétaoctets (i.e. 10¹⁵ octets) de contenus vidéos sur Amazon S3 [Hun14]. Cette application privilégie la mise à l’échelle afin de supporter un pic de connexions (lors de la sortie d’un nouveau contenu vidéo par exemple) ;
• le « Big Data » concerne la fouille et le traitement analytique d’une quantité massive et non structurée de données. Les moteurs de recherche par exemple, doivent gérer une quantité de données théoriquement limitée par l’échelle d’Internet. Pour adresser ce problème, Google a développé son propre système de fichiers distribué, Google File System (GFS) [GGL03], ainsi que le modèle de programmation MapReduce [DG08]. Ces outils permettent d’extraire des relations entre différents types de contenus, tels que des données collectées sur les pages web, les contenus générés par les utilisateurs, ou encore les données proposées par les différents services Google (e.g. maps, shopping) ;
• le calcul à haute performance (HPC, pour High Performance Computing) traite le cas d’importantes quantités de données structurées. Par exemple, Zwaenepoel [Zwa15] adresse le problème de l’optimisation du traitement d’analyse d’un graphe très large (i.e. 32 milliards de sommets, et 10¹² arêtes) par un système distribué constitué de seulement 32 serveurs. Ce type d’application nécessite principalement de hauts débits en lecture et écriture ;
• l’archivage de données en revanche ne possède pas de contraintes fortes sur les débits. Toutefois, cette application a besoin de NDSS avec d’importantes capacités de stockage, et, qui soient tolérants aux pannes. Par exemple, Amazon Glacier fournit un : « service de stockage sécurisé, durable et à très faible coût pour l’archivage (. . .) de données rarement consultées et pour lesquelles un délai d’extraction de plusieurs heures reste acceptable » .
Problèmes du stockage distribué identifiés
Nous avons vu précédemment des applications qui répondent à des problèmes différents. L’offre des systèmes de stockage est en conséquence fragmentée afin de favoriser certains des critères énoncés. Par exemple, les délais garantis par Amazon Glacier ne sont pas appropriés pour gérer des données sur lesquelles seront exécutés des traitements HPC. À l’inverse, le coût d’une grappe de calcul est beaucoup trop élevé pour y archiver des données. On peut ainsi différencier deux types de données : (i) les données froides qui correspondent à du contenu peu accédé (utilisé typiquement dans les applications d’archivage où les données sont écrites une fois pour être sollicitées à l’occasion) ; (ii) les données chaudes, qui à l’inverse sont fréquemment sollicitées (typiquement le cas des applications HPC qui mettent en jeu plusieurs milliers d’entrées/sorties à la seconde). Les administrateurs des systèmes de stockage sont souvent contraints de définir deux systèmes de stockage différents (un système coûteux pour le traitement intensif, l’autre bon marché pour archiver des données). Dans ce formalisme, notre premier problème consiste alors à concevoir un système de stockage capable de gérer aussi bien les données froides, que les données chaudes.
Les applications citées précédemment peuvent interagir avec une quantité massive de données (de l’ordre du pétaoctet par exemple). Il est donc nécessaire de concevoir des systèmes de stockage capables de supporter une charge de plus en plus importante. Les besoins de l’application peuvent également évoluer dans le temps, et nécessiter moins de capacité de stockage. L’approche verticale (scale up) consiste à migrer les données vers des supports de stockage de plus grandes capacités, avant que la capacité du système de stockage ne soit atteinte. Cette approche n’est ni flexible (limite de la taille des ressources) ni économique (requiert d’acheter du matériel récent). Notre second problème consiste alors à mettre en place un système de stockage capable de gérer dynamiquement les ressources de stockage.
Les systèmes de stockage sont sujets à des défaillances inévitables. Ces défaillances entraînent l’inaccessibilité temporaire, voire la perte définitive, de blocs de données [For+10]. En particulier, la probabilité d’apparition des pannes augmente avec la taille du système de stockage (e.g. défaillance d’un disque, défaillance réseau). Il est donc nécessaire d’intégrer de la redondance dans le système de stockage. La solution classique pour supporter ces pannes consiste à exploiter la nature des NDSS en distribuant plusieurs copies des blocs de données sur des supports de stockage différents. Cette méthode permet d’accéder à la copie d’un bloc lorsque les autres ne sont pas disponibles. Bien que simple à mettre en œuvre, chaque copie générée ajoute un surcout de redondance de 100%. Cette méthode implique alors un coût de stockage important. Notre troisième problème consiste à garantir un seuil de redondance permettant au NDSS de supporter les pannes, tout en minimisant cette quantité de redondance. Une fois qu’un seuil de redondance est mis en place dans le NDSS, certaines pannes entraînent une perte de données qui se traduit par une réduction de la quantité de redondance. Notre quatrième problème sera de déterminer un moyen efficace afin de rétablir et maintenir un seuil de redondance. Pour résumer, les quatre problèmes identifiés dans cette section visent à concevoir un NDSS capable:
1. d’être capable de délivrer de très hauts débits de lecture et d’écriture ;
2. d’adapter dynamiquement ses ressources de stockage ;
3. d’être tolérant aux pannes, tout en minimisant la quantité de redondance ;
4. de maintenir cette redondance dans le temps.
Codes à effacement en géométrie discrète
Principe et évaluation des codes à effacement
Les systèmes de communication numérique permettent de faire transiter l’information d’un émetteur vers un destinataire à travers un canal de communication. On considère qu’une transmission est fiable lorsque le destinataire accède à l’information en un temps acceptable. Pour cela, il est souvent nécessaire d’améliorer les débits. Le schéma classique d’une telle transmission repose sur deux étapes. La première consiste à compresser l’information afin d’améliorer les débits. Pour cela, la redondance dans l’information est supprimée (codage source). En revanche, sans ces données de redondance, le message est particulièrement sensible au bruit présent sur le canal. Afin de tolérer une dégradation de l’information, la seconde étape consiste à rajouter de la redondance (codage canal). Apparaissant comme une alternative au codage conjoint source/canal [DR97], ce schéma, engendré par le « théorème de séparation », introduit par Shannon dans les années 1950, considère chaque étape d’encodage indépendamment. Dans ce travail de thèse, nous nous intéresserons uniquement au codage canal. En particulier, nous nous focaliserons sur les dégradations qui engendrent la perte d’une partie de l’information (appelé « effacement »). Nous verrons précisément en quoi la correction d’effacements se distingue de la correction des valeurs des données reçues.
Théorie algébrique des codes correcteurs
Cette section présente une étude des codes linéaires par blocs à travers une approche algébrique. Une définition des opérations d’encodage et de décodage sera présentée, ainsi que la notion fondamentale de la distance de Hamming [Ham50]. Cette notion fondamentale de la théorie des codes permet de déterminer la capacité de correction d’un code.
Codes par blocs
Jusque là, nous avons étudié le transfert d’information bit à bit. En pratique, on souhaite transférer un flux d’information de taille conséquente. Pour travailler efficacement sur ce flux d’information, il est préférable de le segmenter en éléments de taille fixe. Ces éléments sont appelés « mots » (ou encore blocs ou paquets). Les mots de code sont le résultat d’une opération d’encodage utilisant des mots d’information en entrée. Dans la suite, nous définirons ce qu’est l’encodage, le décodage, le rendement d’un code, ainsi que la distance de Hamming.
Encodage Pour un code correcteur (n, k), l’encodage correspond à une application injective φ : Ak → An , où A est un alphabet (dans le cas du canal binaire, A = {0, 1}) et où k ≤ n. En particulier, on appelle k la dimension du code, et n sa longueur. L’ensemble Cφ = {φ(s) : s ∈ Ak} correspond au code (n, k) dont les éléments sont des mots de code. Les corps finis correspondent à des structures discrètes adaptées aux applications de codage. Lors d’une transmission, les valeurs de n et k sont définies en fonction de la capacité du canal. Les mots de code ainsi calculés sont transmis sur le canal en direction du destinataire.
Décodage Le décodage consiste à vérifier si les mots reçus appartiennent à Cφ. Si ce n’est pas le cas, deux stratégies sont possibles pour corriger l’erreur :
1. Le récepteur peut demander à la source de réémettre le message. Cette stratégie appelée Automatic Repeat reQuest (ARQ), n’est pas toujours possible (certains médias ne disposent pas de canal de retour). De plus elle entraîne un délai significatif ; 2. L’émetteur ajoute a priori de l’information de redondance afin que le destinataire puisse reconstituer l’information en cas de perte. C’est cette stratégie, appelée Forward Erasure Code (FEC), qui sera principalement étudiée dans cette thèse.
Dans le deuxième cas, s’il existe un entier i et un unique mot de code ayant au moins n − i bits égaux au mot reçu, alors on corrige le mot reçu par ce mot. Sinon, on ne peut pas corriger l’erreur.
Codes linéaires
Dans le cas où l’application φ est linéaire, on dit que le code (n, k) est linéaire. L’avantage des codes linéaires est que les opérations de codage et de décodage sont réalisées en temps polynomial sur n. Il faut alors munir A d’une structure vectorielle. En particulier les corps finis F correspondent à des ensembles adaptés pour l’étude des codes. Dans la suite de cette section, nous verrons l’application d’encodage, les propriétés MDS et systématique du code, ainsi que la matrice de parité et le décodage.
|
Table des matières
Introduction générale
Contexte
Problèmes du stockage distribué identifiés
Notre approche
Contributions
Plan du manuscrit
Contexte de la thèse
1 Principe et évaluation des codes à effacement
Introduction du chapitre
1.1 Notions de théorie des codes
1.1.1 Théorie mathématique de l’information
1.1.2 Exemples de canaux
1.1.3 Théorie algébrique des codes correcteurs
1.2 Codage à effacement
1.2.1 Codage par paquets sur la couche applicative
1.2.2 Principe des codes à effacement
1.2.3 Distinction entre les différents codes
1.3 Exemples de codes à effacement
1.3.1 Les codes de répétition
1.3.2 Les codes de parité
1.3.3 Les codes de Reed-Solomon
1.3.4 Les codes LDPC
Conclusion du chapitre
2 Conception de codes à effacement en géométrie discrète
Introduction du chapitre
2.1 Discrétisation de la transformation de Radon continue
2.1.1 Transformation de Radon dans le domaine continu
2.1.2 Quelques bases de la géométrie discrète
2.1.3 Méthode algébrique de reconstruction d’une image discrète
2.2 Code MDS par transformation de Radon finie
2.2.1 Transformation de Radon finie
2.2.2 Représentation partielle et fantôme discret
2.2.3 Code à effacement par transformation de Radon finie
2.2.4 Relations avec d’autres codes MDS
2.3 Code à effacement par transformation Mojette
2.3.1 Transformation Dirac-Mojette directe
2.3.2 Reconstruction par transformation Mojette
2.3.3 Code à effacement Mojette
Conclusion du chapitre
3 Code à effacement Mojette systématique
Introduction du chapitre
3.1 Conception du code à effacement Mojette systématique
3.1.1 Construction du code systématique
3.1.2 Algorithme de reconstruction
3.2 Évaluation du gain dans le rendement du code
3.2.1 Réduction de la redondance en systématique
3.2.2 Coût de la redondance par rapport à d’autres codes
3.3 Considérations sur la réduction du nombre d’opérations
3.3.1 Contraintes en performances des codes à effacement
3.3.2 Bénéfices de cette nouvelle technique sur l’encodage
3.3.3 Bénéfice de cette technique sur le décodage
Conclusion du chapitre
Conclusion générale
