Persistance et disponibilite dans les systemes repartis : application a Guide

Support de la persistance

   La notion de persistance est fournie dans les langages de programmation pour unifier l’utilisation des données persistantes et temporaires [Atkinson 87]. Elle a été introduite d’abord dans les langages fonctionnels et notamment LISP, puis dans les langages de programmation de bases de données, tels que Pascal/R [Schmidt 77] et PS−Algol [Atkinson 83]. Il existe plusieurs manières de rendre visible la persistance au niveau des langages de programmation : dans les langages Trellis/Owl et Eiffel, elle est fournie comme un trait rajouté du langage d’origine ; dans le langage Guide, un objet est persistant dès lors qu’il existe un chemin d’accès menant à lui depuis un des objets appelés racines de persistance. On peut remarquer que cette technique est actuellement l’une des plus reconnue. Dans tous les cas de figure, l’implantation de ce type de langages nécessite l’utilisation d’un support de la persistance. Ce support peut être basé soit sur le système de fichiers fourni par le système d’exploitation, soit sur un système de gestion de bases de données, soit sur un système de gestion d’objets persistants [Cockshot 84]. Ces systèmes de gestion associent de façon très fine la notion de persistance à celle d’objets. Le système offre ainsi des fonctions de stockage de haut niveau sémantique, c’est à dire dans lesquelles la notion d’objet est connue, avec comme corollaire la prise en compte au niveau du système de stockage des problèmes de désignation et de partage relatifs aux objets. L’objet est alors l’unité de persistance et de partage [Hosking 93], ce qui permet de coller idéalement au langage. L’inconvénient majeur de cette solution est qu’elle impose l’objet comme unité de transfert entre la mémoire de travail et celle de stockage. Or l’expérience, acquise avec le langage Guide [Freyssinet 91], a montré que la taille moyenne des objets était inférieure à 500 octets, ce qui est petit relativement à la taille des pages (en général 4 Ko). De plus, un chargement objet par objet risque de mal convenir aux applications visées qui utilisent couramment des milliers sinon des millions d’objets [Cahill 93]. Le coût d’une lecture objet par objet deviendrait vite prohibitif. C’est pourquoi, des études sur le regroupement d’objets dans des conteneurs, de façon à réduire le nombre des transferts entre la mémoire et le disque ont été menées [Benzaken 90][Deppish 91]. Des solutions basées sur le couplage de l’espace de stockage dans la mémoire virtuelle des processus ont été proposées [Millard 93] [Shekita 90]. Le gros avantage de ce type de solution, est qu’il permet de découpler l’unité d’accès à l’information de l’unité de transfert entre la mémoire et les disques. On accède aux objets de manière uniforme et on transfère des pages. On peut ainsi clairement séparer la gestion de l’accès aux objets de celle de leur persistance. La solution que nous avons choisie pour le support des objets persistants des langages Guide et d’une version étendue de C++ intégrant la persistance et la distribution, s’appuie sur la définition d’une machine de stockage de bas niveau sémantique [Chevalier 94c]. L’approche retenue est celle du conteneur de stockage non typé et non structuré, appelé grappe. La sémantique interne d’une grappe est définie par une couche supérieure du système : la machine à objets qui gère l’accès aux objets (synchronisation et protection) [Hagimont 93]. L’accès à une grappe est réalisé par son couplage dans l’espace d’adressage des applications. La machine à grappe est mise en œuvre sur la machine de stockage pour laquelle la grappe est une simple suite de blocs. On peut caractériser notre proposition du support de la persistance pour les langages à objets par deux points forts :
• Un modèle de mémoire uniforme structuré autour de la notion de grappe,qui offre un support efficace pour le développement de la machine qui gère les objets.
• Une mise en œuvre répartie de ce support (par des gérants de mémoire(2)) qui permet de partager la charge associée entre un ensemble de machines. Le mécanisme de couplage, fourni par la machine à grappes, permet d’offrir à la machine à objets, une mémoire de grappes uniforme au sens de Multics [Organick 72]. La machine de stockage fournit une interface suffisamment générale pour permettre la mise en œuvre du stockage des grappes par utilisation de serveurs de stockage externes à la plate−forme Guide.

