SGBD distribué - Contrôle de la réplication
Ce chapitre examine le contrôle de la réplication, qui est nécessaire pour maintenir des données cohérentes sur tous les sites. Nous étudierons les techniques de contrôle de réplication et les algorithmes nécessaires au contrôle de réplication.
Comme discuté plus tôt, replicationest une technique utilisée dans les bases de données distribuées pour stocker plusieurs copies d'une table de données sur différents sites. Le problème d'avoir plusieurs copies sur plusieurs sites est la surcharge de maintien de la cohérence des données, en particulier pendant les opérations de mise à jour.
Afin de maintenir des données mutuellement cohérentes dans tous les sites, des techniques de contrôle de réplication doivent être adoptées. Il existe deux approches pour le contrôle de réplication, à savoir -
- Contrôle de réplication synchrone
- Contrôle de réplication asynchrone
Contrôle de réplication synchrone
Dans l'approche de réplication synchrone, la base de données est synchronisée afin que toutes les réplications aient toujours la même valeur. Une transaction demandant une donnée aura accès à la même valeur dans tous les sites. Pour garantir cette uniformité, une transaction qui met à jour une donnée élémentaire est développée pour effectuer la mise à jour dans toutes les copies de la donnée élémentaire. Généralement, un protocole de validation en deux phases est utilisé à cette fin.
Par exemple, considérons une table de données PROJECT (PId, PName, PLocation). Nous devons exécuter une transaction T1 qui met à jour PLocation en «Mumbai», si PLocation est «Bombay». S'il n'y a pas de réplication, les opérations de la transaction T1 seront -
Begin T1:
Update PROJECT Set PLocation = 'Mumbai'
Where PLocation = 'Bombay';
End T1;Si la table de données a deux réplicas dans le site A et le site B, T1 doit générer deux enfants T1A et T1B correspondant aux deux sites. La transaction étendue T1 sera -
Begin T1:
Begin T1A :
Update PROJECT Set PLocation = 'Mumbai'
Where PLocation = 'Bombay';
End T1A;
Begin T2A :
Update PROJECT Set PLocation = 'Mumbai'
Where PLocation = 'Bombay';
End T2A;
End T1;Contrôle de réplication asynchrone
Dans l'approche de réplication asynchrone, les réplicas ne conservent pas toujours la même valeur. Un ou plusieurs réplicas peuvent stocker une valeur obsolète et une transaction peut voir les différentes valeurs. Le processus d'amener toutes les répliques à la valeur actuelle est appelésynchronization.
Une méthode populaire de synchronisation est la méthode de stockage et de transfert. Dans cette méthode, un site est désigné comme site principal et les autres sites sont des sites secondaires. Le site principal contient toujours des valeurs mises à jour. Toutes les transactions entrent d'abord sur le site principal. Ces transactions sont ensuite mises en file d'attente pour application dans les sites secondaires. Les sites secondaires sont mis à jour à l'aide de la méthode de déploiement uniquement lorsqu'une transaction est planifiée pour s'exécuter dessus.
Algorithmes de contrôle de réplication
Certains des algorithmes de contrôle de réplication sont -
- Algorithme de contrôle de réplication maître-esclave.
- Algorithme de vote distribué.
- Algorithme de consensus majoritaire.
- Algorithme de jeton de circulation.
Algorithme de contrôle de réplication maître-esclave
Il existe un site maître et des sites esclaves «N». Un algorithme maître s'exécute sur le site maître pour détecter les conflits. Une copie de l'algorithme esclave s'exécute sur chaque site esclave. L'algorithme global s'exécute dans les deux phases suivantes -
Transaction acceptance/rejection phase- Lorsqu'une transaction entre dans le moniteur de transaction d'un site esclave, le site esclave envoie une requête au site maître. Le site maître recherche les conflits. S'il n'y a pas de conflit, le maître envoie un message «ACK +» au site esclave qui démarre alors la phase d'application de la transaction. Sinon, le maître envoie un message «ACK-» à l'esclave qui rejette alors la transaction.
Transaction application phase- En entrant dans cette phase, le site esclave où la transaction est entrée diffuse une requête à tous les esclaves pour l'exécution de la transaction. A la réception des demandes, les esclaves homologues exécutent la transaction et envoient un «ACK» à l'esclave demandeur à la fin. Une fois que l'esclave demandeur a reçu des messages «ACK» de tous ses pairs, il envoie un message «DONE» au site maître. Le maître comprend que la transaction est terminée et la supprime de la file d'attente en attente.
Algorithme de vote distribué
Cela comprend «N» sites homologues, qui doivent tous «OK» une transaction avant qu'elle ne commence à s'exécuter. Voici les deux phases de cet algorithme -
Distributed transaction acceptance phase- Lorsqu'une transaction entre dans le gestionnaire de transactions d'un site, celui-ci envoie une demande de transaction à tous les autres sites. À la réception d'une demande, un site homologue résout les conflits à l'aide de règles de vote basées sur la priorité. Si tous les sites homologues sont «OK» avec la transaction, le site demandeur démarre la phase de candidature. Si l'un des sites homologues ne «valide» pas une transaction, le site demandeur rejette la transaction.
Distributed transaction application phase- En entrant dans cette phase, le site où la transaction est entrée, diffuse une demande à tous les esclaves pour l'exécution de la transaction. A la réception des requêtes, les esclaves homologues exécutent la transaction et envoient un message «ACK» à l'esclave demandeur à la fin. Une fois que l'esclave demandeur a reçu des messages «ACK» de tous ses homologues, il informe le gestionnaire de transactions que la transaction est terminée.
Algorithme de consensus majoritaire
Il s'agit d'une variante de l'algorithme de vote distribué, dans lequel une transaction est autorisée à s'exécuter lorsqu'une majorité des pairs «OK» une transaction. Ceci est divisé en trois phases -
Voting phase- Lorsqu'une transaction entre dans le gestionnaire de transactions d'un site, celui-ci envoie une demande de transaction à tous les autres sites. À la réception d'une demande, un site homologue teste les conflits à l'aide de règles de vote et conserve les transactions en conflit, le cas échéant, dans la file d'attente. Ensuite, il envoie un message «OK» ou «PAS OK».
Transaction acceptance/rejection phase- Si le site demandeur reçoit une majorité «OK» sur la transaction, il accepte la transaction et diffuse «ACCEPTER» sur tous les sites. Dans le cas contraire, il diffuse «REJECT» à tous les sites et rejette la transaction.
Transaction application phase- Lorsqu'un site pair reçoit un message «REJETER», il supprime cette transaction de sa liste en attente et reconsidère toutes les transactions différées. Lorsqu'un site homologue reçoit un message «ACCEPTER», il applique la transaction et rejette toutes les transactions différées dans la file d'attente en attente qui sont en conflit avec cette transaction. Il envoie un «ACK» à l'esclave demandeur à la fin.
Algorithme de jeton de circulation
Dans cette approche, les transactions dans le système sont sérialisées à l'aide d'un jeton en circulation et exécutées en conséquence contre chaque réplique de la base de données. Ainsi, toutes les transactions sont acceptées, c'est-à-dire qu'aucune n'est rejetée. Cela comporte deux phases -
Transaction serialization phase- Dans cette phase, toutes les transactions sont planifiées pour s'exécuter dans un ordre de sérialisation. Chaque transaction dans chaque site se voit attribuer un ticket unique d'une série séquentielle, indiquant l'ordre de la transaction. Une fois qu'un ticket a été attribué à une transaction, elle est diffusée sur tous les sites.
Transaction application phase- Lorsqu'un site reçoit une transaction avec son ticket, il place la transaction pour exécution en fonction de son ticket. Une fois la transaction terminée, ce site diffuse un message approprié. Une transaction se termine lorsqu'elle a terminé son exécution sur tous les sites.