BD parallèles et réparties

Département de génie logiciel et des TI

LOG660 - Bases de données de haute performance

BD parallèles et réparties


BD parallèles vs réparties

■ BD réparties– Les données se trouvent sur plusieurs sites (noeuds) – Chaque site possède un certain degré d’autonomie

■ BD parallèles– Exploitent le parallélisme à l’intérieur d’un même site– Peuvent utiliser plusieurs processeurs et/ou disques

© R. Godin, C. Desrosiers - Hiver 2011 2

Département de génie logiciel et des TI © R. Godin, C. Desrosiers - Hiver 2011 3

Bases de données réparties

Réseau

Logicielintermédiaire

Pilote detélécommunication

SGBD réparti

Serveur dedonnées



Programmed'application

Client

Réseau



SGBD réparti

Serveur dedonnées

BDlocale

BDlocale

■ BD répartie dans deux sites■ Chaque site peut avoir une architecture parallèle


Bénéfices de BD réparties

■ Performance– Coûts de transfert réduits en rapprochant les données de leurs

traitements■ Ex: clients des succursales de Montréal dans une BD située à

Montréal– Parallélisme entre les sites (peu évident en pratique)

■ Fiabilité et disponibilité– En cas de panne, les autres sites peuvent assurer la disponibilité

des données

■ Extensibilité (scalabilité)– Si les besoins en stockage et calcul augmentent, on peut rajouter

un nouveau noeud, au lieu de remplacer le serveur


Complexité des BD réparties

■ Transparence de la répartition– Les applications ne doivent pas se soucier du fait que les données

sont réparties sur plusieurs sites– Les nœuds peuvent avoir des schémas/SGBD différents– Répartition du dictionnaire de données

■ Gestion des transactions réparties– Maintenir les propriété d’atomicité, isolation et durabilité des

transactions est plus complexe dans un contexte réparti

■ Évaluation de requêtes réparties– Les plans d’exécution doivent tenir compte

■ Localisation des données sur chaque site■ Coût de transfert des données


Architectures réparties

1. SGBD répartis homogènes

2. Multi-SGBD

3. SGBD fédérés


SGBD répartis homogènes

■ Toutes les BD suivent un même schéma et utilisent la même technologie (ex: Oracle)

■ Accès aux données et gestion des transactions réparties souvent fait de manière centralisée

■ Plus grande fiabilité et performance dû à un meilleure couplage entre les sites

Site 1(Oracle)

Application 2

Site 2(Oracle)

Application 1

Application 3


Multi-SGBD

■ Chaque site est autonome et peut avoir un SGBD de type différent■ Aucun interface (ex: schéma conceptuel) commun■ Accès aux données fait à partir de requêtes ad-hoc spécialisées■ Peut devenir très complexe à gérer

Site 1(Oracle)

Application 2

Site 2(MySQL)

Application 1

Application 3


SGBD fédérés

■ Intègre plusieurs SGBD autonomes et potentiellement hétérogènes en une seule BD virtuelle

■ Interface d’accès commun pour masquer l’hétérogénéité des BD et la répartition des données

■ Mécanismes de coordination communs (ex: protocole XA 2-phases)

Site 1(Oracle)

Application 2Site 2(MySQL)Application 1

Application 3Interface d’accès commun

BD répartie virtuelle


SGBD fédérés

■ Application type: – Consolidation des données après la fusion/acquisition de

compagnies

■ Inconvénients: – Intégration du schéma– Réécriture des requêtes complexes – Performance limitée.

■ Produits commerciaux: – IBM InfoSphere Federation Server, Oracle Data Service Integrator,

etc.


Architecture des schémas

Schémaexterne

Schémaexterne

Schémaexterne...

Schémaconceptuel

global

Schéma delocalisation

Schémalocal

Schémalocal

Schémalocal...

Applications

BD réparties

BD distribuée


Duplication répartie

■ Copie partielle ou totale d’une ou plusieurs tables maîtresses situées sur des sites distants

■ Accès plus rapide aux données car moins de transferts ■ Redondance assure la disponibilité des données si une des

