Plan introduction systemes applications distribues ( repartis ) bds REPARTIES bds relationnelles, techniques utilisees I introduction
télécharger 126.63 Kb.
|
PLAN
2. SYSTEMES APPLICATIONS DISTRIBUES ( REPARTIS ) 3. BDs REPARTIES BDs RELATIONNELLES , TECHNIQUES UTILISEES I - INTRODUCTIONSystèmes, applications distribuésApplications qui utilisent des données de types différents , situées sur des sites différents , avec des requetes plus ou moins complexes Ex : applications multimédia , multi bases Problématique des applications avec BDs réparties II SYSTEMES APPLICATIONS DISTRIBUES ( REPARTIS ) 1 ou plusieurs processus fonctionnent sur plusieurs machines (ordinateurs ) OS différents , des micro- noyaux d’un OS réparti client /windows serveur Unix appl.c++ binaire,fortran      réseau  Client/ Linux serveur /IBM , java Problèmes : - la communication ( RPC, messages )
- Transparence de la localisation des ressources - Migration des ressources sans aucune transformation de l’environnement utilisateur - Réplication des ressources
3. Fiabilité , disponibilité : indépendance des éléménts du système , redondance logicielle , matérielle, sécurité ( contrôle d’acces ) 4. Performance 5. Gérer grand nombre (applications , utilisateurs , machines , services , trafic ) Centralisation difficile , peu performante Hétérogénéité Extensibilité 6. Maintenabilité 2.2 Systemes distribués - objets        Processus sur meme machine ou sur plusieurs machines Communication inter processus : RPC ( appel de procédure distante) dans appli. Client- serveur, appel de procédure local , à travers un bus logiciel ou interface de transport Système à objets répartis :  Invocation méthodes objet  réponse ORB , CORBA ( OMG object management group) :middleware - IDL interface data language pour décrire les données impliquées dans les RPC - STUB (souche,squelette) - Edition de liens dynamique entre clients et objets CONCEPT OBJET - Encapsulation des données et opérations dans meme entité - Accès aux données à travers l’interface objet ( méthodes ) - Séparation entre l’interface externe de l’objet et son implantation
sur autres objets de l’application
    idl idl idl idl   Stub client Stub serveur ORB ( bus à objet répartis ) ORB : communications entre objets, référentiels d’interfaces , mapping avec les langages de programmation des objets ( services de localisation , gestion réseau , environnement d’ exécution , sécurité , outils ) Des objets : Coté client : - création et identification d’objets
