Systèmes à quorums dynamiques et projet ViSaGe

Ivan Frain

Institut de Recherche en Informatique de Toulouse (IRIT)

Grenoble - 17/11/2006 2

Plan

Cohérence des réplicas et systèmes à quorums Problème de la charge des noeuds Protocoles de reconfiguration de systèmes à

quorums Un cadre de construction Prise en compte de la charge des nœuds de

stockage Prise en compte de la latence réseau

ViSaGe : intergiciel de stockage pour grille Architecture logicielle Carnet de route

Conclusion et Perspectives

Grenoble - 17/11/2006 3

Problème de la cohérence

Copie de Paul

Copie de Jeanne

Jeanne

Paul

Ecrire

Ecrire

Lire

Lire

Règle: chacun lit et écrit sa copie locale

Grenoble - 17/11/2006 4

Problème de la cohérencePremier exemple de solution : ROWA

Jeanne

Paul

Ecrire

Ecrire

Ecrire

Ecrire

Lire

Lire

Règle: chacun lit sa copie locale mais écrit toutes les copies

Grenoble - 17/11/2006 5

Jeanne

Paul

Ecrire

Ecrire

Nicolas

Problème de la cohérenceDeuxième exemple de solution : un système à quorums

Règle : chacun lit et écrit une majorité de copiesRemarque : ajout d’un numéro de version aux copies

Version

Version

VersionEcrire

Ecrire

Lire

Lire

0

0

0

1

1

2

2

1

Version ?

Version ?

Grenoble - 17/11/2006 6

Systèmes à quorums : définition

Quorum q - Ensemble minimum de copies impliquées dans une opération de lecture ou d’écriture afin que l’opération réussisse.

Coterie C - Ensemble des quorums possibles pour un groupe de copies et un protocole donné

≠∩:∈,∀ 2121 qqCqq

2121 :∈, qqCqq

Intersection :

Minimalité :

Grenoble - 17/11/2006 7

Systèmes à quorums : coterie en arbre

Nœuds organisés logiquement en arbre

Quorum = un chemin de la racine à une feuille = {P1,P2,P4}

Coterie = {{P1,P2,P4},{P1,P2,P5}, {P1,P3,P6},{P1,P3,P7}}

Protocole de Agrawal et Abbadi [1]

P2 P3

P4 P5 P6 P7

P1

Sur quel critère construire la coterie ? Les solutions existantes : latence réseau Notre solution : charge des noeuds

Grenoble - 17/11/2006 8

