Caches adaptables et applications aux systèmes de gestion de données répartis à grande échelle

Caches adaptables et applications aux systèmes de gestion de données

répartis à grande échelle

D’ORAZIO Laurent

Sous la direction deClaudia RONCANCIOCyril LABBÉ

Grenoble, lundi 17 décembre 2007

2

Grille informatique

Besoins en puissance de calcul et de stockage– Physique– Météorologie– Biologie : décryptage de génome– Imagerie médicale– Etc.

3

Caractéristiques de la gestionde données sur grille

Partage de ressources– Grappe (cluster) : ensemble de nœuds– Grille : grappe de grappes

4

Problèmes liés à la gestionde données sur grilles

?????

Dispersion géographique, volumes importants de données,

5

Problèmes liés à la gestionde données sur grilles

Dispersion géographique, volumes importants de données,nombreux clients

6

Problèmes liés à la gestionde données sur grilles

Dispersion géographique, volumes importants de données,nombreux clients, variabilité

7

Objectif de la thèse

Optimiser la gestion de données sur grillesUtilisation de caches au niveau intergiciel

• Réduire les temps d’attente• Augmenter la disponibilité

8

Exemple de données dans une application bio-informatique

ID 104K_THEPA STANDARD; PRT; 924 AA.AC P15711;DT 01-APR-1990 (Rel. 14, Created)DT 01-APR-1990 (Rel. 14, Last sequence update)DT 10-MAY-2005 (Rel. 47, Last annotation update)DE 104 kDa microneme-rhoptry antigen.OS Theileria parva.OC Eukaryota; Alveolata; Apicomplexa;

Piroplasmida;OC Theileria....SQ MKFLILLFNILCLFPVLAADNHG...HICKMVYHKNV

• Swiss-Prot– 210 000 entrées– 750 Mb

• Intergiciel GedeonSystème de fichiers pour grilles avec capacités d’interrogation par requêtes déclaratives

Donnée

Méta-donnéesIdentifiant

9

Plan de la présentation

• Caches et interrogation de données• Service de caches adaptables et caches pour l’interrogation de

données• Applications à la gestion de données bio-informatiques sur

grille• Conclusions et perspectives

10

Plan de la présentation

• Caches et interrogation de données– Notion de cache– Caches coopératifs– Caches sémantiques

• Service de caches adaptables et caches pour l’interrogation de données

• Applications à la gestion de données bio-informatiques sur grille

• Conclusions et perspectives

11

Notion de cache

Cache

année=2006

{enr-P15711,enr-Q43495}

Sourcede données

année = 2006

année = 2006

Défaut

Motivations– Optimisation des

performances• Accès rapide

– Support physique– Placement

• Réduction de la charge– Sur les serveurs– Sur les réseaux

– Disponibilité

12

Notion de cache

Cache

année=2006

{enr-P15711,enr-Q43495}

année = 2006

Succès

Motivations– Optimisation des

performances• Accès rapide

– Support physique– Placement

• Réduction de la charge– Sur les serveurs– Sur les réseaux

– Disponibilité

Sourcede données

13

Caches adaptables

Besoin de nombreux caches + conception complexe coût de développement élevé

• Efficacité dépendante de la configuration par rapport au contexte• Hétérogénéité des grilles (Données, Matériels, Clients)

Cacheadaptable

ServeursServeurs

14

Limites des caches adaptablespour la gestion de données sur grille

• Non adaptables aux variations de l’environnement

ServeursServeurs

15

Limites des caches adaptablespour la gestion de données sur grille

• Non adaptables aux variations de l’environnement• Non utilisation des capacités locales pour l’évaluation• Non utilisation des ressources des autres caches

16

Cache coopératif [Dahlin94] [Chankhunthod96]

• Profiter des ressources d’autres caches

• Avantages– Répartition des transferts de

données– Réduction de la charge sur les

serveurs– Augmentation de la disponibilité

Sourcede données

Cache

Cache

Cache

Cache Cache

CacheCaches

coopératifs

Cachescoopératifs

?

17

État de l’art des caches coopératifsCaches répartis [Braun95]

• Principe généralDistribution des requêtes

• Aléatoire• Tourniquet• En fonction des demandes• En fonctions des clients• Etc.

• InconvénientCaches proches physiquement

Sourcede données

Cacheréparti

Cacheréparti

Cacheréparti

Cacheréparti

18

État de l’art des caches coopératifsRésolution verticale [Chankhunthod96]

• Principe généralRésolution par des parents

