Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

BASES DE DONNÉES RÉPARTIES ET RÉPLIQUÉES 1. INTRODUCTION.......................

BASES DE DONNÉES RÉPARTIES ET RÉPLIQUÉES 1. INTRODUCTION................................................................................................................................................. 2. QU’ESTCEQU’UNE BDR ?............................................................................................................................. 2.1 DÉFINITION ET EXEMPLE........................................................................................................................................ 2.2 SCHÉMA GLOBAL................................................................................................................................................... 2.3 QUELQUES DÉFINITIONS DE BASE........................................................................................................................... 2.4 QUELQUES DÉFINITIONS COMPLÉMENTAIRES......................................................................................................... 2.5 EXEMPLE DE BD FÉDÉRÉES................................................................................................................................... 2.6 AVANTAGES ET INCONVÉNIENTS............................................................................................................................ 3. OBJECTIFS DES SGBDR................................................................................................................................... 3.1 MULTICLIENTS MULTISERVEURS......................................................................................................................... 3.2 TRANSPARENCE À LA LOCALISATION DES DONNÉES.............................................................................................. 3.3 MEILLEURE DISPONIBILITÉ..................................................................................................................................... 3.4 AUTONOMIE LOCALE.............................................................................................................................................. 3.5 HÉTÉROGÉNÉITÉ.................................................................................................................................................... 4. ARCHITECTURE DES SGBDR........................................................................................................................ 4.1 FONCTIONS D’UN SGBDR..................................................................................................................................... 4.2 ORGANISATION DES SCHÉMAS............................................................................................................................... 4.3 ARCHITECTURE DE RÉFÉRENCE.............................................................................................................................. 4.4 GÉNÉRATIONS DE PROTOTYPES.............................................................................................................................. 5. CONCEPTION DES BDR................................................................................................................................... 5.1 CONCEPTION ASCENDANTE OU DESCENDANTE....................................................................................................... 5.2 TECHNIQUES DE FRAGMENTATION......................................................................................................................... 5.3 EXTENSION DE LA FRAGMENTATION HORIZONTALE............................................................................................... 5.4 FRAGMENTATION MIXTE........................................................................................................................................ 5.5 ALLOCATION DES FRAGMENTS............................................................................................................................... 5.6 ALLOCATION OPTIMALE......................................................................................................................................... 6. GESTION DE TRANSACTIONS....................................................................................................................... 6.1 PROPRIÉTÉS DES TRANSACTIONS............................................................................................................................ 6.2 VALIDATION EN DEUX PHASES............................................................................................................................... 6.2.1 Principe......................................................................................................................................................... 6.2.2 Protocole C/S................................................................................................................................................ 6.2.3 Commit distribué ou centralisé..................................................................................................................... 6.2.4 Actions du Protocole..................................................................................................................................... 6.3 COMMIT EN TROIS PHASES..................................................................................................................................... 6.4 PROTOCOLE ARBORESCENT TP.............................................................................................................................. 6.5 BILAN SUR LA GESTION DE TRANSACTIONS........................................................................................................... 7. MONITEURS TRANSACTIONNELS............................................................................................................... 7.1 LES OBJECTIFS........................................................................................................................................................ 7.2 MODÈLE DE MONITEUR TRANSACTIONNEL............................................................................................................. 7.3 INTERFACE APPLICATIVE TX................................................................................................................................. 7.4 L’INTERFACE APPLICATIVE TX SE COMPOSE DES PRIMITIVES SUIVANTES :........................................................... 7.5 INTERFACE RESSOURCE XA................................................................................................................................... 7.6 PRINCIPAUX MONITEURS........................................................................................................................................ 8. CONTRÔLE DE CONCURRENCE.................................................................................................................. 8.1 OBJECTIFS.............................................................................................................................................................. 8.2 LA THÉORIE DE BASE............................................................................................................................................. 8.3 LE VERROUILLAGE DEUX PHASES........................................................................................................................... 8.4 DEGRÉ D'ISOLATION EN SQL2............................................................................................................................... 8.5 PROBLÈMES DE CONTRÔLE DU VERROUILLAGE EN RÉPARTI.................................................................................. 8.6 LES SOLUTIONS AU PROBLÈME DU VERROU MORTEL............................................................................................. 8.6.1 Prévention du verrou mortel......................................................................................................................... 8.6.2 Détection du verrou mortel........................................................................................................................... 8.7 ORDONNANCEMENT PAR ESTAMPILLAGE............................................................................................................... 8.8 CERTIFICATION OPTIMISTE..................................................................................................................................... 8.9 BILAN SUR LA CONCURRENCE................................................................................................................................ 9. RÉPLICATION DANS LES BD RÉPARTIES................................................................................................. 9.1 RÉPLICATION : AVANTAGES ET PROBLÈMES........................................................................................................... 9.2 MISE À JOUR SYNCHRONE ET ASYNCHRONE........................................................................................................... 9.3 TECHNIQUES DE DIFFUSION DES MISES À JOUR...................................................................................................... 9.4 RÉPLICATION ASYMÉTRIQUE.................................................................................................................................. 9.5 RÉPLICATION SYMÉTRIQUE.................................................................................................................................... 9.6 CONVERGENCE DE COPIES SYMÉTRIQUES.............................................................................................................. 9.7 PROBLÈMES DE FIABILITÉ ET REPRISE.................................................................................................................... 9.8 COPIES DÉRIVÉES ET CLICHÉS................................................................................................................................ 10. OPTIMISATION DES REQUÊTES RÉPARTIES........................................................................................ 10.1 OBJECTIFS DE L’OPTIMISATION............................................................................................................................ 10.2 FONCTION DE COÛT À OPTIMISER......................................................................................................................... 10.3 DÉCOMPOSITION ET OPTIMISATION ÉLÉMENTAIRE DES REQUÊTES....................................................................... 10.4 LOCALISATION DES DONNÉES.............................................................................................................................. 10.5 ALGORITHME ÉLÉMENTAIRE................................................................................................................................ 10.6 OPTIMISATIONS POSSIBLES................................................................................................................................... 10.7 ALGORITHMES DE SSD1..................................................................................................................................... 10.8 ALGORITHME DE R*............................................................................................................................................ 11. CONCLUSION ET PERSPECTIVES.............................................................................................................. 12. RÉFÉRENCES ET BIBLIOGRAPHIE........................................................................................................... Chapitre V BASES DE DONNƒES RƒPARTIES ET RƒPLIQUƒES Ç Distributed database systems technoology is one of the major recent developments in the database system area. There are claims that in the next ten years centralized database managers will be an Ç antique curiosity È and most organizations will move toward distributed database managers. È M. Tamer …zsu, Patrick Valduriez, in […zsu91]. V.1.INTRODUCTION Les systmes de gestion de bases de donnŽes rŽparties ont ŽtŽ inventŽs ˆ la fin des annŽes 70 afin d’intŽgrer les bases de donnŽes et les rŽseaux. Le premier grand projet fut SDD1 [Rothnie80] lancŽ en 1976 pour gŽrer des donnŽes embarquŽes sur les bateaux de la Navy amŽricaine. En France, ˆ la suite du projet Cyclades qui construisit le premier rŽseau national, fut lancŽ le projet Sirius [Litwin82] ds 1977. Dans la mme pŽriode a ŽtŽ lancŽ le projet Ingres/Star ˆ Berkeley [Stonebraker77], puis un peu plus tard le projet R* au centre de recherche d’IBM ˆ San-JosŽ (* signifie N systmes R interconnectŽs). Ces projets ont en gŽnŽral abouti ˆ des produits dont les reprŽsentants sont aujourd’hui les versions distribuŽes de Oracle, Ingres ou Sybase. Au milieu des annŽes 80, l’intŽrt des chercheurs s’est dŽplacŽ vers les systmes hŽtŽrognes, avec par exemple Multibase [Landers82], MRDSM [Litwin87], ou encore Sabrina-Star [BrŽant90]. Aujourd’hui, une nouvelle gŽnŽration de systmes basŽs sur le modle objet et une coopŽration plus l‰che est en train de na”tre dans les laboratoires [Burkhres94]. La fŽdŽration de bases de donnŽes existantes est une nŽcessitŽ pour un grand nombre d’entreprises. En effet, il faut souvent accŽder de manire intŽgrŽe ˆ des donnŽes dissŽminŽes sur les diffŽrents calculateurs du sige et des usines. Plus prŽcisŽment, il faut offrir un systme de gestion intŽgrant des sources de donnŽes hŽtŽrognes en assurant la transparence ˆ la distribution et ˆ l’hŽtŽrogŽnŽitŽ, ceci afin de faciliter les dŽveloppements pour l’utilisateur. Avec les grands rŽseaux internationaux tels Internet, le besoin de fŽdŽration de donnŽes hŽtŽrognes (tables, textes, documents audio-visuel, gŽomŽtrie, cartes, etc.) est immense. La recherche en bases de donnŽes rŽparties — dont un des aboutissement est dŽjˆ le client-serveur — a donc encore un bel avenir. Dans ce chapitre, nous apportons une synthse des techniques connues et implŽmentŽes dans les systmes d’aujourd’hui. Nous prŽcisons dans la section 2 ce qu’est une base de donnŽes rŽparties et dŽfinissons les diffŽrents termes qualifiant souvent des variantes. La section 3 est centrŽe sur les objectifs des SGBD rŽpartis ; elle mne naturellement ˆ la section 4 qui introduit une architecture type de systme. La section 5 aborde les problmes de conception de bases rŽparties et prŽcise les diffŽrents moyens de distribuer une table. La section 6 aborde les problmes de gestion de transactions atomiques. Les protocoles de validation en deux et trois Žtapes sont dŽcrits. Cette section conduit ˆ examiner dans la section suivante l’architecture de systme transactionnel DTP qui supporte le protocole XA et l’implŽmentation des moniteurs transactionnels. La section 8 dŽveloppe les principales techniques de contr™le de concurrence adaptŽes aux systmes rŽpartis. Puis, la section 9 aborde les mŽthodes de rŽplication l‰che qui sont aujourd’hui en plein dŽveloppement au niveau des produits. Nous terminons le chapitre par la section 10 — qui prŽcde bien sžr la conclusion Žtablissant un bilan et Žvoquant les perspectives nouvelles — en analysant les techniques d’optimisation de requtes, leurs fondements et quelques algorithmes reprŽsentatifs, plus particulirement ceux de SDD1 et R*. V.2.QU’EST-CE-QU’UNE BDR ? Dans cette section, nous prŽcisons et illustrons le concept de base de donnŽes rŽpartie (BDR). Nous introduisons les diffŽrentes formes possibles de coopŽration de bases de donnŽes. 2.1DŽfinition et exemple Une base de donnŽes rŽpartie permet de rassembler des ensembles de donnŽes plus ou moins hŽtŽrognes, dissŽminŽs dans un rŽseau d’ordinateurs, sous forme d’une base de donnŽes globale, homogne et intŽgrŽe. Une dŽfinition classique est donnŽe ci-dessous. Notion 1 : Base de donnŽes rŽpartie (Distributed database) Ensemble de bases de donnŽes gŽrŽes par des sites diffŽrents et apparaissant ˆ l'utilisateur comme une base unique. Une base de donnŽes rŽpartie peut aussi tre vue comme une collection de bases de donnŽes logiquement reliŽes, distribuŽes sur un rŽseau. Cependant, la dŽfinition prŽcŽdente est plus complte, car elle insiste sur le fait que la base rŽpartie doit appara”tre comme une base unique ˆ l’utilisateur. Afin d’illustrer, considŽrons un rŽseau d’ordinateurs localisŽs ˆ Paris, Dijon et Bordeaux. Chaque ordinateur est muni d’un SGBD, supposŽ relationnel pour simplifier. L’ensemble est utilisŽ pour gŽrer une coopŽrative vinicole, afin de gŽrer les commandes des clients, appelŽs pour l’exemple buveurs. Les vins sont produits par des producteurs ˆ Dijon (rŽgion Bourgogne) et ˆ Bordeaux (rŽgion Bordelais). Les commandes sont passŽes par les buveurs depuis Paris aux producteurs. La figure 1 illustre une rŽpartition possible des donnŽes. Figure 1 — Exemple de donnŽes rŽparties. 2.2SchŽma global Comme toute base de donnŽes, une base de donnŽes rŽpartie possde un schŽma appelŽ schŽma global qui permet de dŽfinir l’ensemble des types de donnŽes de la base. Par exemple, le schŽma global de la base de donnŽes rŽpartie prŽsentŽe en exemple ci- dessus est dŽfini figure 2. Il s’agit d’une vision relationnelle de la base. Une vision plus conceptuelle, en termes d’entitŽ et d’association est donnŽe figure 3. Le schŽma global ignore les concepts d’implŽmentation. A ce titre, il est souvent appelŽ schŽma conceptuel. Dans une base de donnŽes rŽpartie, le schŽma global ou conceptuel n’est pas forcŽment matŽrialisŽ. Chaque base locale implŽmente une partie. Ces parties locales sont les seules matŽrialisŽes sur des disques. BUVEURS (NB, NOM, PRƒNOM, VILLE) COMMANDES (NB, NV, DATE, QTƒ) VINS (NV, CRU, ANNƒE, DEGRƒ) PRODUCTEURS (NP, NOM, RƒGION) PRODUIT (NV, NP, QTƒ) Figure 2 — Exemple de schŽma global relationnel. Figure 3 — SchŽma global associŽ entitŽ-association. 2.3Quelques dŽfinitions de base Nous prŽcisons maintenant les composants essentiels nŽcessaires pour gŽrer des bases de donnŽes rŽparties. Le Systme de Gestion de Bases de DonnŽes RŽparties (SGBDR) cache aux applications l’existence de multiples bases. Il fournit aux clients du SGBDR l’illusion que l’ensemble des bases gŽrŽes par les serveurs du SGBDR est intŽgrŽ en une base unique. Notion 2 : SGBD rŽparti ou SGBDR (Distributed DBMS ou DDBMS) Systme qui gre des collections de BD logiquement reliŽes, distribuŽes sur un rŽseau, en fournissant un mŽcanisme d'accs qui rend la rŽpartition transparente aux utilisateurs. Notion 3 : Client de SGBDR (DDBMS client) Application qui accde aux informations distribuŽes par les interfaces du SGBDR. Notion 4 : Serveur de SGBDR (DDBMS server) SGBD gŽrant une base de donnŽes locale intŽgrŽe dans une base de donnŽes rŽpartie. Au-delˆ des notions de client de SGBDR et de serveur, un calculateur gŽrant la base est appelŽ noeud ou site. Un site peut tre ˆ la fois client et serveur du SGBDR : il exŽcute des applications et gre une partie de la base. C’est sans doute le cas le plus frŽquent. Notion 5 : Noeud ou Site de SGBDR (DDBMS node ou site) Calculateur dans le rŽseau participant ˆ la gestion d’une base de donnŽes rŽpartie. En uploads/Management/ cs-reparti.pdf