La persistance dans les systèmes de gestion de fichiers

   Nous allons tout d’abord faire un bref rappel sur la mise en œuvre de la persistance dans les systèmes de gestion de fichiers (SGF) fournis par les systèmes d’exploitation classiques. Un SGF assure trois fonctions : il permet la conservation des données sous la forme de fichiers (c’est à dire, un ensemble contigu ou non d’octets), il fournit une fonction de désignation des fichiers afin que les utilisateurs puissent les manipuler au travers de noms symboliques et enfin il fournit une fonction de protection entre les utilisateurs. Au niveau du traitement de la persistance des données (de leur conservation sous forme de fichier), les environnements classiquement bâtis au−dessus des SGF (comme l’environnement C/C++) souffrent de deux défauts majeurs :
• L’appel aux fonctions de conservation, que se soit pour l’écriture ou la lecture, est explicite. Le programmeur d’applications doit donc gérer les transferts entre la mémoire de ses applications et les disques de conservation.
• L’unité d’échange entre la mémoire de travail et la mémoire de stockage n’est pas le fichier mais l’enregistrement ou le bloc d’enregistrements (c.a.d. une chaîne de caractères quelconques). Il est donc nécessaire de convertir la représentation des données en mémoire virtuelle, en une représentation différente propre à être conservée. Le système introduit une dichotomie, au niveau des traitements, entre les données temporaires et les données persistantes. Des efforts ont été entrepris depuis une dizaine d’années pour atténuer, voire éliminer les contraintes dues à la persistance classique. C’est ainsi qu’a été introduite au début des années 80, la notion de programmation persistante. L’idée de base consiste à associer aux données la propriété d’être persistantes et de laisser le système mettre en œuvre cette propriété de manière automatique. De plus, le système essaye de conserver la même représentation des données en mémoire virtuelle qu’en espace de conservation éliminant par la même les conversions d’une représentation dans l’autre. La mise en œuvre de ces différentes idées suppose que le système d’exploitation offre un support approprié. Dans la section suivante, nous allons donc étudier les problèmes liés à ce support.

Support d’un modèle de mémoire persistante

   Le but de la présente section est d’évaluer les incidences du modèle de mémoire persistante sur la mise en œuvre de la persistance dans un système réparti et d’identifier notamment les principales caractéristiques d’un tel support. Dans cette optique, une étude de cas sur différents systèmes support de persistance est proposée dans la section II.4. L’influence de la répartition sur la gestion de la persistance concerne principalement trois aspects :
• La désignation qui englobe les problèmes d’identification des objets, ainsi que ceux relatifs à leur accès. Le système doit être capable de retrouver les objets conservés mais aussi de gérer les accès aux objets composites (ensemble ou groupe d’objets).
• Le partage qui regroupe la gestion de la concurrence d’accès et le maintien de la cohérence des données en mémoire virtuelle. La gestion du partage, notamment en mémoire virtuelle, est ce qui différencie le plus un système support de persistance d’un SGF classique.
• La conservation qui doit garantir l’intégrité des données en espace de conservation, prenant notamment en compte les problèmes de reprise après panne. A ce niveau, on attend du support de la persistance qu’il offre une qualité de service proche de celle fournie par les systèmes de gestion de base de données.

Le système Clouds

   Clouds [Dasgupta 90] est un projet de recherche du Georgia Institute of Technology dont le but est la réalisation d’un système distribué à base d’objets. Deux des principaux domaines explorés sont la tolérance aux fautes et la reconfiguration dynamique. Le système Clouds est réalisé au dessus du noyau Ra sur un ensemble de stations Sun 3/60 reliées par un réseau Ethernet. Ra [Bernabeu 88] est un noyau minimal, développé par la même équipe que Clouds, qui fournit les outils nécessaires pour la réalisation de systèmes d’exploitation distribués. Clouds définit deux concepts :
