Transaktionen
Eine Transaktion ist eine Abfolge von Datenoperationen, die einen Anfang und ein Ende hat.
Eine Transaktion ist die sequenzielle Ausführung von Lese- und Schreiboperationen. Das Ende einer Transaktion kann entweder das Speichern von Änderungen (Commit) oder das Zurücksetzen der Änderungen (Rollback) sein. Im Hinblick auf Datenbanken bedeutet eine Transaktion mehrere Anfragen, die als eine einzige Anfrage behandelt werden.
Transaktionen müssen die ACID-Eigenschaften erfüllen.
Atomarität. Eine Transaktion wird entweder vollständig ausgeführt oder gar nicht.
Konsistenz. Bei Abschluss der Transaktion dürfen die Datenbeschränkungen (z. B. Constraints in der DB) nicht verletzt werden. Konsistenz bedeutet, dass das System von einem konsistenten Zustand in einen anderen überführt wird.
Isolierung. Parallel ausgeführte Transaktionen dürfen sich nicht gegenseitig beeinflussen, z. B. keine Daten ändern, die eine andere Transaktion verwendet. Das Ergebnis der parallelen Transaktionen sollte so sein, als wären die Transaktionen sequenziell ausgeführt worden.
Beständigkeit. Nach dem Commit dürfen Änderungen nicht verloren gehen.
Transaktionsprotokoll
Das Protokoll speichert Änderungen, die durch Transaktionen vorgenommen werden, und gewährleistet die Atomarität und Beständigkeit 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 Write-ahead-Log-Strategie verlangt, dass frühere Werte vor Beginn der Transaktion und die Endwerte nach Abschluss der Transaktion im Protokoll festgehalten werden. Im Fall eines plötzlichen Systemstopps liest die Datenbank das Protokoll in umgekehrter Reihenfolge und macht die von den Transaktionen vorgenommenen Änderungen rückgängig. Bei einer unterbrochenen Transaktion führt die Datenbank diese aus und dokumentiert die Änderungen im Protokoll. Im Zustand zum Zeitpunkt des Ausfalls liest die Datenbank das Protokoll in normaler Reihenfolge und stellt die von den Transaktionen vorgenommenen Änderungen wieder her. So wird die Beständigkeit von bereits durchgeführten Transaktionen und die Atomarität der unterbrochenen Transaktion gewährleistet.
Einfaches Wiederholen fehlerhafter Transaktionen reicht nicht aus, um eine Wiederherstellung zu erreichen.
Beispiel. Der Benutzer hat 500$ auf dem Konto und entscheidet, diese über einen Geldautomaten abzuheben. Es werden zwei Transaktionen durchgeführt. Die erste liest den Kontostand und gibt Geld aus, wenn genügend Mittel vorhanden sind. Die zweite zieht den benötigten Betrag vom Kontostand ab. Angenommen, es kam zu einem Systemfehler und die erste Transaktion wurde nicht ausgeführt, während die zweite erfolgreich war. In diesem Fall können wir dem Benutzer kein Geld erneut geben, ohne das System in den ursprünglichen Zustand mit einem positiven Kontostand zurückzuführen.
Isolationsstufen
Lesen von festgelegten Daten (Read Committed)
Das Problem des schmutzigen Lesens (Dirty Read) besteht darin, dass eine Transaktion ein Zwischenergebnis einer anderen Transaktion lesen kann.
Beispiel. Der Anfangsstand beträgt 0$. T1 fügt 50$ zum Stand hinzu. T2 liest den Stand (50$). T1 macht die Änderungen rückgängig und wird abgeschlossen. T2 führt mit falschen Daten zum Stand fort.
Die Lösung besteht darin, festgelegte Daten (Read Committed) zu lesen, die das Lesen von durch die Transaktion geänderten Daten verhindern. Wenn Transaktion A einen bestimmten Datensatz geändert hat, muss Transaktion B warten, bis Transaktion A abgeschlossen ist, um auf diese Daten zuzugreifen.
Wiederholtes Lesen (Repeatable Read)
Das Problem verlorener Änderungen (Lost Updates). T1 speichert Änderungen über den Änderungen von T2.
Beispiel. Der Anfangsstand beträgt 0$ und zwei Transaktionen fügen gleichzeitig zum Stand hinzu. T1 und T2 lesen den Stand als 0$. Dann fügt T2 200$ zu 0$ hinzu und speichert das Ergebnis. T1 fügt 100$ zu 0$ hinzu und speichert das Ergebnis. Das Endergebnis beträgt 100$ anstelle von 300$.
Das Problem des nicht-wiederholbaren Lesens (Unrepeatable Read). Ein erneutes Lesen derselben Daten liefert unterschiedliche Werte.
Beispiel. T1 liest einen Kontostand von 0$. Dann fügt T2 50$ hinzu und wird abgeschlossen. T1 liest die Daten erneut und bemerkt eine Diskrepanz zum vorherigen Ergebnis.
Wiederholtes Lesen (Repeatable Read) garantiert, dass ein erneutes Lesen dasselbe Ergebnis zurückgibt. Daten, die von einer Transaktion gelesen wurden, dürfen bis zum Abschluss der Transaktion nicht von anderen geändert werden. Wenn Transaktion A einen bestimmten Datensatz gelesen hat, muss Transaktion B warten, bis Transaktion A abgeschlossen ist, um auf diese Daten zuzugreifen.
Sortiertes Lesen (Serializable)
Das Problem des Phantomlesens (Phantom Reads). Zwei Abfragen, die Daten aufgrund einer bestimmten Bedingung abrufen, geben unterschiedliche Werte zurück.
Beispiel. T1 fragt die Anzahl aller Benutzer an, deren Kontostand größer als 0 $ und kleiner als 100 $ ist. T2 zieht 1 $ von einem Benutzer mit einem Kontostand von 101 $ ab. T1 führt die Abfrage erneut aus.
Ordnungsgemäßes Lesen (Serializable). Transaktionen werden als vollkommen sequenziell ausgeführt. Es ist verboten, Datensätze zu aktualisieren und hinzuzufügen, die unter die Bedingungen der Abfrage fallen. Wenn Transaktion A die Daten der gesamten Tabelle angefragt hat, wird die Tabelle für die anderen Transaktionen bis zum Abschluss von Transaktion A vollständig eingefroren.
Planer (Scheduler)
Stellt die Reihenfolge fest, in der die Operationen bei parallel ablaufenden Transaktionen ausgeführt werden müssen.
Stellt ein festgelegtes Maß an Isolation sicher. Wenn das Ergebnis der Ausführung der Operationen nicht von ihrer Reihenfolge abhängt, sind solche Operationen kommutativ (Permutable). Leseoperationen und Operationen an verschiedenen Daten sind kommutativ. Lese-Schreib-Operationen und Schreib-Schreib-Operationen sind nicht kommutativ. Die Aufgabe des Planers besteht darin, die Operationen, die von parallelen Transaktionen ausgeführt werden, so abwechselnd zu gestalten, dass das Ergebnis der Ausführung äquivalent zu einer sequenziellen Ausführung der Transaktionen ist.
Mechanismen zur Kontrolle paralleler Aufgaben (Concurrency Control)
Optimistisch basierend auf der Erkennung und Behebung von Konflikten, pessimistisch auf der Verhinderung von Konflikten.
Beim optimistischen Ansatz erhalten mehrere Benutzer Kopien der Daten. Der erste, der die Bearbeitung abschließt, speichert die Änderungen, die anderen müssen dann eine Zusammenführung der Änderungen vornehmen. Der optimistische Algorithmus ermöglicht das Entstehen von Konflikten, aber das System muss sich nach dem Konflikt erholen.
Beim pessimistischen Ansatz verhindert der erste Benutzer, der die Daten erfasst hat, dass andere die Daten erhalten. Wenn Konflikte selten auftreten, ist es sinnvoll, eine optimistische Strategie zu wählen, da sie ein höheres Maß an Parallelität gewährleistet.
Sperrung (Locking)
Wenn eine Transaktion die Daten sperrt, müssen die anderen Transaktionen beim Zugriff auf die Daten auf die Freigabe warten.
Ein Block kann auf eine Datenbank, eine Tabelle, eine Reihe oder ein Attribut angewendet werden. Ein Shared Lock kann auf dieselben Daten von mehreren Transaktionen angewendet werden, erlaubt allen Transaktionen (einschließlich der anwendenden) das Lesen, verbietet jedoch Änderungen und exklusiven Zugriff. Ein Exclusive Lock kann nur von einer Transaktion angewendet werden, erlaubt alle Aktionen der anwendenden Transaktion und verbietet alle Aktionen der anderen.
Als Deadlock bezeichnet man eine Situation, in der Transaktionen in einem Zustand des Wartens feststecken, der unendlich lange dauert.
Beispiel. Die erste Transaktion wartet auf die Freigabe von Daten, die von der zweiten erfasst wurden, während die zweite auf die Freigabe von Daten wartet, die von der ersten erfasst wurden.
Eine optimistische Lösung des Deadlock-Problems ermöglicht es, dass ein Deadlock auftritt, stellt jedoch das System wieder her, indem eine der Transaktionen, die an dem Deadlock beteiligt sind, zurückgesetzt wird.
In bestimmten Zeitabständen wird nach Deadlocks gesucht. Eine der Möglichkeiten zur Erkennung ist die Zeit: Man betrachtet eine Situation als Deadlock, wenn eine Transaktion zu lange ausgeführt wird. Wenn ein Deadlock erkannt wird, wird eine der Transaktionen zurückgesetzt, was es den anderen Transaktionen, die am Deadlock beteiligt sind, ermöglicht, abzuschließen. Die Wahl des Opfers kann auf den Kosten der Transaktionen oder ihrem Alter basieren (Wait-Die- und Wound-Wait-Schemata).
Jeder Transaktion T wird ein Zeitstempel zugewiesen TS der die Startzeit der Ausführung der Transaktion enthält.
Wait-Die.
Wenn TS(Ti) < TS(Tj), dann Ti wartet, andernfalls Ti wird zurückgesetzt und beginnt mit demselben Zeitstempel neu.
Wenn eine junge Transaktion eine Ressource erfasst hat und eine ältere dieselbe Ressource anfordert, darf die ältere Transaktion warten. Wenn die ältere Transaktion eine Ressource erfasst hat, wird die junge Transaktion, die diese Ressource anfordert, zurückgesetzt.
Wound-Wait.
Wenn TS(Ti) < TS(Tj), dann Tj wird zurückgesetzt und beginnt mit demselben Zeitstempel neu, andernfalls Ti wartet.
Wenn eine jüngere Transaktion eine Ressource erfasst hat und eine ältere Transaktion dieselbe Ressource anfordert, wird die jüngere Transaktion zurückgerollt. Wenn eine ältere Transaktion die Ressource erfasst hat, darf die jüngere Transaktion, die diese Ressource anfordert, warten. Die Auswahl des Opfers basierend auf dem Alter verhindert das Auftreten von Deadlocks, rollt jedoch Transaktionen zurück, die sich in keinem Deadlock-Zustand befinden. Das Problem besteht darin, dass Transaktionen mehrmals zurückgerollt werden können, da eine ältere Transaktion die Ressource lange halten kann.
Die pessimistische Lösung für das Problem der Deadlocks erlaubt es einer Transaktion nicht, die Ausführung zu beginnen, wenn das Risiko eines Deadlocks besteht.
Zur Erkennung von Deadlocks wird ein Diagramm (Wartegraf, wait-for-graph) erstellt, dessen Knoten Transaktionen sind und dessen Kanten von Transaktionen, die auf die Freigabe von Daten warten, zu der Transaktion führen, die diese Daten erfasst hat. Es wird angenommen, dass ein Deadlock aufgetreten ist, wenn das Diagramm eine Zyklenbildung aufweist. Der Aufbau des Wartediagramms, insbesondere in verteilten Datenbanken, ist ein kostspieliger Prozess.
Zwei-Phasen-Sperre — Vermeidung von Deadlocks durch Erfassung aller Ressourcen, die von einer Transaktion zu Beginn der Transaktion verwendet werden, und Freigabe dieser Ressourcen am Ende.
Alle sperrenden Operationen müssen der ersten freigebenden Operation vorausgehen. Es gibt zwei Phasen — die Wachstumsphase, in der Ressourcen erfasst werden, und die Schrumpfungsphase, in der Ressourcen freigegeben werden. Wenn es nicht möglich ist, eine der Ressourcen zu erfassen, beginnt die Transaktion neu. Es kann vorkommen, dass eine Transaktion die benötigten Ressourcen nicht erfassen kann, zum Beispiel wenn mehrere Transaktionen um dieselben Ressourcen konkurrieren.
Das Zwei-Phasen-Commit gewährleistet die Durchführung des Commits auf allen Replikaten der Datenbank.
Jede Datenbank fügt Informationen über die Daten, die geändert werden sollen, in das Protokoll ein und antwortet dem Koordinator mit OK (Voting Phase). Nachdem alle mit OK geantwortet haben, sendet der Koordinator ein Signal, das alle verpflichtet, den Commit durchzuführen. Nach dem Commit Server antworten sie mit OK; wenn auch nur einer nicht mit OK geantwortet hat, sendet der Koordinator ein Signal zum Abbrechen der Änderungen an alle Server (Completion Phase).
Methode der Zeitstempel.
Eine ältere Transaktion wird zurückgerollt, wenn versucht wird, auf Daten zuzugreifen, die von einer jüngeren Transaktion verwendet werden.
Jedem Transaktion wird ein Zeitstempel zugewiesen TS der dem Beginn der Ausführung entspricht. Wenn Ti älter Tj, dann TS(Ti) < TS(Tj).
Wenn eine Transaktion zurückgesetzt wird, erhält sie einen neuen Zeitstempel. Jedes Datenobjekt Q das durch die Transaktion betroffen ist, wird mit zwei Zeitstempeln markiert. W-TS(Q) — der Zeitstempel der jüngsten Transaktion, die einen Schreibvorgang über Q. R-TS(Q) — der Zeitstempel der jüngsten Transaktion, die einen Lesevorgang über Q.
Wenn die Transaktion T eine Datenleseanfrage stellt, Q gibt es zwei Möglichkeiten.
Wenn TS(T) < W-TS(Q), das heißt, die Daten wurden von einer jüngeren Transaktion aktualisiert, dann wird die Transaktion T rückgesetzt.
Wenn TS(T) >= W-TS(Q), dann wird das Lesen durchgeführt und R-TS(Q) wird MAX(R-TS(Q), TS(T)).
Wenn die Transaktion T eine Datenänderung anfragt, Q gibt es zwei Möglichkeiten.
Wenn TS(T) < R-TS(Q), das heißt, die Daten wurden bereits von einer jüngeren Transaktion gelesen und wenn die Änderung durchgeführt wird, entsteht ein Konflikt. Die Transaktion T rückgesetzt.
Wenn TS(T) < W-TS(Q), das heißt, die Transaktion versucht, einen neueren Wert zu überschreiben, wird die Transaktion T zurückgesetzt. In anderen Fällen wird die Änderung vorgenommen und W-TS(Q) wird gleich TS(T).
Es ist kein kostspieliger Aufbau eines Wartegraphen erforderlich. Ältere Transaktionen sind von neueren abhängig, daher gibt es im Wartegraphen keine Zyklen. Es gibt keine Deadlocks, da Transaktionen nicht warten, sondern sofort zurückgesetzt werden. Kaskadierende Rücksetzungen sind möglich. Wenn Ti zurückgesetzt wurde, und Tj Daten gelesen hat, die sie geändert hat, Ti, dann Tj muss auch zurückgesetzt werden. Wenn dies der Fall ist, Tj bereits festgeschrieben wurde, führt dies zu einem Verstoß gegen das Stabilitätsprinzip.
Eine der Lösungen für kaskadierende Rücksetzungen. Die Transaktion führt alle Schreibvorgänge am Ende durch, und die anderen Transaktionen müssen auf den Abschluss dieser Operation warten. Transaktionen warten auf das Commit, bevor sie lesen.
Thomas-Schreibregel — eine Variation der Zeitstempel-Methode, bei der Daten, die von einer jüngeren Transaktion aktualisiert wurden, nicht von einer älteren überschrieben werden dürfen.
Die Transaktion T eine Datenänderung anfragt, Q. Wenn TS(T) < W-TS(Q), das heißt, die Transaktion versucht, einen neueren Wert zu überschreiben, wird die Transaktion T nicht wie bei der Zeitstempel-Methode zurückgesetzt.
Quelle: habr.com
