Transaktionen
Eine Transaktion ist eine Abfolge von Datenoperationen mit einem Anfang und einem Ende.
Eine Transaktion ist die sequentielle Ausführung von Lese- und Schreibvorgängen. Das Ende einer Transaktion kann entweder das Speichern der Änderungen (Commit) oder das Abbrechen der Änderungen (Rollback) sein. Bezogen auf eine Datenbank besteht eine Transaktion aus mehreren Anfragen, die als eine einzige Anfrage behandelt werden.
Transaktionen müssen ACID-Eigenschaften erfüllen
Atomarität. Die Transaktion wird entweder vollständig oder gar nicht abgeschlossen.
Konsistenz. Beim Abschluss einer Transaktion dürfen die den Daten auferlegten Beschränkungen (z. B. Einschränkungen in der Datenbank) nicht verletzt werden. Konsistenz bedeutet, dass das System von einem korrekten Zustand in einen anderen korrekten Zustand überführt wird.
Isolierung. Parallel laufende Transaktionen sollten sich nicht gegenseitig beeinflussen, beispielsweise Daten ändern, die von einer anderen Transaktion verwendet werden. Das Ergebnis der Ausführung paralleler Transaktionen sollte dasselbe sein, als ob die Transaktionen nacheinander ausgeführt würden.
Nachhaltigkeit. Nach der Festschreibung sollten Änderungen nicht verloren gehen.
Transaktionsprotokoll
Das Protokoll speichert durch Transaktionen vorgenommene Änderungen und gewährleistet die Atomizität und Stabilität der Daten im Falle eines Systemausfalls
Das Protokoll enthält die Werte, die die Daten vor und nach der Änderung durch die Transaktion hatten. Die Protokollstrategie zum Vorausschreiben erfordert das Hinzufügen eines Protokolleintrags über vorherige Werte vor dem Start und über endgültige Werte nach Abschluss der Transaktion. Im Falle eines plötzlichen Systemstopps liest die Datenbank das Protokoll in umgekehrter Reihenfolge und verwirft die durch Transaktionen vorgenommenen Änderungen. Wenn eine unterbrochene Transaktion festgestellt wird, führt die Datenbank diese aus und nimmt Änderungen daran im Protokoll vor. Da sich die Datenbank im Zustand zum Zeitpunkt des Fehlers befindet, liest sie das Protokoll in Vorwärtsreihenfolge und gibt die durch Transaktionen vorgenommenen Änderungen zurück. Auf diese Weise bleiben die Stabilität bereits festgeschriebener Transaktionen und die Atomizität der unterbrochenen Transaktion erhalten.
Die bloße erneute Ausführung fehlgeschlagener Transaktionen reicht für die Wiederherstellung nicht aus.
Beispiel. Der Benutzer hat 500 $ auf seinem Konto und beschließt, diese an einem Geldautomaten abzuheben. Zwei Transaktionen sind im Gange. Der erste liest den Saldowert und gibt dem Benutzer Geld aus, wenn genügend Guthaben vorhanden ist. Der zweite zieht den erforderlichen Betrag vom Restbetrag ab. Nehmen wir an, das System ist abgestürzt und der erste Vorgang ist fehlgeschlagen, der zweite jedoch. In diesem Fall können wir dem Benutzer kein Geld erneut auszahlen, ohne das System in seinen ursprünglichen Zustand mit einem positiven Saldo zurückzusetzen.
Isolationsniveaus
Lesen Sie Committed
Das Dirty-Read-Problem besteht darin, dass eine Transaktion das Zwischenergebnis einer anderen Transaktion lesen kann.
Beispiel. Der anfängliche Saldowert beträgt 0 $. T1 fügt Ihrem Guthaben 50 $ hinzu. T2 liest den Saldowert (50 $). T1 verwirft die Änderungen und wird beendet. T2 setzt die Ausführung mit falschen Bilanzdaten fort.
Die Lösung besteht darin, feste Daten zu lesen (Read Committed), was das Lesen von durch die Transaktion geänderten Daten verhindert. Wenn Transaktion A einen bestimmten Datensatz geändert hat, muss Transaktion B beim Zugriff auf diese Daten warten, bis Transaktion A abgeschlossen ist.
Wiederholbares Lesen
Problem mit verlorenen Updates. T1 speichert Änderungen zusätzlich zu den Änderungen von T2.
Beispiel. Der anfängliche Saldowert beträgt 0 $ und zwei Transaktionen gleichzeitig füllen den Saldo auf. T1 und T2 zeigen einen Saldo von 0 $ an. T2 addiert dann 200 $ zu 0 $ und speichert das Ergebnis. T1 addiert 100 $ zu 0 $ und speichert das Ergebnis. Das Endergebnis beträgt 100 $ statt 300 $.
Unwiederholbares Leseproblem. Das wiederholte Lesen derselben Daten liefert unterschiedliche Werte.
Beispiel. T1 liest einen Saldowert von 0 $. T2 fügt dann 50 $ zum Guthaben hinzu und endet. T1 liest die Daten erneut und stellt eine Diskrepanz zum vorherigen Ergebnis fest.
Wiederholbarer Lesevorgang stellt sicher, dass ein zweiter Lesevorgang das gleiche Ergebnis zurückgibt. Von einer Transaktion gelesene Daten können in anderen Transaktionen nicht geändert werden, bis die Transaktion abgeschlossen ist. Wenn Transaktion A einen bestimmten Datensatz gelesen hat, muss Transaktion B beim Zugriff auf diese Daten warten, bis Transaktion A abgeschlossen ist.
Geordnetes Lesen (serialisierbar)
Phantom-Reads-Problem. Zwei Abfragen, die Daten basierend auf einer bestimmten Bedingung auswählen, geben unterschiedliche Werte zurück.
Beispiel. T1 fordert die Anzahl aller Benutzer an, deren Guthaben größer als 0 $, aber kleiner als 100 $ ist. T2 zieht 1 $ von einem Benutzer mit einem Guthaben von 101 $ ab. T1 gibt die Anfrage erneut aus.
Geordnetes Lesen (serialisierbar). Transaktionen werden vollständig sequentiell ausgeführt. Es ist verboten, Datensätze zu aktualisieren oder hinzuzufügen, die den Bedingungen der Anfrage entsprechen. Wenn Transaktion A Daten aus der gesamten Tabelle angefordert hat, wird die gesamte Tabelle für andere Transaktionen eingefroren, bis Transaktion A abgeschlossen ist.
Planer
Legt die Reihenfolge fest, in der Vorgänge während paralleler Transaktionen ausgeführt werden sollen.
Bietet eine bestimmte Isolationsstufe. Wenn das Ergebnis von Operationen nicht von ihrer Reihenfolge abhängt, sind solche Operationen kommutativ (permutierbar). Leseoperationen und Operationen an verschiedenen Daten sind kommutativ. Lese-Schreib- und Schreib-Schreibvorgänge sind nicht kommutativ. Die Aufgabe des Schedulers besteht darin, von parallelen Transaktionen ausgeführte Vorgänge so zu verschachteln, dass das Ausführungsergebnis der sequentiellen Ausführung von Transaktionen entspricht.
Mechanismen zur Steuerung paralleler Jobs (Concurrency Control)
Beim Optimismus geht es darum, Konflikte zu erkennen und zu lösen, beim Pessimismus geht es darum, das Entstehen von Konflikten zu verhindern.
Beim optimistischen Ansatz stehen mehreren Benutzern Kopien der Daten zur Verfügung. Die erste Person, die die Bearbeitung abschließt, speichert die Änderungen, während die anderen die Änderungen zusammenführen müssen. Ein optimistischer Algorithmus lässt das Auftreten von Konflikten zu, das System muss sich jedoch von dem Konflikt erholen.
Bei einem pessimistischen Ansatz verhindert der erste Benutzer, der die Daten erfasst, dass andere Benutzer die Daten erhalten. Wenn Konflikte selten auftreten, ist es sinnvoll, die optimistische Strategie zu wählen, da sie ein höheres Maß an Parallelität bietet.
Sperren
Wenn eine Transaktion Daten gesperrt hat, müssen andere Transaktionen warten, bis die Daten entsperrt werden, wenn sie auf die Daten zugreifen.
Ein Block kann einer Datenbank, einer Tabelle, einer Zeile oder einem Attribut überlagert werden. Eine gemeinsame Sperre kann von mehreren Transaktionen auf dieselben Daten angewendet werden, ermöglicht das Lesen aller Transaktionen (einschließlich derjenigen, die sie verhängt hat) und verbietet Änderungen und exklusive Erfassungen. Eine exklusive Sperre kann nur für eine Transaktion auferlegt werden, erlaubt alle Aktionen der auferlegenden Transaktion und verbietet alle Aktionen anderer.
Ein Deadlock ist eine Situation, in der Transaktionen in einem auf unbestimmte Zeit andauernden Status „Ausstehend“ enden.
Beispiel. Die erste Transaktion wartet auf die Freigabe der von der zweiten erfassten Daten, während die zweite auf die Freigabe der von der ersten erfassten Daten wartet.
Eine optimistische Lösung des Deadlock-Problems lässt zu, dass der Deadlock auftritt, stellt dann aber das System wieder her, indem eine der am Deadlock beteiligten Transaktionen zurückgesetzt wird.
In bestimmten Zeitabständen wird nach Deadlocks gesucht. Eine der Erkennungsmethoden ist die Zeiterkennung, d. h. es wird davon ausgegangen, dass ein Deadlock aufgetreten ist, wenn die Transaktion zu lange bis zum Abschluss dauert. Wenn ein Deadlock festgestellt wird, wird eine der Transaktionen zurückgesetzt, sodass andere am Deadlock beteiligte Transaktionen abgeschlossen werden können. Die Auswahl des Opfers kann auf dem Wert der Transaktionen oder ihrem Dienstalter basieren (Wait-Die- und Wound-Wait-Systeme).
Jede Transaktion T es wird ein Zeitstempel vergeben TS Enthält die Startzeit der Transaktion.
Warten-sterben.
wenn TS(Ti) < TS(Tj)dann Ti wartet, sonst Ti Rollt zurück und beginnt erneut mit demselben Zeitstempel.
Wenn eine junge Transaktion eine Ressource erworben hat und eine ältere Transaktion dieselbe Ressource anfordert, darf die ältere Transaktion warten. Wenn eine ältere Transaktion eine Ressource erworben hat, wird die jüngere Transaktion, die diese Ressource anfordert, zurückgesetzt.
Wund-warten.
wenn TS(Ti) < TS(Tj)dann Tj Andernfalls wird ein Rollback durchgeführt und mit demselben Zeitstempel erneut gestartet Ti warten.
Wenn eine jüngere Transaktion eine Ressource erworben hat und eine ältere Transaktion dieselbe Ressource anfordert, wird die jüngere Transaktion zurückgesetzt. Wenn eine ältere Transaktion eine Ressource erworben hat, darf die jüngere Transaktion, die diese Ressource anfordert, warten. Die vorrangige Opferauswahl verhindert Deadlocks, setzt jedoch Transaktionen zurück, die nicht blockiert sind. Das Problem besteht darin, dass Transaktionen viele Male zurückgesetzt werden können, weil ... Eine ältere Transaktion kann die Ressource für längere Zeit halten.
Eine pessimistische Lösung des Deadlock-Problems erlaubt nicht, dass eine Transaktion mit der Ausführung beginnt, wenn die Gefahr eines Deadlocks besteht.
Um einen Deadlock zu erkennen, wird ein Diagramm erstellt (Wartediagramm, Wait-for-Graph), dessen Eckpunkte Transaktionen sind und dessen Kanten von Transaktionen, die auf die Freigabe von Daten warten, auf die Transaktion gerichtet sind, die diese Daten erfasst hat. Ein Deadlock liegt dann vor, wenn das Diagramm eine Schleife aufweist. Das Erstellen eines Wartediagramms ist insbesondere in verteilten Datenbanken ein kostspieliges Verfahren.
Zwei-Phasen-Sperre – verhindert Deadlocks, indem alle von einer Transaktion verwendeten Ressourcen zu Beginn der Transaktion belegt und am Ende freigegeben werden
Alle Sperrvorgänge müssen vor dem ersten Entsperrvorgang erfolgen. Es besteht aus zwei Phasen: der Wachstumsphase, in der sich die Griffe ansammeln, und der Schrumpfungsphase, in der die Griffe gelöst werden. Wenn es nicht möglich ist, eine der Ressourcen zu erobern, beginnt die Transaktion von vorne. Es ist möglich, dass eine Transaktion nicht in der Lage ist, die erforderlichen Ressourcen zu erhalten, beispielsweise wenn mehrere Transaktionen um dieselben Ressourcen konkurrieren.
Ein zweiphasiges Commit stellt sicher, dass das Commit auf allen Datenbankreplikaten ausgeführt wird
Jede Datenbank trägt Informationen zu den Daten, die geändert werden, in das Protokoll ein und antwortet auf das OK des Koordinators (Abstimmungsphase). Nachdem alle mit „OK“ geantwortet haben, sendet der Koordinator ein Signal, das alle zum Engagement verpflichtet. Nach dem Festschreiben antworten die Server mit OK. Wenn mindestens einer nicht mit OK antwortet, sendet der Koordinator ein Signal zum Abbrechen der Änderungen an alle Server (Abschlussphase).
Zeitstempelmethode
Eine ältere Transaktion wird zurückgesetzt, wenn versucht wird, auf Daten zuzugreifen, die von einer jüngeren Transaktion betroffen sind
Jeder Transaktion wird ein Zeitstempel zugewiesen TS entsprechend der Startzeit der Ausführung. Wenn Ti alter Mann Tjdann TS(Ti) < TS(Tj).
Wenn eine Transaktion zurückgesetzt wird, wird ihr ein neuer Zeitstempel zugewiesen. Jedes Datenobjekt Q Die an der Transaktion beteiligten Personen sind mit zwei Etiketten gekennzeichnet. W-TS(Q) – Zeitstempel der jüngsten Transaktion, die einen Datensatz erfolgreich abgeschlossen hat Q. R-TS(Q) – Zeitstempel der jüngsten Transaktion, bei der ein Lesedatensatz durchgeführt wurde Q.
Wenn die Transaktion T Anfragen zum Lesen von Daten Q Es gibt zwei Möglichkeiten.
wenn TS(T) < W-TS(Q), das heißt, die Daten wurden von einer jüngeren Transaktion als der Transaktion aktualisiert T rollt zurück.
wenn TS(T) >= W-TS(Q), dann wird die Lesung durchgeführt und R-TS(Q) wird werden MAX(R-TS(Q), TS(T)).
Wenn die Transaktion T fordert Datenänderungen an Q Es gibt zwei Möglichkeiten.
wenn TS(T) < R-TS(Q), das heißt, die Daten wurden bereits von einer jüngeren Transaktion gelesen und bei einer Änderung kommt es zu einem Konflikt. Transaktion T rollt zurück.
wenn TS(T) < W-TS(Q)Das heißt, die Transaktion versucht, einen neueren Wert zu überschreiben, und Transaktion T wird zurückgesetzt. In anderen Fällen wird die Änderung durchgeführt und W-TS(Q) wird gleich TS(T).
Es ist keine teure Wartegraphenkonstruktion erforderlich. Ältere Transaktionen hängen von neueren ab, daher gibt es im Wartediagramm keine Zyklen. Es gibt keine Deadlocks, da Transaktionen nicht abgewartet, sondern sofort zurückgesetzt werden. Kaskadierende Rollbacks sind möglich. Wenn Ti weggerollt, und Tj Ich habe die Daten gelesen, die ich geändert habe Tidann Tj sollte auch zurückrollen. Wenn gleichzeitig Tj bereits begangen wurde, liegt ein Verstoß gegen das Stabilitätsprinzip vor.
Eine der Lösungen für kaskadierende Rollbacks. Eine Transaktion schließt alle Schreibvorgänge am Ende ab und andere Transaktionen müssen warten, bis dieser Vorgang abgeschlossen ist. Transaktionen warten darauf, festgeschrieben zu werden, bevor sie gelesen werden.
Thomas-Schreibregel – eine Variante der Zeitstempelmethode, bei der durch eine jüngere Transaktion aktualisierte Daten nicht durch eine ältere überschrieben werden dürfen
Transaktion T fordert Datenänderungen an Q. Wenn TS(T) < W-TS(Q)Das heißt, die Transaktion versucht, einen neueren Wert zu überschreiben. Transaktion T wird nicht wie bei der Zeitstempelmethode zurückgesetzt.
Source: habr.com