7.2.1 Verteiltes Zwei-Phasen-Commit (Basis-Protokoll)

7.2 Commit-Behandlung

7.2.1 Verteiltes Zwei-Phasen-Commit (Basis-Protokoll)

Als Basis-Protokoll betrachten wir ein verteiltes Zwei-Phasen-Commit-Protokoll mit zentralisierter Kommunikationsstruktur zwischen Koordinator und Agenten [Gr78, MLO86]. Der Nachrichtenfluß dieses Protokolls ist in Abb. 7-3 skizziert, wobei die gezeigten Nachrichten für jeden Agenten anfallen. Im einzelnen laufen dabei folgende Schritte ab:

Abb. 7-3: Nachrichtenfluß im 2PC-Basisprotokoll

1. Bei Transaktionsende sendet der Koordinator eine PREPARE-Nachricht gleichzeitig an alle Agenten, um deren lokales Commit-Ergebnis in Erfahrung zu bringen.

2. Nach Empfang der PREPARE-Nachricht sichert der Agent einer erfolgreich zu Ende gekommene Sub-Transaktion deren Wiederholbarkeit durch das Ausschreiben von möglicherweise noch ungesicherten Log-Daten sowie eines Prepared-Satzes auf die lokale Log-Datei. Anschließend sendet der Agent eine READY-Nachricht an den Koordinator zurück. Danach wartet der Agent bis der Koordinator den Ausgang der globalen Transaktion (Commit oder Abort) mitteilt.
Für eine gescheiterte Sub-Transaktion werden ein Abort-Satz auf die lokale Log-Datei geschrieben und eine FAILED-Nachricht zum Koordinator geschickt. Der Agent setzt die Sub-Transaktion zurück, wobei auch von ihr gehaltene Sperren freigegeben werden[26]. Da das Scheitern der globalen Transaktion damit feststeht, wird die Sub-Transaktion daraufhin bereits beendet.

3. Nach Eintreffen aller Antwortnachrichten der Agenten beim Koordinator ist Phase 1 beendet. Haben alle Agenten mit READY geantwortet (und war das lokale Commit-Ergebnis am Koordinator-Knoten auch positiv), schreibt der Koordinator einen Commit-Satz in die lokale Log-Datei, woraufhin die globale Transaktion als erfolgreich beendet gilt. Danach wird eine COMMIT-Nachricht gleichzeitig an alle Agenten gesendet.
Stimmte mindestens ein Agent mit FAILED, so ist damit auch die globale Transaktion zum Scheitern verurteilt. Der Koordinator schreibt daher einen Abort-Satz auf seinen Log und sendet eine ABORT-Nachricht an alle Agenten, die mit READY gestimmt haben.

4. Ein Agent schreibt nach Eintreffen einer COMMIT-Nachricht ebenfalls einen Commit-Satz auf die Log-Datei und gibt anschließend die Sperren der Sub-Transaktion frei. Bei einer ABORT-Nachricht werden ein Abort-Satz geschrieben und die Sub-Transaktion zurückgesetzt, wobei gehaltene Sperren ebenfalls freigegeben werden.
Der Agent sendet danach zur Bestätigung noch eine Quittung (ACK-Nachricht) an den Koordinator. Nach Eintreffen aller ACK-Nachrichten beim Koordinator ist die globale Transaktion beendet, was durch einen Ende-Satz in der Log-Datei des Koordinators vermerkt wird.

Das Basisprotokoll erfordert pro Agent 4 Nachrichten, so daß bei einer über N Knoten verteilten globalen Transaktion insgesamt 4*(N-1) Nachrichten zur Commit-Behandlung anfallen. Weiterhin sind für den Koordinator sowie jeden Agenten zwei Schreibvorgänge auf die Log-Datei erforderlich. Bis auf den Ende-Satz sind diese Schreibvorgänge synchron, das heißt, die weitere Verarbeitung wird durch die E/A-Dauer verzögert. Es fallen somit insgesamt 2N-1 solcher synchronen Log-Vorgänge an.

Jeder an einer globalen Transaktion beteiligte Agent hat bis zur lokalen Commit-Entscheidung in Phase 1 das Recht des "unilateral abort", d.h. des einseitigen Transaktionsabbruchs. Dieses Recht wird jedoch nach Senden der READY-Nachricht aufgegeben; stattdessen wird die Verpflichtung übernommen, das globale Commit-Ergebnis des Koordinators zu akzeptieren. Die damit eingeführte Abhängigkeit zum Koordinator ist ein Hauptproblem des 2PC-Protokolls. Denn ein Koordinatorausfall kann dazu führen, daß andere Knoten lange Zeit auf das globale Commit-Ergebnis warten müssen (i.a. bis der Koordinator-Knoten wieder funktionsfähig ist). Da jedoch Sperren für die betroffenen Sub-Transaktionen bis zur globalen Entscheidung zu halten sind, kann dies zu erheblichen Leistungsproblemen ("Blockierungen") für andere Transaktionen führen.

