Transactions et mécanismes de contrôle

Les transactions

Une transaction est une séquence d'opérations sur des données qui a un début et une fin.

Une transaction est une opération séquentielle de lecture et d'écriture. La fin d'une transaction peut être soit l'enregistrement des modifications (validation, validation) ou l'annulation des modifications (restauration, restauration). En ce qui concerne la base de données, une transaction est une série de requêtes, qui sont traitées comme une requête unique.

Les transactions doivent satisfaire les propriétés ACID

Atomicité. Une transaction est soit entièrement exécutée, soit pas exécutée du tout.

Cohérence. À la fin de la transaction, les restrictions imposées aux données (par exemple, les contraintes dans la base de données) ne doivent pas être violées. La cohérence implique que le système sera transféré d'un état correct à un autre état correct.

Isolement. Les transactions exécutées simultanément ne doivent pas s’affecter mutuellement, par exemple en modifiant les données utilisées par une autre transaction. Le résultat des transactions parallèles doit être comme si les transactions étaient exécutées séquentiellement.

Durabilité. Une fois validés, les changements ne doivent pas être perdus.

Journal des transactions

Le journal stocke les modifications apportées par les transactions, garantit l'atomicité et la stabilité des données en cas de défaillance du système

Le journal contient les valeurs que les données avaient avant et après leur modification par la transaction. La stratégie de journal à écriture anticipée nécessite que vous ajoutiez au journal un enregistrement des valeurs précédentes avant le début et des valeurs finales une fois la transaction terminée. En cas d'arrêt brutal du système, la base de données lit le journal dans l'ordre inverse et annule les modifications apportées par les transactions. Après avoir rencontré une transaction interrompue, la base de données l'exécute et y apporte des modifications dans le journal. Étant en état au moment de l'échec, la base de données lit le journal dans l'ordre direct et renvoie les modifications apportées par les transactions. Ainsi, la stabilité des transactions déjà engagées et l'atomicité de la transaction interrompue sont préservées.

Il ne suffit pas de réexécuter des transactions erronées pour récupérer.

Un exemple. L'utilisateur dispose de 500 $ dans le compte et l'utilisateur décide de les retirer via un guichet automatique. Deux transactions sont effectuées. Le premier lit la valeur du solde et s'il y a suffisamment de fonds sur le solde, il donne de l'argent à l'utilisateur. Le second soustrait le montant requis du solde. Supposons qu'un système se bloque et que la première opération échoue et que la seconde échoue. Dans ce cas, nous ne pouvons pas réémettre de l'argent à l'utilisateur sans remettre le système à son état d'origine avec un solde positif.

Niveaux d'isolement

Lire Engagé

Le problème avec une lecture incorrecte est qu'une transaction peut lire le résultat intermédiaire d'une autre transaction.

Un exemple. La valeur initiale du solde est de 0 $. T1 ajoute 50 $ au solde. T2 lit la valeur du solde (50 $). T1 annule les modifications et se termine. T2 continue l'exécution avec des données de solde incorrectes.

La solution est Read Committed, qui interdit la lecture des données modifiées par une transaction. Si la transaction A a modifié un ensemble de données, la transaction B, lors de l'accès à ces données, est obligée d'attendre la transaction A.

Lecture répétable

Le problème des modifications perdues (Lost Updates). T1 enregistre les modifications par rapport aux modifications apportées à T2.

Un exemple. La valeur du solde initial est de 0 $ et deux transactions reconstituent simultanément le solde. T1 et T2 lisent un solde de 0 $. Ensuite, T2 ajoute 200 $ à 0 $ et enregistre le résultat. T1 ajoute 100 $ à 0 $ et enregistre le résultat. Le résultat total est de 100 $ au lieu de 300 $.

Problème de lecture irremplaçable. La lecture répétée des mêmes données renvoie des valeurs différentes.

Un exemple. T1 lit une valeur de solde de 0 $. Ensuite, T2 ajoute 50 $ au solde et se termine. T1 relit les données et détecte un écart avec le résultat précédent.

La lecture répétable garantit que la lecture répétée donnera le même résultat. Il est interdit de modifier les données lues par une transaction dans d'autres jusqu'à ce que la transaction soit terminée. Si la transaction A a lu un ensemble de données, la transaction B, lors de l'accès à ces données, est obligée d'attendre la transaction A.

Lecture ordonnée (sérialisable)

