Transaktionen
Eine Transaktion bezeichnet eine Folge von Datenoperationen mit einem Anfang und einem Ende.
Eine Transaktion ist die sequenzielle Ausführung von Lese- und Schreiboperationen. Das Ende einer Transaktion kann entweder die Speicherung von Änderungen (Commit) oder die Rückgängigmachung von Änderungen (Rollback) sein. In Bezug auf Datenbanken ist eine Transaktion eine Gruppe von Anfragen, die als eine einzige Anfrage betrachtet werden.
Transaktionen müssen den ACID-Eigenschaften entsprechen.
Atomarität. Eine Transaktion wird entweder vollständig ausgeführt oder gar nicht.
Konsistenz. Beim Abschluss einer Transaktion dürfen die auferlegten Einschränkungen für die Daten (z. B. Constraints in der DB) nicht verletzt werden. Konsistenz bedeutet, dass das System von einem korrekten Zustand in einen anderen korrekten Zustand überführt wird.
Isolation. Parallel ausgeführte Transaktionen dürfen sich nicht gegenseitig beeinflussen, z. B. keine Daten ändern, die von einer anderen Transaktion verwendet werden. Das Ergebnis parallel ausgeführter Transaktionen sollte so sein, als ob die Transaktionen nacheinander durchgeführt worden wären.
Beständigkeit. Nach der Bestätigung dürfen Änderungen nicht verloren gehen.
Transaktionsprotokoll
Das Protokoll speichert Änderungen, die durch Transaktionen vorgenommen wurden, und gewährleistet die Atomarität und die Integritä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 Write-ahead-Log-Strategie erfordert, dass vor Beginn der Transaktion die vorherigen Werte im Protokoll festgehalten werden, und nach Abschluss der Transaktion die Endwerte. Bei einem plötzlichen Systemabsturz liest die Datenbank das Protokoll in umgekehrter Reihenfolge und macht die von den Transaktionen vorgenommenen Änderungen rückgängig. Wenn die Datenbank auf eine unterbrochene Transaktion stößt, führt sie diese aus und ergänzt die Änderungen im Protokoll. Im Zustand zum Zeitpunkt des Absturzes liest die Datenbank das Protokoll in regulärer Reihenfolge und stellt die von Transaktionen vorgenommenen Änderungen wieder her. Auf diese Weise wird die Integrität der bereits bestätigten Transaktionen und die Atomarität unterbrochener Transaktionen sichergestellt.
Ein einfaches Wiederholen fehlgeschlagener Transaktionen reicht nicht aus, um die Wiederherstellung zu gewährleisten.
Beispiel. Der Kontostand des Nutzers beträgt 500 €, und der Nutzer entscheidet sich, Geld am Geldautomaten abzuheben. Es werden zwei Transaktionen ausgeführt. Die erste liest den Kontostand, und wenn genügend Mittel vorhanden sind, gibt sie dem Nutzer das Geld aus. Die zweite zieht den entsprechenden Betrag vom Konto ab. Angenommen, es gab einen Systemfehler, und die erste Transaktion wurde nicht ausgeführt, während die zweite erfolgreich war. In diesem Fall können wir dem Nutzer kein Geld erneut auszahlen, ohne das System in den ursprünglichen Zustand mit einem positiven Kontostand zurückzusetzen.
Isolationsstufen
Lesen von festgelegten Daten (Read Committed)
Das Problem des schmutzigen Lesens (Dirty Read) besteht darin, dass eine Transaktion das Zwischenresultat einer anderen Transaktion lesen kann.
Beispiel. Anfangswert des Kontostands 0 €. T1 fügt 50 € zum Kontostand hinzu. T2 liest den Kontostand (50 €). T1 macht die Änderungen rückgängig und wird beendet. T2 führt seine Verarbeitung mit falschen Kontostandsdaten fort.
Die Lösung besteht darin, dass das Lesen von fixierten Daten (Read Committed) das Lesen von durch Transaktionen geänderten Daten verbietet. Wenn Transaktion A eine bestimmte Menge an Daten geändert hat, muss Transaktion B, wenn sie auf diese Daten zugreifen möchte, auf den Abschluss von Transaktion A warten.
Wiederholtes Lesen (Repeatable Read)
Das Problem der verlorenen Änderungen (Lost Updates). T1 speichert Änderungen über die Änderungen von T2.
Beispiel. Anfangswert des Kontos 0 $ und zwei Transaktionen füllen gleichzeitig das Konto auf. T1 und T2 lesen das Kontoguthaben, das 0 $ beträgt. 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 $ statt 300 $.
Das Problem des nicht wiederholbaren Lesens (Unrepeatable Read). Ein erneutes Lesen derselben Daten gibt unterschiedliche Werte zurück.
Beispiel. T1 liest einen Kontostand von 0 $. Dann fügt T2 50 $ zum Kontostand hinzu und wird abgeschlossen. T1 liest die Daten erneut und stellt fest, dass sie nicht mit dem vorherigen Ergebnis übereinstimmen.
Die wiederholbare Leseebene (Repeatable Read) gewährleistet, dass ein wiederholtes Lesen das gleiche Ergebnis zurückgibt. Daten, die von einer Transaktion gelesen wurden, dürfen von anderen bis zum Abschluss der Transaktion nicht verändert werden. Wenn Transaktion A eine bestimmte Datensätze liest, muss Transaktion B warten, bis Transaktion A abgeschlossen ist, um auf diese Daten zuzugreifen.
Die serielle Lesebene (Serializable)
Das Problem des Phantomlesens (Phantom Reads). Zwei Abfragen, die Daten basierend auf einer Bedingung auswählen, geben unterschiedliche Werte zurück.
Beispiel. T1 fragt die Anzahl aller Benutzer an, deren Kontostand über 0 $ und unter 100 $ liegt. T2 zieht 1 $ von einem Benutzer mit einem Kontostand von 101 $ ab. T1 führt die Abfrage erneut aus.
Serielle Lesebene (Serializable). Transaktionen werden als vollständig sequenziell ausgeführt. Das Aktualisieren und Hinzufügen von Datensätzen, die unter die Abfragebedingungen fallen, ist untersagt. Wenn Transaktion A Daten der gesamten Tabelle angefordert hat, wird die gesamte Tabelle für andere Transaktionen bis zum Abschluss von Transaktion A gesperrt.
Scheduler
Bestimmt die Reihenfolge, in der Operationen bei parallel ablaufenden Transaktionen ausgeführt werden müssen.
Stellt ein festgelegtes Maß an Isolation sicher. Wenn das Ergebnis der Operationen nicht von deren Reihenfolge abhängt, sind solche Operationen kommutativ (Permutable). Leseoperationen und Operationen mit unterschiedlichen Daten sind kommutativ. Lese-Schreib-Operationen und Schreib-Schreib-Operationen sind nicht kommutativ. Die Aufgabe des Planers besteht darin, die von parallel ablaufenden Transaktionen durchgeführten Operationen so abzuwechseln, dass das Ergebnis mit dem des sequenziellen Ablaufs der Transaktionen übereinstimmt.
Mechanismen zur Kontrolle paralleler Aufgaben (Concurrency Control)
Der optimistische Ansatz basiert auf der Erkennung und Behebung von Konflikten, während der pessimistische Ansatz darauf abzielt, Konflikte zu verhindern.
Beim optimistischen Ansatz erhalten mehrere Benutzer Kopien der Daten. Der erste, der die Bearbeitung abschließt, speichert die Änderungen, während die anderen ihre Änderungen zusammenführen müssen. Der optimistische Algorithmus erlaubt einen Konflikt, aber das System muss sich nach dem Konflikt erholen.
Bei einer pessimistischen Herangehensweise blockiert der erste Benutzer, der auf die Daten zugreift, anderen den Zugriff auf diese Daten. Wenn Konflikte selten sind, ist es sinnvoll, eine optimistische Strategie zu wählen, da diese ein höheres Maß an Parallelität bietet.
Sperrung (Locking)
Wenn eine Transaktion Daten sperrt, müssen alle anderen Transaktionen, die auf diese Daten zugreifen möchten, auf die Freigabe warten.
Eine Sperre kann auf eine Datenbank, eine Tabelle, eine Zeile oder ein Attribut angewendet werden. Eine gemeinsame Sperre (Shared Lock) kann auf dieselben Daten von mehreren Transaktionen angewendet werden, erlaubt allen Transaktionen (einschließlich der, die die Sperre gesetzt hat) das Lesen, verbietet jedoch Änderungen und exklusive Sperren. Eine exklusive Sperre (Exclusive Lock) kann nur von einer Transaktion gesetzt werden, erlaubt der sperrenden Transaktion alle Aktionen und verbietet allen anderen Transaktionen jegliche Aktionen.
Eine Deadlock-Situation liegt vor, wenn Transaktionen in einem Zustand der Wartezeit feststecken, der unbegrenzt lange dauert.
Beispiel: Die erste Transaktion wartet auf die Freigabe von Daten, die von der zweiten Transaktion gesperrt sind, während die zweite Transaktion auf die Freigabe von Daten wartet, die von der ersten gesperrt sind.
Die optimistische Lösung für das Deadlock-Problem ermöglicht das Auftreten von Deadlocks, stellt jedoch das System wieder her, indem eine der am Deadlock beteiligten Transaktionen zurückgesetzt wird.
In regelmäßigen Abständen wird nach Deadlocks gesucht. Ein Ansatz zur Erkennung besteht darin, die Ausführungszeit zu überwachen und anzunehmen, dass ein Deadlock aufgetreten ist, wenn eine Transaktion zu lange dauert. Wenn ein Deadlock erkannt wird, wird eine der Transaktionen zurückgesetzt, was anderen am Deadlock beteiligten Transaktionen ermöglicht, abzuschließen. Die Auswahl des Opfers kann auf den Kosten der Transaktionen oder deren Alter beruhen (Wait-Die und Wound-Wait-Strategien).
Jeder Transaktion T wird ein Zeitstempel TS zugewiesen, der den Beginn der Transaktionsausführung enthält.
Wait-Die.
Wenn TS(Ti) < TS(Tj), dann Ti wartet, ansonsten Ti wird zurückgesetzt und beginnt neu mit demselben Zeitstempel.
Wenn eine jüngere Transaktion eine Ressource erlangt hat und eine ältere dieselbe Ressource anfordert, darf die ältere Transaktion warten. Hat jedoch eine ältere Transaktion eine Ressource erlangt, wird die jüngere Transaktion, die diese Ressource anfordert, zurückgesetzt.
Wound-Wait.
Wenn TS(Ti) < TS(Tj), dann Tj rollt zurück und beginnt erneut mit demselben Zeitstempel, andernfalls Ti wartet.
Wenn eine neuere Transaktion eine Ressource beansprucht hat und eine ältere Transaktion dieselbe Ressource anfordert, wird die neuere Transaktion zurückgerollt. Wenn eine ältere Transaktion die Ressource beansprucht hat, darf die jüngere Transaktion, die diese Ressource anfordert, warten. Die Wahl des Opfers basierend auf dem Alter verhindert das Auftreten von Deadlocks, rollt jedoch Transaktionen zurück, die sich nicht im Zustand des Deadlocks befinden. Das Problem besteht darin, dass Transaktionen mehrfach zurückgerollt werden können, da eine ältere Transaktion die Ressource lange halten kann.
Eine pessimistische Lösung für das Deadlock-Problem erlaubt es einer Transaktion nicht, mit der Ausführung zu beginnen, wenn das Risiko eines Deadlocks besteht.
Zur Erkennung von Deadlocks wird ein Graph (Wartegraph, wait-for-graph) erstellt, dessen Knoten Transaktionen darstellen. Die Kanten sind gerichtet von den Transaktionen, die auf die Freigabe von Daten warten, zu den Transaktionen, die diese Daten bereits erfasst haben. Ein Deadlock wird angenommen, wenn der Graph Zyklen aufweist. Der Aufbau des Wart графа, insbesondere in verteilten Datenbanken, ist ein kostenintensiver Prozess.
Die Zwei-Phasen-Sperre verhindert Deadlocks, indem sie zu Beginn der Transaktion alle Ressourcen erfasst, die von der Transaktion benötigt werden, und sie am Ende wieder freigibt.
Alle sperrenden Operationen müssen vor der ersten entsperrenden Operation durchgeführt werden. Es gibt zwei Phasen: die Wachstumsphase (Growing Phase), in der die Sperren akkumuliert werden, und die Schrumpfungsphase (Shrinking Phase), in der die Sperren freigegeben werden. Wenn es nicht möglich ist, eine der benötigten Ressourcen zu erfassen, beginnt die Transaktion von vorn. Es kann vorkommen, dass eine Transaktion die erforderlichen Ressourcen nicht erlangen kann, insbesondere wenn mehrere Transaktionen um dieselben Ressourcen konkurrieren.
Das Zwei-Phasen-Commit gewährleistet die Ausführung des Commits auf allen Replikaten der Datenbank.
Jede Datenbank protokolliert die Informationen über die Daten, die geändert werden sollen, im Log und bestätigt dem Koordinator mit OK (Voting-Phase). Nachdem alle mit OK geantwortet haben, sendet der Koordinator ein Signal, das alle verpflichtet, ein Commit durchzuführen. Nach dem Commit Server antworten mit OK; wenn auch nur einer nicht mit OK antwortet, sendet der Koordinator ein Signal zur Stornierung der Änderungen an alle Server (Completion-Phase).
Methode der Zeitstempel
Eine ältere Transaktion wird zurückgesetzt, wenn versucht wird, auf Daten zuzugreifen, die von einer neueren Transaktion verwendet werden.
Jeder Transaktion wird ein Zeitstempel zugewiesen TS der dem Zeitpunkt des Beginns 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 von der Transaktion verwendet wird, wird mit zwei Zeitstempeln versehen. W-TS(Q) — der Zeitstempel der jüngsten Transaktion, die erfolgreich einen Schreibvorgang über Q. R-TS(Q) — der Zeitstempel der jüngsten Transaktion, die einen Lesevorgang über Q.
Wenn eine Transaktion T eine Anfrage zum Lesen von Daten stellt, Q gibt es zwei Möglichkeiten.
Wenn TS(T) < W-TS(Q), das heißt, die Daten wurden durch eine jüngere Transaktion aktualisiert, dann wird die Transaktion T zurückgesetzt.
Wenn TS(T) >= W-TS(Q), dann wird das Lesen ausgeführt und R-TS(Q) wird MAX(R-TS(Q), TS(T)).
Wenn eine Transaktion T fordert eine Änderung der Daten an Q gibt es zwei Möglichkeiten.
Wenn TS(T) < R-TS(Q), das bedeutet, dass die Daten bereits von einer jüngeren Transaktion gelesen wurden und eine Änderung zu einem Konflikt führen würde. Die Transaktion T zurückgesetzt.
Wenn TS(T) < W-TS(Q), das bedeutet, dass die Transaktion versucht, einen neueren Wert zu überschreiben, wodurch die Transaktion T zurückgerollt wird. In anderen Fällen wird die Änderung erfolgreich durchgeführt und W-TS(Q) wird gleich TS(T).
Es ist kein kostspieliger Aufbau eines Abhängigkeitsgraphen erforderlich. Ältere Transaktionen hängen von neueren ab, daher gibt es keine Zyklen im Warteschlangengraphen. Es gibt keine Deadlocks, da die Transaktionen nicht warten, sondern sofort zurückgerollt werden. Kaskadierende Rollbacks sind möglich. Wenn Ti zurückgerollt wurde, und Tj Daten gelesen wurden, die geändert wurden Ti, dann Tj muss ebenfalls zurückgerollt werden. Wenn dabei Tj schon festgeschrieben wurde, verletzt dies das Prinzip der Konsistenz.
Eine der Lösungen für kaskadierende Rollbacks. Die Transaktion führt alle Schreiboperationen am Ende durch, wobei andere Transaktionen auf den Abschluss dieser Operation warten müssen. Transaktionen warten auf das Commit, bevor sie lesen.
Die Thomas-Schreibregel – eine Variante des Zeitstempelverfahrens, bei dem Daten, die von einer jüngeren Transaktion aktualisiert wurden, nicht von einer älteren zurückgeschrieben werden dürfen.
Transaktion T fordert eine Änderung der Daten an QuseString TS(T) < W-TS(Q), das heißt, die Transaktion versucht, einen neueren Wert zu überschreiben. Die Transaktion T wird nicht wie beim Zeitstempel zurückgesetzt.
Quelle: habr.com