copies n’est plus accessible■ Permet de contrôler l’accès en limitant les données distantes qui

sont accessibles localement ■ La synchronisation entre la table maîtresse et sa copie locale

peut être synchrone ou asynchrone


Duplication répartie

■ Duplication synchrone (synchronous replication)– La sérialisabilité est assurée sur l’ensemble des noeuds– Une transaction est confirmée seulement lorsque tous les sites ont

été mis à jour

■ Duplication asynchrone (asynchronous replication)– Les mises-à-jour sont d’abord faites sur une copie primaire– Les sites de réplication sont mis-à-jour en différé, à partir de la

copie primaire, après la confirmation de la transaction– Ex. d’implémentation: vues matérialisées


Fragmentation répartie

■ Découpe une table en fragments répartis sur plusieurs sites■ Co-localisation des données avec leurs traitements■ Favorise l’extensibilité du système (vs données centralisées)

■ Deux types de fragmentation:1. Fragmentation horizontale2. Fragmentation verticale


■ Fragmentation horizontale

– Chaque fragment contient un sous-ensemble de lignes– Ex: comptes des clients de Montréal sur le site de Montréal



Tablecol 1 col 2 col 3 col 4 col 5 col 6 col 1 col 1 col 1

Fragment 2…

Fragment 1



■ Fragmentation verticale

– Chaque fragment contient un sous-ensemble de colonnes– Ex: la colonne des salaires sur le site de la comptabilité– Moins utilisé que la fragmentation horizontale

Tablecol 1 col 2 col 3 col 4 col 5 col 6 col 1 col 1 col 1

Fragment 1 Fragment 2 …


Transactions réparties

Gestionnaire detransaction

Transactionsréparties

Gestionnaire del'ordonnancement

Gestionnaire dedonnées

BD et journal

Sitecoordonnateur

Gestionnaire detransaction

Gestionnaire del'ordonnancement

Gestionnaire dedonnées

BD et journal

Site participant

Site coordonnateur:À l’origine de la transaction répartie

Site participant: Coopère avec le gestionnaire de transaction du site coordonnateur


Protocole de confirmation en deux phases(Two-phase commit – 2PC)

Début

Ecrire préparer au journal Début

Attente

Préparer à confirmer

Ecrire prêt au journal (vider tampons journal)

Prêt

Site coordonnateur (usager) Site participant (données)

Vote OK

Tous ont répondu OK

Confirmer

Ecrire confirmer au journal

Confirmé

Oui

Non Ecrire annuler au journal

Annuler

Annulé

Confirmer?

Ecrire confirmer au journal

Ecrire annuler au journal

Confirmé Annulé

Oui Non

Accepter

Accepter

Ecrire fin de la transaction au journal


Protocole de confirmation en deux phases(Two-phase commit – 2PC)

■ Phase 1: demande de confirmation– Le coordonnateur demande aux participants de confirmer ou

infirmer le succès des transactions locales ■ Phase 2: confirmation

– Le coordonnateur reçoit les réponses des sites participants– Si tous les participants ont confirmé le succès, le coordonnateur

autorise les participants à compléter les transactions locales (écriture du commit dans leur journal)

– Sinon, le coordonnateur demande aux participants d’annuler les transactions locales

■ Note: les ressources sont bloquées (verrous) durant l’attente de la confirmation



Optimisation de requête répartie

■ Requêtes répartie vs locales – Requête locale: le principal coût provient des écritures et lectures

(E/S) en mémoire secondaire (ex: disques durs)– Requête répartie: le coût des E/S peut être inférieur à celui des

transferts de données entre les sites

■ Parallélisme intra-opération– Parallélisation des sélections, jointures, etc.– Rarement avantageux dans les architectures réparties

■ Parallélisme inter-opération– Calcule simultanément plusieurs opérations d’une même requête– Plus avantageux dans le contexte réparti


Étapes d’optimisation

Décomposition

Requête (ex:SQL)

Schémaconceptuel &externe global

Requête interneglobale

Localisationdes données

Requête surfragments

Optimisationglobale

Schéma delocalisation

