12 Föderative Datenbanksysteme

12.5 Transaktionsverwaltung

Die Unterstützung von globalen Änderungstransaktionen in FDBS wirft große Probleme hinsichtlich der Transaktionsverwaltung auf, wenn keine Erweiterung der LDBS in Kauf genommen wird. Gemäß der zweigeteilten Architektur von FDBS (Abb. 12-1) erfolgt auch die Transaktionsverwaltung zweistufig: neben einer lokalen Transaktionsverwaltung in jedem LDBS liegt eine globale Transaktionsverwaltung in der FDBS-Zusatzschicht vor (Abb. 12-4). Globale Transaktionen (GT) werden von der globalen Transaktionsverwaltung in eine Folge von lokal ausführbaren Sub-Transaktionen (GST) zerlegt. Die LDBS kennen bei vollständiger Autonomie keinen Unterschied zwischen lokalen Transaktionen (LT) und GST. Ferner soll keine Kooperation zwischen den LDBS und der globalen Transaktionsverwaltung sowie unter den LDBS erfolgen. Schließlich kann bei den lokalen Transaktionsverwaltungen Heterogenität vorliegen, insbesondere bei der Synchronisation (z.B. können unterschiedliche Sperrverfahren oder eine optimistische Synchronisation im Einsatz sein).

Abb. 12-4: Transaktionsverwaltung in FDBS

Unter diesen Voraussetzungen ist es äußerst schwer, die ACID-Eigenschaften für globale Transaktionen zu wahren. Die automatische Unterstützung globaler Integritätsbedingungen (Eigenschaft C) setzt deren Spezifikation durch den GDBA voraus, so daß sie prinzipiell vom FDBS bei der Abarbeitung globaler Änderungsoperationen überwacht weren können. Die Eigenschaften A, I und D verlangen die Gewährleistung der globalen Serialisierbarkeit sowie die Realisierung eines korrekten Commit-Protokolls zwischen den an der Föderation beteiligten Knoten. Die Realisierung eines globalen Commit-Protokolls wird bereits dadurch nahezu unmöglich, da die LDBS keinen Unterschied zwischen lokalen Transaktionen und globalen Sub-Transaktionen machen. Daher nimmt ein LDBS am Ende einer GST bereits das Commit für diese (Sub-) Transaktion vor, so daß deren Änderungen zu diesem Zeitpunkt dauerhaft und sichtbar werden. Ein Rücksetzen dieser Sub-Transaktion, wie beim Scheitern der globalen Transaktion erforderlich, ist damit prinzipiell nicht mehr möglich. Die globale Transaktionsverwaltung kann höchstens noch versuchen, die Änderungen der Sub-Transaktion durch eine sogenannte Kompensationstransaktion zurückzunehmen [SW91]. Die lokale Sichtbarkeit von aus globaler Sicht ungültigen Änderungen kann damit jedoch nicht verhindert werden.

Abb. 12-5: Synchronisationsproblem in FDBS

Die Entkopplung von globaler und lokaler Transaktionsverwaltung verursacht ähnlich schwerwiegende Probleme für die Synchronisation. Zur Wahrung der globalen Serialisierbarkeit bereiten dabei vor allem Konflikte mit lokalen Transaktionen Schwierigkeiten, da diese der globalen Transaktionsverwaltung unbekannt sind. So ist im Beispiel von Abb. 12-5 aus globaler Sicht keine Verletzung der Serialisierbarkeit erkennbar, da nur das Objekt a von beiden globalen Transaktionen referenziert wird. Da GT1 als erstes auf a zugreift, besteht die Abhängigkeit (der Konflikt)
GT1 < GT2.

Auch liegt in beiden LDBS keine Verletzung der lokalen Serialisierbarkeit vor. Jedoch führen die Zugriffe der lokalen Transaktion LT3 zu der indirekten (transitiven) Abhängigkeit
GT2 < LT3 < GT1

zwischen den beiden globalen Transaktionen. Damit besteht eine zyklische Abhängigkeit zwischen GT1 und GT2, so daß die globale Serialisierbarkeit verletzt wird. Dies wird jedoch nicht erkannt, da die globale Transaktionsverwaltung die transitive Abhängigkeit nicht mitbekommt.

Die Lösung der genannten Probleme erfordert Abstriche in einem oder mehreren der folgenden Bereiche:

Es ist klar, daß diese Punkte auf verschiedenste Weise berücksichtigt werden können. Einfache "Ansätze" bestehen so darin, keine globalen Änderungstransaktionen zuzulassen bzw. auf eine ändernde Sub-Transaktion zu beschränken (Kap. 11.3.1). Für den allgemeinen Fall mit beliebig vielen ändernden Sub-Transaktionen besitzt der ebenfalls in Kap. 11.3.1 diskutierte Ansatz zur Transaktionsverwaltung für die Praxis die größte Bedeutung. Er sieht vor, daß alle LDBS ein striktes Zwei-Phasen-Sperrprotokoll sowie einen Timeout-Ansatz zur Behandlung globaler Deadlocks unterstützen. Ferner müssen die LDBS an einem globalen Commit-Protokoll teilnehmen (über die XA-Schnittstelle). Mit diesen relativ geringen LDBS-Erweiterungen werden die Eigenschaften A, I und D für globale Transaktionen sichergestellt. Ferner ergibt sich auch für die globale Transaktionsverwaltung eine einfache Realisierung, da diese im wesentlichen auf die Durchführung des globalen Commit-Protokolls beschränkt ist. Weitere Vorteile sind, daß außer für das Commit-Protokoll keine zusätzlichen Nachrichten zur globalen Transaktionsverwaltung anfallen und daß jeder Knoten als globaler Commit-Koordinator fungieren kann (verteilte Realisierung der globalen Transaktionsverwaltung). Die in Kauf zu nehmenden Einschränkungen sind eine reduzierte Autonomie (LDBS-Erweiterungen, Abhängigkeit zum globalen Commit-Koordinator) sowie weitgehender Verzicht auf Heterogenität bei der lokalen Transaktionsverwaltung.

In der Forschung wurde in den letzten Jahren eine Vielzahl anderer Ansätze zur Transaktionsverwaltung in FDBS vorgeschlagen, die einen höheren Grad an Autonomie und Heterogenität anstreben. Die praktische Tauglichkeit vieler Vorschläge ist jedoch fraglich, da sie häufig auf zweifelhaften Annahmen basieren; zudem wurde kaum eines der vorgeschlagenen Verfahren tatsächlich implementiert. So wurde vielfach ein zentralisierter globaler Transaktions-Manager unterstellt, über den sämtliche globale Transaktionen ausgeführt werden müssen. Dies ist vor allem für geographisch verteilte Systeme aus Leistungs- und Autonomiegründen eine inakzeptable Lösung. Ferner wurde häufig angenommen, daß der globale Transaktionsverwalter zur Synchronisation die Objektreferenzen (i.a. Sätze oder Seiten) globaler Transaktionen genau kennt. Selbst dies kann jedoch bei entkoppelten LDBS nicht vorausgesetzt werden, da die genauen Objektreferenzen sich i.a. erst bei der Abarbeitung im LDBS ergeben. Andere Ansätze verursachen (aufgrund pessimistischer Konfliktannahmen) große Einschränkungen hinsichtlich der Parallelität zwischen globalen Transaktionen, so daß das Leistungsverhalten stark beeinträchtigt wird. Schließlich betrachten eine Reihe von Arbeiten lediglich die Synchronisationsproblematik, so daß die in engem Zusammenhang stehende Commit-Behandlung ungelöst bleibt. Wir wollen im folgenden stellvertretend zwei Vorschläge näher diskutieren, nämlich Commit-Ordnung und Quasi-Serialisierbarkeit. Eine Übersicht zu weiteren Ansätzen bietet [VG93].

Commit-Ordnung [Raz92, Raz93]

Das Prinzip der Commit-Ordnung (Commitment Ordering, CO) ist ein allgemeiner Ansatz zur Gewährleistung von Serialisierbarkeit, der sich vorteilhaft auf föderative DBS übertragen läßt. Ein Transaktions-Schedule erfüllt die CO-Eigenschaft, wenn die Commit-Operationen von in Konflikt stehenden Transaktionen in der gleichen Reihenfolge ausgeführt werden wie die Konflikt-Operationen selbst. In [Raz92] wurde gezeigt, daß die Erfüllung der CO-Eigenschaft eine hinreichende Bedingung für Serialisierbarkeit ist. Mit einem strikten Zwei-Phasen-Sperrprotokoll wird die CO-Eigenschaft offenbar immer garantiert, jedoch läßt sich dies auch für andere, deadlock-freie (z.B. optimistische) Synchronisationsverfahren erreichen.