Lectures fantômes Deux requêtes qui sélectionnent des données par une condition renvoient des valeurs différentes.

Un exemple. T1 demande le nombre de tous les utilisateurs dont le solde est supérieur à 0 $ mais inférieur à 100 $. T2 soustrait 1 $ d'un utilisateur avec un solde de 101 $. T1 réexécute la demande.

Lecture ordonnée (sérialisable). Les transactions sont effectuées de manière complètement séquentielle. Il est interdit de mettre à jour et d'ajouter des enregistrements soumis aux conditions de la demande. Si la transaction A a demandé des données à l'ensemble de la table, la table entière est gelée pour le reste des transactions jusqu'à la transaction A.

Planificateur

Définit l'ordre dans lequel les opérations doivent être effectuées dans les transactions parallèles

Fournit un niveau d'isolement spécifié. Si le résultat des opérations ne dépend pas de leur ordre, ces opérations sont commutables (permutables). Les commandes sont lues et les opérations sur différentes données. Les opérations de lecture-écriture et d'écriture-écriture ne sont pas commutatives. L'ordonnanceur a pour tâche d'alterner les opérations effectuées par des transactions parallèles afin que le résultat de l'exécution soit équivalent à l'exécution séquentielle des transactions.

Mécanismes de contrôle des accès concurrents

Optimiste basé sur la détection et la résolution des conflits, pessimiste basé sur la prévention des conflits

Avec une approche optimiste, plusieurs utilisateurs ont à leur disposition des copies des données. Le premier qui a terminé l'édition enregistre les modifications, les autres doivent fusionner les modifications. Un algorithme optimiste permet à un conflit de se produire, mais le système doit se remettre du conflit.

Avec une approche pessimiste, le premier utilisateur à capturer des données empêche les autres de recevoir des données. Si les conflits sont rares, il est sage de choisir une stratégie optimiste, car elle offre un niveau de parallélisme plus élevé.

Verrouillage

Si une transaction a bloqué des données, le reste de la transaction doit accéder aux données lors de l'accès aux données.

Un bloc peut être superposé à une base de données, une table, une ligne ou un attribut. Le verrouillage partagé (verrou partagé) peut être imposé aux mêmes données par plusieurs transactions, permet la lecture de toutes les transactions (y compris imposées), interdit la modification et la capture exclusive. Le verrouillage exclusif peut être imposé par une seule transaction, autorise toutes les actions de la transaction imposée, interdit toutes les actions par les autres.

Un blocage est une situation où les transactions sont en mode veille, d'une durée indéfinie

Un exemple. La première transaction attend la libération des données capturées par la seconde, tandis que la seconde attend la libération des données capturées par la première.

Une solution optimiste au problème de blocage permet un blocage, mais restaure ensuite le système en annulant l'une des transactions impliquées dans le blocage.

Avec une certaine fréquence, une recherche de blocages est effectuée. L'une des méthodes de détection est dans le temps, c'est-à-dire de considérer qu'un blocage s'est produit si la transaction prend trop de temps. Lorsqu'un blocage est détecté, l'une des transactions est annulée, ce qui permet aux autres transactions impliquées dans le blocage de se terminer. Le choix de la victime peut être basé sur la valeur des transactions ou leur ancienneté (systèmes Wait-Die et Wound-Wait).

Chaque transaction T se voit attribuer un horodatage TS contenant l'heure de début de la transaction.

Wait-Die

Si TS (Ti) < TS (Tj) , alors Ti attend, sinon Ti annule et recommence avec le même horodatage.

Si une transaction jeune a capturé une ressource et qu'une ancienne demande la même ressource, alors une transaction plus ancienne est autorisée. Si une transaction plus ancienne a capturé une ressource, une transaction jeune demandant cette ressource sera annulée.

Attends une blessure.

Si TS (Ti) < TS (Tj) , alors Tj revient en arrière et recommence avec le même horodatage, sinon Ti attend.

Si une transaction plus récente a capturé une ressource et qu'une transaction plus ancienne demande la même ressource, la transaction jeune sera annulée. Si une transaction plus ancienne a capturé la ressource, une transaction plus récente demandant cette ressource est autorisée à attendre. La sélection de la victime en fonction de l'ancienneté évite les blocages, mais annule les transactions qui ne sont pas dans un état de verrouillage. Le problème est que les transactions peuvent être annulées plusieurs fois car Une transaction plus ancienne peut contenir une ressource pendant longtemps.

