8 Synchronisation in Verteilten Datenbanksystemen

8.4 Mehrversionen-Konzept

Mehrversionen-Synchronisationsverfahren (multiversion concurrency control) streben eine Reduzierung an Synchronisationskonflikten an, indem für geänderte Objekte zeitweilig mehrere Versionen geführt werden und Leser ggf. auf ältere Versionen zugreifen. Voraussetzung dabei ist, daß für jede Transaktion vorab Wissen darüber vorliegt, ob sie möglicherweise Änderungen vornimmt. Einer reinen Lesetransaktion T wird dabei während ihrer gesamten Laufzeit eine Sicht auf die Datenbank gewährt, wie sie bei ihrem BOT gültig war; Änderungen, die während ihrer Bearbeitung vorgenommen werden, bleiben für T unsichtbar. Um dies zu realisieren, erzeugt jede erfolgreiche Änderung eine neue Version des modifizierten Objekts; die Versionen werden in einem sogenannten Versionen-Pool verwaltet. Im Gegensatz zu Lesetransaktionen greifen Änderungstransaktionen stets auf die aktuelle Version eines Objektes zu. Für ihre Synchronisation kann praktisch jedes der allgemeinen Synchronisationsverfahren verwendet werden [CM86, AS89].

Da mit den Versionen jeder Lesetransaktion der bei BOT gültige (und konsistente) DB-Zustand zur Verfügung gestellt wird, ist für Lesetransaktionen keinerlei Synchronisation mehr erforderlich. Weiterhin brauchen sich andere Transaktionen nicht mehr gegen Lesetransaktionen zu synchronisieren. Damit reduziert sich sowohl die Konfliktwahrscheinlichkeit (und damit die Anzahl von Blockierungen und Rücksetzungen) sowie der Synchronisierungsaufwand (Anzahl von Sperranforderungen, Validierungen etc.). Die Serialisierbarkeit bleibt generell gewahrt.

Beispiel 8-8

Für den Schedule in Abb. 8-1a trat mit einem RX-Protokoll ein Sperrkonflikt auf (Beispiel 8-2). In Kombination mit einem Mehrversionen-Konzept wird der Lesezugriff von T2 auf Objekt y nun ohne Konflikt abgewickelt, da der Zugriff auf die ungeänderte Version erfolgt. Die Serialsierungsreihenfolge lautet jetzt T2 < T3 < T1.

Für die Vorteile, die ein Mehrversionen-Konzept bietet, muß zum einen in Kauf genommen werden, daß Lesetransaktionen (vor allem lange Leser) nicht immer die aktuellen Daten sehen. Zum anderen ist ein erhöhter Speicherplatzbedarf zur Haltung der Versionen sowie ein zusätzlicher Verwaltungsaufwand für den Versionen-Pool erforderlich. Bezüglich der Versionen-Pool-Verwaltung sind vor allem zwei Aufgaben zu behandeln, nämlich Bestimmung der zu lesenden Versionen sowie die Freigabe nicht mehr benötigter Versionen (garbage collection).

Diese Aufgaben lassen sich relativ einfach durch Verwendung von Zeitstempeln lösen. Im zentralen Fall genügt dazu das Führen eines Transaktionszählers TNC. Änderungstransaktionen bekommen am Transaktionsende den aktuellen TNC-Wert als Commit-Zeitstempel cts zugewiesen, anschließend wird TNC inkrementiert. Für jede Version eines geänderten Objektes wird ein Schreibzeitstempel WTS geführt, der dem Commit-Zeitstempel der ändernden Transaktion entspricht. Für Lesetransaktionen wird dagegen beim Transaktionsbeginn der aktuelle TNC-Wert als BOT-Zeitstempel bts übernommen. Damit muß einer Lesetransaktion T für den Zugriff auf Objekt x die jüngste Version von x bereitgestellt werden, für die

WTS (x) < bts (T)
gilt.
Änderungstransaktionen greifen stets auf die aktuellsten Objektversionen zu.

Um feststellen zu können, welche Versionen nicht mehr benötigt werden, wird der BOT-Zeitstempel der ältesten Lesetransaktion Min-bts geführt. Eine Version xi von Objekt x kann gelöscht werden, falls es eine neuere Version xj gibt, so daß gilt:

WTS (xi) < WTS (xj) < Min-bts.

Beispiel 8-9

