Chapitre 7 bda Bases de données avancées Télécharger pdf

Télécharger PDF

Introduction aux Transactions Distribuées

Les objectifs du traitement des transactions distribuées sont les mêmes que ceux des systèmes centralisés. Cependant, la complexité est accrue du fait que le Système de Gestion de Bases de Données Distribuées (SGBDD) gère à la fois des transactions locales et globales.

Rappel : une transaction est une unité logique et indivisible de traitement, balisée par des instructions telles que "Begin Transaction" et "End Transaction". Les transactions possèdent les propriétés ACID (Atomicité, Cohérence, Isolation, Durabilité), garantissant leur exécution fiable.

Types de Transactions

Transaction locale (TL) : Initiée par un utilisateur local et soumise directement au SGBD local.
Transaction globale (TG) : Initiée par un utilisateur global et soumise via l’interface du SGBDD.

Le SGBDD dispose d'une composante qui assure la gestion des transactions globales, appelée « Gestionnaire de Transactions Globales » (GTM).

Décomposition d'une Transaction Globale

Une transaction globale (TG) est décomposée par le GTM en plusieurs sous-transactions (TGi1, TGi2, ... TGen) qui sont exécutées sur différents Systèmes de Gestion de Bases de Données Locaux (SGBDL). Le GTM est responsable du contrôle de la concurrence et de l'atomicité globale de cette transaction distribuée.

Ordonnancement des Transactions Distribuées

La gestion de la concurrence dans un SGBDD requiert deux types d’ordonnancement : local et global.

Ordonnancement local

L'ordonnancement local modélise la concurrence des sous-transactions globales et des transactions locales au sein de chaque SGBDL. La détermination de l'ordre local d'exécution est un point central, mais la nature distribuée du SGBDD rend difficile la communication de cet ordre au système global.

Ordonnancement global

L’ordonnancement global modélise l’intégration des exécutions des différents SGBDLs. L’ordre global est l’union des ordres relatifs aux ordonnancements local et global.

Notion de Conflits

Le GTM doit gérer deux types de conflits :

Conflits classiques (ou directs) : Ils surviennent entre transactions globales et impliquent l’accès à une même donnée par les actions de deux transactions différentes.
Conflits indirects : Causés par l’entrelacement de transactions globales avec des transactions locales sur chaque site. Le GTM ne peut pas toujours les détecter, car les transactions locales s’exécutent en dehors de son contrôle direct.

Sérialisabilité Globale

Une exécution globale est dite sérialisable si elle produit les mêmes résultats et possède les mêmes effets sur la base de données qu’une exécution globale série des mêmes transactions.
Une exécution globale série est une exécution pour laquelle, si des transactions sont ordonnancées (par exemple, TG1 avant TG2), les actions de TG1 s'exécutent entièrement avant les opérations de TG2.
Un ordonnancement global est dit globalement sérialisable si et seulement si il existe un ordre total des transactions globales validées qui est consistant avec l’ordre de sérialisation des transactions validées sur chaque site.

Exemple de Sérialisabilité

Soient deux transactions globales TGi et TGj. Si l'ordre global spécifié est TGi avant TGj :

Alors, pour toute sous-transaction TGi1 de TGi au site S1, et TGj1 de TGj au site S1, on doit avoir TGi1 < TGj1 (TGi1 avant TGj1). Ce principe s'applique à tous les sites Sx où TGi et TGj ont des sous-transactions (TGix < TGjx).

Problèmes liés à l’Autonomie des SGBDLs

La plupart des problèmes de gestion de la concurrence dans les bases de données distribuées proviennent du maintien de l’autonomie des SGBDLs (Systèmes de Gestion de Bases de Données Locaux).
Certains chercheurs ont proposé des approches qui réduisent l'autonomie en soumettant les transactions locales (TLs) au contrôle du SGBD global, au même titre que les transactions globales (TGs).
D’autres ont proposé de relâcher le contrôle global et d'utiliser un ordonnancement local à deux phases.
Un ordonnancement global est sérialisable si l’ordonnancement local de chaque SGBDL l'est également.

