SGBD distribué - Contrôle de la concurrence
Les techniques de contrôle de la concurrence garantissent que plusieurs transactions sont exécutées simultanément tout en conservant les propriétés ACID des transactions et la sérialisabilité dans les horaires.
Dans ce chapitre, nous étudierons les différentes approches de contrôle d'accès concurrentiel.
Protocoles de contrôle d'accès concurrentiel basés sur le verrouillage
Les protocoles de contrôle d'accès concurrentiel basés sur le verrouillage utilisent le concept de verrouillage des éléments de données. UNElockest une variable associée à un élément de données qui détermine si des opérations de lecture / écriture peuvent être effectuées sur cet élément de données. En règle générale, une matrice de compatibilité de verrouillage est utilisée qui indique si un élément de données peut être verrouillé par deux transactions en même temps.
Les systèmes de contrôle d'accès concurrentiel basés sur le verrouillage peuvent utiliser des protocoles de verrouillage monophasés ou biphasés.
Protocole de verrouillage monophasé
Dans cette méthode, chaque transaction verrouille un élément avant utilisation et libère le verrou dès qu'elle a fini de l'utiliser. Cette méthode de verrouillage offre une concurrence maximale mais n'impose pas toujours la sérialisation.
Protocole de verrouillage biphasé
Dans ce procédé, toutes les opérations de verrouillage précèdent la première opération de déverrouillage ou de déverrouillage. La transaction comprend deux phases. Dans la première phase, une transaction n'acquiert que tous les verrous dont elle a besoin et ne libère aucun verrou. C'est ce qu'on appelle l'expansion ou legrowing phase. Dans la deuxième phase, la transaction libère les verrous et ne peut pas demander de nouveaux verrous. C'est ce qu'on appelle leshrinking phase.
Chaque transaction qui suit le protocole de verrouillage en deux phases est garantie d'être sérialisable. Cependant, cette approche fournit un faible parallélisme entre deux transactions en conflit.
Algorithmes de contrôle de la concurrence d'horodatage
Les algorithmes de contrôle d'accès concurrentiel basés sur l'horodatage utilisent l'horodatage d'une transaction pour coordonner l'accès simultané à un élément de données afin d'assurer la sérialisation. Un horodatage est un identifiant unique donné par le SGBD à une transaction qui représente l'heure de début de la transaction.
Ces algorithmes garantissent que les transactions s'engagent dans l'ordre dicté par leur horodatage. Une transaction plus ancienne doit être validée avant une transaction plus jeune, car la transaction la plus ancienne entre dans le système avant la plus jeune.
Les techniques de contrôle d'accès concurrentiel basées sur l'horodatage génèrent des programmes sérialisables de telle sorte que le programme en série équivalent est organisé par ordre d'âge des transactions participantes.
Certains des algorithmes de contrôle de concurrence basés sur l'horodatage sont -
- Algorithme de classement d'horodatage de base.
- Algorithme de classement d'horodatage conservateur.
- Algorithme de multiversion basé sur l'ordre d'horodatage.
L'ordre basé sur l'horodatage suit trois règles pour appliquer la sérialisabilité -
Access Rule- Lorsque deux transactions tentent d'accéder simultanément à la même donnée, pour des opérations conflictuelles, la priorité est donnée à la transaction plus ancienne. Cela oblige la transaction plus récente à attendre que la transaction plus ancienne soit validée en premier.
Late Transaction Rule- Si une transaction plus récente a écrit un élément de données, une transaction plus ancienne n'est pas autorisée à lire ou à écrire cet élément de données. Cette règle empêche la transaction plus ancienne de s'engager une fois que la transaction plus récente a déjà été validée.
Younger Transaction Rule - Une transaction plus jeune peut lire ou écrire un élément de données qui a déjà été écrit par une transaction plus ancienne.
Algorithme de contrôle de concurrence optimiste
Dans les systèmes à faible taux de conflit, la tâche de validation de chaque transaction pour la sérialisabilité peut réduire les performances. Dans ces cas, le test de sérialisabilité est reporté juste avant la validation. Comme le taux de conflit est faible, la probabilité d'abandonner des transactions qui ne sont pas sérialisables est également faible. Cette approche est appelée technique de contrôle de concurrence optimiste.
Dans cette approche, le cycle de vie d'une transaction est divisé en trois phases:
Execution Phase - Une transaction récupère les éléments de données en mémoire et effectue des opérations sur eux.
Validation Phase - Une transaction effectue des vérifications pour s'assurer que la validation de ses modifications dans la base de données passe le test de sérialisabilité.
Commit Phase - Une transaction réécrit une donnée modifiée en mémoire sur le disque.
Cet algorithme utilise trois règles pour appliquer la sérialisation dans la phase de validation -
Rule 1- Étant donné deux transactions T i et T j , si T i lit la donnée que T j est en train d’écrire, alors la phase d’exécution de T i ne peut pas chevaucher la phase de validation de T j . T j ne peut s'engager qu'après la fin de l'exécution de T i .
Rule 2- Étant donné deux transactions T i et T j , si T i écrit la donnée que T j lit, alors la phase de validation de T i ne peut pas chevaucher la phase d’exécution de T j . T j ne peut commencer à s'exécuter qu'après que T i s'est déjà engagé.
Rule 3- Étant donné deux transactions T i et T j , si T i écrit la donnée que T j est également en train d’écrire, alors la phase de validation de T i ne peut pas chevaucher la phase de validation de T j . T j ne peut commencer à s'engager qu'après que T i s'est déjà engagé.
Contrôle de la concurrence dans les systèmes distribués
Dans cette section, nous verrons comment les techniques ci-dessus sont implémentées dans un système de base de données distribué.
Algorithme de verrouillage biphasé distribué
Le principe de base du verrouillage biphasé distribué est le même que le protocole de verrouillage biphasé de base. Cependant, dans un système distribué, il existe des sites désignés comme gestionnaires de serrures. Un gestionnaire de verrouillage contrôle les demandes d'acquisition de verrous des moniteurs de transaction. Afin de renforcer la coordination entre les gestionnaires de serrures dans divers sites, au moins un site est autorisé à voir toutes les transactions et à détecter les conflits de verrouillage.
Selon le nombre de sites capables de détecter les conflits de verrouillage, les approches de verrouillage en deux phases distribuées peuvent être de trois types:
Centralized two-phase locking- Dans cette approche, un site est désigné comme le gestionnaire central des écluses. Tous les sites de l'environnement connaissent l'emplacement du gestionnaire central de verrouillage et en obtiennent le verrouillage lors des transactions.
Primary copy two-phase locking- Dans cette approche, un certain nombre de sites sont désignés comme centres de contrôle des écluses. Chacun de ces sites a la responsabilité de gérer un ensemble défini de serrures. Tous les sites savent quel centre de contrôle de serrure est responsable de la gestion du verrouillage de quelle table de données / élément de fragment.
Distributed two-phase locking- Dans cette approche, il existe un certain nombre de gestionnaires de serrures, où chaque gestionnaire de verrouillage contrôle les verrous des éléments de données stockés sur son site local. L'emplacement du gestionnaire de verrouillage est basé sur la distribution et la réplication des données.
Contrôle de simultanéité d'horodatage distribué
Dans un système centralisé, l'horodatage de toute transaction est déterminé par la lecture de l'horloge physique. Mais, dans un système distribué, les lectures d'horloge physique / logique locale d'un site ne peuvent pas être utilisées comme horodatage global, car elles ne sont pas uniques au monde. Ainsi, un horodatage comprend une combinaison d'ID de site et de lecture d'horloge de ce site.
Pour implémenter des algorithmes de classement d'horodatage, chaque site dispose d'un planificateur qui gère une file d'attente distincte pour chaque gestionnaire de transactions. Lors de la transaction, un gestionnaire de transactions envoie une demande de verrouillage au planificateur du site. Le planificateur place la demande dans la file d'attente correspondante dans un ordre d'horodatage croissant. Les requêtes sont traitées depuis le début des files d'attente dans l'ordre de leurs horodatages, c'est-à-dire les plus anciennes en premier.
Graphiques de conflit
Une autre méthode consiste à créer des graphiques de conflit. Pour cette transaction, des classes sont définies. Une classe de transaction contient deux ensembles d'éléments de données appelés ensemble de lecture et ensemble d'écriture. Une transaction appartient à une classe particulière si l'ensemble de lecture de la transaction est un sous-ensemble de l'ensemble de lecture de la classe et que l'ensemble d'écriture de la transaction est un sous-ensemble de l'ensemble d'écriture de la classe. Dans la phase de lecture, chaque transaction émet ses demandes de lecture pour les éléments de données dans son ensemble de lecture. Dans la phase d'écriture, chaque transaction émet ses demandes d'écriture.
Un graphique de conflit est créé pour les classes auxquelles appartiennent les transactions actives. Celui-ci contient un ensemble d'arêtes verticales, horizontales et diagonales. Une arête verticale relie deux nœuds au sein d'une classe et dénote des conflits au sein de la classe. Un bord horizontal relie deux nœuds sur deux classes et dénote un conflit d'écriture-écriture entre différentes classes. Un bord diagonal relie deux nœuds à travers deux classes et dénote un conflit en écriture-lecture ou en lecture-écriture entre deux classes.
Les graphiques de conflit sont analysés pour déterminer si deux transactions au sein de la même classe ou entre deux classes différentes peuvent être exécutées en parallèle.
Algorithme de contrôle de concurrence optimiste distribué
L'algorithme de contrôle de concurrence optimiste distribué étend l'algorithme de contrôle de concurrence optimiste. Pour cette extension, deux règles sont appliquées -
Rule 1- Selon cette règle, une transaction doit être validée localement sur tous les sites lors de son exécution. Si une transaction s'avère invalide sur un site, elle est abandonnée. La validation locale garantit que la transaction maintient la sérialisabilité sur les sites où elle a été exécutée. Une fois qu'une transaction réussit le test de validation local, elle est validée globalement.
Rule 2- Selon cette règle, une fois qu'une transaction a passé le test de validation local, elle doit être validée globalement. La validation globale garantit que si deux transactions en conflit s'exécutent ensemble sur plus d'un site, elles doivent s'engager dans le même ordre relatif sur tous les sites qu'elles exécutent ensemble. Cela peut nécessiter qu'une transaction attende l'autre transaction en conflit, après validation avant la validation. Cette exigence rend l'algorithme moins optimiste car une transaction peut ne pas être en mesure de s'engager dès qu'elle est validée sur un site.