8.3 Optimistische Synchronisation

8.3.1 Validierungsansätze

Um die Validierungen durchführen zu können, werden für jede Transaktion Ti während ihrer Lesephase die Namen von ihr gelesener bzw. geänderter Objekte in einem Read-Set RS (Ti) bzw. Write-Set WS (Ti) geführt. Wir nehmen an, daß vor jeder Änderung das entsprechende Objekt gelesen wird, so daß der Write-Set einer Transaktion stets eine Teilmenge des Read-Sets bildet. Nach [Hä84] lassen sich optimistische Synchronisationsverfahren gemäß ihrer Validierungsstrategie grob in zwei Klassen unterteilen. Bei den rückwärtsorientierten Verfahren (Backward Oriented Optimistic Concurrency Control, BOCC) erfolgt die Validierung ausschließlich gegenüber bereits beendeten Transaktionen. Bei den vorwärtsorientierten Verfahren (Forward Oriented Optimistic Concurrency Control, FOCC) dagegen wird gegen noch laufende Transaktionen validiert. In beiden Fällen wird durch die Validierung sichergestellt, daß die validierende Transaktion alle Änderungen von zuvor erfolgreich validierten Transaktionen gesehen hat. Damit ist die Serialisierungsreihenfolge durch die Validierungsreihenfolge gegeben.

Im ursprünglichen BOCC-Verfahren nach [KR81] wird bei der Validierung überprüft, ob die validierende Transaktion ein Objekt gelesen hat, das während ihrer Lesephase geändert wurde. Dazu wird in der Validierungsphase der Read-Set der validierenden Transaktion Tj mit den Write-Sets aller Transaktionen Ti verglichen, die während der Lesephase von Tj validiert haben (Abb. 8-4a). Ergibt sich eine Überschneidung mit einem dieser Write-Sets, wird die validierende Transaktion zurückgesetzt, da sie möglicherweise auf veraltete Daten zugegriffen hat (die am Konflikt beteiligten Transaktionen können nicht mehr zurückgesetzt werden, da sie bereits beendet sind). Die Validierungen werden dabei in einem kritischen Abschnitt durchgeführt, der sicherstellt, daß zu einem Zeitpunkt höchstens eine Validierung vorgenommen wird.

Abb. 8-4: Validierung einer Transaktion Tj bei BOCC und FOCC

Beispiel 8-4

Für den Schedule in Abb. 8-1a wird mit diesem BOCC-Protokoll zunächst T3 erfolgreich validiert. Bei der nachfolgenden Validierung von T1 wird festgestellt, daß das gelesene Objekt x sich im Write-Set der parallel ausgeführten und bereits validierten Transaktion T3 befindet. Folglich wird T1 zurückgesetzt. Die Validierung von T2 schließlich ist erfolgreich. Es ergibt sich damit folgende Serialisierungsreihenfolge: T3 < T2.

Die skizzierte BOCC-Validierung hat den Nachteil, daß Transaktionen oft unnötigerweise (wegen eines "unechten" Konfliktes) zurückgesetzt werden, obwohl die aktuellen Objektversionen gesehen wurden. Dies ist dann der Fall, wenn auf das von einer parallelen Transaktion geänderte Objekt erst nach dem Einbringen in die Datenbank zugegriffen wurde. So wird in obigem Beispiel (Abb. 8-1a) T1 unnötigerweise zurückgesetzt, weil die Änderung von T3 gesehen wurde. Diese unnötigen Rücksetzungen betreffen v.a. lange Transaktionen, die bereits durch kurze Änderer zum Scheitern gezwungen werden können. Eine Abhilfe des Problems wird jedoch möglich, indem man Änderungszähler oder Versionsnummern an den Objekten führt und eine Rücksetzung nur vornimmt, wenn tatsächlich veraltete Daten gelesen wurden (s. Übungsaufgaben).
Ein weiteres Problem ist auch hier die Gefahr des "Verhungerns", daß also Transaktionen bei der Validierung ständig scheitern. Dies ist v.a. für lange Transaktionen zu befürchten, da sie einen großen Read-Set aufweisen und sich gegenüber vielen Transaktionen validieren müssen. Weiterhin verursacht das späte Zurücksetzen am Transaktionsende ein hohes Maß unnötig verrichteter Arbeit.

Diese Probleme werden von FOCC-Verfahren zumindest teilweise umgangen. Bei ihnen wird nicht gegen bereits beendete Transaktionen validiert, sondern gegenüber aktiven Transaktionen. In der Validierungsphase, die nur von Änderungstransaktionen durchzuführen ist, wird untersucht, ob eine der in der Lesephase befindlichen Transaktionen ein Objekt gelesen hat, das die validierende Transaktion zu ändern im Begriff ist (Abb. 8-4b). In diesem Fall muß der Konflikt durch Zurücksetzen einer (oder mehrerer) der beteiligten Transaktionen aufgelöst werden. Anstatt der validierenden Transaktion können also auch die betroffenen laufenden Transaktionen zurückgesetzt werden, um z.B. den Arbeitsverlust zu verringern. Auch das Verhungern von Transaktionen kann durch eine geeignete Bestimmung der "Opfer" verhindert werden (s. Übungsaufgaben). Im Gegensatz zum (ursprünglichen) BOCC-Ansatz führen bei FOCC daneben nur echte Konflikte zu Rücksetzungen.

Beispiel 8-5

Für den Schedule in Abb. 8-1a wird mit dem FOCC-Protokoll zunächst die Änderungstransaktion T3 erfolgreich validiert, da kein Konflikt mit laufenden Transaktionen vorliegt. Somit wird im Gegensatz zu BOCC richtigerweise kein Konflikt mit T1 festgestellt, da T1 erst nach Abschluß von T3 auf (die aktuelle Version von) x zugreift. Bei der Validierung von T1 wird dann jedoch ein Konflikt mit T2 erkannt (Objekt y), der durch Rücksetzen von T1 oder T2 aufgelöst werden kann. Da T1 bereits beendet ist, empfiehlt sich die Rücksetzung von T2. Als Serialisierungreihenfolge ergibt sich T3 < T1.

In Verteilten DBS kommen auch für die optimistischen Synchronisationsverfahren eine zentrale oder eine verteilte Realisierung in Betracht, die im folgenden diskutiert werden.