Contrôle de la concurrence dans les SGBD : protocoles de verrouillage et d’horodatage
Fiona Brun
⚡ Résumé intelligent
Le contrôle de concurrence dans les SGBD gère les transactions simultanées afin qu'elles s'exécutent correctement sans compromettre l'intégrité des données. Il prévient les anomalies telles que les mises à jour perdues et les lectures non validées grâce à des protocoles basés sur le verrouillage, le chiffrement en deux phases, l'horodatage et la validation, qui garantissent des résultats sérialisables.
Qu’est-ce que le contrôle de concurrence ?
Contrôle de la concurrence Dans un système de gestion de bases de données, la gestion simultanée est une procédure permettant de gérer des opérations simultanées sans conflit. Elle garantit que les transactions de la base de données sont exécutées de manière concurrente et précise afin de produire des résultats corrects sans compromettre l'intégrité des données de la base de données concernée.
L'accès concurrent est relativement simple si tous les utilisateurs se contentent de lire les données, car ils ne peuvent pas interférer les uns avec les autres. Cependant, toute base de données réelle comporte un mélange d'opérations de lecture et d'écriture, ce qui complexifie la gestion de la concurrence.
Le contrôle de concurrence des SGBD permet de gérer ces conflits, qui surviennent principalement dans un système multi-utilisateurs. Il constitue donc un élément essentiel au bon fonctionnement d'une base de données où plusieurs transactions s'exécutent simultanément et nécessitent l'accès aux mêmes données. Il fonctionne en étroite collaboration avec gestion des transactions, qui définit les unités de travail que le contrôle de concurrence doit entrelacer en toute sécurité.
Problèmes potentiels liés à la concurrence
Voici quelques problèmes auxquels vous risquez d'être confronté sans un contrôle adéquat de la concurrence dans le SGBD :
- Mises à jour perdues Cela se produit lorsque plusieurs transactions sélectionnent la même ligne et la mettent à jour en fonction de la valeur sélectionnée.
- Dépendance non engagée (Lecture sale) se produit lorsqu'une deuxième transaction sélectionne une ligne qui a été mise à jour par une autre transaction qui n'a pas encore été validée.
- Lecture non répétable Cela se produit lorsqu'une deuxième transaction accède plusieurs fois à la même ligne et lit des données différentes à chaque fois.
- Résumé incorrect Ce problème survient lorsqu'une transaction calcule la somme des valeurs de toutes les occurrences d'une donnée répétée, tandis qu'une seconde transaction met à jour seulement quelques-unes de ces occurrences. La somme obtenue est alors incorrecte.
Pourquoi utiliser une méthode de concurrence ?
Raisons d'utiliser une méthode de contrôle de concurrence dans un SGBD :
- Appliquer l'isolation par exclusion mutuelle entre les transactions conflictuelles.
- Pour résoudre les problèmes de conflit de lecture-écriture et d'écriture-écriture.
- Pour préserver la cohérence de la base de données en appliquant constamment les contraintes d'exécution.
- Pour contrôler l'interaction entre les transactions simultanées, on utilise des schémas de contrôle de la concurrence.
- Pour contribuer à garantir la sérialisabilité.
Exemple
Supposons que deux personnes se rendent en même temps à des bornes électroniques pour acheter un billet de cinéma pour le même film et la même séance.
Il ne reste cependant qu'une seule place pour cette séance. Sans gestion des réservations simultanées, il est possible que les deux spectateurs achètent le même billet. La gestion des réservations simultanées empêche cela. Les deux spectateurs peuvent toujours consulter les informations dans la base de données des places, mais la gestion des réservations simultanées ne délivre un billet qu'à celui qui finalise la transaction en premier.
Protocoles de contrôle de concurrence
Les différents protocoles de contrôle de concurrence offrent différents compromis entre le niveau de concurrence autorisé et la surcharge qu'ils imposent. Les principales techniques de contrôle de concurrence dans les SGBD sont :
- Protocoles basés sur le verrouillage
- Protocole de verrouillage à deux phases
- Protocoles basés sur l'horodatage
- Protocoles basés sur la validation
Chacun est examiné tour à tour ci-dessous, en commençant par les protocoles à verrouillage les plus répandus.
Protocoles basés sur le verrouillage
Protocoles basés sur le verrouillage Dans les SGBD, les verrous sont un mécanisme qui empêche une transaction de lire ou d'écrire sur une donnée tant qu'elle n'a pas acquis un verrou approprié. Les protocoles basés sur les verrous contribuent à éliminer les problèmes de concurrence en verrouillant ou en isolant une donnée particulière pour une seule transaction.
Un verrou est une variable de données associée à un élément de données, indiquant les opérations autorisées sur cet élément. Les verrous permettent de synchroniser l'accès aux éléments de la base de données par des transactions simultanées. Toutes les demandes de verrouillage sont adressées au gestionnaire de contrôle de concurrence, et les transactions ne sont exécutées qu'une fois le verrou accordé.
Verrous binaires : Un verrou binaire sur un élément de données peut être soit verrouillé, soit déverrouillé.
Partagé/Exclusif : Ce mécanisme de verrouillage sépare les verrous en fonction de leur utilisation. Si un verrou est acquis pour effectuer une opération d'écriture, il s'agit d'un verrou exclusif.
1. Verrou(s) partagé(s) : Un verrou partagé est également appelé verrou en lecture seule. Avec un verrou partagé, la donnée peut être partagée entre plusieurs transactions, car aucune d'entre elles n'est autorisée à la modifier. Par exemple, si deux transactions consultent le solde du compte d'une personne, le base de données Permet la lecture grâce à un verrou partagé. Si une autre transaction souhaite modifier ce solde, le verrou partagé l'en empêche jusqu'à la fin de la lecture.
2. Verrouillage exclusif (X) : Avec un verrou exclusif, une donnée peut être lue et écrite. Ce verrou est exclusif et ne peut être détenu simultanément sur la même donnée. Un verrou X est demandé à l'aide de l'instruction `lock-x`. Par exemple, lorsqu'une transaction doit mettre à jour le solde d'un compte, elle est autorisée par la mise en place d'un verrou X ; toute autre transaction souhaitant lire ou écrire sur la même donnée est alors bloquée.
3. Protocole de verrouillage simplifié : Cela permet aux transactions d'obtenir un verrou sur chaque objet avant de commencer une opération. Les transactions peuvent déverrouiller l'élément de données une fois l'opération d'écriture terminée.
4. Verrouillage avant réclamation : Ce protocole évalue les opérations et établit la liste des données nécessaires à leur exécution. Une fois tous les verrous accordés, la transaction s'exécute, puis tous les verrous sont libérés une fois les opérations terminées.
Famine: La famine survient lorsqu'une transaction attend indéfiniment l'acquisition d'un verrou. Les causes peuvent être un système d'attente mal géré pour les éléments verrouillés, une fuite de ressources ou la sélection répétée d'une même transaction comme victime.
Impasse: Le terme «interblocage» désigne une situation où deux ou plusieurs processus s'attendent mutuellement pour libérer une ressource, formant ainsi une chaîne circulaire.
Protocole de verrouillage à deux phases (2PL)
Le Protocole de verrouillage à deux phases, également connu sous le nom de 2PL, est une méthode de contrôle de concurrence qui garantit la sérialisabilité en appliquant un verrou aux données de transaction, ce qui empêche d'autres transactions d'accéder simultanément aux mêmes données.
Le protocole de verrouillage en deux phases permet à chaque transaction d'effectuer une demande de verrouillage ou de déverrouillage en deux étapes :
- Phase de croissance : Durant cette phase, une transaction peut obtenir des verrous mais ne peut en libérer aucun.
- Phase de rétrécissement : Durant cette phase, une transaction peut libérer des verrous mais ne peut pas en acquérir de nouveaux.
Il est vrai que le protocole 2PL offre la sérialisabilité. Cependant, il ne garantit pas l'absence d'interblocages. Dans le schéma ci-dessus, des détecteurs d'interblocages locaux et globaux recherchent ces interblocages et les résolvent en rétablissant les transactions à leur état initial.
Méthode de verrouillage stricte en deux phases
Le protocole 2PL strict est quasiment identique au protocole 2PL. La seule différence réside dans le fait que le protocole 2PL strict ne libère jamais un verrou après son utilisation. Il conserve tous les verrous jusqu'au point de validation et les libère tous simultanément une fois le processus terminé.
2PL centralisé
Dans une architecture 2PL centralisée, un seul site est responsable de la gestion des verrous. Il ne dispose que d'un seul gestionnaire de verrous pour l'ensemble du SGBD.
Copie principale 2PL
Dans le mécanisme 2PL de copie primaire, plusieurs gestionnaires de verrouillage sont répartis sur différents sites, et chaque gestionnaire est responsable du verrouillage d'un ensemble de données. Lorsqu'une copie primaire est mise à jour, la modification est propagée aux serveurs esclaves.
2PL distribué
Dans ce mécanisme, les gestionnaires de verrouillage sont répartis sur tous les sites et sont responsables de la gestion des verrous de données sur chaque site. En l'absence de réplication de données, le mécanisme est équivalent à une solution 2PL à copie primaire. Les coûts de communication d'une solution 2PL distribuée sont nettement supérieurs à ceux d'une solution 2PL à copie primaire.
Protocoles basés sur l'horodatage
Le Protocole basé sur l'horodatage Dans un SGBD, l'horodatage est un algorithme qui utilise l'heure système ou un compteur logique comme horodatage pour sérialiser l'exécution des transactions concurrentes. Il garantit que chaque opération de lecture et d'écriture conflictuelle est exécutée dans l'ordre chronologique.
Dans cette méthode, la transaction la plus ancienne est toujours prioritaire. Elle utilise l'heure système pour déterminer l'horodatage de la transaction et constitue le protocole de concurrence le plus couramment utilisé. Les protocoles basés sur les verrous gèrent l'ordre d'exécution des transactions conflictuelles ; les protocoles basés sur l'horodatage gèrent les conflits dès la création d'une opération.
Exemple :
Suppose there are three transactions T1, T2, and T3. T1 has entered the system at time 0010 T2 has entered the system at 0020 T3 has entered the system at 0030 Priority will be given to transaction T1, then T2 and lastly T3.
Avantages :
- Les calendriers sont sérialisables, tout comme les protocoles 2PL.
- Aucune attente pour la transaction, ce qui élimine tout risque de blocage.
Inconvénients : Une famine peut survenir si la même transaction est redémarrée puis continuellement interrompue.
Protocole basé sur la validation
Le Protocole basé sur la validation Dans les SGBD, le contrôle de concurrence optimiste est une méthode permettant d'éviter les conflits de concurrence lors des transactions. Ce protocole met à jour des copies locales des données de transaction plutôt que les données elles-mêmes, ce qui réduit les interférences pendant l'exécution.
Le protocole basé sur la validation se déroule en trois phases :
- Phase de lecture
- Validation
- Phase d'écriture
Phase de lecture
Lors de la phase de lecture, les valeurs des données peuvent être lues par une transaction, mais les opérations d'écriture ou les mises à jour ne sont appliquées qu'aux copies locales des données, et non à la base de données elle-même.
Validation
Lors de la phase de validation, les données sont vérifiées afin de s'assurer que l'application des mises à jour ne violera pas la sérialisabilité.
Phase d'écriture
Lors de la phase d'écriture, les mises à jour sont appliquées à la base de données si la validation réussit ; sinon, elles sont rejetées et la transaction est annulée.
Comparaison des protocoles de contrôle de concurrence
Les quatre familles de protocoles font des estimations différentes quant à la fréquence réelle des conflits entre transactions. Le tableau ci-dessous récapitule la position de chacune.
| Passerelle | Approche | Deadlock | Meilleur lorsque |
|---|---|---|---|
| à base de serrure | Pessimiste, il verrouille avant d'accéder | Possible | Les conflits sont fréquents |
| Verrouillage à deux phases | Phases pessimistes, de croissance et de décroissance | Possible | La sérialisabilité est requise |
| Basé sur l'horodatage | Tri par horodatage | Sans blocage | Commander est important, attendre coûte cher. |
| Basé sur la validation | Optimiste, validez avant d'écrire | Sans blocage | Les conflits sont rares |
En résumé, les protocoles basés sur le verrouillage et les protocoles 2PL supposent que les conflits sont fréquents et les préviennent en amont, tandis que les protocoles d'horodatage et de validation supposent que les conflits sont rares et ne les résolvent que lorsqu'ils apparaissent.
Caractéristiques d'un bon protocole de concurrence
Un mécanisme de contrôle de concurrence idéal a les objectifs suivants :
- Il doit être résilient aux pannes de site et de communication.
- Il permet l'exécution parallèle de transactions pour obtenir une concurrence maximale.
- Ses mécanismes de stockage et ses méthodes de calcul doivent être modestes pour minimiser les frais généraux.
- Il doit imposer certaines contraintes à la structure des actions atomiques des transactions.
