8.3 Optimistische Synchronisation

8.3.3 Verteilte Validierung

Beim verteilten Validierungsschema wird jede (Sub-) Transaktion an ihrem ausführenden Rechner validiert. Damit wird für rein lokale Transaktionen, die idealerweise den größten Transaktionsanteil ausmachen, keine Interprozessor-Kommunikation erforderlich. Auch für globale Transaktionen verursacht (wie schon bei verteilten Sperrverfahren) die Synchronisation keine zusätzlichen Nachrichten, da sich Validierungen und Schreibphasen im Rahmen eines Zwei-Phasen-Commit-Protokolls durchführen lassen:

Diese Vorgehensweise reicht jedoch allein nicht aus, um eine korrekte Synchronisation zu gewährleisten. Denn durch die lokalen Validierungen wird zwar die lokale Serialisierbarkeit in jedem Knoten sichergestellt, nicht aber notwendigerweise die globale Serialisierbarkeit, da die lokale Serialisierungsreihenfolge von Sub-Transaktionen zweier globaler Transaktionen auf verschiedenen Rechnern entgegengesetzt sein kann. Zur Behandlung dieses Problems wurden mehrere Alternativen vorgeschlagen [Ra88a], wobei die wohl einfachste Lösung möglich wird, wenn die Validierungen globaler Transaktionen auf allen Knoten in der gleichen Reihenfolge ausgeführt werden. In diesem Fall entspricht die auf allen Rechnern gleiche Validierungsreihenfolge nicht nur der lokalen, sondern zugleich der globalen Serialisierungsreihenfolge.

Um die gleiche Validierungsreihenfolge auf allen Knoten zu erzwingen, können global eindeutige Transaktions-Zeitstempel verwendet werden. Diese Zeitstempel werden (im Gegensatz zu Zeitmarkenverfahren) beim EOT am Heimatknoten zugewiesen und bestimmen die Position der Transaktion in der globalen Serialisierungsreihenfolge. Der Transaktions-Zeitstempel wird bei den Validierungsaufforderungen mitgeschickt, so daß in jedem Knoten die gleiche Validierungsreihenfolge eingehalten werden kann. "Zu spät" eintreffende Transaktionen, deren Zeitstempel kleiner ist als die von zuletzt lokal validierten Transaktionen, werden zurückgesetzt. Das Ausmaß solcher Rücksetzungen ist umso geringer, je schneller und gleichmäßiger die Übertragungszeiten zwischen den Rechnern sind und je enger die lokalen Uhren der Rechner synchronisiert sind.

Ein weiteres Problem bei verteilter Validierung entsteht durch die zeitliche Trennung zwischen lokaler Validierung und Schreibphase. Denn im Gegensatz zu zentralisierten DBS ist nun auf einem Knoten nach erfolgreicher lokaler Validierung das Schicksal der globalen Transaktion ungewiß. Die von lokal erfolgreich validierten Sub-Transaktionen beabsichtigten Änderungen sind demnach "unsicher", da sie je nach Validierungsausgang der globalen Transaktion weggeworfen oder in die Datenbank eingebracht werden.

Beispiel 8-6

Im Schedule von Abb. 8-5 will Transaktion T2 auf Objekt x zugreifen, das von der lokal bereits erfolgreich validierten, globalen Änderungstransaktion T1 geändert wurde. Deren Änderung ist jedoch unsicher, da zu diesem Zeitpunkt ihr globales Commit-Ergebnis noch nicht bekannt ist.

Abb. 8-5: Probleme mit "unsicheren" Änderungen

Für die Behandlung dieser unsicheren Änderungen in der Lesephase und bei der Validierung lokaler Transaktionen kommen im wesentlichen folgende Alternativen in Betracht [Ra88a]:

1. Bei der ersten Möglichkeit werden unsichere Änderungen nicht beachtet, sondern auf die aktuell gültige, ungeänderte Version zugegriffen. Dies ist allerdings wenig sinnvoll, wenn - wie bisher vorausgesetzt - sich die laufenden Transaktionen in der Serialisierungsreihenfolge nach allen bereits (lokal) validierten Transaktionen einreihen müssen. Denn in diesem Fall wird die auf eine alte Objektversion zugreifende Transaktion zurückgesetzt, wenn die globale Transaktion erfolgreich abschließt, wovon optimistischerweise auszugehen ist. Der Zugriff auf die ungeänderte Objektversion kommt daher allenfalls in Frage, wenn sich die betreffende Transaktion in der Serialisierungsreihenfolge vor der die Änderung beabsichtigende globalen Transaktion einreihen läßt. Die Entscheidung darüber ist im verteilten Fall relativ komplex und soll hier nicht weiter untersucht werden.