Techniques de Gestion des Accès Concurrents

1. Les Techniques d’Estampillage

L'ordre de sérialisation est obtenu par l'assignation d'une estampille unique à chaque transaction.
La gestion des estampilles peut être centralisée, impliquant un composant de gestion des estampilles sur un seul site.
En gestion décentralisée, 2 paramètres sont nécessaires : <estampille, identifiant du site>.
Dans ce dernier cas, il y a le problème de synchronisation des horloges ou des compteurs des différents sites.

Exemple d'Algorithme d’Estampillage :

Soit i l'estampille de la transaction Ti et j l'estampille du granule Gj (estampille de la dernière transaction l'ayant modifié).

Si Ti veut écrire sur le granule Gj :

Si j <= i : La transaction Ti (plus récente ou d'âge égal) peut s’exécuter.
Sinon (j > i, c'est-à-dire une transaction plus ancienne veut écrire un granule déjà mis à jour par une transaction plus récente) : ABORT(Ti) et reprise.

Problème : cette approche peut entraîner des cascades d’annulations (ROLLBACKs).

2. Protocoles de Verrouillage

Plusieurs versions existent : Verrouillage à Deux Phases (V2P) centralisé, V2P à copie primaire, V2P distribué, et Verrouillage à la majorité.

V2P Centralisé

Un seul site conserve et gère toutes les informations de verrouillage.

Pour une transaction globale amorcée au site S1, les actions suivantes sont :

Le coordinateur de transaction du site S1 scinde la transaction globale en sous-transactions à l’aide du catalogue système.
Les gestionnaires de transactions locaux impliqués dans la transaction globale demandent, puis libèrent les verrous exigés, en suivant les règles du protocole de verrouillage centralisé à deux phases.
Le gestionnaire de verrouillage centralisé vérifie la compatibilité de la demande de verrou sur une donnée avec les verrous déjà appliqués.
Si la demande est compatible, le gestionnaire de verrouillage retourne une confirmation. Sinon, il place la requête dans une file d’attente jusqu’à ce que le verrou puisse être accordé.

Avantages :

Mise en place relativement simple.
Un seul gestionnaire de verrouillage traite toutes les informations.
Les coûts de communication sont relativement faibles (pour n sites) :
- 1 demande de verrouillage
- 1 message d’accord de verrouillage
- n messages de mise à jour
- n confirmations
- 1 demande de libération de verrou

Inconvénients :

La centralisation peut impliquer des problèmes d’embouteillage et de fiabilité.
La panne du site central entraîne des pannes systèmes majeures.

V2P à Copie Primaire

Ce protocole est une amélioration du V2P centralisé, en répartissant les gestionnaires de verrouillage sur un certain nombre de sites.

Chaque gestionnaire de verrouillage est responsable des verrous sur un sous-ensemble de données.
Pour chaque donnée dupliquée, une copie est choisie comme copie primaire, les autres devenant des copies esclaves.
Lorsqu’une donnée doit être mise à jour, le coordinateur doit déterminer où se trouve la copie primaire afin d’envoyer la demande de verrouillage au gestionnaire de verrouillage approprié.
Seule la copie primaire est verrouillée exclusivement. Après la mise à jour, celle-ci est propagée sur les copies esclaves.

V2P Distribué

Répartition des gestionnaires de verrouillage sur chaque site.
Avantage : prise en charge des verrous de manière parallèle.
Inconvénients :
- Gestion plus complexe des verrous.
- Coûts de communication plus élevés (5n messages) :
  - n messages de verrouillage
  - n messages d’accord de verrouillage
  - n messages de mise à jour
  - n confirmations
  - n demandes de libération de verrous

Verrouillage à la Majorité

Extension du V2P distribué, en évitant le verrouillage de toutes les copies d’une donnée dupliquée avant une mise à jour.

Quand une transaction souhaite lire ou écrire une donnée répliquée sur n sites, elle doit expédier une demande de verrou à plus de la moitié des sites où la donnée est entreposée.
La transaction ne peut poursuivre que si elle a obtenu le verrou sur une majorité de copies.
Nombre de messages :
- [(n+1)/2] messages de demandes de verrouillage
- [(n+1)/2] messages de demandes de déverrouillage

Détection des Interblocages (Deadlock)

Rappel : Systèmes Centralisés vs Distribués

Dans un système centralisé, on utilise :
- Le graphe d’attente : s'il existe un cycle, il faut « tuer » une transaction (c’est-à-dire l’annuler puis la reprendre).
- Le délai (timeout).
Dans un système distribué, on utilise :
- Le graphe d’attente local.
- Le graphe d’attente global.
- Le délai (timeout).

Remarque : S’il n’existe pas de cycle sur un graphe d'attente local, cela n’implique pas la non-existence d’un cycle global.

Exemple d'Interblocage Distribué

Soient trois transactions T1, T2, T3 :

T1 démarre au site S1 et crée un agent au site S2.
T2 est amorcée au site S2 et crée un agent au site S3.
T3 est amorcée au site S3 et crée un agent au site S1.

Dans ce scénario, des requêtes de verrous peuvent créer un interblocage :

Au site S1 : T3 attend une ressource détenue par T1 (T3 → T1).
Au site S2 : T1 attend une ressource détenue par T2 (T1 → T2).
Au site S3 : T2 attend une ressource détenue par T3 (T2 → T3).

Le graphe d'attente global révèle un cycle : T1 → T2 → T3 → T1, indiquant un interblocage.

Méthodes de Détection de l’Interblocage

Dans un contexte distribué, il ne suffit pas de considérer le graphe d’attente propre à chaque site. Il faut construire un graphe d’attente global, qui est l'union des graphes d’attente locaux. L'existence d'un cycle dans le graphe global implique un interblocage. Trois méthodes de détection de l’interblocage existent :

1. Détection Centralisée

Un seul site est désigné comme Coordinateur de la Détection de Verrou Indéfini (CDVI).
Il a la responsabilité de construire et de maintenir le graphe d’attente global.
Il vérifie la présence de cycles.
S'il y a un cycle, il a la possibilité de le briser en annulant une ou plusieurs transactions sélectionnées.
Le CDVI doit prévenir tous les sites concernés de l’annulation des transactions.

2. Détection Hiérarchique

Les sites du réseau sont structurés en une hiérarchie (arborescence).
Chaque site envoie son graphe d’attente local au site situé juste au-dessus de lui dans la hiérarchie.
Les nœuds d'un niveau supérieur sont responsables de la détection des interblocages impliquant leurs sites subordonnés.
La racine de l’arborescence détecte l'interblocage global.
Cette approche minimise les coûts de communication et la dépendance d’un site.

3. Détection Distribuée

Un nouveau type de nœud est introduit dans les graphes d'attente locaux : « Transaction Extérieure » (TExt).
Un arc TExt → Ti signifie que la transaction extérieure TExt est en attente d’une ressource locale détenue par Ti sur ce site.
Un arc Ti → TExt signifie que la transaction locale Ti est en attente d’une ressource non locale, détenue par une transaction représentée par TExt.
Le graphe global est construit en agrégeant les graphes locaux de chaque site.

Exemple de Détection Distribuée

Soient cinq transactions, T1, T2, T3, T4, T5, avec leurs interactions sur les sites S1, S2, S3.

Initialement, les graphes d’attente locaux peuvent être établis pour chaque site. Voici les dépendances clés observées dans les graphes d'attente locaux :

Site S1 : T2 attend T1 (T2 → T1).
Site S2 : T1 attend T4 (T1 → T4).
Site S3 : T4 attend T2 (T4 → T2).
Site S3 : T3 attend T5 (T3 → T5) et T5 attend T3 (T5 → T3), formant un cycle local T3 ↔ T5.

Conclusion des graphes locaux : Il n’y a pas d’interblocages inter-sites apparents au niveau des sites individuels (sauf T3 ↔ T5 localement sur S3). Cependant, dans un système distribué, ce n’est pas suffisant ; il faut construire le graphe d’attente global, qui est l'union des graphes locaux.

Analyse du graphe d’attente global :

Le graphe global révèle l’existence de plusieurs cycles d'interblocage :

C1 = {T1, T4, T2, T1}
C2 = {T1, T3, T4, T2, T1}
C3 = {T1, T3, T5, T4, T2, T1}

L'intersection de ces cycles est {T1, T2, T4}. La solution consiste à choisir une transaction victime parmi celles-ci pour briser le cycle. Par exemple, si T4 est choisie comme victime (étant la plus récente), T4 sera annulée et relancée à la fin.

Récupération de Bases de Données Distribuées

Objectif : Maintenir l’atomicité et la durabilité des transactions distribuées.

Pour s’assurer de l’atomicité d’une transaction globale, il faut s’assurer que toutes les sous-transactions de la transaction globale soient validées ou s'annulent toutes. Le SGBD doit suivre les étapes suivantes en cas de défaillance :

Annuler toute transaction affectée par la défaillance.
Marquer le site défaillant d’un indicateur l’empêchant d’être utilisé.
Vérifier périodiquement si le site défaillant a retrouvé son état normal. Après récupération, le site diffuse un message indiquant qu’il a récupéré.
Au redémarrage, le site défaillant doit annuler toute transaction active lors de la panne.
Après la récupération locale, le site doit mettre à jour ses données pour lui restituer sa cohérence par rapport au reste du système.

Protocole de Validation à Deux Phases (2PC)

L’étape la plus importante dans la gestion de la validation des transactions, dans un contexte distribué, est celle qui consiste à rendre définitives les mises à jour dans la base de données. Le protocole le plus utilisé pour assurer l’atomicité globale est le protocole de validation en deux phases (2PC).

Ce protocole est exécuté sur chaque site ; il est contrôlé par un Coordinateur ou gestionnaire de transaction. Les sites où la transaction globale a des agents sont appelés participants ou gestionnaires de ressources. Nous supposons que le coordinateur connaît l’identifiant de tous les participants et que chaque participant connaît l’identifiant du coordinateur, mais pas nécessairement tous les autres participants.

Déroulement du 2PC

Le 2PC opère en deux phases :

Phase de vote (Phase 1) : Le coordinateur envoie un message 'PREPARE' aux participants.
Phase de décision (Phase 2) : Si tous répondent 'READY', le coordinateur envoie 'COMMIT'. Sinon, il envoie 'ABORT'.

Phase de Validation (Succès)

La préparation (Phase de vote) :

Le coordinateur demande à tous les participants (sites concernés par la transaction) de se préparer pour la validation.
Il envoie un message ‘PREPARE’ à tous les participants et attend une réponse dans un délai déterminé.
Les participants, s’ils sont prêts à valider, écrivent ‘READY’ dans leur journal local et envoient ‘READY’ au coordinateur.

La validation (Phase de décision) :

Si tous les participants ont répondu ‘READY’, le coordinateur écrit ‘COMMIT’ dans son journal et ordonne aux sites participants de valider les mises à jour (COMMIT).
Il attend que tous les participants confirment la validation dans un délai déterminé (message ‘COMMITTED’).
Dès que toutes les confirmations ont été reçues, le coordinateur écrit un enregistrement de ‘fin de transaction’ dans son journal.

Remarque : Le protocole nécessite la journalisation des mises à jour et des états des transactions dans un journal local à chaque site.

Phase d'Annulation (Échec)

Un site peut, au moment du vote, décider unilatéralement de voter 'ABORT', l’inscrit dans son journal et informe le coordinateur. Ou bien, si le coordinateur ne reçoit pas toutes les réponses 'READY' dans le délai imparti, il prend la décision d'annuler.

Si le coordinateur reçoit un ‘ABORT’ ou n'a pas toutes les réponses ‘READY’, il écrit ‘ANNULATION’ dans son journal et envoie ‘ABORT’ (Annulation globale) à tous les participants.
Les participants reçoivent le message ‘ABORT’, annulent la transaction, écrivent ‘ABORT’ dans leur journal et envoient une confirmation d’annulation au coordinateur.

Gestion de Pannes avec 2PC

Les cas de pannes se présentent sous trois formes principales :

Panne du coordinateur lui-même : Dans ce cas, les sites participants qui se sont déclarés prêts (READY) restent bloqués, d’où le blocage des ressources jusqu’à la reprise du coordinateur. Le protocole 2PC est dit "bloquant" dans cette situation.
Panne d’un des sites participants ou rupture de liaison : Ces deux cas sont traités de manière similaire. Si les accusés de réception ne parviennent pas au coordinateur dans un délai précis, celui-ci considère que la réponse est négative et envoie une annulation (ABORT) à tous les participants.

Protocole de Validation à Trois Phases (3PC)

Afin de résoudre le problème de blocage du 2PC en cas de panne du coordinateur, le protocole a été augmenté d’une nouvelle étape, appelé Protocole de validation en trois phases (3PC).

On rajoute entre l’état « prêt » et l’état « validé » un état intermédiaire appelé « prêt à valider » (PREPARE_TO_COMMIT).
Tous les processus opérationnels peuvent atteindre une décision globale de valider grâce à l'état PREPARE_TO_COMMIT avant que le premier processus ne s'engage à valider.
Si le coordinateur défaille, les sites peuvent communiquer entre eux et déterminer si la transaction doit être validée ou annulée sans attendre que le coordinateur se rétablisse (utilisation d’un algorithme d’élection pour élire un nouveau coordinateur).
Si aucun des sites opérationnels n’a reçu le message PREPARE_TO_COMMIT, alors ils annulent la transaction.

Conclusion

La gestion des accès concurrents dans un système distribué implique la cohabitation de transactions globales et locales, ce qui impacte les protocoles de gestion traditionnels. La sérialisabilité est enrichie par le concept de sérialisabilité globale, complétant la sérialisabilité locale.

Le protocole de verrouillage à deux phases (2PL) est adapté avec un coordinateur et des participants, nécessitant de nouvelles techniques de détection d'interblocages. Le protocole de validation à deux phases (2PC) assure l’atomicité des transactions globales via des échanges de messages spécifiques.

Cependant, le 2PC est bloquant en cas de panne du coordinateur. Le protocole de validation à trois phases (3PC) est une variante qui vise à pallier ces situations en ajoutant une phase intermédiaire de "prêt à valider", permettant une meilleure résilience aux pannes.

Foire Aux Questions (FAQ)

Qu'est-ce qu'une transaction distribuée ?

Une transaction distribuée est une opération logique qui accède et modifie des données réparties sur plusieurs bases de données gérées par des systèmes distincts. Elle doit maintenir les propriétés ACID (Atomicité, Cohérence, Isolation, Durabilité) à travers tous les sites impliqués.

Quelles sont les principales méthodes de contrôle de concurrence dans les bases de données distribuées ?

Les principales méthodes incluent les techniques d'estampillage, qui attribuent un identifiant unique à chaque transaction pour ordonnancer les opérations, et les protocoles de verrouillage à deux phases (2PL), qui peuvent être centralisés, à copie primaire, distribués ou à la majorité, pour contrôler l'accès aux données partagées.

Quels sont les avantages et inconvénients du protocole de validation à deux phases (2PC) ?

Le 2PC garantit l'atomicité des transactions globales, assurant que toutes les sous-transactions soient validées ou annulées collectivement. Son inconvénient majeur est qu'il est "bloquant" : si le coordinateur tombe en panne après la phase de vote mais avant la décision finale, les participants peuvent rester indéfiniment en attente, bloquant ainsi les ressources.