Plan d'exécutionréparti

Statistiques surfragments

Optimisation locale

Plan d'exécutionlocal

Shéma internelocal & statistiques

Sitecoordonnateur

Site participant


Optimisation globale (sans parallélisme)

Plan 1 : Transférer T1 au site 2 T1 ⋈ T2 = R au site 2 Transférer R au site 3 R ⋈ T3 = Résultat final au site 3

Plan 2 : Transférer T2 au site 1 T1 ⋈ T2 = R au site 1 Transférer R au site 3 R ⋈ T3 = Résultat final au site 3

Plan 3 : Transférer T1 au site 3 Transférer T2 au site 3 T1 ⋈ T2 ⋈ T3 = Résultat final au site 3

■ Exemple: jointure entre les tables T1, T2 et T3

■ Chaque site Si contient une seule table Ti

Règle:Transférer la plus petite table d’abord


Stratégie par semi-jointurePlan 1 (sans optimisation) :

Transférer T2 au site 1 T1 T2 = Résultat final au site 1

Plan 2 (stratégie par semi-jointure): Transférer πA(T2) au site 1 T1 πA(T2) (= T1 T2) = R au site 2 Transférer R au site 2 R T2 = Résultat final au site 2

■ Stratégie: – Transférer au site 1 seulement les colonnes de T2 nécessaires à la

semi-jointure (ensemble A)– Renvoyer ensuite au site 2 le résultat de la semi-jointure pour

compléter la jointure avec les autres colonnes – Note: le nombre de lignes de T1! T2 doit être petit comparé au

nombre de lignes de T2: taille de πA(T2) + taille de R < taille de T2


Parallélisme inter-opération et inter-site

■ Opération : T1 ! T2 ! T3 ! T4

Transférer T2 au site 1T1 ! T2 = R au site 1

En parallèle, transférer T4 au site 3T3 ! T4 = S au site 3Transférer S au site 1

Ensuite, R ! S = Résultat final au site 1


BD répartie avec Oracle (DATABASE LINKS)

■ Permet à un usager local d’accéder aux tables d’une autre BD sans qu’il soit usager de cette BD

■ Syntaxe:

– SHARED: permet de partager la connexion entre plusieurs usagers– PUBLIC : rend le lien disponible à tous les usagers locaux– nomService : doit être défini dans un fichier de configuration de la

BD

CREATE [SHARED] [PUBLIC] DATABASE LINK nomLienCONNECT TO compteUsager IDENTIFY BY motDePasseUSING nomService


BD répartie avec Oracle (DATABASE LINKS)

■ Exemple: accès au catalogue de produits en Grande-Bretagne

CREATE DATABASE LINK site.europe.ukCONNECT TO Compte14 IDENTIFY BY ”abc123” USING SID_siteUK

SELECT * FROM [email protected]


■ Synonyme– Évite aux applications de devoir connaître la localisation des

données (transparence de localisation)– Permet de conserver les mêmes requêtes, même si le lien change

■ Exemple (suite):


Transparence de localisation (SYNONYM)

CREATE [PUBLIC] SYNONYM nomSynonymeFOR [nomSchéma].nomObjet[@lienBD]

CREATE SYNONYM CatalogueEuropeFOR [email protected]

SELECT * FROM CatalogueEuropeWHERE ...


Duplication avec vues matérialisées

■ Syntaxe:

– FAST: mise-à-jour incrémentale de la copie locale– COMPLETE: mise-à-jour complète de la copie locale à chaque

rafraîchissement– FORCE: mise-à-jour incrémentale lorsque possible, sinon complète– ON COMMIT: rafraîchissement lorsqu’une transaction modifiant les

tables maîtresses fait un commit– ON DEMAND (défaut): rafraîchissement sur demande de l’usager

(l’instant peut être spécifié avec les clauses START et NEXT)– FOR UPDATE: permet de mettre à jour la copie locale (les changements

sont propagés aux tables maîtresses)

CREATE MATERIALIZED VIEW nomVue[REFRESH {FAST|COMPLETE|FORCE} [ON COMMIT|ON DEMAND]][FOR UPDATE]