Coté serveur : - implantation objets ( méthodes , modèles d’exécution )
Architecture client-serveur : client léger , type web serveurs d’applications , standards TCP/IP , HTTP,…. données encapsulées,enveloppées dans formats HTML , XML , .. applications à codes binaires exécutables à distance, mobiles,etc - 1 client < ----- > 1 serveur - 1 client <---------> serveur accès (bd) - serveur 1(bd1)   serveur 2 (bd2)   serveur 3(bd3) III.BDs REPARTIES , RELATIONNELLES
BD répartie : 1 ensemble de BD coopérantes , chacune résidant sur 1 site différent , vu par l’utilisateur comme une seule base ( transparence à la localisation des données ) Multi bases primaires ,avec données propres ou non , sur chaque site, 1 base centrale avec informations propres et duplication des mises à jour des bases locales
- Performance , accès distants occasionnels - Fiabilité , sécurité 3.2 Techniques utilisées dans la répartition des données : Fragmentation et réplication ( duplication ) en fonction des données et requetes
+ fragmentation horizontale + frag. verticale + frag. mixte - Préserver la cohérence sémantique de la BD + décomposition sans perte d’information + reconstitution pour vérification + non duplication - Fragmentation horizontale Découpage selon les tuples de la relation + directe : avec opérateur sélection : ( R ) + indirecte : semi-jointure R1 R2 Découpage selon les attributs d’une autre relation On ne prend que les attributs de R1 ayant le meme attribut de jointure avec R2
+ projection ( R ) Ai selon les attributs de la relation - Fragmentation mixte ( horizontale + verticale ) - Reconstitution de la BD avec les opérateurs , Schéma relationnel : Departement ( ndep , ……..,… ) Bureau ( nbur , ndep,….. ) Employé ( nempl , enom , ndep, …..) Projet ( nproj , nempl, ndep ) Departement i = p i Departement i Bureau i = Bureau Departement i Snum Employé i = ( Employé Departement i ) nempl,… Reconstitution : Departement = Departement i Employé = ( Employé i ) Bureau = Bureau i Projet = Projet i Requete :1 - Employés des départements différents , participant au meme projet , ou à 1 projet j requete envoyée au site primaire select Empl.nempl, Empl.ntel,Empl.nbur From Projet Proj , Employé Emp,Département Dep,Bureau Bur Where Proj.nempl = Emp.nempl And Emp.ndep = Dep.ndep And Bur.ndep = Dep.ndep Une répartition des relations : Projet , Employép sur site primaire Des relations en fragments sur sites différents : Depi , Bur i , Employéi   nemp,ndep Bureau i Departement i Projet Employé Employé i ( Projet ) proj = j site primaire site i informations transférées : nemp,ndep 2 - Rapports des employés des départements différents j participant à 1 projet du département i La plupart de participants aux projets departement i dépendent de de département , peu de participants de départements externes Données à transférer aux autres sites limitées requete envoyée au site i 1 répartition des relations : site i : Projet i , Employé i , Département i, Bureau i sites j != i synthèse des réponses   nproj,nemp,ndep,nrap jointures,projection sur site i (Proji,Empi,Depi,Buri) nproj,nemp,ndep,nrap projection ( Proj ) jointures proj = p , ndep =i  ( Proj ) proj =p, ndep = ! i site j site i
Copies des fragments des relations sur sites différents Mise à jour des données peuvent etre synchrone , asynchrone d’un fragment , de la relation ------- - grande disponibilité - résistance aux pannes - consultations parallèles , compromis entre performance d’accès et cohérence des données - diminution trafic réseau Des BDs réparties peuvent etre réalisées avec des modules : Réplication server , DatabaseLink , SQL net,etc chez Oracle , Sybase,….. 3.4 Plan d’exécution des requetes dans 1 bd répartie réponse   S1     ER req  S2 req S3  S4ER site émetteur des sous requetes locales ,exécutées sur sites répartis Si Jointure des réponses intermédiaires sur S1 Quantité totale des transmissions des requetes ou réponses intermédiaires:8 Le plan d’exécution de requete : décomposition d’une requete enrequetes locales et l’ordre d’exécution , et sites de jointure dépend de la quantité des requetes ou réponses intermédiaires , temps de traitement sur sites locaux , temps de communication Le temps de communication inter-sites souvent élévé par rapport aux temps d’acces et traitement ----- minimiser quantité des requetes , réponses intermédiaires Il peut y avoir plusieurs points d’acces A chaque points d’acces , le plan d’exécution réparti est sélectionné en fonction de la localisation des données nécessaires au traitement de la requete ( description , image de la BD répartie dans dictionnaire ) sur tous les sites Problème de synchronisation : ordre d’arrivée des requetes, réponses intermédiaires pour effectuer des opérations binaires Les réponses intermédiaires peuvent etre transférées bloc par bloc ,au fur et à mesure , à 1 autre site pour faire des jointures par pipelinage Une BD répartie : couplage ( cohérence ) faible entre sites pour limiter des communications intersites Plusieurs BDs : requetes emboitées , cohérence globale et interblocage 3.5 Optimisation des requetes distribuees La performance de l’exécution d’une requete en environnement réparti dépend des facteurs suivants :
- Méthode d’accès aux relations locales - Algo des opérations logiques,physiques - Ordre des transferts des données entre sites (déplacement des tables,nuplets ) le temps total de l’exécution d’une requete : t = t acces données locales + t traitement local + t communication t depend de la localisation ,allocation des données sur différents sites et du nombre de communications inter-sites et la taille des tables ou nuplets transféres si tc >> ta + tt , minimiser nb sites,communications si tt + ta > tc , plusieurs sites (réseau local ) L’optimisation des requetes distribuées peuvent etre faite par latransformation des requetes avec des règles de réecriture comme pour le cas d’un seul site Plusieurs sites impliquent la décomposition d’une requete en plusieurs requetes locales ( transformation sémantique ) Les plus utilisés sont la distributivité des sélection,projection (unaires) sur union,jointures (binaires) (5,6,7,8 du cours) La semi-jointure permet de réduire la taille des nuplets résultat des jointures à transmettre sur support de communication L’optimisation dépend du chemin pris parmi des chemins possibles et de l’ordre d’exécution sur différents sites Algo de la semi-jointure sur plusieurs sites :
- Transmission des résultats intermédiaires
2 méthodes pour optimiser le cout de transmission des semi-jointures : - Calcul du cout de la jointure : R S TR , TS tuples Cout de transmission de n tuples : c0 + n c0 : cout fixe (overhead) pour chaque transmission n : cout proportionnel de transmission de n tuplestransmettre TR sur le site de S et jointure avec S, cout = c0 + TR transmettre TS sur le site de R et jointure avec R, cout = c0 + TS cout de la jointure = c0 + min ( TR, TS )
Effectuer R S par ( R S ) S 1 - Projection de S sur attribut commun de de R,S ( S ) R S 2 - Transférer résultat sur R 3 - Semi-jointure R S sur R R S = R ( S ) R S 4 - Transférer résultat sur S 5 - R S = ( R S ) S cout = 2 c0 + min ( T’s + T ’’R + T’R + T ’’S ) T’s : nb de tuples de R S ( S ) T’R : nb tuples de R S ( R ) T’’R : nb tuples de R S T’’S : nb tuples de S R La semi-jointure est plus efficace que la jointure sic0 + min ( T’s + T’’R +TR + T’’s ) < min ( TR,TS ) C’est vrai si : - c0 n’est pas très élévé par rapport au cout incrémental de transfert de petite quantité de tuples - R et S de taille comparable - T’S et T’’S << TS de meme pour R Pour la jointure de plusieurs( >2) relations , appliquer l’algo de semi-jointure pour réduire nb de tuples - Calcul de semi-jointure Schéma relationnel R = { R1 , R2 , …. , Rn } de la BD Supposons que les relations Ri localisées sur des sites différents Il faut transférer certaines Rj sur 1 site pour effectuer la jointure La semi-jointure : R S = R ( R S ) On vérifie que : R S = ( R S ) S = ( S R ) R Dans beaucoup de cas , calculer la jointure par 1 de ces expressions Algébriques peut réduire le cout des données à transférer On peut remplacer des relations Ri sur des sites différents par des semi-jointures avec autres relations de R ( on ne garde que des tuples , attributs ‘utiles’ et transférer les résultats intermédiaires de taille réduite , aucun tuple ‘inutile’ pour la jointure ou calcul de la requete sur 1 autre site ne sera transféré ) Programme de semi –jointure pour R est une suite de commandes : R i1 = Ri1 Rj1 ; R i2 = Ri2 Rj2 ; ----------- Rip = Rip Rjp ; En pratique , les valeurs initiales des Rij ne peuvent pas etre surchargées Le réducteur complet ( reducer ) : Appliquer le programme au schéma R conduit à 1 schéma consistant Un schéma R = { ABC , BCDE , BCDG , CDEF } = { R1,R2,R3,R4 } R n ’est ni globalement , ni relativement consistant R1 A B C R2 B C D E 0 3 2 3 2 1 0 0 1 2 1 2 3 0 3 1 2 1 3 1 6 1 1 3 R3 B C D G R4 C D E F 3 2 1 4 2 1 1 4 1 2 3 2 2 3 0 1 1 3 1 0 3 1 0 2 1 3 1 1 3 1 0 3 réducteur complet : R2 = R2 R1 ; R2 = R2 R4 ; R3 = R3 R2 ; R2 = R2 R3 ; R4 = R4 R2 ; R1 = R1 R2 ; Appliquer ce programme permet d’éliminer le 1er tuple de chaque relation 3.6 Transactionnel réparti Transactionnel dans 1 environnement réparti Techniques utilisées : - Contrôle de concurrence : estampilles , verrouillage - Gestion de fiabilité : journalisation , points de reprises
- Estampillage : chaque message contient l’horloge vectorielle qui permet d’établir l’ordre causal ou total ,local de l’application détermination d’un état cohérent - Verrouillage : le graphe des dépendance des transactions n’est connu que partiellement sur 1 site local , il faut vérifier à tout instant si il y a 1 circuit dans le graphe , verifier la sériabilité Le verrouillage à 2 phases dans l’env. réparti , détection d’interblocage dans graphe de dépendances, difficile Utiliser 1 temporisateur pour limiter l’acces - Validation à 2 phases Protocole de validation atomique à 2 phases : validation si tous les sites ont ‘voté’ oui Algo bloquant si 1 site ne répond pas ,il faut attendre ou répéter des messages au terme du délai de garde 1 coordinateur et des participants coordinateur participant  prepare  mise à jour ds journal ready ou refuse ecrire ds journal  commit valider la transaction ( mise à jour ds BD )  ack ecrire ds BD 1 délai de garde après chaque transmission réémission s’il n’y a pas réponse après délai de garde ou abort écrire dans la base après réception de Commit aux sites participants écrire dans la base à la réception Ack au site coordinateur écrire dans journal sur tous les sites pour reprises en cas de panne - Validation à 3 phases La validation à 2 phases peut se bloquer en cas de pannes des supports de communication ou de sites la validation à 3 phases propose de gérer les pannes de sites Principe de non- blocage : si il existe 1 processus opérationnel dans 1 état incertain , alors aucun processus opérationnel ou en panne ne peut avoir décidé de commuter ( valider ou abandonner la transaction ) coordinateur participant prepare ready ou refuse precommit ack commit ecrire ds BD valider la transaction ( mise à jour ds BD ) 3.7 Schéduler ( coordinateur ) d’une application distribuée : gestion de
- états des machines distribuées
- optimisation de l’utilisation des ressources disponibles ( équilibrage des charges,……. ) gain de performance avec minimisation accès réseaux , disques , chemins d’accès 3.8 - Applications à plusieurs BDs différentes de meme fabricant ( SGBD ) + décomposer 1 requete ( utilisateur ) en plusieurs requetes locales à envoyer aux BDs différentes ( structures ) + intégration , agrégation des réponses + modèles des requetes , meme interface d’accès aux BDs ( adaptateurs ) -Extensibilité de la BD répartie : + Conserver la structure de la Bd existante + Meme interface externe + Scalabilité prévue à la conception - Hétérogénéité des SGBD (relationnelle,objet) : BD fédérée + cas précédent , plus + encapsulation des relations dans un meme modèle objet + SQL3 Biliographie : Cours B6 Fondements des BDs par Abitboul et autres Databases et knowledge base syst par J. Ullman Distributed database systems par D. Bell,J . Grimson |
