Upload
arluin-sellier
View
103
Download
0
Embed Size (px)
Citation preview
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,
Problèmes liés à la gestionde données sur grilles
4
Dispersion géographique, volumes importants de données,nombreux clients
Problèmes liés à la gestionde données sur grilles
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
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
18
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 %
19
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 %
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
Gestionnaired’admission
Fonctionnalités élémentaires
Fonctionnalités optionnelles
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
Gestionnaired’admission
Fonctionnalités élémentaires
Fonctionnalités optionnelles
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
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
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é
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
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
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.