THÈSE

NumØro d’ordre : 3462 TH¨SE prØsentØe devant L’UNIVERSIT DE RENNES 1 pour obtenir le grade de DOCTEUR DE L’UNIVERSIT DE RENNES 1 Mention INFORMATIQUE PAR Monsieur SØbastien Monnet quipe d’accueil : projet PARIS, IRISA, Rennes cole doctorale MATISSE Composante universitaire : IFSIC Gestion des donnØes dans les grilles de calcul : support pour la tolØrance aux fautes et la cohØrence des donnØes. soutenue le 30 novembre 2006 devant la commission d’examen Composition du jury Monsieur Gabriel ANTONIU, chargØ de recherche, INRIA directeur de thŁse Roberto BALDONI, professeur, Universit di Roma examinateur Monsieur Luc BOUG , professeur, ENS Cachan/Antenne de Bretagne directeur de thŁse FrØdØric DESPREZ, directeur de recherche, INRIA rapporteur Monsieur Philippe PUCHERAL, Professeur, UniversitØ de Versailles examinateur Pierre SENS, professeur, UniversitØ Paris 6Remerciements Trois ans c’est long, mais c’est Øgalement horriblement court ! Je souhaite ici remercier ceux qui m’ont aidØ, soutenu, supportØ. . . Je remercie tout d’abord les six membres de mon jury pour avoir relu et ØvaluØ mon travail ainsi que pour leurs questions lors de la soutenance. Je remercie en particulier Pierre et FrØdØric qui ont eu la patience de lire mon manuscrit, de rØdiger des rapports dØtaillØs et de faire des remarques qui m’ont permis d’amØliorer ce document. Je souhaite Øgalement remercier Thierry pour son accueil au sein de l’Øquipe PARIS dont je remercie au passage tous les membres qui en font une Øquipe dynamique et sympathique. Un grand merci mes directeurs de thŁse Luc et Gabriel. Gabriel merci d’avoir cru en moi dŁs le dØbut et d’avoir pris le temps de m’expliquer... J’ai beaucoup appris tes c tØs. Luc merci de m’avoir fait dØcouvrir les plaisirs du travail bien fait. Je tiens Øgalement te remercier pour ton Øcoute et pour tous les conseils que tu m’as donnØs sur bien des sujets. . . J’ai eu la chance de faire ma thŁse au sein de l’IRISA. Je voudrais remercier toutes les personnes qui en font un environnement de travail exceptionnel ! En particulier, Christiane et lodie du service mission qui nous permettent de voyager l’esprit tranquille, merci lodie de m’avoir sorti du pØtrin quand j’Øtais Chicago en 2004 ! Merci Maryse de t’occuper de nous comme tu le fais. Je souhaite aussi remercier Christine Morin, Anne-Marie Kermarrec, Pierre Sens, Marin Bertier, Etienne RiviŁre, Christian Perez, Yvon Jegou, Fran oiseAndrØ, Indy Gupta, CØcile Le Pape, Landry Breuil, Lo cCudennec et Øvidemment toi Mathieu ! Je vous remercie pour toute l’aide que vous m’avez apportØe, pour nos discussions, vos relectures et commentaires. . . La liste est longue ! Je remercie Øgalement tous mes amis d’avoir compris qu’une thŁse c’Øtait une passion et demandait beaucoup de disponibilitØ. Je pense en particulier Nathalie, Joris et Lise-Marie. Ces remerciements vont Øgalement ma famille, en toi Sophie, merci pour tous tes petits messages d’encouragement sur la n, cela m’a vraiment aidØ... Mathieu, tu m’as dit lorsque j’ai commencØ ma thŁse : je suis content que tu fasses ta thŁse avec nous . De mon c tØ, je suis ravi d’avoir fait ma thŁse tes c tØs, tes qualitØs font de toi un bon collŁgue, mais aussi plus que a;-). Un merci tout particulier pour Caroline. Merci simplement d’Œtre l , de m’avoir soutenu, encouragØ, aidØ. Merci pour tes relectures bien sßr, mais surtout merci d’avoir acceptØ d’Œtre ma femme ! En n je remercie mes parents. Claude, tu as toujours ØtØ l pour nous, j’ai toujours su que je pouvais compter sur toi en toute occasion, merci, merci d’Œtre toi. Mon dernier remer- ciement, c’est pour toi Dominique. . .v Table des matiŁres Liste des dØ nitions ix 1 Introduction 1 1.1 Objectifs de la thŁse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Contributions et publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organisation du manuscrit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Partie I Contexte d’Øtude : gestion des donnØes dans les grilles de calcul 7 2 Les donnØes dans les grilles de calcul 9 2.1 Les grilles de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Historique et dØ nition . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Les fØdØrations de grappes . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.3 Un exemple de grille : Grid’5000 . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Les applications de couplage de codes . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Exemple d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.3 Les grilles de calcul : une solution pour les applications de couplage de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Approches pour le partage de donnØes dans les grilles . . . . . . . . . . . . . . 17 2.3.1 Le partage de donnØes dans les grilles de calcul . . . . . . . . . . . . . 17 2.3.2 SystŁmes existants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.3 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 ProblŁmes induits par la dynamicitØ de la grille . . . . . . . . . . . . . . . . . . 20 2.5 TolØrance aux fautes et gestion de la cohØrence dans les grilles . . . . . . . . . 21 3 Approches pour la gestion de la tolØrance aux fautes 23 3.1 Notion de faute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 DØfaillances, erreurs et fautes . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.2 Types de dØfaillance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1.3 Quel modŁle de fautes pour les grilles de calcul ? . . . . . . . . . . . . 26 3.1.4 Comment faire face aux fautes ? . . . . . . . . . . . . . . . . . . . . . . 28 3.2 DØtection de dØfaillances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28vi Table des matiŁres 3.2.1 Principes gØnØraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.2 Classi cation des dØtecteurs de dØfaillances . . . . . . . . . . . . . . . 29 3.2.3 Mise en uvr e de de . . . . . . . . . . . . . . . 30 3.2.4 Passage l’Øchelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Techniques de rØplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.1 Gestion des groupes de copies . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.2 Propagation des mises jour . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.3 Utilisation de groupes de copies . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Sauvegarde de points de reprise . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.4.1 Principe de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.2 Points de reprise coordonnØs . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.3 Points de reprise non-coordonnØs . . . . . . . . . . . . . . . . . . . . . 36 3.5 TolØrance aux fautes dans les grilles : vers une approche hiØrarchique . . . . . 37 4 Approches pour la gestion de la cohØrence de donnØes 39 4.1 ModŁles et protocoles de cohØrence dans les systŁmes mØmoire virtuelle- ment partagØe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.1 Notion de cohØrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.2 ModŁles de cohØrence forte . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1.3 de cohØrence rel chØe . . . . . . . . . . . . . . . . . . . . . . . 41 4.1.4 Approches pour la localisation des donnØes . . . . . . . . . . . . . . . 42 4.2 ModŁles et protocoles de cohØrence dans les systŁmes pair- -pair . . . . . . . 44 4.2.1 Les systŁmes pair- -pair . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.2 Approches pour la localisation des donnØes . . . . . . . . . . . . . . . 45 4.2.3 CohØrence des donnØes dans les systŁmes pair- -pair . . . . . . . . . . 46 4.3 ModŁles et protocoles de cohØrence dans les bases de donnØes . . . . . . . . . 48 4.3.1 ParticularitØ des donnØes . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.2 Notion de transaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.3 CohØrence de donnØes rØpliquØes : divergence et rØconciliation . . . . 50 4.4 CohØrence de donnØes dans les grilles : vers une approche hiØrarchique . . . 50 Partie II Notre contribution : une approche hiØrarchique conjointe pour la tolØrance aux fautes et la cohØrence des donnØes 53 5 tude de cas : vers un protocole de cohØrence des donnØes tolØrant aux fautes pour la grille 55 5.1 Le partage de donnØes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.2 Un exemple de protocole non tolØrant aux fautes . . . . . . . . . . . . . . . . . 57 5.2.1 Le modŁle de cohØrence l’entrØe . . . . . . . . . . . . . . . . . . . . . 57 5.2.2 Un protocole basØ sur une copie de rØfØrence . . . . . . . . . . . . . . . 58 5.2.3 Fonctionnement du protocole de cohØrence . . . . . . . . . . . . . . . . 58 5.3 Un protocole de cohØrence hiØrarchique . . . . . . . . . . . . . . . . . . . . . . 62 5.3.1 Limites d’un protocole plat . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.2 Solution : un pr hiØrarchique . . . . . . . . . . . . . . . . . . . . 62 5.4 Un protocole de cohØrence tolØrant aux fautes . . . . . . . . . . . . . . . . . . 65Table des matiŁres vii 5.4.1 NØcessitØ de tolØrer les fautes . . . . . . . . . . . . . . . . . . . . . . . . 65 5.4.2 Utilisation de techniques de rØplication . . . . . . . . . . . . . . . . . . 66 5.5 Vers un protocole hiØrarchique tolØrant aux fautes . . . . . . . . . . . . . . . . 68 6 Une approche conjointe 69 6.1 Cadre : le service de partage de donnØes JUXMEM . . . . . . . . . . . . . . . . 70 6.1.1 Notion de service de partage de donnØes pour la grille . . . . . . . . . 70 6.1.2 Architecture gØnØrale . . . . . . . . . . . . .