Beispiel 12-4

Von den beiden Schedules
. . . w1 (x), r2 (x), c1, c2
und
. . . w1 (x), r2 (x), c2, c1
erfüllt lediglich der erste die CO-Eigenschaft, da die Commit-Operationen (ci) der beiden in Konflikt stehenden Transaktionen T1 und T2 in der gleichen Reihenfolge ausgeführt werden, wie ihre Konflikt-Operationen auf Objekt x. Der zweite Schedule ist serialisierbar (T1 < T2), obwohl die CO-Eigenschaft nicht erfüllt ist. Dies zeigt, daß die CO-Bedingung keine notwendige Voraussetzung für Serialisierbarkeit darstellt.
Bei einem Sperrverfahren ist der zweite Schedule nicht möglich, da beim Lesezugriff von T2 ein Sperrkonflikt mit T1 entsteht, der erst nach dem Commit von T1 (Sperrfreigabe) behoben wird (c2 muß somit nach c1 kommen). Bei einem nicht-blockierenden, CO-konformen Synchronisationsprotokoll wird für den zweiten Schedule bei der Operation c2 erkannt, daß eine Verletzung der CO-Eigenschaft droht. Dies kann z.B. durch Abbruch von T1 verhindert werden.

Für föderative DBS ist es nun einfach, die globale Serialisierbarkeit sicherzustellen, sofern jedes LDBS ein Synchronisationsverfahren verwendet, das die CO-Eigenschaft bezüglich der bei ihm ausgeführten (Sub-) Transaktionen gewährleistet (diese Bedingung allein ist aber offenbar nicht ausreichend, da die lokale Serialisierbarkeit in jedem Knoten keine globale Serialisierbarkeit garantiert). Dazu genügt es, daß jedes LDBS an einem globalen Commit-Protokoll teilnimmt (z.B. einem verteilten Zwei-Phasen-Commit-Protokoll), so daß die LDBS eine externe Commit-Entscheidung akzeptieren. Während der lokalen Commit-Behandlung einer Transaktion T müssen dabei alle Transaktionen abgebrochen werden, die aufgrund lokal erfolgter Konflikte vor T hätten beendet werden müssen. Im Beispiel von Abb. 12-5 würde so beim globalen Commit von GT1 (nach Beendigung von GST12) in LDBS2 erkannt werden, daß GST22 noch nicht beendet ist, obwohl diese Transaktion in der lokalen CO-Reihenfolge vor GST12 steht. Durch Abbruch von GST22 (und damit von GT2) wird das Problem behoben und die globale Serialisierbarkeit gewahrt.

Dieses Protokoll stellt offenbar eine Verallgemeinerung des oben diskutierten Ansatzes dar, bei dem neben der Teilnahme an einem globalen Commit-Protokoll vorausgesetzt wurde, daß jedes LDBS ein striktes Zwei-Phasen-Sperrprotokoll verwendet. Der skizzierte CO-Ansatz erlaubt jedoch Heterogenität bei der lokalen Synchronisationskomponente, solange die CO-Eigenschaft gewahrt bleibt. Insbesondere können deadlock-freie Synchronisationsverfahren unterstützt werden. In Kauf zu nehmen sind wiederum Autonomie-Einschränkungen aufgrund des globalen Commit-Protokolls sowie (möglicherweise) Erweiterungen der LDBS zur Gewährleistung der CO- Eigenschaft.

Bei der Überprüfung der CO-Eigenschaft erfolgt im Basisverfahren keine Unterscheidung zwischen lokalen Transaktionen und globalen Sub-Transaktionen. Wenn in den LDBS jedoch eine Unterscheidung zwischen diesen beiden Transaktionstypen möglich ist, kann dies dazu genutzt werden, die CO-Überprüfung auf globale Transaktionen zu beschränken, sofern das lokale Synchronisationsprotokoll lokale Serialisierbarkeit garantiert [Raz93]. Mit diesem erweiterten Protokoll kann eine verringerte Abbruchhäufigkeit für lokale Transaktionen erwartet werden.

Quasi-Serialisierbarkeit

