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 l'exécution séquentielle d'opérations de lecture et d'écriture. La fin d'une transaction peut consister soit à enregistrer les modifications (commit), soit à annuler les modifications (rollback). Par rapport à une base de données, une transaction est constituée de plusieurs requêtes qui sont traitées comme une seule requête.
Les transactions doivent satisfaire aux propriétés ACID
Atomicité. La transaction est soit entièrement terminée, soit pas du tout.
Cohérence. Lors de la réalisation d'une transaction, les restrictions imposées aux données (par exemple, les contraintes de 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 en parallèle ne doivent pas s'influencer mutuellement, par exemple 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 les transactions étaient exécutées séquentiellement.
Durabilité. Une fois validées, les modifications ne doivent pas être perdues.
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 panne 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 journalisation à écriture anticipée nécessite l'ajout d'une entrée de journal sur les valeurs précédentes avant le début et sur les 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 apporte des modifications à ce sujet dans le journal. Étant dans l'état au moment de la panne, la base de données lit le journal dans l'ordre direct et renvoie les modifications apportées par les transactions. De cette façon, la stabilité des transactions déjà validées et l'atomicité de la transaction interrompue sont préservées.
La simple réexécution des transactions ayant échoué ne suffit pas à la récupération.
Exemple. L'utilisateur a 500 $ sur son compte et décide de le retirer à un guichet automatique. Deux transactions sont en cours. Le premier lit la valeur du solde et s’il y a suffisamment de fonds sur le solde, il remet de l’argent à l’utilisateur. Le second soustrait le montant requis du solde. Disons que le système est tombé en panne et que la première opération a échoué, mais la seconde a échoué. Dans ce cas, nous ne pouvons pas réémettre de l'argent à l'utilisateur sans remettre le système dans son état d'origine avec un solde positif.
Niveaux d'isolation
Lecture validée
Le problème du Dirty Read est qu’une transaction peut lire le résultat intermédiaire d’une autre transaction.
Exemple. La valeur du solde initial est de 0 $. T1 ajoute 50 $ à votre solde. T2 lit la valeur du solde (50 $). T1 ignore les modifications et quitte. T2 continue l'exécution avec des données de solde incorrectes.
La solution est de lire des données fixes (Read Comended), ce qui interdit de lire les données modifiées par la transaction. Si la transaction A a modifié un certain ensemble de données, alors la transaction B, lors de l'accès à ces données, est obligée d'attendre la fin de la transaction A.
Lecture répétable
Problème de mises à jour perdues. T1 enregistre les modifications en plus de celles de T2.
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 $. T2 ajoute ensuite 200 $ à 0 $ et enregistre le résultat. T1 ajoute 100 $ à 0 $ et enregistre le résultat. Le résultat final 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.
Exemple. T1 lit une valeur de solde de 0 $. T2 ajoute ensuite 50 $ au solde et se termine. T1 relit les données et trouve un écart avec le résultat précédent.
La lecture répétable garantit qu'une deuxième lecture renverra le même résultat. Les données lues par une transaction ne peuvent pas être modifiées dans d'autres jusqu'à ce que la transaction soit terminée. Si la transaction A a lu un certain ensemble de données, alors la transaction B, lors de l'accès à ces données, est obligée d'attendre la fin de la transaction A.
Lecture ordonnée (sérialisable)
Problème de lecture fantôme. Deux requêtes qui sélectionnent des données en fonction d'une certaine condition renvoient des valeurs différentes.
Exemple. T1 demande le nombre de tous les utilisateurs dont le solde est supérieur à 0 $ mais inférieur à 100 $. T2 déduit 1 $ d'un utilisateur avec un solde de 101 $. T1 réémet la demande.
Lecture ordonnée (sérialisable). Les transactions sont exécutées de manière complètement séquentielle. Il est interdit de mettre à jour ou d'ajouter des enregistrements entrant dans les termes de la demande. Si la transaction A a demandé des données sur la table entière, la table entière est gelée pour d'autres transactions jusqu'à ce que la transaction A soit terminée.
Planificateur
Définit l'ordre dans lequel les opérations doivent être effectuées lors des transactions parallèles.
Fournit un niveau d’isolement spécifié. Si le résultat des opérations ne dépend pas de leur ordre, alors ces opérations sont commutatives (permutables). Les opérations de lecture et les opérations sur différentes données sont commutatives. Les opérations de lecture-écriture et d'écriture-écriture ne sont pas commutatives. La tâche du planificateur est d'entrelacer 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 tâches parallèles (Concurrency Control)
L’optimisme repose sur la détection et la résolution des conflits, le pessimiste repose sur la prévention des conflits.
Dans l’approche optimiste, plusieurs utilisateurs disposent de copies des données. La première personne à terminer l'édition enregistre les modifications, tandis que les autres doivent fusionner les modifications. Un algorithme optimiste permet qu'un conflit se produise, mais le système doit se remettre du conflit.
Avec une approche pessimiste, le premier utilisateur à capturer les données empêche les autres de les recevoir. Si les conflits sont rares, il est sage de choisir la stratégie optimiste, car elle offre un niveau de concurrence plus élevé.
Verrouillage
Si une transaction a verrouillé des données, les autres transactions doivent attendre qu'elles soient déverrouillées lors de l'accès aux données.
Un bloc peut être superposé sur une base de données, une table, une ligne ou un attribut. Shared Lock peut être imposé sur les mêmes données par plusieurs transactions, permet la lecture de toutes les transactions (y compris celle qui l'a imposé), interdit la modification et la capture exclusive. Le verrouillage exclusif peut être imposé par une seule transaction, autorise toutes les actions de la transaction imposante, interdit toute action des autres.
Une impasse est une situation dans laquelle les transactions se retrouvent dans un état en attente qui dure indéfiniment.
Exemple. La première transaction attend que les données capturées par la seconde soient libérées, tandis que la seconde attend que les données capturées par la première soient libérées.
Une solution optimiste au problème de blocage permet au blocage de se produire, mais récupère ensuite le système en annulant l'une des transactions impliquées dans le blocage.
Les blocages sont recherchés à certains intervalles. L'une des méthodes de détection est le temps, c'est-à-dire considérer qu'un blocage s'est produit si la transaction prend trop de temps à se terminer. Lorsqu'un blocage est détecté, l'une des transactions est annulée, permettant ainsi 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 sur son ancienneté (systèmes Wait-Die et Wound-wait).
Chaque transaction T un horodatage est attribué TS contenant l'heure de début de la transaction.
Attendez-Meurs.
si TS(Ti) < TS(Tj)puis Ti attend, sinon Ti revient en arrière et recommence avec le même horodatage.
Si une jeune transaction a acquis une ressource et qu'une transaction plus ancienne demande la même ressource, alors la transaction la plus ancienne est autorisée à attendre. Si une transaction plus ancienne a acquis une ressource, la transaction la plus jeune demandant cette ressource sera annulée.
Blessure-attendez.
si TS(Ti) < TS(Tj)puis Tj revient en arrière et recommence avec le même horodatage, sinon Ti attendre.
Si une transaction plus récente a acquis une ressource et qu'une transaction plus ancienne demande la même ressource, la transaction la plus jeune sera annulée. Si une transaction plus ancienne a acquis une ressource, la transaction la plus jeune demandant cette ressource est autorisée à attendre. La sélection des victimes basée sur la priorité évite les blocages, mais annule les transactions qui ne sont pas bloquées. Le problème est que les transactions peuvent être annulées plusieurs fois car... une transaction plus ancienne peut conserver la ressource pendant une longue période.
Une solution pessimiste au problème de blocage ne permet pas à une transaction de commencer à s'exécuter s'il existe un risque de blocage.
Pour détecter une impasse, un graphe est construit (waiting graph, wait-for-graph), dont les sommets sont des transactions, et les arêtes sont dirigées depuis les transactions en attente de libération de données vers la transaction qui a capturé ces données. Un blocage est considéré comme survenu si le graphique comporte une boucle. Construire un graphe d'attente, en particulier dans les bases de données distribuées, est une procédure coûteuse.
Verrouillage en deux phases - évite les blocages en saisissant toutes les ressources utilisées par une transaction au début de la transaction et en les libérant à la fin
Toutes les opérations de blocage doivent précéder la première opération de déverrouillage. Il comporte deux phases : la phase de croissance, pendant laquelle les poignées s'accumulent, et la phase de rétrécissement, pendant laquelle les poignées sont relâchées. S'il est impossible de capturer l'une des ressources, la transaction recommence. Il est possible qu'une transaction ne puisse pas acquérir les ressources requises, par exemple si plusieurs transactions sont en concurrence pour les mêmes ressources.
Une 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 saisit les informations sur les données qui seront modifiées dans le journal et répond au coordinateur OK (phase de vote). Après que tout le monde a répondu OK, le coordinateur envoie un signal obligeant chacun à s'engager. Après la validation, les serveurs répondent OK ; si au moins un ne répond pas OK, alors le coordinateur envoie un signal pour annuler les modifications à tous les serveurs (phase d'achèvement).
Méthode d'horodatage
Une transaction plus ancienne est annulée lors de la tentative d'accès aux données impliquées par une transaction plus récente.
Chaque transaction se voit attribuer un horodatage TS correspondant à l'heure de début d'exécution. Si Ti sur Tjpuis 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) — horodatage de la plus récente transaction ayant complété avec succès un enregistrement sur Q. R-TS(Q) — horodatage de la transaction la plus récente ayant effectué un enregistrement de lecture sur Q.
Lorsque la transaction T demandes de lecture de données Q Il existe deux options.
si TS(T) < W-TS(Q), c'est-à-dire que les données ont été mises à jour par une transaction plus récente, puis la transaction T recule.
si TS(T) >= W-TS(Q), puis la lecture est effectuée et R-TS(Q) devient MAX(R-TS(Q), TS(T)).
Lorsque la transaction T demande des modifications de données Q Il existe deux options.
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 une modification est apportée, un conflit surviendra. Transaction T recule.
si TS(T) < W-TS(Q), c'est-à-dire que la transaction tente d'écraser une valeur plus récente, la transaction T est annulée. Dans les autres cas, le changement est effectué et W-TS(Q) devient égal TS(T).
Aucune construction coûteuse de graphe d’attente n’est requise. Les transactions plus anciennes dépendent des plus récentes, il n'y a donc pas de cycles dans le graphique d'attente. Il n'y a pas de blocage car les transactions ne sont pas attendues mais annulées immédiatement. Des restaurations en cascade sont possibles. Si Ti roulé, et Tj J'ai lu les données que j'ai modifiées Tipuis Tj devrait également revenir en arrière. Si en même temps Tj a déjà été commis, il y aura alors violation du principe de stabilité.
Une des solutions aux rollbacks en cascade. Une transaction termine toutes les opérations d'écriture à la fin et les autres transactions doivent attendre la fin de cette opération. Les transactions attendent d'être validées avant d'être lues.
Règle d'écriture Thomas - une variante de la méthode d'horodatage dans laquelle il est interdit aux données mises à jour par une transaction plus récente d'être écrasées par une transaction plus ancienne.
Transaction T demande des modifications de données Q. Si TS(T) < W-TS(Q), c'est-à-dire que la transaction tente d'écraser une valeur plus récente, la transaction T n'est pas annulée comme dans la méthode d'horodatage.
Source: habr.com