Gestion de données dans les grilles de calcul · 2014. 10. 4. · Grilles de calcul et partage de données Gestion de la cohérence et de la tolérance aux fautes Problème : la

Contexte et motivationsContributions

Mise en œuvre et évaluationConclusions et perspectives

Gestion de données dans les grilles de calcul:Support pour la tolérance aux fautes

et la cohérence des données

Sébastien Monnet

Projet PARIS/IRISAUniversité de Rennes 1

France

30 novembre 2006

Directeurs de thèse :Luc Bougé et Gabriel Antoniu



Grilles de calcul et partage de donnéesGestion de la cohérence et de la tolérance aux fautes

De nouveaux besoins

Simulations numériquesGrande précisionPhénomènes physiquescomplexes

Importants besoinsEfficacité d’interactionExploitation des résultatsPuissance de calculEspace de stockage

Thermodynamique Optique

Mécanique

X

1 / 43




Une solution : les grilles de calcul

Une puissance de calcul virtuellement infinieMutualisation de ressources (calcul, transport, stockage)Ressources distribuées dans différentes organisationsOrganisation virtuelle

Un cas particulier : lesfédérations de grappes

À grande échelle103 − 104 nœudsHétérogènesDynamiquesHiérarchiques

2 / 43




Problème : la gestion des données

BesoinsApplications distribuées sur plusieursnœudsDonnées partagées

Propriétés attenduesTransparence

Localisation, transfert, etc.Persistance

Dépendance de données entreplusieurs calculs

3 / 43




Systèmes existants

Limites : gestion explicite des données par les applicationsLocalisationCohérence des copies

Défi : gestion transparente du partage des données

4 / 43




Les systèmes à mémoire virtuellement partagée(MVP)

PropriétésAccès aux données uniforme via des identifiants globauxLocalisation et transfert transparentsModèles et protocoles de cohérence

5 / 43




Exemple de protocole de cohérence

Cohérence à l’entréeModèle relâchéAssociation explicite de verrous aux donnéesLectures parallèles

acquireacquire_read

Utilisation d’une copie de référence

acquire(data)write (data)release(data)

Client 1 Client 2Responsable

acqui_read

ack

acquire

ack

release

acquire_read(data)read(data)

6 / 43




Défis dans les grilles

Protocoles de cohérence conçus pour des architecturesStatiquesDe petite taille

Défi : intégrer de nouvelles hypothèses !Grande échelleNature dynamique

7 / 43




Premier défi : grande échelle

Rennes Orsay

NiceNoeud responsableClient (application)Copie de référence

Différence de latence d’un facteur 1000

8 / 43



Approche hiérarchiqueGestion conjointe

Solution : une approche hiérarchique

Rennes Orsay

NiceNoeud responsableClient (application)Copie de référence

Basé sur CLRC [LIP6] et H2BRC [IRISA]

9 / 43




Deuxième défi : nature dynamique

Hypothèses : fautes (crashs) et déconnexionsProblème : disponibilité des donnéesSolution : réplication

10 / 43






10 / 43






?

10 / 43




Solution : réplication des entités critiques

Solution utilisée pour fiabiliser de nombreux systèmesDARX [LIP6], HORUS [Cornell], LegionFS [U.Va], etc.

BesoinsNotion de groupe : composition de groupesCommunications de groupes : diffusion atomique

11 / 43







11 / 43







11 / 43




Notre approche : réplication hiérarchique

LDG LDG

LDG

LDG : Local Data Group

12 / 43





LDG LDG

LDG

LDG : Local Data Group

12 / 43





LDG LDG

LDG

LDG : Local Data GroupGDG : Global Data Group

12 / 43




Double intérêt de la réplication

Localité des accès aux donnéesCopies créées par le protocole de cohérence pouraméliorer les performances des accès

Disponibilité des donnéesCopies créées par les mécanismes de tolérance aux fautes

Deux types de copiesGestion intégrée

Faible nombre de copiesGrande complexité

Gestion disjointeGrand nombre de copiesTolérance aux fautes et cohérence gérées séparément

13 / 43




Une approche intermédiaire : gestion conjointe

Gestion découpléeCohérence des donnéesTolérance aux fautes

Avantages :Conception séparéeMultiples mises en œuvrepossiblesArchitecture multi-protocole

Gestion fine des interactionsCouche de jonction

Gestion de la tolérance aux fautes

Gestion de la cohérence des données

Couche de jonction

14 / 43




Gestion de la tolérance aux fautes

But : mise en place desgroupes de réplication

Mécanismes :Détection de fautesDiffusion atomiqueComposition de groupeAuto-organisation

Conservation dudegré de réplication