• Inconvénients– Charge sur les parents– Sensibilité

Sourcede données

CacheCache Cache

Cache

Cacheparent

Cache

19

État de l’art des caches coopératifsRésolution horizontale

• Principe généralRésolution par des frères

• Protocoles– Inondation

[Chankhunthod96]– Catalogue [Fan98]

• InconvénientGestion dans un environnement grande échelle

Sourcede données

Cachefrère

Cache

Cachefrère

Cachefrère

Cachefrère

Cachefrère

Cachefrère

20

Limites des caches coopératifspour la gestion de données sur grilles

• Configuration complexe dans un environnement grande échelle• Gestion des coopérations à grande échelle• Non utilisation des capacités locales pour l’évaluation

21

Cache sémantique [Dar96] [Keller96]

• Profiter des capacités locales d’évaluation– Réduction de la charge sur les

serveurs– Réduction des transferts de

données– Augmentation de la

disponibilité

• Principes– Gestion de résultats de

requêtes– Décomposition des requêtes

posées• Requête de consultation• Requête restante

Cache sémantique

DT>2005 {enr-P15711,enr-Q43495}

ConsultationDT>2005

DT>2005

Sourcede données

Restante :DT>2000DT<2005

22

État de l’art des caches sémantiquesGestion de la sémantique

• Évaluation– Sélection [Dar96]– Projection [Ren03]– Jointure [Keller96]– Requête de localisation

[Zheng01]

• Analyse [Godfrey97]– Équivalence– Inclusions– Recouvrement partiel

Équivalence succès étenduE : année = 2006Q : année < 2007 année > 2005

Entrée

Requête

Requête

Entrée

Requête dans entrée succès étendu

E : année = 2006Q : année=2006 auteur= «Blanchet»

Entrée

Requête

Entrée dans requête succès partiel

E : année = 2006Q : année > 2005

Requête Entrée

Recouvrement partiel succès partielE : auteur = « Blanchet » année = 2006Q : auteur = « Blanchet » espèce = virus

23

État de l’art des caches sémantiquesGestion des régions

• Résultats de requêtes [Dar96]– Agrégation des objets– Duplication dans le cache– Mélange calculs et données

• Prédicats et objets [Keller96]– Pas de duplication dans le

cache– Pas d’agrégation des objets– Synchronisation forte

prédicats / objets Mélange calculs et données

Cache de résultats de requêtes

année=2006 {enr-P15711, enr-Q43495}

année=2010 {}

espèce=virus {enr-P15711, enr-P13813}

auteur=Blanchet

{enr-P13813, enr-P19084}

Cache de prédicats et d’objets

année=2006 {P15711, Q43495}

année=2010 {}

espèce=virus {P15711, P13813}

auteur=Blanchet

{P13813, P19084}

P15711 enr-P15711

Q43495 enr-Q43495

P13813 enr-P13813

P19084 enr-P19084

24

Limites des caches sémantiquespour la gestion de données sur grilles

• Configuration complexe dans un environnement grande échelle• Mélange calculs et données• Non utilisation des ressources des autres caches

25

Caches pour la gestionde données sur grille

• Caches adaptables– Gestion de la sémantique– Gestion de la coopération– Adaptabilité dynamique

• Caches sémantiques– Séparation contenu et sémantique– Séparation données et évaluations

• Caches coopératifs– Utilisation des capacités d’évaluation– Gestion de la coopération à grande échelle

26

Plan de la présentation

• Caches et interrogation de données• Service de caches adaptables et caches pour l’interrogation de

données– ACS (Adaptable Cache Service)– Cache sémantique pour grille– Réseaux de caches dans des environnements grande échelle

• Applications à la gestion de données bio-informatiques sur grille

• Conclusions et perspectives

27

ACS (Adaptable Cache Service)

• ObjectifConstruction de caches• Adaptés• Reconfigurables

dynamiquement

• Choix d’architecture– Canevas logiciel

• Capture des fonctionnalités(cohérence non considérée)

• Capture des interactions entre les fonctionnalités

– Composants logiciels• Paramétrisation• Modularité

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Gestionnairede

résolution

Gestionnaired’analyse

Gestionnaired’évaluation

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

RésolutionSource 1

Contenuhachage

Cacheélémentaire

RemplacementLRU

RésolutionSource 2

RemplacementSIZE

28

Prototype d’ACS

• Architecture du canevas– Java + Fractal

– Interfaces + patrons d’interactions

– Bibliothèque de composants

29