• L’objet est conceptuellement vu comme un espace virtuel d’adressage persistant(2). L’objet est une entité passive dont la durée de vie est indépendante de la durée de vie de tout flot d’exécution. Il survit aux arrêts et aux pannes du système. Sa destruction est explicite.
• Le flot d’exécution (ou « thread ») est l’entité active du système. Il peut être vu comme un processus léger qui s’exécute dans les espaces virtuels d’adressage constitués par les objets sur lesquels il exécute des méthodes. (2) Notons que Clouds gère aussi des objets temporaires. Un flot peut ainsi « traverser » plusieurs objets. Plusieurs flots peuvent s’exécuter concurremment dans un même objet, la synchronisation de base est associée aux opérations de l’objet.
Désignation et localisation Les objets sont désignés par des identificateurs universels (sysname). Les sysnames sont des identificateurs logiques ne contenant aucune information de localisation physique. La localisation d’un objet se fait d’abord par recherche dans des tables locales à la machine courante. Puis par la consultation des disques locaux. Enfin, en cas d’échec, le système diffuse la demande de localisation à l’ensemble des machines.
Partage Chaque objet est représenté par un espace d’adressage partagé distinct. Le partage d’objet est réalisé par partage de l’espace d’adressage qui le constitue par les différents flots d’exécution. Dans la pratique, un espace d’adressage vu par un flot d’exécution est constitué de trois régions : la O−région dans laquelle se trouve l’objet proprement dit, la P−région dans laquelle se trouve la pile du flot d’exécution et la K−région utilisée par le noyau. L’appel de méthode sur un objet O2 depuis un objet O1 provoque la désinstallation de l’objet courant O1 de la O−région, l’installation de O2 dans la O−région. Puis une fois l’invocation terminée, la réinstallation de O1.
Stockage La mise en œuvre de la persistance des objets est assurée par le noyau au travers de segments. Le segment est un bloc non−typé et contigu de mémoire (le noyau n’associe aucune sémantique quant au contenu du segment). Un objet est réalisé par un ou plusieurs segments ; en général, un segment de code et un segment de données. Le segment permet au noyau d’accéder directement aux pages des objets (par exemple, pour pouvoir les paginer) au travers des mécanismes de gestion de la mémoire virtuelle. Les segments sont créés de manière explicite ; ils persistent jusqu’à leur destruction, elle aussi explicite. Les segments sont désignés par un nom global unique. La localisation d’un segment, similaire à celle d’un objet, se fait par recherche dans la table locale des segments actifs (en cours d’utilisation), puis par diffusion de la demande. Les segments sont gérés par des serveurs de partitions. Une partition est une entité active responsable de la gestion d’un ensemble de segments dans l’espace de conservation. Le noyau lui réclame les segments lorsque cela est nécessaire (installation d’un segment), puis les libère lorsqu’ils ne sont plus utilisés. Le noyau accède donc aux segments au travers de l’interface des partitions. Cette interface de bas niveau offre des fonctions de création, destruction, extension et installation ainsi que des fonctions permettant le chargement/déchargement (« page in/out ») des pages de segments. Notons que les segments et les partitions de Clouds sont des concepts respectivement proches des objets mémoires et des paginateurs externes du micro−noyau Mach (cf sous−section III.3.3). Le stockage des segments est réalisé en utilisant le système de fichier Unix. Chaque segment est stocké dans un fichier Unix. Le serveur de partition responsable du segment fournit les pages de ce segment au noyau Ra à travers le réseau. Ce mécanisme est rendu transparent au noyau grâce à l’interposition d’un client de partition sur la machine du noyau (cf Fig. 2.2).
Protection La protection dans Clouds est réalisée par isolation des objets. Chaque objet est représenté par un espace d’adressage distinct dans la mesure où le système ne place qu’un seul objet à un instant donné dans une O−région. On peut considérer qu’un flot d’exécution traverse les espaces d’adressage des objets qu’il invoque au cours de son exécution. La protection entre utilisateurs ou applications est basée sur l’utilisation de capacités. Vu d’un utilisateur, un objet est identifié par une capacité qui contient l’identificateur de l’objet ainsi que des droits d’accès. Le propriétaire d’un objet peut contrôler la diffusion de la capacité associée à son objet vers les autres utilisateurs.

Table des matières