Die Korrektheit des Protokolls im Normalbetrieb ist offensichtlich. Es bleibt also noch zu zeigen, wie unterschiedliche Fehlersituationen korrekt behandelt werden können. Hierzu ist die Betrachtung von Zustandsübergängen während der Commit-Bearbeitung hilfreich, wie sie in Abb. 7-4 für den Koordinator sowie die Agenten gezeigt sind. Die Knoten entsprechen dabei den einzelnen Zuständen, die Verbindungen zwischen ihnen den Zustandsübergängen. Zustandsübergänge sind durch zwei Angaben gekennzeichnet, die den Übergang auslösende Aktion (oben) sowie die dadurch veranlaßten Aktionen (unten).

Die Diagramme repräsentieren eine andere Darstellung des oben beschriebenen 2PC-Protokolls. Neu hinzugekommen sind vor allem die Berücksichtigung von Timeout-Ereignissen, über die Rechnerausfälle sowie Kommunikationsfehler abgefangen werden. Der Koordinator (Abb. 7-4a) befindet sich zunächst in einem Initialzustand (INITIAL). Nach Eingang der EOT-Operation wird für die betreffende Transaktion das Commit-Protokoll durch Verschicken der PREPARE-Nachrichten gestartet. Der Koordinator geht daraufhin in einen Wartezustand (WAIT). Nachdem alle Agenten mit READY gestimmt haben, wird das positive Commit-Ergebnis protokolliert und mitgeteilt; der Koordinator befindet sich jetzt im Zustand COMMITTING. Nach Eintreffen aller ACK-Nachrichten wird ein Ende-Satz auf den Log geschrieben, der den Endzustand TERMINATED kennzeichnet. Der Koordinator veranlaßt den Abbruch einer Transaktion, wenn einer der Agenten mit FAILED stimmt oder nicht innerhalb eines spezifizierten Timeout-Intervalls antwortet (Zustand ABORTING). Nach Eingang aller vom Abbruch informierten Agenten wird auch im Fehlerfall ein Ende-Satz auf den Log geschrieben. Wenn für die ACK-Nachrichten eine Timeout-Bedingung eintritt, dann protokolliert der Koordinator anstelle des Ende-Satzes in der Log-Datei, welche Agenten noch nicht geantwortet haben (in Abb. 7-4a nicht gezeigt).

Abb. 7-4: Zustandsübergänge beim 2PC-Protokoll

Nach Ausführung einer Sub-Transaktion befindet sich der zugehörige Agent zunächst in einem Wartezustand WAIT, um auf die PREPARE-Nachricht zu warten (Abb. 7-4b). Wenn diese eintrifft, wird das lokale Commit-Ergebnis protokolliert und eine READY-Antwort an den Koordinator geschickt. Der Agent befindet sich danach im Zustand PREPARED, wo er auf das globale Commit-Ergebnis wartet. Trifft dieses ein, dann wird es auf die lokale Log-Datei protokolliert, eine Quittung an den Koordinator gesendet und der Endzustand COMMITTED bzw. ABORTED eingenommen. Der Agent entscheidet auf ein lokales Abort, wenn die PREPARE-Aufforderung nicht innerhalb eines spezifizierten Timeout-Intervalls eintrifft oder ein sonstiger Fehler vorkommt (Empfang einer ABORT-Nachricht). In diesen Fällen wird direkt in den Zustand ABORTED gewechselt. Trifft in diesem Zustand die PREPARE-Nachricht des Koordinators noch ein, so wird mit FAILED geantwortet.
Beim Agenten droht eine Blockierung, wenn im PREPARED-Zustand eine Timeout-Bedingung einsetzt (in Abb. 7-4b nicht gezeigt). In diesem Fall kann versucht werden, beim Koordinator das globale Commit-Ergebnis nachzufragen, da das Ergebnis möglicherweise aufgrund eines Kommunikationsfehlers nicht empfangen werden konnte. Ist dies erfolglos (z.B. wegen Ausfall des Koordinators), kann erfragt werden, ob einer der anderen Agenten[27] möglicherweise das globale Commit-Ergebnis noch erhalten hat oder mit FAILED gestimmt hat (in letzterem Fall steht das Scheitern der gesamten Transaktion fest)[28]. Ist auch das nicht der Fall, muß gewartet werden, bis der Koordinator wieder funktionsfähig wird und das Ergebnis mitteilt ("Blockierung").