Duplication avec vues matérialisées

■ Exemple: copie locale du catalogue européen

CREATE MATERIALIZED VIEW CatalogueCompletREFRESH FAST ON COMMITAS(SELECT * FROM [email protected]) UNION(SELECT * FROM CatalogueCanada)

SELECT * FROM CatalogueCompletWHERE ...


Bases de données parallèles

■ Exploitation du parallélisme intrasite■ Parallélisme de disques et d’unités de traitement

■ Améliorent la fiabilité en dupliquant les données (ex: disques miroirs)

■ Augmentent la performance en permettant de traitement en parallèle des requêtes

Mémoire viveUnité detraitement

Disque Disque Disque Disque Disque


Parallélisme de disque

■ Disques miroirs:– Les données d’un disque maître sont dupliquées sur un autre

disque

■ Code détecteur/correcteur d ’erreur– Utilise un certain nombre de bits dans les données pour

détecter une corruption et possiblement la corriger– Ex: bit de parité, code de Hamming

■ Répartition cyclique (striping)– Améliore la performance en lecture/écriture par l’utilisation

de plusieurs disques en parallèle– Répartit les données sur plusieurs disques, soit par bit (bit-level

striping) ou par bloc (bloc-level striping)

A A


Architectures RAID (Redundant Array of Independent Disks )

■ RAID 0– Répartition par bloc

■ RAID 1– Disques miroirs

■ RAID 2– Codes correcteurs (ex: Hamming)– Moins de disque que 1

■ RAID 3– Répartition par bit (ou octet)– Un disque de parité (détection)– Récupération d’une faute d’un

disque■ RAID 4

– Répartition par bloc– Disque de parité

■ RAID 5 – Répartition par bloc– Blocs de parité répartis– Permet les écritures parallèles

■ RAID 6– Répartition par bloc– Codes correcteurs répartis

Bloc 0Bloc 4Bloc 8

...

Bloc 1Bloc 5Bloc 9

...

Bloc 2Bloc 6Bloc 10

...

Bloc 3Bloc 7Bloc 11

...

Raid 0 : Répartition par bloc

A A B B

Raid 1 : Mirroirs

A1B1C1

A2B2C2

A3B3C3

A4B4C4

Raid 2 : Codes correcteurs d’erreurs

CCEA1CCEB1CCEC1

CCEA2CCEB2CCEC2

CCEA3CCEB3CCEC3

Bit 0Bit 4Bit 8

...

Bit 1Bit 5Bit 9

...

Bit 2Bit 6Bit 10

...

Bit 3Bit 7Bit 11

...

Raid 3 : Répartition par bit + parité

Parité

Bloc 0Bloc 4Bloc 8

...

Bloc 1Bloc 5Bloc 9

...

Bloc 2Bloc 6Bloc 10

...

Bloc 3Bloc 7Bloc 11

...

Raid 4 : Répartition par bloc + parité

Parité

ParitéBloc 4Bloc 8

Bloc 12Bloc 16

Bloc 0ParitéBloc 9

Bloc 13Bloc 17

Bloc 1Bloc 5Parité

Bloc 14Bloc 18

Bloc 2Bloc 6Bloc 10Parité

bloc 19

Raid 5 : Répartition par bloc + parité répartie

Bloc 3Bloc 7

Bloc 11Bloc 15Parité

Bloc 0Bloc 2Bloc 4

...

Bloc 1Bloc 3Bloc 5

...

Bloc 0Bloc 2Bloc 4

...

Bloc 1Bloc 3Bloc 5

...

Raid 0+1


Principales architectures RAID

■ RAID 1:– Duplication complète des données à l’aide de disques miroirs– Très haut niveau de fiabilité au coût d’un espace disque important– Met l’emphase sur la fiabilité, pas la performance

■ RAID 0+1:– Combine la répartition par bloc de RAID 0 avec les disques miroirs

de RAID 1– Offre fiabilité et performance, mais demande beaucoup d’espace

■ RAID 5:– Répartition par blocs (sans duplication) avec bits de parité répartis– Offre la performance et une certaine fiabilité (détection d’erreur),