Chapitre I Introduction
I.1 Support de la persistance 
I.2 Stockage fiable 
I.3 Organisation du mémoire 
Chapitre II Support de la persistance
II.1 La persistance dans les systèmes de gestion de fichiers
II.2 Modèle de persistance 
II.3 Support d’un modèle de mémoire persistante 
II.3.1 La désignation
II.3.2 Le partage
II.3.3 Le stockage
II.3.4 La protection
II.4 Présentation de différents systèmes 
II.4.1 Le système Clouds
II.4.2 Le Distributed Shared Repository
II.4.3 Le gestionnaire de persistance Cricket
II.4.4 Le système O2
II.4.5 Tableau récapitulatif
II.5 Conclusion 
Chapitre III L’environnement Guide
III.1 Introduction au système Guide 
III.1.1 La machine virtuelle Guide
III.1.2 Le modèle de données
III.1.3 Le modèle d’exécution
III.1.4 Le modèle de mémoire
III.1.5 Protection et sécurité
III.1.6 Les services du système Guide
III.2 Architecture générale 
III.2.1 Machine à objets
III.2.2 Machine à segments
III.2.3 Machine à grappes
III.2.4 Service de stockage
III.2.5 Machine d’exécution
III.3 Quelques caractéristiques de Mach 3.0 
III.3.1 Les tâches et les flots de contrôles
III.3.2 Les communications
III.3.3 La gestion de la mémoire virtuelle
III.4 Conclusion 
Chapitre IV Le support de la persistance dans Guide
IV.1 Architecture générale
IV.1.1 Gestion de grappes en mémoire d’exécution
IV.1.1.1 Organisation générale
IV.1.1.2 Désignation et localisation des grappes en mémoire d’exécution
IV.1.1.3 Protection
IV.1.1.4 Partage
IV.1.1.5 Gestion dynamique de la taille des grappes
IV.1.1.6 Interface
IV.1.2 Gestion de grappes en mémoire de stockage
IV.1.2.1 Organisation générale
IV.1.2.2 Concepts
IV.1.2.3 Désignation et localisation
IV.1.2.4 Conservation et intégrité
IV.1.2.5 Interface
IV.2 Mise en œuvre
IV.2.1 Architecture
IV.2.2 Gestion de la pagination
IV.2.3 La journalisation
IV.2.3.1 Algorithme
IV.2.3.2 Limitations
IV.2.3.3 Élimination des anciens journaux
IV.3 Conclusion
Chapitre V Evaluation du support de la persistance
V.1 Évaluation qualitative
V.1.1 Support des grappes temporaires
V.1.2 Conclusion
V.2 Évaluation quantitative 
V.2.1 Instrumentation
V.2.2 Fonctions de la machine à grappes
V.2.3 Pagination locale et pagination à distance
V.2.4 Impact de la journalisation sur le service de stockage
V.2.5 Conclusion
V.3 Support du micro−noyau 
V.4 Conclusion
Chapitre VI Vers une fiabilité accrue
VI.1 Concepts de base et terminologie 
VI.2 De la duplication appliquée au stockage des données 
VI.2.1 La cohérence des copies
VI.2.2 Gestion de la cohérence
VI.3 Mise en œuvre de la duplication des données
VI.3.1 Algorithmes pessimistes
VI.3.1.1 Le quorum
VI.3.2 Algorithmes optimistes
VI.3.2.1 L’anti−entropie estampillée
VI.4 Application au stockage fiable 
VI.4.1 Coda
VI.4.2 Echo
VI.4.2.1 La gestion des caches dans Echo
VI.4.2.2 La tolérance aux pannes dans Echo
VI.4.3 Comparaison
VI.5 Conclusion
Chapitre VII Pour un stockage fiable dans le système Guide−2
VII.1 Un prototype pour le système Guide−1
VII.1.1 Architecture
VII.1.2 Fonctions principales
VII.1.2.1 Cohérence
VII.1.2.2 Verrouillage des objets et invalidation
VII.1.2.3 Localisation des objets
VII.1.3 Évaluation
VII.2 De Guide−1 à Guide−2 
VII.3 Un serveur de stockage fiable pour Guide−2 
VII.3.1 Architecture
VII.3.2 Fonctions principales
VII.3.3 Traitement de la panne d’un gérant de mémoire
VII.3.4 Restauration d’un serveur de secours
VII.3.5 Opérations en mode déconnecté
VII.3.6 Évaluation
VII.4 Conclusion 
Chapitre VIII Conclusion
VIII.1 Contribution 
VIII.2 Évolution du domaine
VIII.2.1 Évolution des besoins
VIII.2.2 Évolution des techniques
VIII.3 Perspectives
VIII.3.1 Expérimentations
VIII.3.2 Plate−forme

Télécharger le rapport complet