In obigem Beispiel (Schedule von Abb. 8-1a) seien folgende Initialwerte gegeben:
WTS (x0) = 0, WTS (y0) = 0, TNC = 1.
Die Lesetransaktion T2 erhält den BOT-Zeitstempel bts (T2) = 1; zugleich wird Min-bts auf diesen Wert gesetzt. Für den Zugriff auf y wird daher die ungeänderte Version y0 mit WTS (y0) = 0 ausgewählt. Beim Commit von T3 werden der Commit-Zeitstempel cts (T3) = 1 zugewiesen und TNC auf 2 inkrementiert. Für die neue Version von Objekt x (x1) gilt WTS (x1) = 1. Beim Commit von T1 werden analog TNC auf 3 erhöht und eine neue Version y1 mit WTS (y1) = 2 erzeugt.
Am Ende von T2 wird Min-bts angepaßt und überprüft, welche Versionen freigegeben werden können. Da zu diesem Zeitpunkt keine Lesetransaktion mehr läuft, wird Min-bts auf den Wert gesetzt. Die alten Versionen x0 und y0 werden freigegeben, da in beiden Fällen neuere Versionen existieren, deren Schreibzeitstempel kleiner als Min-bts sind.

Zur effizienten Lokalisierung und Freigabe von Versionen empfiehlt sich die Implementierung des Versionen-Pools in Form eines Ringpuffers, wie in [Ch82, HP87, CM86] näher beschrieben. Leistungsuntersuchungen zeigten, daß mit Mehrversionen-Verfahren die Leistungsfähigkeit in konfliktträchtigen Anwendungen signifikant verbessert werden kann [CM86, HP87]. In mit realen DB-Lasten vorgenommenen Untersuchungen zeigte sich, daß die überwiegende Mehrzahl der Objektzugriffe (> 90%) auf die aktuelle Version und die Mehrzahl der restlichen Zugriffe auf die nächstältere Version entfallen [HP87]. Der Umfang des Versionen-Pools kann daher meist klein gehalten werden[33]. Einige kommerzielle DBS verwenden bereits einen Mehrversionen-Ansatz (Oracle, Rdb, Prime, InterBase); Einzelheiten der Implementierung wurden jedoch nicht veröffentlicht.

Bei der Übertragung der skizzierten Mehrversionen-Synchronisation auf Verteilte DBS ist vor allem zu klären, wie eine korrekte Vergabe von BOT- und Commit-Zeitstempeln gewährleistet werden kann. Eine einfache Lösung dieses Problems besteht darin, den Zähler TNC auf einem dedizierten Knoten zu führen und die BOT- und Commit-Zeitstempel dort anzufordern. Der Commit-Zeitstempel wird dabei erst zugewiesen, nachdem das Durchkommen der Änderungstransaktion sichergestellt ist (nach Phase 1 des Commit-Protokolls). Er wird in der zweiten Commit-Phase allen Sub-Transaktionen zur Vergabe der Versionsnummern für geänderte Objekte mitgeteilt. Am zentralen Knoten können auch für jeden Rechner die BOT-Zeitstempel der ältesten Lesetransaktionen (Min-bts) vermerkt werden. Diese Angaben müssen nicht immer aktuell sein, sondern die Rechner können die betreffenden Änderungen asynchron (z.B. gebündelt mit Zeitmarkenanforderungen) mitteilen. Ebenso kann der zentrale Knoten das globale Minimum asynchron an die einzelnen Rechner weiterleiten, damit dort die nicht mehr benötigten Versionen ermittelt werden können.

Eine solche zentralisierte Zeitstempelverwaltung weist jedoch wieder die bekannten Nachteile hinsichtlich Verfügbarkeit und Knotenautonomie auf, zudem entstehen zusätzliche Kommunikationsverzögerungen zur Zeitstempelvergabe. Die lokale Vergabe global eindeutiger Zeitstempel (z.B. bestehend aus lokaler Uhrzeit und Knoten-ID) ist jetzt jedoch problematisch, wenn nur innerhalb eines Rechners - nicht jedoch rechnerübergreifend - monoton wachsende Zeitstempel gewährleistet sind (z.B. aufgrund unsynchronisierter Uhren). Eine Folge davon ist, daß eine Lesetransaktion nicht notwendigerweise alle bei ihrem Start gültigen Änderungen zu sehen bekommt. Dies ist dann möglich, wenn sie einen BOT-Zeitstempel erhält, der kleiner ist als der Commit-Zeitstempel von an anderen Rechnern bereits beendeten Änderern. Noch gravierender ist jedoch, daß eine Änderungstransaktion T1 möglicherweise einen Commit-Zeitstempel erhält, der kleiner ist als der BOT-Zeitstempel einer an einem anderen Knoten zuvor gestarteten Lesetransaktion T2. Wenn T1 ein Objekt ändert, auf das T2 vorher bereits zugegriffen hat, dann ist die Serialisierbarkeit der Transaktionen in der Reihenfolge ihrer Zeitstempel nicht mehr möglich.

Beispiel 8-10