2. In einer optimistischeren Alternative wird sofort auf unsichere Änderungen zugegriffen, weil davon ausgegangen wird, daß die globale Transaktion erfolgreich zu Ende kommt. Damit machen die auf unsichere Änderungen zugreifenden Transaktionen ihr Schicksal von dem der globalen Transaktion abhängig. Sinnvollerweise warten dann diese abhängigen Transaktionen vor ihrer lokalen Validierung ab, ob ihr Optimismus berechtigt war, d.h., ob die globalen Transaktionen, deren Änderungen gesehen wurden, erfolgreich waren oder nicht. Würden nämlich diese abhängigen Transaktionen ebenfalls wieder unsichere Änderungen zugänglich machen, könnte eine Rücksetzung einen Domino-Effekt nach sich ziehen.

3. Die dritte Alternative schließlich blockiert den Zugriff auf unsichere Änderungen bis der Ausgang der globalen Transaktion feststeht. Damit werden unnötige Rücksetzungen - wie bei Alternative a) möglich - umgangen, allerdings wird durch das "Sperren" der Objekte auch die Parallelität reduziert. Da die Sperren jedoch nur während der Commit-Behandlung gehalten werden, ist die Wahrscheinlichkeit von Sperrkonflikten entsprechend geringer als bei reinen Sperrverfahren. Deadlocks können dabei nicht entstehen, da die Transaktion, auf die gewartet wird, ihre Lesephase bereits beendet hat und somit selbst nicht mehr auf solche Sperren laufen kann.

Von den genannten Alternativen erscheint der letzte Ansatz am vielversprechendsten. Insbesondere können damit im Falle BOCC-artiger Synchronisation Validierungen und Schreibphasen quasi wie im zentralen Fall erfolgen. Wie in [TR90] beschrieben, können die Sperren weitergehend genutzt werden, um ein mehrfaches Zurücksetzen derselben Transaktion zu verhindern. Dabei werden die von einer Transaktion erworbenen Sperren im Falle einer gescheiterten Validierung beibehalten. Die Sperren sichern zu, daß die erneute Transaktionsausführung erfolgreich ist, sofern keine zusätzlichen Objekte referenziert werden[32]. Es handelt sich dabei um eine spezielle Kombination von optimistischem Ansatz und Sperrverfahren. Deadlocks können verhindert werden, da die Sperranforderungen in allen Knoten in der Reihenfolge der Transaktions-Zeitstempel bearbeitet werden.

Bei FOCC war im zentralen Fall für Lesetransaktionen keine Validierung erforderlich; mit Erreichen ihres EOT war ihr erfolgreiches Abschneiden gewährleistet. Dies gilt aufgrund der unsicheren Änderungen im verteilten Fall jedoch nicht mehr. Zum einen müssen - wie auch für BOCC - lokale Lesetransaktionen beim Objektzugriff die Sperren globaler Transaktionen beachten. Weiterhin kann es sein, daß eine lesende Sub-Transaktion noch nach ihrer lokalen Beendigung, jedoch vor Abschluß der Gesamttransaktion, zurückgesetzt wird, wenn man im Konfliktfall nicht stets die validierende Transaktion zurücksetzen will. Daher ist auch für eine globale Lesetransaktion eine Validierung notwendig, um sicherzustellen, daß sämtliche Änderungen von zuvor beendeten Transaktionen gesehen wurden.

Beispiel 8-7

Im Schedule von Abb. 8-6 führt die globale Lesetransaktion T1 Sub-Transaktionen in Rechner 1 und 2 aus. Die Sub-Transaktion in Rechner 2 ist bei FOCC-Validierung bis zu ihrem Ende in keinen Konflikt verwickelt. Bei der danach stattfindenden Validierung der lokalen Update-Transaktion T2 wird jedoch ein Konflikt für Objekt z entdeckt, da T1 zu diesem Zeitpunkt noch nicht beendet ist. Zur Konfliktbehebung ist entweder T2 oder T1 abzubrechen. Beim EOT der globalen Lesetransaktion T1 ist eine Validierung erforderlich, um festzustellen, ob alle Sub-Transaktionen unbeschadet blieben.

Abb. 8-6: Probleme mit Lesetransaktionen bei verteilter FOCC-Validierung


[32] Um dies zu gewährleisten, sind bei der Validierung zusätzlich gesetzte Sperren zu berücksichtigen [TR90].