ACS - Un canevas pour la construction de caches adaptables

ACS - Un canevas pour la construction de caches adaptables

Laurent d’OrazioLIMOS – Equipe Base de Données

Vendredi 13 mars 2009

Grilles informatiques

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

2

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

3

?????

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


4

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


5

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

Objectif

6

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

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

Notion de cache

Motivations– Optimisation des

performances• Accès rapide

– Support physique– Placement

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

– Disponibilité

7

Cache

année=2006

{enr-P15711,enr-Q43495}

Sourcede données

année = 2006

année = 2006

Défaut

Notion de cache

Motivations– Optimisation des

performances• Accès rapide

– Support physique– Placement

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

– Disponibilité

8

Cache

année=2006

{enr-P15711,enr-Q43495}

année = 2006

Succès

Sourcede données

Grilles et 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)

9

Cacheadaptable

ServeursServeurs

Plan

• Introduction• ACS (Adaptable Cache Service)

– Architecture globale– Construction à l’aide d’ACS d’un cache pour l’application bio-

informatique

• ACS et caches sémantiques• ACS et caches coopératifs• Prototype et validation• Conclusion et perspectives

10

Architecture globale

11

• 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

12

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}

Plan

• Introduction• ACS• ACS et caches sémantiques

– Gestion du contenu– Gestion de la sémantique

• ACS et caches coopératifs• Prototype et validation• Conclusion et perspectives

13

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

14

ConsultationDT>2005

DT>2000

Sourcede données

Restante :DT>2000DT<2005

Cache sémantique

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

15

É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

16

État de l’art des caches sémantiquesGestion du contenu

• 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

17

ACS et gestion de la sémantique

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Gestionnairede

résolution






Cache sémantique

Gestionnaired’évaluation, , TRIS,

etc.

Évaluation, , TRIS,

etc.

Gestionnaired’analyse, ,

Analyse, ,

Gestionnairecache

sémantique

18

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


,



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






ÉvaluateurGedeon

Analysevecteurs,

Gestionnairecache

sémantique


19

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


,


Cache sémantique


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






ÉvaluateurGedeon

Analysevecteurs,

Gestionnairecache

sémantique


Plan

• Introduction• ACS• ACS et caches sémantiques• ACS et caches coopératifs

– Cache coopératif– Caches répartis– Résolution verticale– Résolution horizontale

• Prototype et validation• Conclusion et perspectives

20

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é

21Source

de données

Cache

Cache

Cache

Cache Cache

CacheCaches

coopératifs

Cachescoopératifs

?

22

É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

23

ACS et caches répartis

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Gestionnairede

résolution




Cache réparti

Sourcede données

Cacheréparti

Cacheréparti

Cacheréparti

Cacheréparti

24

É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

25

ACS et caches avecrésolution verticale

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

Résolutioncacheparent




Sourcede données

CacheCache Cache

Cache

Cacheparent

Cache

26

É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

27

ACS et caches avecrésolution horizontale

Gestionnairede

remplacement

Gestionnairede

cache

Gestionnairede

contenu

RésolutionInondation/ catalogue




Sourcede données

Cachefrère

Cache

Cachefrère

Cachefrère

Cachefrère

Cachefrère

Cachefrère

Plan

• Introduction• ACS• ACS et caches sémantiques• ACS et caches sémantiques• Prototype et validation

– Prototype– Expérimentations sur grille

• Conclusion et perspectives

28

Prototype d’ACS(disponible sur ligforge.imag.fr)

Architecture du canevas– Java + Fractal

– Interfaces + patrons d’interactions

– Bibliothèque de composants

29

30

Expérimentations sur Grid’5000

Rennes

Sophia-Antipolis

Nancy

SP1

SP2SP3

Architecture à union de serveurs

31

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é

32

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é


73.52 s 19.16 %

56.38 %

24,46 % 24,46 % 187.526 Go


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

33

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 %

34

• 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

Plan

• Introduction• ACS• ACS et caches sémantiques• ACS et caches coopératifs• Prototype et validation• Conclusion et perspectives

35

Résumé

• ObjectifOptimiser la gestion de données sur grilles

• ContributionCanevas pour la construction de caches adaptables

• Expérimentations sur grille de données

36

Perspectives

• Diffusion d’ACSACS sous licence GNU LGPL http://ligforge.imag.fr/projects/acs/

• Problématiques de recherche– Gestion de données sur grilles pervasives– Gestion de données hétérogènes– Gestion de données sur grilles– Gestion de cohérence à grande échelle (transactions sur grilles

?)

37

http://ligforge.imag.fr/projects/acs/

Optimisation dans les environnements variables : adaptation contextuelle (1)

38

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

Optimisation dans les environnements variables : adaptation contextuelle (2)

39

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

Adaptation contextuelle...Vers des caches autonomes

40

Merci

Questions ?

41

42

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.

43

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.

Documents

ACS - Un canevas pour la construction de caches adaptables