Mehrrechner-Datenbanksysteme

8 Synchronisation in Verteilten Datenbanksystemen

Eine Schlüsseleigenschaft von DBS ist, daß viele Benutzer gleichzeitig lesend und ändernd auf die gemeinsamen Datenbestände zugreifen können, ohne daß die Konsistenz der Daten verletzt wird. Die Wahrung der DB-Konsistenz trotz paralleler Zugriffe ist Aufgabe der Synchronisationskomponente, wobei der Mehrbenutzerbetrieb gegenüber den Benutzern verborgen wird (Transparenz der konkurrierenden Verarbeitung, logischer Einbenutzerbetrieb). Werden alle Transaktionen seriell ausgeführt, dann ist der geforderte logische Einbenutzerbetrieb ohne jegliche Synchronisation erreicht, und die DB-Konsistenz ist am Ende jeder Transaktion gewährleistet. Eine strikt serielle Ausführung der Transaktionen zur Umgehung der Synchronisationsproblematik verbietet sich jedoch v.a. aus Leistungsgründen. Denn im Einbenutzerbetrieb könnten die Prozessoren aufgrund langer Transaktionsunterbrechungen, z.B. wegen Kommunikations- oder E/A-Vorgängen, nicht vernünftig genutzt werden.

Beim unkontrollierten Zugriff auf Datenobjekte im Mehrbenutzerbetrieb können eine Reihe von unerwünschten Phänomenen auftreten. Die wichtigsten dieser Anomalien sind verlorengegangene Änderungen ("lost update"), Lesen "schmutziger" Änderungen ("dirty read"), inkonsistente Analyse ("non-repeatable read") sowie sogenannte Phantome [Re87]. Änderungen können verlorengehen, wenn zwei Transaktionen parallel dasselbe Objekt ändern, wobei die zuerst vorgenommene Änderung durch die zweite Transaktion fälschlicherweise überschrieben wird. Das Lesen schmutziger Änderungen, welche von noch nicht zu Ende gekommenen Transaktionen stammen, führt zu fehlerhaften Ergebnissen, wenn die ändernde Transaktion noch zurückgesetzt werden muß und somit ihre Änderungen ungültig werden. Die inkonsistente Analyse sowie das Phantom-Problem betreffen Lesetransaktionen, die aufgrund parallel durchgeführter Änderungen während ihrer Ausführungszeit unterschiedliche DB-Zustände sehen.

Die genannten Anomalien werden vermieden durch Synchronisationsverfahren, welche das Korrektheitskriterium der Serialisierbarkeit erfüllen [EGLT76, BHG87]. Dieses Kriterium verlangt, daß das Ergebnis einer parallelen Transaktionsausführung äquivalent ist zu dem Ergebnis irgendeiner der seriellen Ausführungsreihenfolgen der beteiligten Transaktionen. Äquivalent bedeutet in diesem Zusammenhang, daß für jede der Transaktionen dieselbe Ausgabe wie in der seriellen Abarbeitungsreihenfolge abgeleitet wird und daß der gleiche DB-Endzustand erzeugt wird. Dies erfordert, daß eine Transaktion alle Änderungen der Transaktionen sieht, die vor ihr in der äquivalenten seriellen Ausführungsreihenfolge stehen, jedoch keine der in dieser Reihenfolge nach ihr kommenden Transaktionen. Die zur parallelen Transaktionsbearbeitung äquivalente serielle Ausführungsreihenfolge wird auch als Serialisierungsreihenfolge bezeichnet.

Um zu überprüfen, ob ein bestimmter Schedule, d.h. eine Ablauffolge von Transaktionen mit ihren zugehörigen Operationen, serialisierbar ist, kann ein Serialisierbarkeits- oder Abhängigkeitsgraph geführt werden. In diesem Graphen treten die einzelnen Transaktionen als Knoten auf und die Abhängigkeiten zwischen Transaktionen als (gerichtete) Kanten. Eine Abhängigkeit zwischen zwei Transaktionen Ti und Tj liegt vor, wenn Ti vor Tj auf dasselbe Objekt zugegriffen hat und die Operationen der beiden Transaktionen nicht reihenfolgeunabhängig (kommutativ) sind. Werden (wie üblich) als Operationen Lese- und Schreibzugriffe betrachtet, dann liegt eine Abhängigkeit vor, wenn wenigstens eine der beiden Operationen eine Schreiboperation darstellt. Es kann gezeigt werden, daß ein Schedule genau dann serialisierbar ist, wenn der zugehörige Abhängigkeitsgraph azyklisch ist. Denn nur in diesem Fall reflektiert der Graph eine partielle Ordnung zwischen den Transaktionen, die zu einer vollständigen Ordnung, die zugleich den äquivalenten seriellen Schedule bestimmt, erweitert werden kann.

Beispiel 8-1