Construction à l’aide d’ACS d’un cache pour l’application bio-informatique

RemplacementLRU

Cacheélémentaire

Contenuhachage

Résolutiongrille

Admissiontaille

Composants réutilisés

Composants spécifiques

Réutilisation de code = 88 %

Cache

année=2006

{enr-P15711,enr-Q43495}

30

ACS et gestion de la sémantique

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Gestionnairede

résolution

Gestionnaired’analyse

Gestionnaired’évaluation

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

Cache sémantique

Gestionnaired’évaluation, , TRIS,

etc.

Évaluation, , TRIS,

etc.

Gestionnaired’analyse, ,

Analyse, ,

Gestionnairecache

sémantique

31

Construction à l’aide d’ACS d’un cachede résultats de requêtes pourl’application bio-informatique

Gestionnaired’analyse

,

Gestionnaired’évaluation

Cache de résultats de requêtes

année=2006 {enr-P15711, enr-Q43495}

année=2010 {}

espèce=virus {enr-P15711, enr-P13813}

auteur=Blanchet

{enr-P13813, enr-P19084}

Gestionnairede

remplacement

Gestionnairede

contenu

Gestionnairede

résolution

Gestionnaired’analyse

Gestionnaired’évaluation

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

ÉvaluateurGedeon

Analysevecteurs,

Gestionnairecache

sémantique

Réutilisation de code = 81 %

32

Construction à l’aide d’ACS d’un cachede prédicats et d’objets pourl’application bio-informatique

Gestionnaired’analyse

,

Gestionnaired’évaluation

Cache sémantique

Cache de prédicats et d’objets

année=2006 {P15711, Q43495}

année=2010 {}

espèce=virus {P15711, P13813}

auteur=Blanchet

{P13813, P19084}

P15711 enr-P15711

Q43495 enr-Q43495

P13813 enr-P13813

P19084 enr-P19084Gestionnaire

deremplacement

Contenuprédicats/ objets

Gestionnairede

résolution

Gestionnaired’analyse

Gestionnaired’évaluation

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

ÉvaluateurGedeon

Analysevecteurs,

Gestionnairecache

sémantique

Réutilisation de code = 100 %

33

ACS et caches répartis

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Gestionnairede

résolution

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

Cache réparti

Sourcede données

Cacheréparti

Cacheréparti

Cacheréparti

Cacheréparti

34

ACS et caches avecrésolution verticale

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Résolutioncacheparent

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

Sourcede données

CacheCache Cache

Cache

Cacheparent

Cache

35

ACS et caches avecrésolution horizontale

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

RésolutionInondation/ catalogue

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

Sourcede données

Cachefrère

Cache

Cachefrère

Cachefrère

Cachefrère

Cachefrère

Cachefrère

36

ACS et caches sémantiques coopératifs

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Résolutionhorizontaleinondation

Gestionnaired’analyse

Gestionnaired’évaluation

Gestionnaired’admission

Fonctionnalités élémentaires

Fonctionnalités optionnelles

Évaluation, , etc.

Analyse, ,

Gestionnairecache

sémantique

Sourcede données

Cachefrère

Cachesémantique coopératif

Cachefrère

Cachefrère

Cachefrère

Cachefrère

Cachefrère

37

Caches pour la gestionde données sur grille

• Caches adaptables– Gestion de la sémantique

– Gestion de la coopération

– Adaptabilité dynamique

• Caches sémantiques– Séparation contenu et sémantique

– Séparation données et évaluations

• Caches coopératifs– Utilisation des capacités d’évaluation – Gestion de la coopération à grande échelle

38

Cache dual

Cache dual

• Caches indépendants– Cache de requêtes évaluations– Cache d’objets données

• Avantages– Conservation d’évaluations sans

les objets– Pas de duplication d’objets– Configuration fine du cache dual

(stratégie des caches)

• Limites– Pas d’agrégation– Accès par requête et par

identifiants

Cache de requêtesannée=2006 {P15711,

Q43495}

année=2010 {}

espèce=virus {P15711, P13813}

auteur=Blanchet

{P13813, P19084}

Cache d’objetsP15711 enr-P15711

Q43495 enr-Q43495

P18646 enr-P18646

Q9XHP0 enr-Q9XHP0

ServeursServeurs

Requête

{identifiant}

39

Cache dual sémantique

Cache dual

Cache de requêtesannée=2006 {P15711,

Q43495}

année=2010 {}

espèce=virus {P15711, P13813}

auteur=Blanchet

{P13813, P19084}

