Transactions
Une transaction est une séquence d'opérations sur des données ayant un début et une fin.
Une transaction est l'exécution séquentielle d'opérations de lecture et d'écriture. La fin d'une transaction peut être soit la validation des modifications (commit) soit l'annulation des modifications (rollback). Dans le cadre des bases de données, une transaction est composée de plusieurs requêtes qui sont traitées comme une seule.
Les transactions doivent satisfaire aux propriétés ACID.
Atomicité. Une transaction est soit entièrement réalisée, soit pas du tout.
Cohérence. À la fin d'une transaction, les contraintes imposées sur les données ne doivent pas être violées (par exemple, les constraints dans une base de données). La cohérence signifie que le système passera d'un état correct à un autre état correct.
Isolation. Les transactions exécutées en parallèle ne doivent pas interférer les unes avec les autres, par exemple, ne pas modifier les données utilisées par une autre transaction. Le résultat de l'exécution de transactions parallèles doit être le même que si elles avaient été exécutées séquentiellement.
Durabilité. Après validation, les modifications ne doivent pas être perdues.
Journal des transactions.
Le journal conserve les modifications effectuées par les transactions, garantissant l'atomicité et la durabilité 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 du journal d'écriture anticipée oblige à ajouter dans le journal un enregistrement des valeurs précédentes avant le début, et des valeurs finales après la fin d'une transaction. En cas d'arrêt soudain du système, la base de données lit le journal à l'envers et annule les modifications effectuées par les transactions. En rencontrant une transaction interrompue, la base de données l'exécute et enregistre ses modifications dans le journal. En étant dans l'état au moment de la défaillance, la base de données lit le journal dans l'ordre et rétablit les modifications effectuées par les transactions. Ainsi, la durabilité des transactions déjà validées et l'atomicité de la transaction interrompue sont préservées.
Une simple réexécution des transactions erronées n'est pas suffisante pour la récupération.
Exemple. Un utilisateur a un solde de 500$ et décide de retirer cet argent via un distributeur automatique. Deux transactions sont exécutées. La première lit la valeur du solde et, si le solde est suffisant, délivre l'argent à l'utilisateur. La seconde soustrait le montant du solde. Supposons qu'un dysfonctionnement du système se produise et que la première opération n'ait pas été exécutée, tandis que la seconde l'a été. Dans ce cas, nous ne pouvons pas redélivrer de l'argent à l'utilisateur sans restaurer le système à son état initial avec un solde positif.
Niveaux d'isolement
Lecture des données fixes (Read Committed)
Le problème de la lecture sale (Dirty Read) réside dans le fait qu'une transaction peut lire un résultat intermédiaire provenant d'une autre transaction.
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 son exécution avec des données incorrectes sur le solde.
La solution est la lecture des données fixes (Read Committed) qui interdit de lire les données modifiées par une transaction. Si la transaction A a modifié un certain ensemble de données, alors la transaction B, en essayant d'accéder à ces données, doit attendre que la transaction A soit terminée.
Lecture répétée (Repeatable Read)
Le problème des mises à jour perdues (Lost Updates). T1 enregistre des modifications sur les modifications de T2.
Exemple. La valeur initiale du solde est de 0$ et deux transactions remplissent simultanément le solde. T1 et T2 lisent un solde égal à 0$. Ensuite, T2 ajoute 200$ à 0$ et enregistre le résultat. T1 ajoute 100$ à 0$ et enregistre le résultat. Le résultat final est 100$ au lieu de 300$.
Le problème de la lecture non répétée (Unrepeatable Read). Une nouvelle lecture des mêmes données renvoie des valeurs différentes.
Exemple. T1 lit une valeur de solde égale à 0$. Ensuite, T2 ajoute 50$ au solde et se termine. T1 relit les données et découvre un écart avec le résultat précédent.
La lecture répétée (Repeatable Read) garantit qu'une nouvelle lecture renverra le même résultat. Les données lues par une transaction ne peuvent pas être modifiées par d'autres jusqu'à la fin de la transaction. Si la transaction A a lu un certain ensemble de données, alors la transaction B, en essayant d'accéder à ces données, doit attendre que la transaction A soit terminée.
Lecture ordonnée (Serializable)
Problème de lecture fantôme (Phantom Reads). Deux requêtes sélectionnant des données sur une certaine condition retournent des valeurs différentes.
Exemple. T1 demande le nombre total d'utilisateurs dont le solde est supérieur à 0 $ mais inférieur à 100 $. T2 soustrait 1 $ à un utilisateur avec un solde de 101 $. T1 exécute à nouveau la requête.
Lecture ordonnée (Serializable). Les transactions s'exécutent comme entièrement séquentielles. Il est interdit de mettre à jour ou d'ajouter des enregistrements correspondant aux conditions de la requête. Si la transaction A demande des données de toute la table, celle-ci est entièrement gelée pour les autres transactions jusqu'à ce que la transaction A soit terminée.
Planificateur (Scheduler)
Établit l'ordre dans lequel les opérations doivent être exécutées lors de transactions simultanées.
Assure un niveau d'isolation spécifié. Si le résultat de l'exécution des opérations ne dépend pas de leur ordre, alors ces opérations sont commutatives (Permutable). Les opérations de lecture et les opérations sur des données différentes sont commutatives. Les opérations de lecture-écriture et les écritures-écritures ne sont pas commutatives. La tâche du planificateur est d'alterner les opérations exécutées par des transactions parallèles de manière à ce que le résultat soit équivalent à une exécution séquentielle des transactions.
Mécanismes de contrôle de la concurrence (Concurrency Control)
Optimiste basé sur la détection et la résolution de conflits, pessimiste sur la prévention de l'apparition de conflits.
Avec l'approche optimiste, plusieurs utilisateurs reçoivent des copies des données. Le premier à terminer l'édition sauvegarde ses modifications, les autres doivent fusionner les changements. L'algorithme optimiste permet un conflit, mais le système doit se rétablir après le conflit.
Avec l'approche pessimiste, le premier utilisateur à capturer les données empêche les autres d'accéder aux données. Si les conflits sont rares, il est raisonnable de choisir une stratégie optimiste, car elle offre un niveau de parallélisme plus élevé.
Verrouillage (Locking)
Si une transaction a verrouillé des données, les autres transactions doivent attendre le déverrouillage lorsqu'elles accèdent aux données.
Un bloc peut s'appliquer à une base de données, une table, une ligne ou un attribut. Un verrou partagé (Shared Lock) peut être imposé sur certaines données par plusieurs transactions, permettant à toutes les transactions (y compris celle qui l'a appliqué) de lire, tout en interdisant les modifications et le verrouillage exclusif. Un verrou exclusif (Exclusive Lock) ne peut être imposé que par une seule transaction, autorisant toutes les actions de la transaction ayant appliqué le verrou, tout en interdisant les actions des autres.
Un interblocage est une situation où les transactions se retrouvent en attente indéfiniment.
Exemple. La première transaction attend la libération des données bloquées par la seconde, tandis que la seconde attend la libération des données, bloquées par la première.
La solution optimiste au problème des interblocages permet que l'interblocage se produise, mais restaure ensuite le système en annulant l'une des transactions impliquées dans l'interblocage.
À des intervalles réguliers, une recherche d'interblocages est effectuée. L'un des moyens de détection consiste à évaluer le temps, c'est-à-dire considérer qu'un interblocage s'est produit si une transaction s'exécute trop longtemps. Lorsque l'interblocage est identifié, l'une des transactions est annulée, permettant aux autres transactions impliquées dans l'interblocage de se terminer. Le choix de la transaction à annuler peut être basé sur le coût des transactions ou sur leur ancienneté (schémas Wait-Die et Wound-wait).
À chaque transaction des est attribuée un horodatage , donc pourquoi solliciter inutilement le scanner avec des manipulations et des vérifications supplémentaires. Nous définirons le langage d'analyse en ajoutant un autre paramètre dans le fichier de configuration indiquant l'heure du début d'exécution de la transaction.
Wait-Die.
Si TS(Ti) < TS(Tj), alors Ti attend, sinon Ti elle est annulée et recommence avec le même horodatage.
Si une transaction jeune a acquis une ressource et qu'une transaction plus ancienne demande la même ressource, la transaction plus ancienne est autorisée à attendre. Si une transaction plus ancienne a acquis la ressource, alors la transaction jeune demandant cette ressource sera annulée.
Wound-wait.
Si TS(Ti) < TS(Tj), alors Tj est annulée et recommence avec le même horodatage, sinon Ti elle attend.
Si une transaction plus jeune a acquis une ressource et qu'une transaction plus ancienne demande cette même ressource, alors la transaction plus jeune sera annulée. Si une transaction plus ancienne a acquis la ressource, alors la transaction plus jeune demandant cette ressource est autorisée à attendre. Le choix de la victime basé sur l'ancienneté permet d'éviter l'apparition de blocages mutuels, mais annule des transactions qui ne sont pas dans un état de blocage mutuel. Le problème est que les transactions peuvent être annulées plusieurs fois, car une transaction plus ancienne peut retenir la ressource pendant longtemps.
La solution pessimiste au problème de blocage mutuel n'autorise pas une transaction à commencer son exécution s'il existe un risque de blocage mutuel.
Pour détecter un blocage mutuel, un graphique est construit (graphique d'attente, wait-for-graph), dont les sommets sont des transactions et les arêtes vont des transactions en attente de libération des données aux transactions ayant acquis ces données. On considère qu'un blocage mutuel s'est produit si le graphique présente des cycles. La construction du graphique d'attente, en particulier dans les bases de données distribuées, est une procédure coûteuse.
Le verrouillage à deux phases — prévention des blocages mutuels en acquérant toutes les ressources utilisées par la transaction au début de celle-ci et en les libérant à la fin.
Toutes les opérations de verrouillage doivent précéder la première opération de déverrouillage. Cela a deux phases — la phase de croissance (Growing Phase) pendant laquelle les acquisitions s'accumulent et la phase de réduction (Shrinking Phase) pendant laquelle les acquisitions sont libérées. En cas d'impossibilité d'acquérir l'une des ressources, la transaction recommence. Il peut y avoir des situations où la transaction ne pourra pas acquérir les ressources requises, par exemple si plusieurs transactions doivent concourir pour les mêmes ressources.
Le commit à deux phases assure l'exécution du commit sur toutes les répliques de la base de données.
Chaque base de données enregistre les informations sur les données qui seront modifiées dans un journal et répond au coordinateur par un OK (Voting Phase). Après que toutes les réponses ont été reçues, le coordinateur envoie un signal obligatoire à tous pour effectuer le commit. Après le commit, de serveurs les systèmes répondent par OK, si au moins un n'a pas répondu OK, le coordinateur envoie un signal d'annulation des modifications à tous les serveurs (Completion Phase).
Méthode des horodatages
Une transaction plus ancienne est annulée lors de la tentative d'accès aux données auxquelles une transaction plus jeune a participé.
Chaque transaction se voit attribuer un horodatage , donc pourquoi solliciter inutilement le scanner avec des manipulations et des vérifications supplémentaires. Nous définirons le langage d'analyse en ajoutant un autre paramètre dans le fichier de configuration correspondant au début de son exécution. Si Ti plus ancien Tj, alors TS(Ti) < TS(Tj).
Lorsqu'une transaction est annulée, elle se voit attribuer un nouvel horodatage. Chaque objet de données Q impliqué dans la transaction est marqué par deux horodatages. W-TS(Q) — l'horodatage de la transaction la plus récente ayant réussi à écrire sur Q. R-TS(Q) — l'horodatage de la transaction la plus récente ayant effectué une lecture sur Q.
Lorsque la transaction des demande une lecture de 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, alors la transaction des est annulée.
Si TS(T) >= W-TS(Q), alors la lecture s'effectue et R-TS(Q) devient MAX(R-TS(Q), TS(T)).
Lorsque la transaction des 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 que si une modification est effectuée, un conflit surviendra. La transaction des est annulée.
Si TS(T) < W-TS(Q), c'est-à-dire que la transaction essaie de réécrire une valeur plus récente, la transaction T est annulée. Dans les autres cas, la modification est effectuée et W-TS(Q) devient égal à TS(T).
Aucun besoin de construire un graphe d'attente coûteux. Les transactions plus anciennes dépendent de transactions plus récentes, par conséquent, il n'y a pas de cycles dans le graphe d'attente. Il n'y a pas de blocages, car les transactions n'attendent pas, mais sont immédiatement annulées. Des annulations en cascade peuvent se produire. Si Ti a été annulée et Tj a lu des données qu'elle a modifiées Ti, alors Tj doit également être annulée. Si de plus Tj a déjà été validée, alors cela violera le principe de durabilité.
Une des solutions aux annulations en cascade. La transaction effectue toutes les opérations d'écriture à la fin, tandis que les autres transactions doivent attendre la fin de cette opération. Les transactions attendent la validation avant de lire.
Règle de Thomas — une variation de la méthode des horodatages où les données mises à jour par une transaction plus récente ne peuvent pas être réécrites par une ancienne
La transaction des demande une modification des données Q. Si TS(T) < W-TS(Q), c'est-à-dire que la transaction essaie de réécrire une valeur plus récente, la transaction T n'est pas annulée comme dans la méthode des horodatages.
Source : habr.com