Wir diskutieren jetzt, wie die Recovery für globale Transaktionen nach einem Rechnerausfall aussieht. Wesentlich hierzu ist, daß mit dem Log-Inhalt festgestellt werden kann, welcher Commit-Zustand vor dem Rechnerausfall erreicht wurde. Bei der Crash-Recovery für einen Agenten-Knoten sind folgende Fälle möglich:

Wird ein Commit-Satz auf dem Log gefunden (Zustand: COMMITTED), so handelt es sich um eine erfolgreich beendete Transaktion. Es wird eine Redo-Recovery vorgenommen, um Änderungen der Transaktion zu wiederholen, die aufgrund des Rechnerausfalls noch nicht in die physische Datenbank gelangten.
Falls ein Abort-Satz vorliegt (Zustand: ABORTED), ist die Transaktion zurückzusetzen. Mit einer Undo-Recovery können Änderungen der Transaktion, die bereits in die physische Datenbank gelangten, zurückgenommen werden.
Liegt ein Prepared-Satz vor (PREPARED-Zustand), dann wird das globale Commit-Ergebnis beim Koordinator nachgefragt. Dieser hält die Information noch, da er von dem ausgefallenen Agenten noch keine ACK-Nachricht erhalten hatte. Sollte der Koordinator zu diesem Zeitpunkt nicht verfügbar sein, so sind wieder die oben erwähnten Aktionen vorzusehen (Nachfragen bei anderen Agenten bzw. Blockierung).
Liegt keiner der drei Log-Sätze vor, dann wird die Transaktion abgebrochen, da das Commit-Protokoll noch nicht begonnen wurde.

Bei der Crash-Recovery für den Koordinator-Knoten bestehen folgende Möglichkeiten:

Wird ein Ende-Satz auf dem Log gefunden (Zustand: TERMINATED), dann sind keine offenen Sub-Transaktionen mehr möglich. Je nach Commit-Ergebnis wird eine Redo- bzw. Undo-Recovery veranlaßt.
Im Zustand ABORTING (Abort-Satz, jedoch kein Ende-Satz auf dem Log) wird eine Undo-Recovery vorgenommen. Agenten, die das (negative) Commit-Ergebnis noch nicht quittiert haben, werden davon jetzt in Kenntnis gesetzt (falls auf dem Log nicht vermerkt wurde, von welchen Agenten die ACK-Nachricht noch aussteht, werden alle informiert).
Im Zustand COMMITTING (Commit-Satz, jedoch kein Ende-Satz auf dem Log) wird eine Redo-Recovery veranlaßt. Agenten, die das (positive) Commit-Ergebnis noch nicht quittiert haben, werden davon jetzt in Kenntnis gesetzt.
Liegt keiner der vorhergehenden Fälle vor, dann befand sich die Transaktion zum Zeitpunkt des Koordinatorausfalls in einem Zustand (INITIAL oder WAIT), in dem noch nicht alle lokalen Commit-Ergebnisse empfangen wurden. Es wird daher wie im ABORTING-Fall verfahren.

In den Zwischenzuständen wird das Commit-Protokoll jeweils wieder an dem Punkt fortgeführt, an dem die Unterbrechung stattfand. Insbesondere werden die noch ausstehenden Log-Sätze (z.B. das Commit-Ergebnis beim Agenten bzw. der Ende-Satz beim Koordinator) geschrieben, da sie bei einem erneuten Rechnerausfall benötigt werden.

Der Ausfall einer Kommunikationsverbindung wird wie beschrieben über Timeout-Bedingungen behandelt. Für nicht mehr erreichbare Knoten, auch im Rahmen von Netzwerk-Partitionierungen, ergibt sich somit die gleiche Behandlung wie für ausgefallene Rechner. Netzwerk-Partitionierungen bleiben nur dann ohne Auswirkungen, wenn Koordinator und alle Agenten in einer Partition verbleiben.

[26] Wir gehen in diesem Kapitel davon aus, daß Sperrverfahren zur Synchronisation verwendet werden.

[27] Falls nicht alle Knoten befragt werden sollen, setzt dies voraus, daß der Koordinator z.B. mit der PREPARE-Nachricht mitteilt, welche Agenten noch an der Transaktion beteiligt sind.

[28] Diese Vorgehensweise wird z.B. in Cincom's Verteiltem DBS Supra-Server unterstützt und dort als "Transaction Partnering" bezeichnet (Kap. 19.11).