Charge d’une coterie : définition

):( jiPQ QPloadMaxij

Charge d’un Quorum :

iPload Charge d’un nœud :

CQQC

j

j Charge d’une Coterie :

Un nœud possédant une réplique : iP

Grenoble - 17/11/2006 9

Problème

Q

12

9 8 21

50

23

P2 P3

P4 P5 P6 P7

P1

23 15 50 50

138CQ

QC 4040

180

1540

Grenoble - 17/11/2006 10

Protocoles de reconfiguration de systèmes à quorums

Reconfiguration = changement de coterie

But : utiliser une coterie mieux adaptée à l’environnement

Un protocole de reconfiguration : Quand effectuer une reconfiguration?

Politique de récupération des informations Récupération à la demande Récupération périodique

Politique de déclenchement Déclenchement à la demande Déclenchement périodique

Comment effectuer une reconfiguration? Politique de reconfiguration

Grenoble - 17/11/2006 11

Trois protocoles de reconfiguration pour systèmes à quorums en arbre

Reconfiguration en fonction de la charge des nœuds

Protocole des permutations élémentaires Protocole de permutation globale

Reconfiguration en fonction de la charge et de la latence réseau

Protocole de permutation hybride

Grenoble - 17/11/2006 12

Protocole des permutations élémentaires (1/2)

Politique de reconfiguration Permuter deux nœuds parents si le père est plus chargé que le fils

Q

40

9

15

8 21

50

23

40 40 50 50

180C

Q 23 40 50 50

9

15

40 8 21

50

23

163C…

Q

8

15

40 50 21

9

23

23 40 50 21

134C

15

9

40 8 21

50

23

23 40 50 50

163C

Q

Grenoble - 17/11/2006 13

Protocole des permutations élémentaires (2/2)

Politique d’information à la demande Un des clients est choisit A chacune de ses opérations de lecture ou d’écriture (un quorum)

Politique de déclenchement à la demande Si une permutation élémentaire est possible dans le quorum

contacté lors d’une opération de lecture ou d’écriture

Problème Les nœuds les plus chargés se trouvent dans les feuilles

Q

8

15

40 50 21

9

23

23 40 50 21

134C

Q

8

21

40 50 15

9

23

23 40 50 15

128C

Grenoble - 17/11/2006 14

Protocole de permutation globale

Politique de reconfiguration agréger les noeuds les plus chargés dans le même sous arbre

Q

8

15

40 50 21

9

23

23 40 50 21

134C

Q

8

23

40 21 15

9

50

50 40 21 15

126C

Politique d’information périodique

Politique de déclenchement périodique

Grenoble - 17/11/2006 15

Prise en compte de la latence réseauTemps de réponse d’une coterie

):()( , kjPPkP QPMaxQjii

Temps de réponse d’un quorum vis-à-vis d’un noeud Pi :

)(*2, jPPPP Platloadijji

Temps de réponse d’un nœud Pj vis-à-vis d’un autre nœud Pi :

CQ

kPP

k

iiQC )()(

Temps de réponse d’une coterie vis-à-vis d’un nœud Pi :

Grenoble - 17/11/2006 16

Le problèmeP1 P2 P3 P4 P5 P6 P7

80 20 90 40 110 50 30

Grenoble - 17/11/2006 17

Protocole de permutation hybride

Politique d’information périodique Récupération de la latence la première fois Récupération des charges les autres fois

Politique de déclenchement périodique

Pj P1 P2 P3 P4 P5 P6 P7

180 120 290 240 310 50 30

80 20 190 140 210 150 130

180 120 90 40 110 250 230

Médiane 180 120 190 140 210 150 130

Politique de reconfiguration Permutation globale avec temps de réponse médians

jA Pclient ,

jA Pclient ,

jA Pclient ,

Grenoble - 17/11/2006 18

Évaluation des protocoles de reconfiguration

Algorithme de Shvartsman et Lynch Plusieurs lecteurs et plusieurs rédacteurs Supporte la reconfiguration dynamique de coterie

Propriété d’intersection entre deux coteries

Implémentation dans le simulateur Neko de Urban, Défago et Schiper

La grille simulée utilise 7, 15, 31, 63 et 127 réplicas (nœuds) La charge d’un nœud n’évolue pas trop vite Les nœuds ne sont pas dédiés au système de stockage 3 contextes de simulation :

La latence au niveau des serveurs est dominante (contexte LS) La latence réseau est dominante (contexte LR) Les latences serveur et réseau sont équivalentes (contexte LEQ)

Temps de simulation fixe

Grenoble - 17/11/2006 19

Sans reconfiguration avec 7 noeuds

Contexte LS Contexte LEQ

Contexte LR

Grenoble - 17/11/2006 20

Protocole des permutations élémentairesContexte LS et 7 réplicas

Sans reconfiguration Protocole des permutations élémentaires

Grenoble - 17/11/2006 21

Protocole de permutation globaleContexte LS et 31 réplicas

Sans reconfiguration Protocole de permutation globalePériode = 200K

Grenoble - 17/11/2006 22

Protocole de permutation hybrideContexte LEQ et 63 réplicas

Sans reconfiguration Protocole de permutation hybridePériode = 200K

Grenoble - 17/11/2006 23

Synthèse des résultats

ContexteNœuds

LS LR LEQ

7 Elem Sans Hybride 100K

15 Elem Sans Hybride 300K

31 Globale 200K Hybride 300K Hybride 100K

63 Sans Hybride 400K Hybride 200K

127 Sans Sans Hybride 300K

Calcul du débit d’opérations (throughput) pour un temps de simulation fixé

Grenoble - 17/11/2006 24

Grenoble - 17/11/2006 25

Architecture physique d’une grille

Grenoble - 17/11/2006 26

Composants logiciels de ViSaGe

Fabrique

Communication

Virtualisation

Système de gestion de fichiersConcurrence

et

Cohérence

Administration

Et

Monitoring

Application

Grenoble - 17/11/2006 27

ViSaGe : carnet de route

0 2417 21

1. Expression des besoins

2. Architecture et Design

3.1 Prototypage

3.2 Développement

4. Gridification

5. Tests in situ

2 4

Prototypage

Développement

Gridification

Tests

8

février 2005 mars 2007

Aujourd’hui

Grenoble - 17/11/2006 28

Conclusion

Protocoles de reconfiguration : Définition de la charge et du temps de réponse d’une

coterie Variation de la charge des nœuds est un problème Protocoles de reconfiguration

Permutations élémentaires Permutation globale Permutation hybride

Amélioration du débit d’opération sous certaines conditions

Projet ViSaGe : Proposition d’un nouvel intergiciel dédié a stockage de

données sur grille : ViSaGe Interface fichier fournissant une certaine qualité de service Différentes méthodes de gestion de la cohérence

Grenoble - 17/11/2006 29

Perspectives

Protocoles de reconfiguration : Preuve de l’algorithme des permutations globales Comparaison avec un plus grand nombre de systèmes à

quorums : grilles, hiérarchique… Évaluation en environnement réel : projet ViSaGe

Quels sont les critères de charges à prendre en compte ? Identification de seuils pour effectuer une reconfiguration Historique de l’état des nœuds…

Projet ViSaGe : Terminer l’intégration et les tests Mars 2007 Déploiement et tests sur Grid 5000 Tester avec d’autres applications … des partenariats? ViSaGe comme stockage pour une BD distribuée

Grenoble - 17/11/2006 30

Références

Protocoles de reconfiguration :[1] I. Frain, R. Basmadjian, J-P. Bahsoun and A. M’zoughi. How to

improve the scalability of read/write operations with dynamic reconfiguration of a tree-structured coterie. In ICPP’06 workshops, pages 123-134, August 2006.

[2] I. Frain, A. M’zoughi and J-P. Bahsoun. How to achieve high throughput with dynamic tree-structured coterie. In the 5th International Symposium on Parallel and Distributed Computing (ISPDC’06), July 2006.

Projet ViSaGe :[3] F.Thiebolt, I.Frain et A. M’zoughi. Virtualisation du stockage dans les

grilles informatiques. Dans les 16ème rencontres francophones de parallèlisme, (Renpar’05), avril 2005.

[4] http://www.irit.fr/visage

Grenoble - 17/11/2006 31

Opération de lecture ou d’écriture

Grenoble - 17/11/2006 32

Opération de reconfiguration

Grenoble - 17/11/2006 33

Protocole de permutation élémentaire

Grenoble - 17/11/2006 34

Protocoles de permutation globale et de permutation hybride

Grenoble - 17/11/2006 35

Permutation élémentaire :éléments de preuve

Grenoble - 17/11/2006 36

La place de ViSaGe au sein des intergiciels existants

Grenoble - 17/11/2006 37

Contexte : les grappes de grappes

Grappe de grappes Réplication de données entre sites distants Charge des nœuds de stockage et latence réseau

GRILLE(WAN)

GRILLE(WAN)

S2

S1

S3S4

S5

Client

Légende

Un réplica

Grenoble - 17/11/2006 38

Composants logiciels de ViSaGe

ViSaGe est découpé en 5 composants principaux vcom : un système de communication entre composants vrt : un composant de virtualisation des ressources de

stockage visagefs : un système de gestion de fichiers au niveau grille vccc : une librairie de gestion de la concurrence des accès et

de gestion de la cohérence des réplicas vam : service d’administration et de monitoring de ViSaGe

Un module d’administration Un module de monitoring

Les composants sont déployés à tous les niveaux de la grille:

Hôtes frontaux Hôtes contrôleurs Nœuds de calcul et de stockage

Grenoble - 17/11/2006 39

Gestion de la cohérence dans ViSaGe :le composant vccc