8 Synchronisation in Verteilten Datenbanksystemen

8.2 Zeitmarkenverfahren

Bei diesen Verfahren wird die Serialisierbarkeit durch Zeitstempel bzw. -marken an den Datenobjekten überprüft. Die Überprüfungen werden stets an den Speicherungsorten der Daten vorgenommen, so daß sich ein inhärent verteiltes Protokoll ergibt. Weiterhin entfallen eigene Kommunikationsvorgänge zur Synchronisation, ähnlich wie bei verteilten Sperrverfahren. Ein Hauptvorteil gegenüber Sperrverfahren liegt darin, daß keine Deadlocks vorkommen können.

Wir beschränken uns hier auf das einfachste Zeitmarkenverfahren (Basic Timestamp Ordering [BHG87]). Dabei bekommt jede Transaktion T bei ihrem BOT eine global eindeutige Zeitmarke ts (T) fest zugeordnet. Zur Sicherstellung der globalen Eindeutigkeit dieser Zeitmarken kommen mehrere Methoden in Betracht. Zum Beispiel kann ein dedizierter Knoten (timestamp server) vorgesehen werden, an dem die Zeitstempel verwaltet und angefordert werden. Dieser Ansatz verursacht jedoch Kommunikationverzögerungen und beeinträchtigt die Knotenautonomie. Eine bessere Alternative bildet die Verwendung zweiteiliger Zeitstempel bestehend aus lokaler Uhrzeit und Rechner-ID [La78]. Damit wird die globale Ordnung primär über die lokalen Uhrzeiten festgelegt. Die Rechner-ID wird nur für Transaktionen (verschiedener Rechner) mit übereinstimmender lokaler Uhrzeit benötigt, um eine vollständige Ordnung zu erreichen und die globale Eindeutigkeit sicherzustellen. Der Hauptvorteil eines solchen Ansatzes liegt darin, daß die Zeitstempel an jedem Knoten lokal vergeben werden können. Allerdings ist ohne Synchronisierung der lokalen Uhren [Cr89] nicht gewährleistet, daß die Transaktions-Zeitstempel monoton wachsen. Es kann also sein, daß nach Beendigung einer Transaktion T2 an einem anderen Knoten eine Transaktion mit kleinerem Zeitstempel T1 gestartet wird.

Bei Zeitmarkenverfahren ist die Position einer Transaktion in der Serialisierungsreihenfolge bereits a priori durch ihre BOT-Zeitmarke festgelegt. Konfliktoperationen verschiedener Transaktionen müssen daher stets in der Reihenfolge der Transaktions-Zeitmarken erfolgen. Dies erfordert, daß eine Transaktion alle Änderungen von "älteren" Transaktionen (d.h. Transaktionen mit kleinerem Zeitstempel) sehen muß, jedoch keine Änderungen von "jüngeren" Transaktionen sehen darf. Werden diese Bedingungen verletzt, wird die betroffene Transaktion zurückgesetzt und mit einem neuen Zeitstempel wiederholt.

Die Überprüfung dieser sehr restriktiven Forderungen geschieht mittels Zeitmarken an den Datenobjekten, wobei für jedes Objekt ein Schreib- und ein Lesezeitstempel geführt wird. Der Schreibzeitstempel (write time stamp) WTS bzw. der Lesezeitstempel (read time stamp) RTS entspricht dabei der Transaktions-Zeitmarke derjenigen Transaktion, die das Objekt zuletzt geändert bzw. gelesen hat. Ein Lesezugriff einer Transaktion T mit Zeitstempel ts (T) auf ein Objekt x ist nicht zulässig, wenn gilt:

ts (T) < WTS (x).

Das bedeutet, daß keine jüngere Transaktion als T das Objekt zuletzt geändert haben darf. Analog muß für einen Schreibzugriff geprüft werden, daß keine jüngere Transaktion das Objekt bereits geändert oder gelesen hat, es darf also nicht gelten:

ts (T) < Max (RTS (x), WTS (x)).

Liegt eine dieser Bedingungen vor, erfolgt die Rücksetzung der zugreifenden Transaktion T.

Beispiel 8-3

Für den Schedule in Abb. 8-1a erfolgen die Zugriffe auf Objekt y in der BOT-Reihenfolge der beiden Transaktionen T1 und T2, so daß kein Konflikt vorliegt. Dagegen greift T1 erst nach der jüngeren Transaktion T3 auf Objekt x zu, so daß T1 zurückgesetzt wird. Als Serialisierungsreihenfolge ergibt sich T2 < T3.

Die Rücksetzgefahr einer Transaktion steigt mit zunehmender Verweildauer im System, da dann entsprechend mehr jüngere Transaktionen auf die noch benötigten Datenobjekte zugreifen können. Damit besteht vor allem für lange Transaktionen eine hohe Rücksetzwahrscheinlichkeit. Weiterhin kann ein "Verhungern" (starvation) einer Transaktion nicht verhindert werden, da für eine bereits zurückgesetzte Transaktion wiederum eine Rücksetzung notwendig werden kann. Dies kann dazu führen, daß bestimmte Transaktionen u.U. nie zu Ende kommen.

Ein weiterer Nachteil ergibt sich daraus, daß "schmutzige" Änderungen einer Transaktion durch Zusatzmaßnahmen gegenüber anderen Transaktionen zu verbergen sind. Für den Schedule in Abb. 8-1a ist so der Zugriff auf Objekt y durch T2 aufgrund der Zeitmarken zwar zulässig. Jedoch stellt die von T1 vorgenommene Änderung von y zu diesem Zeitpunkt eine schmutzige (vorläufige) Änderung dar, da T1 noch kein Commit erreicht hat. In der Tat wird ja T1 später aufgrund des Zugriffs auf Objekt x noch zurückgesetzt, so daß die von ihr vorgenommene Änderung von y zurückgenommen werden muß. Damit T2 nicht die schmutzige Änderung sieht, muß ihr Zugriff auf y bis zum Ende von T1 blockiert werden.

Das Beispiel verdeutlicht, daß nach einer Änderung wie bei Sperrverfahren alle weiteren Zugriffe (die nicht schon wegen des Zeitstempelvergleichs abgewiesen wurden) bis zum Transaktionsende des Änderers verzögert werden müssen. Damit kann ein ähnlich hohes Ausmaß an Blockierungen wie bei Sperrverfahren eingeführt werden, zusätzlich zu den aufgrund der Zeitmarkenvergleiche eingeführten Rücksetzungen. Deadlocks (zyklische Wartebeziehungen zwischen Transaktionen) sind jedoch nicht möglich, da die Objektzugriffe stets in der Reihenfolge der BOT-Zeitstempel durchgeführt werden.