Cache d’objetsP15711 enr-P15711

Q43495 enr-Q43495

P18646 enr-P18646

Q9XHP0 enr-Q9XHP0

Ge

stion

na

ired

’an

alyse

Ge

stion

na

ired

’éva

lua

tion

Gestion de la sémantique– Analyse et cache de

requêtes• Équivalence• Inclusions• Recouvrements partiels

– Évaluation et cache d’objets• Sélection• Projection• Tri

40

Caches pour la gestionde données sur grille

• Caches adaptables– Gestion de la sémantique

– Gestion de la coopération

– Adaptabilité dynamique

• Caches sémantiques– Séparation contenu et sémantique

– Séparation données et évaluations

• Caches coopératifs

– Utilisation des capacités d’évaluation – Gestion de la coopération à grande échelle

41

Réseaux de caches pour les environnements grande échelle

42

Notion de proximité

ObjectifMesurer de la pertinence d’une coopération entre caches

• Paramètres physiques– Caractéristiques des hôtes

• Capacité de calcul• Charge

– Caractéristiques des réseaux

• Débit• Latence

• Paramètres sémantiques– Homogénéité des données– Similarité des demandes

43

Exemples de proximité

Proximité physiqueProximité sémantique

44

Cache dual coopératif pour lagestion de données à grande échelle

Cachedual

Cache derequêtes

Cached’objets

Proximité physiqueProximité sémantique

• Protocoles de résolution pour cache dual– Sans coopération– Physique– Sémantique– Physique

etsémantique

45

Plan de la présentation

• Caches et interrogation de données• Service de caches adaptables et caches pour l’interrogation de

données• Applications à la gestion de données bio-informatiques sur

grille– Contexte expérimental– Outils pour l’évaluation de performances– Validation du cache dual– Validation des réseaux de caches à grande échelle

• Conclusions et perspectives

46

Contexte expérimental

Rennes

Sophia-Antipolis

Nancy

SP1

SP2SP3

Architecture à union de serveurs

47

Proximité au sein d’ACS

• Protocole de résolutionInondation utilisation d’un gestionnaire de topologie

• Proximité pour les caches de requêtesprox(a,b) = prox(b,a) = 1 si a et b ont au moins x % de prédicats sur un même ensemble de données

• Proximité pour les caches d’objetsprox(a,b) = prox(b,a) = 1 si a G et b G

• Attention :Proximité établie statiquement au moment du déploiement

48

Génération de requêtes

Charge de travail– Termes appartenant à l’Arbre de vie

– Localité sémantique Rx [Luo01]

– Communauté (bacteria, eucaryota, archaea, viruses)

Bacteria

Archaea VirusesEukaryota

Apicomplexa

Euryarchaeota PositiveFirmicutes Fungi Alveota

Ciliophora …

… …

…

…… ……

…… …

Q1 exemple Eukaryota OCRaffinement

Q2 Q1 exemple Eukaryota OC Alveota OCNouvellerequête Q3 exemple Archaea OC

49

Expérimentations

• Validation du cache dual– Union de 3 serveurs (Sophia-Antipolis, Rennes, Lille)– 50 clients avec des caches de 500Mo (Sophia-Antipolis,

Rennes, Lille, Toulouse)Cache dual : 10 Mo pour cache de requêtes

– 100 requêtes par client– Localité sémantique R60– Pas d’appartenance à une communauté

50

Validation du cache dual

Cache dual plus performant– Taux de succès de cache plus élevés– Charge d’évaluation sur les serveurs plus faible– Volume de données transférées moins important Temps de réponse plus courts

CacheSémantique

Tempsde réponse

Succèsexacts

Succèsétendus

Charge surles serveurs

Évaluations sur les serveurs

Volumetransféré

Cache de résultats de requêtes

73.52 s 19.16 %

56.38 %

24,46 % 24,46 % 187.526 Go

Cache de prédicats et d’objets

71.01 s 26.46 %

49.70 %

23.84 % 23.84 % 185.464 Go

Cache dual 47.26 s 52.94 %

39.02 %

23,34 % 8.04 % 132.197 Go

51

Expérimentations

• Analyse des protocoles de résolution pour cache dual– Union de 3 serveurs (Nancy, Rennes, Sophia-Antipolis)– 50 clients avec des caches de 325Mo (Sophia-Antipolis,

Rennes, Lille, Toulouse)Cache dual : 10 Mo pour cache de requêtes

– 50 requêtes par client– Localité sémantique R40– Communauté 70 %