Une solution pessimiste au problème des blocages ne permet pas à la transaction de démarrer son exécution en cas de risque de blocage

Pour détecter les interblocages, un graphique est construit (un graphique d'attente, un graphique en attente), dont les sommets sont des transactions, et les bords sont dirigés depuis les transactions qui attendent que des données soient libérées vers la transaction qui a capturé ces données. On pense qu'un blocage s'est produit si le graphique est bouclé. La construction d'un graphique d'attente, en particulier dans les bases de données distribuées, est une procédure coûteuse.

Verrouillage en deux phases - évitant les blocages en capturant toutes les ressources utilisées par la transaction au début de la transaction et en les libérant à la fin

Toutes les opérations de blocage doivent précéder le premier déverrouillage. Il comporte deux phases - la phase de croissance au cours de laquelle la capture des grappins a lieu et la phase de rétrécissement au cours de laquelle la libération des grappins se produit. S'il est impossible de capturer l'une des ressources, la transaction recommence. Il est possible qu'une transaction ne puisse pas capturer les ressources requises, par exemple, si plusieurs transactions sont en concurrence pour les mêmes ressources.

La validation en deux phases garantit que la validation est exécutée sur toutes les répliques de base de données

Chaque base de données fournit des informations sur les données qui seront modifiées dans le journal et correspond au coordinateur OK (phase de vote). Après que tout le monde a répondu OK, le coordinateur envoie un signal obligeant tout le monde à s'engager. Après avoir validé le serveur, ils répondent OK, si au moins un n'a pas répondu OK, le coordinateur envoie un signal pour annuler les modifications sur tous les serveurs (phase d'achèvement).

Méthode d'horodatage

Une transaction plus ancienne annule lorsque vous essayez d'accéder aux données impliquées dans une transaction plus récente

Chaque transaction se voit attribuer un horodatage TS correspondant à l'heure de début de l'exécution. Si Ti est plus ancien que Tj , alors TS (Ti) < TS (Tj) .

Lorsqu'une transaction est annulée, un nouvel horodatage lui est attribué. Chaque objet de données Q impliqué dans la transaction est marqué de deux étiquettes. W-TS (Q) est l'horodatage de la transaction la plus récente qui a réussi à écrire à Q. R-TS (Q) est l'horodatage de la transaction la plus récente qui a terminé un enregistrement de lecture sur Q.

Lorsque la transaction T demande de lire les données Q , deux options sont possibles.

Si TS (T) < W-TS (Q) , c'est-à-dire que les données ont été mises à jour par une transaction plus récente, la transaction T est annulée.

Si TS (T) > = W-TS (Q) , alors la lecture est effectuée et R-TS (Q) devient MAX (R-TS (Q), TS (T)) .

Lorsque la transaction T demande une modification des données Q , deux options sont possibles.

Si TS (T) < R-TS (Q) , c'est-à-dire que les données ont déjà été lues par une transaction plus récente et si un changement est effectué, alors un conflit se produira. La transaction T annule.

Si TS (T) < W-TS (Q) , c'est-à-dire que la transaction essaie d'écraser la valeur la plus récente, la transaction T annule. Dans d'autres cas, le changement est effectué et W-TS (Q) devient égal à TS (T) .

Aucune construction coûteuse de graphique d'attente n'est requise. Les transactions plus anciennes dépendent des plus récentes, il n'y a donc pas de boucles dans la colonne d'attente. Il n'y a pas de blocage, car les transactions ne sont pas attendues, mais sont immédiatement annulées. Des pots-de-vin en cascade sont possibles. Si Ti annule et que Tj lit les données que Ti a modifiées, alors Tj doit également revenir en arrière. Si dans ce cas Tj a déjà été communiqué, il y aura alors violation du principe de stabilité.

Une solution aux annulations en cascade. Une transaction effectue toutes les opérations d'écriture à la fin, et les transactions restantes doivent attendre la fin de cette opération. Les transactions attendent un commit avant d'être lues.

Règle d'écriture Thomas - une variante de la méthode d'horodatage dans laquelle les données mises à jour par une transaction plus récente ne peuvent pas être écrasées par une plus ancienne

La transaction T demande une modification des données Q. Si TS (T) < W-TS (Q) , c'est-à-dire que la transaction essaie d'écraser une valeur plus récente, la transaction T n'est pas annulée comme dans la méthode d'horodatage.