sans exiger beaucoup d’espace


Fragmentation de tables (contexte parallèle)

■ Découpe une grosse table en morceaux plus facilement gérables■ Très utilisée dans les entrepôts de données■ Permet le parallélisme intra-opérations (ex: accélération des balayages,

sélections, jointures, etc.)■ Partitionnement par intervalles de valeur:

– Ex: partitionnement de transactions selon l’année – Accélère les sélections par valeurs et par intervalles de valeurs sur la

clé de partitionnement■ Partitionnement par hashage sur la clé

– Ex: hashage de la clé primaire de la table– Assure une distribution uniforme des lignes dans les partitions– Accélère uniquement les sélections par valeur sur la clé de

partitionnement


Partitionnement par intervalles de valeurs■ Exemple: partitionnement selon la date de transaction

CREATE TABLE Transaction (id INTEGER INTEGER NOT NULL,idClient INTEGER NOT NULL,idProduit INTEGER NOT NULL,jour INTEGER DATE NOT NULL,...)PARTITION BY RANGE(jour)( PARTITION P1999ouMoins VALUES LESS THAN TO_DATE(’01/2000’,’MM/YYYY’)

TABLESPACE TS1999ouMoinsPARTITION P2000 VALUES LESS THAN TO_DATE(’01/2001’,’MM/YYYY’)

TABLESPACE TS2000PARTITION P2001 VALUES LESS THAN TO_DATE(’01/2002’,’MM/YYYY’)

TABLESPACE TS2001 );

-- Acces a la partition des transactions de 2001 à 2002SELECT * FROM Transaction PARTITION(P2001);

-- Ajout d’une partitionALTER TABLE Transaction ADD PARTITION (PARTITION P2002 VALUES LESS THAN

TO_DATE(’01/2003’,’MM/YYYY’) TABLESPACE TS2002);


Sélection parallèle

Fragment 1

Sélectionlocale

Fragment 2

Sélectionlocale

Fragment 3

Sélectionlocale

Sélectionglobale

■ On sélectionne les lignes simultanément dans chaque fragment■ On concatène les lignes obtenues de chaque fragment■ Si la sélection se fait par rapport à la clé de partitionnement:

– On peut ignorer les fragments dont l’intervalle (ou la valeur de hashage) ne contient pas les valeurs recherchées


Jointure parallèle ■ Conditions préalables:

– Les tables R et S ont été partitionnées selon la même clé– La jointure est faite selon cette clé

■ On limite la jointure aux paires de lignes dans les fragments ayant la même valeur pour la clé:

■ Similaire à la jointure par hashage (HASH JOIN)

JointurelocaleFragment 1 R

Fragment 2 R

Fragment 3 R

Fragment 1 S

Fragment 2 S

Fragment 3 S

Jointurelocale

Jointurelocale


Autres formes de parallélisme

■ Plusieurs processeurs

■ Plusieurs unités de mémoire■ Duplication des processus SGBD

– Processus miroirs pour fiabilité


Architecture à mémoire partagée (Symmetric MultiProcessor – SMP)

Disque Disque Disque Disque

Unité detraitement

Unité detraitement

Unité detraitement

Disque

Mémoire vive

■ Plusieurs processeurs qui partagent la même mémoire centrale■ Mécanisme d’interconnexion très rapide (bus de données)■ Processus parallèles communiquent rapidement à travers la mémoire

centrale partagée (goulot d’étranglement)


Architecture à disques partagés

Disque Disque Disque Disque

Unité detraitement

Unité detraitement

Unité detraitement

Disque

Mémoire vive Mémoire vive Mémoire vive

Unité detraitement

Mémoire vive

■ Chaque unité de traitement possède sa propre mémoire vive■ Les disques sont partagés entre les unités de traitement■ Évite le goulot d’étranglement au niveau de la mémoire, mais

complexifie la communication entre les processus■ Ex: architecture en grappe (cluster) - À NE PAS CONFONDRE AVEC

LES TABLE CLUSTERS

Documents

BD parallèles et réparties