52

• Les coopérations entre caches améliorent les performances• La proximité sémantique réduit

– Les évaluations sur les serveurs– La consommation de bande passante (le rapatriement par données

évite la récupération d’objets déjà stockés)

• La proximité physique répartit la consommation de bande passante• La proximité physique et sémantique améliorent grandement les

performances

Temps de

réponse

Évaluationssur les serveurs

Données transférées

Données transférées(serveurs - caches)

Sans coopérations

103.3 s 34 % 30.4 Go 30.4 Go

Physique 102.1 s 34 % 30,4 Go 25.9 Go

Sémantique 32.1 s 9 % 29.5 Go 29.5 Go

Physique sémantique

24.4 s 9 % 25.1 Go 11.5 Go

Analyse des protocoles de résolution

53

Plan de la présentation

• Caches et interrogation de données• Service de caches adaptables et caches pour l’interrogation de

données• Applications à la gestion de données bio-informatiques sur

grille• Conclusions et perspectives

54

Résumé

• Objectif de la thèseOptimiser la gestion de données sur grilles

• Contributions– État de l’art des caches sémantiques et des caches coopératifs– Canevas pour la construction de caches adaptables

[MGC2005] [BDA2006]

– Cache sémantique pour la gestion de données sur grille[BDA2006] [CFSE2006] [CLCAR2007]

– Gestion des coopérations entre caches à grande échelle[BDA2007] [DEXA2007]

• Expérimentations sur grille de données

55

Perspectives

• Caches et hétérogénéité de données• Analyses et évaluations dans les caches sémantiques• Accès efficace à des volumes importants de données• Gestion de la cohérence à grande échelle

Considérer les mises à jours

• Adaptation contextuelle de caches

56

Adaptation contextuelle de caches

Gestionnaire de contexte- Modélisation- Capture- Gestion des situations pertinentes

Cache ACS

Gestionnaire d’adaptation

Résolution

Cache élémentaire

Contexte

Règles activesECA

Paramétrisation

57

Adaptation contextuelle de caches

Gestionnaire de contexte- Modélisation- Capture- Gestion des situations pertinentes

Cache ACS

Gestionnaire d’adaptation

Résolution

Cache élémentaire

Contexte

Règles activesECA

Analyse Évaluation

Cache sémantique

58

Vers des caches autonomes

59

Merci

Questions

60

Bibliographie (1)

• [Braun95] Hans-Werner Braun and Kimberly C. Claffy. Web traffic characterization : an assessment of the impact of caching documents from ncsa’s web server. Computer Networks and ISDN Systems, 28(1-2) :37–51, 1995.

• [Chankhunthod96] Anawat Chankhunthod, Peter B. Danzig, Chuck Neerdaels, Michael F. Schwartz, and Kurt J. Worrell. A hierarchical internet object cache. In USENIX Annual Technical Conference, pages 153–164, 1996.

• [Dahlin94] Michael D. Dahlin, Clifford J. Mather, Randolph Y. Wang, Thomas E. Anderson, and David A. Patterson. A quantitative analysis of cache policies for scalable network file systems. In The ACM SIGMETRICS conference on Measurement and modeling of computer systems, pages 150–160, 1994.

• [Dar96] Shaul Dar, Michael J. Franklin, Bj¨orn T. Jonsson, Divesh Srivastava, and Michael Tan. Semantic data caching and replacement. In Proceedings of the international conference on Very Large Data Bases, pages 330–341, 1996.

61

Bibliographie (2)

• [Fan98] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. Summary cache : a scalable wide-area web cache sharing protocol. In The ACM SIGCOMM Conference on Applications, technologies, architectures, and protocols for computer communication, pages 254–265, 1998.

• [Godfrey97] Parke Godfrey and Jarek Gryz. Semantic query caching for hetereogeneous databases. In The international Workshop on Knowledge Representation meets Databases, pages 6.1–6.6, 1997.

• [Keller96] Arthur M. Keller and Julie Basu. A predicate-based caching scheme for clientserver database architectures. The VLDB Journal, 5(1) :35–47, 1996.

• [Ren03] Qun Ren, Margaret H. Dunham, and Vijay Kumar. Semantic caching and query processing. IEEE Transactions on Knowledge and Data Engineering, 15(1) :192–210, 2003.

• [Zheng01] Baihua Zheng and Dik Lun Lee. Semantic caching in location-dependent query processing. In The International Symposium on Advances in Spatial and Temporal Databases, pages 97–116, 2001.