Eine Reihe von Forschungsarbeiten versuchte, die Transaktionsverwaltung in FDBS durch Unterstützung schwächerer Korrektheitskriterien als der globalen Serialisierbarkeit zu erleichtern. Ein solches Kriterium ist die Quasi-Serialisierbarkeit [DE89, DEK91]. Quasi-Serialisierbarkeit verlangt, daß alle lokalen Schedules serialisierbar sind und die Ausführung globaler Transaktionen äquivalent ist zu einer quasi-seriellen Ausführung dieser Transaktionen, bei der globale Transaktionen sequentiell ausgeführt werden. Die Quasi-Serialisierungsreihenfolge ist durch die äquivalente quasi-serielle Ausführungsfolge gegeben und bezieht sich ausschließlich auf globale Transaktionen.

Beispiel 12-5

Die in Abb. 12-6 gezeigte Ausführung von Transaktionen ist nicht serialisierbar, da in LDBS1 die Abhängigkeit GT1 < GT2 und in LDBS2 die Abhängigkeiten GT2 < LT3 < GT1 existieren. Jedoch liegt Quasi-Serialisierbarkeit vor, da die lokalen Schedules serialisierbar sind und der Schedule in LDBS2 äquivalent ist zu folgender Ausführungsreihenfolge, bei der GST12 vor GST22 ausgeführt wird:

w3 (b), r1 (b), w2 (c), r3 (c).

Dabei bezieht sich der Subskript 3 auf die lokale Transaktion LT3, die Subskripte 1 bzw. 2 auf die globalen Sub-Transaktionen GST12 bzw. GST22.

Abb. 12-6: Quasi-serialisierbare (jedoch nicht serialisierbare) Transaktionsausführung

Somit ist die gezeigte Ausführung der beiden globalen Transaktionen äquivalent zu einer (quasi-)seriellen Ausführung, bei der GT1 vor GT2 ausgeführt wird. Der indirekte Konflikt in LDBS2 mit der lokalen Transaktion LT3 ist also für die Quasi-Serialisierbarkeit irrelevant, da es möglich war, eine äquivalente Ausführungsfolge zu finden, bei der sämtliche Operationen von GT1 vor denen von GT2 ausgeführt wurden.

Dies ist jedoch im Beispiel von Abb. 12-5 nicht der Fall, da dort in LDBS2 relevante Abhängigkeiten mit der lokalen Transaktion auftreten, welche eine echte Wechselwirkung zwischen den globalen Sub-Transaktionen bewirkt. Denn die Änderungen von GST22 werden dort über die lokale Transaktion indirekt für die Sub-Transaktion GST12 sichtbar, so daß keine äquivalente Umkehrung ihrer Ausführungsreihenfolge möglich ist.

Ein einfacher Ansatz zur Gewährleistung von Quasi-Serialisierbarkeit besteht darin, globale Transaktionen stets seriell auszuführen, also jeweils höchstens eine globale Transaktion zuzulassen. Dies ist jedoch aus Leistungsgründen offenbar inakzeptabel, da beim Start globaler Transaktionen mit sehr langen Verzögerungszeiten zu rechnen ist. In [DEK91] wurde ein weniger restriktiver Realisierungsansatz vorgeschlagen, bei dem berücksichtigt wird, auf welche Datenbanken die globalen Transaktionen zugreifen. Insbesondere können ohne Verletzung der Quasi-Serialisierbarkeit solche globalen Transaktionen gleichzeitig zugelassen werden, die auf höchstens einer lokalen Datenbank gemeinsam operieren[56]. Globale Transaktionen, die auf alle lokalen Datenbanken zugreifen wollen, müssen damit jedoch weiterhin seriell ausgeführt werden (der in Abb. 12-6 gezeigte quasi-serialisierbare Ablauf wird somit nicht zugelassen). Der Ansatz erfordert keine LDBS-Erweiterungen und ermöglicht unterschiedliche lokale Synchronisationsverfahren, solange diese die lokale Serialisierbarkeit gewährleisten. Ferner können keine globalen Deadlocks auftreten. Andererseits sind für globale Transaktionen bis zur Zulassung immer noch erhebliche Blockierungszeiten möglich. Außerdem wird eine zentralisierte globale Transaktionsverwaltung vorausgesetzt, über die sämtliche globalen Transaktionen zu starten und zu beenden sind. Schließlich behandelt der Ansatz lediglich den Isolationsaspekt und nicht die Atomarität und Dauerhaftigkeit globaler Transaktionen (Commit-Behandlung).

[56] Eine überlappende Ausführung globaler Transaktionen ist damit auf einen Knoten beschränkt, so daß die lokale Serialisierungsreihenfolge die Quasi-Serialisierungsreihenfolge bestimmt.