Détection de fautes

Diffusion atomique

Composition de groupe

Auto-organisation

15 / 43




Gestion de la cohérence des données

But : gestion de lacohérence des donnéesPropriétés :

Selon le modèle decohérence

Mise en œuvre d’unprotocole de cohérence

16 / 43




Couche de jonction

RôleOffrir des interfacesgénériquesConcentrer lesinteractions entre lescouches

Couche de jonction

Auto-organisation


Diffusion atomique


17 / 43




Une architecture logicielle multi-protocole

Couche de jonction

Auto-organisation


Diffusion atomique


18 / 43





Couche de jonction

Auto-organisation


Diffusion atomique


18 / 43





Couche de jonction

Auto-organisation


Diffusion atomique


18 / 43



CadreExempleMise en œuvreÉvaluation

Cadre de mise en œuvre : JUXMEM

Un service de partage de données pour la grilleDéveloppé au sein du projet PARIS à l’IRISA

Cadre : projet GDS de l’ACI Masse de DonnéesObjectifs

Partage de données transparentLocalisation, transfert, cohérence

Persistance de donnéesTolérance aux fautes

Une approche hybrideSystèmes pair-à-pairSystèmes à mémoire virtuellement partagéeSystèmes distribués tolérants aux fautes

19 / 43




JXTA - Sun Microsystems

Notion de pairNotion de groupe de pairsMécanismes de communication

Point-à-pointDiffusion

Notion d’annonceMécanismes depublication/recherche

Groupes JXTA différents des groupes de réplication

20 / 43




Architecture générale

Architecture physiqueArchitecture virtuelleGroupe JuxMem

Groupe cluster 1

Groupe cluster 2

Groupe cluster 3

Groupe data

21 / 43




Le noyau JUXMEM : jukRéalisé au cours de la thèse de Mathieu Jan

Permet de s’abstraire de JXTAFonctionnalités

CommunicationPublication/Recherche

LocaleGlobale

Stockage

Interface avec les applications

Noyau JuxMem

CommunicationPublicationrecherche

Stockage

22 / 43




Exemple de scénario

data_id = juxmem_malloc(size, 2, 2)

23 / 43






23 / 43






23 / 43






23 / 43






23 / 43





juxmem acquire(data_id)juxmem write(data_id)juxmem release(data_id)

23 / 43





juxmem acquire(data_id)juxmem write(data_id)juxmem release(data_id)

juxmem acquire_read(data_id)juxmem read(data_id)juxmem release(data_id)

23 / 43




Mise en œuvre des couches

Mise en œuvre d’unprotocole de cohérence

Module clientModule localModule global

Mise en œuvre d’un groupeauto-organisant

Module clientModule fournisseur

Protocole de cohérence

Groupe auto-organisant

24 / 43




Mise en œuvre des groupes auto-organisants

Approches pour la diffusion atomiqueProtocole d’accordNœud séquenceur

25 / 43






25 / 43






25 / 43




Auto-organisation des groupes

Détection de fautesPolitique

conservation du degré deréplication

Faute d’un fournisseurnon-séquenceur

Recherche d’un remplaçantGel du protocoleMise à jour du remplaçantMise à jour du groupe

Faute du fournisseurséquenceur

Choix du séquenceursuivant (élection)

26 / 43











26 / 43











?

26 / 43











26 / 43











26 / 43











26 / 43




Fonctionnement général

juxmem_acquire(data_id)

27 / 43






27 / 43






27 / 43






27 / 43






27 / 43






27 / 43






27 / 43






27 / 43




MéthodologieExpérimentation sur des architectures réelles

Multiples types d’évaluationPreuves formellesSimulationsExpérimentations

Expérimentations sur grillesGrid’5000Réservation :OAR/OARGrid [IMAG]Déploiement : ADAGE [IRISA]Récupération des résultats

28 / 43




Évaluations

1 Coût des mécanismes de réplication2 Bénéfice de l’approche hiérarchique3 Impact des fautes

29 / 43




1 : Coût de la réplicationDescription des tests

Rennes

Orsay

Nancy

3 grappes géographiquementréparties3×7 fournisseurs1 client

30 / 43




1 : Coût de la réplicationDans une grappe - coût des opérations de lecture

1

10

100

1000

64 Mo16 Mo4 Mo1 Mo256 ko64 ko16 ko4 ko1 ko

Late

nce

des

opér

atio

ns (

en m

s)

Taille de la donnée

1x11x21x31x51x7

Lecture = acquire_read + read + release31 / 43




1 : Coût de la réplicationDans une grappe - coût des opérations d’écriture

1

10

100

1000