Im Schedule von Abb. 8-7 werden die globale Lesetransaktion T2 in Rechner 2, die Änderungstransaktionen T1 und T3 in Rechner 1 bzw. Rechner 3 gestartet. Aufgrund unsynchronisierter Zeitstempelvergabe sei cts (T1) < bts (T2) < cts (T3). Wegen dieser Zeitstempelreihenfolge greift die Sub-Transaktion von T2 in Rechner 3 auf die alte Version x0 zu, obwohl T3 bereits vor dem Start von T2 die Version x1 erzeugt hatte. Dies ist zwar unerwünscht, hat jedoch keine Auswirkungen auf die Serialisierbarkeit. Problematisch ist, daß die Sub-Transaktion von T2 in Rechner 1 auf die Objektversion z0 zugegriffen hat und danach von T1 eine neuere Version z1 erzeugt wurde, mit WTS (z1) = cts (T1) < bts (T2). Dies ist nicht zulässig, da die Serialisierungsreihenfolge T1 < T2 aufgrund des vorherigen Zugriffs von T2 auf z0 nicht mehr eingehalten werden kann.

Abb. 8-7: Probleme mit unsynchronisierter Zeitstempelvergabe

Eine Lösungsmöglichkeit zur Wahrung der Serialisierbarkeit besteht darin, Änderungstransaktionen abzubrechen, falls sie Objektversionen erzeugen, die von bereits ausgeführten Lesetransaktionen hätten gesehen werden müssen. Diese Rücksetzungen können jedoch vermieden werden, wenn bei der Vergabe der Commit-Zeitstempel darauf geachtet wird, daß diese größer sind als die BOT-Zeitstempel aller zuvor an dem Rechner ausgeführten (externen) Lesetransaktionen. Weiterhin muß ein lokal vergebener Commit-Zeitstempel größer sein als der Commit-Zeitstempel von externen Änderungstransaktionen, die an dem Knoten eine Sub-Transaktion ausgeführt haben. Dies ist möglich, da deren Commit-Zeitstempel im Rahmen des Commit-Protokolls propagiert wird. Für globale Änderungstransaktionen müssen diese Bedingungen jedoch an allen Knoten, an denen Sub-Transaktionen ausgeführt wurden, gelten. Daher kann beim EOT zunächst lokal nur ein vorläufiger Commit-Zeitstempel festgelegt werden, der in Phase 1 des Commit-Protokolls an die beteiligten Rechner propagiert wird. Der endgültige Commit-Zeitstempel wird nach Rückmeldung der beteiligten Knoten festgelegt, so daß er größer ist als alle an den involvierten Rechnern bekannten BOT- und Commit-Zeitstempel. Der endgültige Commit-Zeitstempel wird in der zweiten Commit-Phase an die beteiligten Rechner mitgeteilt. Diese Vorgehensweise erreicht eine Synchronisierung der Zeitstempelvergabe ohne zusätzlichen Kommunikationsaufwand. Eine ähnliche Vorgehensweise wird in [BG83, We87] empfohlen; sie kann als Spezialfall der Generierung konsistenter Zeitstempel nach Lamport [La78] aufgefaßt werden.

Eine solche Vergabe von Commit-Zeitstempel hat Auswirkungen auf Lesetransaktionen, da die Auswahl einer Objektversion vom endgültigen Commit-Zeitstempel abhängt. Weiterhin sind die Änderungen einer Transaktion, die noch keinen endgültigen Commit-Zeitstempel besitzt, unsicher, da die Transaktion möglicherweise noch abgebrochen wird. Die unsicheren Änderungen einer globalen Änderungstransaktion T mit vorläufigem Commit-Zeitstempel pcts sind relevant für Lesetransaktionen Tj, für die gilt:

bts (Tj) > pcts (T).

Hier empfiehlt es sich wiederum, die Lesezugriffe solange zu blockieren, bis der Transaktionsausgang sowie der endgültige Commit-Zeitstempel für T feststeht.

Zur Freigabe von alten Objektversionen muß der BOT-Zeitstempel der ältesten Lesetransaktion im System bekannt sein. Hierzu ist es bei verteilter Realisierung des Mehrversionen-Ansatzes erforderlich, daß jeder Knoten seinen lokalen Min-bts-Wert systemweit propagiert (z.B. gebündelt mit Nachrichten für das Commit-Protokoll). Damit kann in jedem Rechner eine Approximation des globalen Minimums geführt werden.

[33] Probleme können durch lange Lesetransaktionen verursacht werden. Kommt es zu einem "Überlauf" des Versionen-Pools sind daher ggf. Rücksetzungen von Lesetransaktionen erforderlich, für die benötigte Versionen nicht mehr weitergeführt werden konnten.