Abb. 8-1a zeigt einen Schedule mit drei Transaktionen, wobei r(x) bzw. w(x) den Lese- bzw. Schreibzugriff der jeweiligen Transaktion auf Objekt x kennzeichnen. Der zugehörige Abhängigkeitsgraph ist in Abb. 8-1b gezeigt, wobei die Kanten zusätzlich mit dem die Abhängigkeit verursachenden Objekt gekennzeichnet sind. Da der Graph keinen Zyklus enthält, ist der gezeigte Schedule serialisierbar. Die Serialisierungsreihenfolge lautet T3 < T1 < T2.

Abb. 8-1: Schedule und Abhängigkeitsgraph (Beispiel)

Das Führen von Abhängigkeitsgraphen bietet jedoch keinen praktikablen Ansatz zur Implementierung eines Synchronisationsverfahrens, da hiermit meist erst nachträglich die Serialisierbarkeit von Schedules geprüft werden kann [Pe87]. Weiterhin wäre der Verwaltungsaufwand prohibitiv hoch, zumal auch Abhängigkeiten zu bereits beendeten Transaktionen zu berücksichtigen sind. Zur Synchronisation wird daher auf andere Verfahren zurückgegriffen, für welche nachgewiesen werden konnte, daß sie Serialisierbarkeit gewährleisten. Die Mehrzahl der vorgeschlagenen Verfahren läßt sich einer der drei folgenden Klassen zuordnen: Sperrverfahren, optimistische Protokolle sowie Zeitmarkenverfahren.

Diese Verfahrensklassen kommen auch für Verteilte Datenbanksysteme in Betracht. Als neue Anforderung ergibt sich hier, eine systemweite Serialisierbarkeit aller lokalen und globalen Transaktionen zu erzielen (globale Serialisierbarkeit). Hierzu reicht es nicht aus, nur die (lokale) Serialisierbarkeit in jedem Rechner zu gewährleisten, da in den einzelnen Rechnern unterschiedliche Serialisierungsreihenfolgen vorliegen können. Um eine hohe Leistungsfähigkeit zu erhalten, sollte diese Aufgabe wiederum mit möglichst geringem Kommunikationsaufwand erfüllt werden. Weiterhin sollte, wie bereits für zentralisierte DBS, die Synchronisation mit möglichst wenig Blockierungen und Rücksetzungen von Transaktionen erfolgen. Denn diese zur Behandlung von Synchronisationskonflikten verfügbaren Methoden haben beide einen negativen Einfluß auf Durchsatz und Antwortzeiten. Eine weitere Anforderung im verteilten Fall ist eine möglichst hohe Robustheit der Synchronisationsprotokolle gegenüber Fehlern (Rechnerausfall, Kommunikationsfehler). Erweiterungen werden daneben bei replizierten Datenbanken notwendig, um die wechselseitige Konsistenz von Replikaten sicherzustellen und Transaktionen mit aktuellen Objektkopien zu versorgen.

Da replizierte Datenbanken in Kap. 9 behandelt werden, konzentrieren wir uns hier zunächst auf die Synchronisation in partitionierten Datenbanken. Eine grobe Übersicht der hierbei in Betracht kommenden Verfahrensklassen ist in Abb. 8-2 gezeigt. Hierbei wird zwischen verteilten und zentralisierten Verfahren unterschieden, wobei letztere auf einem ausgezeichneten Knoten durchgeführt werden. Beide Alternativen bestehen für Sperrverfahren sowie optimistische Protokolle, während für Zeitmarkenverfahren nur eine verteilte Realisierung sinnvoll ist. Wie schon in zentralisierten DBS können die einzelnen Verfahrensklassen auch in Verteilten DBS vielfältig miteinander kombiniert werden (z.B. Sperrverfahren mit optimistischen Protokollen).

Abb. 8-2: Synchronisationsverfahren in Verteilten DBS

Im folgenden diskutieren wir die Realisierung von Sperrverfahren, Zeitmarkenverfahren sowie optimistischen Ansätzen für Verteilte Datenbanksysteme. Danach gehen wir auf die Realisierung einer Mehrversionen-Synchronisation ein, mit der das Ausmaß an Sperrkonflikten reduziert werden kann. Ein solcher Ansatz stellt eine mit allen Verfahrensklassen kombinierbare Optimierung dar, die in kommerziellen (zentralisierten) DBS zunehmend an Bedeutung gewinnt. In Kap. 8.5 werden dann die wichtigsten Alternativen zur Behandlung globaler Deadlocks vorgestellt. Einige zusammenfassende Bemerkungen schließen das Kapitel ab.

8.1 - Sperrverfahren in Verteilten DBS
8.2 - Zeitmarkenverfahren
8.3 - Optimistische Synchronisation
8.4 - Mehrversionen-Konzept
8.5 - Deadlock-Behandlung
8.6 - Abschließende Bemerkungen
Übungsaufgaben