64 Mo16 Mo4 Mo1 Mo256 ko64 ko16 ko4 ko1 ko

Late

nce

des

opér

atio

ns (

en m

s)


1x11x21x31x51x7

Ecriture = acquire + write + release32 / 43




1 : Coût de la réplicationDans deux grappes - coût des opérations de lecture

10

20

30

40

50

60

1 Mo256 ko64 ko16 ko4 ko1 ko

Late

nce

des

opér

atio

ns (

en m

s)


2x12x22x32x5

Lecture = acquire_read + read + release33 / 43




1 : Coût de la réplicationDans deux grappes - coût des opérations d’écriture

10

20

30

40

50

60

70

80

90

100


Late

nce

des

opér

atio

ns (

en m

s)


2x12x22x32x5

1x5 (pour comparaison)

Ecriture = acquire + write + release34 / 43




2 : Bénéfice de l’approche hiérarchiqueConfiguration des expérimentations

Rennes Nancy

LDG unique

Rennes Nancy

GDG

35 / 43




2 : Bénéfice de l’approche hiérarchique

20

40

60

80

100

120

140


Late

nce

des

opér

atio

ns (

en m

s)


Lectures (cas hiérarchique)Écritures (cas hiérarchique)

Lectures (cas non-hiérarchique)Écritures (cas non-hiérarchique)

36 / 43




MéthodologieInjection de fautes

Expérimentations sans fautesCoût de la tolérance aux fautes ?

Expérimentations avec fautesRésistance aux fautes ?Impact des fautes sur les performances ?

Outil d’injection de fautesBesoin de reproductibilité, de précision et de passage àl’échelleGénération d’un calendrier de fautesIntégré à un outil de déploiement (JDF)

37 / 43




3 : Impact des fautes sur les performances

TempsFaute

Temps de détection Temps de recherche Temps d'auto-organisation

(4.6ms)

200

400

600

800

1000

1200

1400

1600

500 1000 1500 2000 2500 3000

Tem

ps d

e dé

tect

ion

(en

ms)

Intervalle entre les messages de vie (ms)

Temps de détection d'une faute

0 5

10 15 20 25 30 35 40 45 50

4 Mo1 Mo256 ko64 ko16 ko4 ko1 koTem

ps d

e d'

auto

-org

anis

atio

n (m

s)

Taille de la donnée hébergée par le groupe

Temps d'auto-organisation

38 / 43



ContributionsPerspectivesPerspectives

Contribution : architecture découplée générique

Gestion conjointeProtocoles de cohérence de donnéesMécanismes de tolérance aux fautesArchitecture logicielle multi-protocole

Mise en œuvre et évaluation expérimentaleJUXMEM-c 13 500 lignes de code

dont 6 100 pour la cohérence des données et la tolérance aux fautes

JUXMEM-java 16 700 lignes de codedont 7 300 pour la cohérence des données et la tolérance aux fautes

Expérimentations multi-sites sur Grid’5000Publications : CCGrid 2006, HPDGrid 2006

39 / 43




Contribution : une approche hiérarchiquepour la tolérance aux fautes et la cohérence des données

Intégration dans une architecture hiérarchique commune

Dans le cadre du projet GDS de l’ACI Masse de DonnéesService de partage de données pour la grille

Mise en œuvre et évaluation expérimentaleIntégration de GFD [LIP6]Expérimentations multi-sites sur Grid’5000Publications

WCGC 2006le journal international Concurrency and Computation :Practice and Experience (2006)le chapitre de livre Future Generation Grids (CoreGRIDseries 2006)

40 / 43




Contribution annexe

Réseau logique malléable

Cadre : Collaboration avec l’UIUCUniversity of Illinois at Urbana-ChampaignRéseau logique pair-à-pairBut : offrir des communications de groupe efficaces

Mise en œuvre et évaluationConception d’un simutateur à évènements discretsPublications : SRDS 2006

41 / 43




Perspectives

Données fragmentéesDécoupage des données en blocsBlocs répartis sur un ensemble de fournisseurs

Support d’autres types d’applicationsApplication collaborativesProjet RESPIRE de l’ANR MDMSA débuté en 2006

Intégration à une plate-forme pour applications de fouillede données sur la grille

Collaboration avec l’université de Calabre débutée en 2006

42 / 43




Perspectives

Mécanismes adaptatifsProtocoles de cohérenceMécanismes de tolérance aux fautes

Fautes des clientsApplications tolérantes aux fautesCouplage points de reprise/réplication

43 / 43

Documents

Gestion de données dans les grilles de calcul · 2014. 10. 4. · Grilles de calcul et partage de données Gestion de la cohérence et de la tolérance aux fautes Problème : la