III. Folge:

Tendenzen auf dem Gebiet der verteilten Datenbanksysteme

08.06.1979

Rasch zunehmende Benutzerakzeptanz und rascher technischer Fortschritt auf logischer, physikalischer und architektonischer Ebene sind die Haupttendenzen in der gegenwärtigen Entwicklung der Datenbanksysteme. Dies stellte George A. Champine, Direktor im "Advanced Systems" -Bereich für Großcomputersysteme bei Sperry Univac kürzlich fest. Die COMPUTERWOCHE berichtete in ihrer Nr. 19 vom 18. Mai 1979 darüber. In den Nummern 21 und 22 sind die ersten beiden Folgen der deutschen Fassung dieses Champine-Berichts abgedruckt.

Aktualisierung- Synchronisation multipler Datenkopien

Aufgrund der verschiedenen Vorteile replizierter oder redundanter untergliederter Datensysteme ist das sehr schwierige Problem der Aktualisierungs-Synchronisation zur Erhaltung der Datenbankintegrität auf beträchtliches Interesse gestoßen.

Viele Anwendungen funktionieren sehr zufriedenstellend mit Stapelaktualisierung verteilter Daten mit oder ohne mehrfache Kopien und können daher die Vorteile des verteilten Datensystems mühelos realisieren. Da diese Lösung auf keine grundlegenden Probleme stößt, wollen wir sie hier nicht weiter betrachten. Bei der Echtzeit-Aktualisierung von Daten mit mehrfachen Kopien entsteht jedoch eine Reihe schwerwiegender Probleme. Jeder Knotenpunkt erfährt anderswo vorgenommene Aktualisierungen erst nach einer unbekannten und nicht voraussehbaren Verzögerung. Wird diese Verzögerung nicht unter Kontrolle gebracht, so kann die interne Konsistenz (auch als Integrität bezeichnet) der Daten zerstört werden. Zum Beispiel können im Falle von Mehrfächkopien einer Flugreservationsdatenbank die Terminals zweier verschiedener Knotenpunkte unabhängig voneinander den letzten Platz eines bestimmten Flugs verkaufen und dann die Aktualisierung, die vom anderen Knotenpunkt ankommt, als ausverkauft zurückweisen.

In zentralisierten oder nicht redundanten, Datensystemen können Mechanismen wie Vereinzelungen eingebaut werden, um die Serialisierung von Aktualisierungen 3), 2), ZU sichern. Diese Serialisierung gewährleistet die Konsistenz der Daten. Um die Konsistenz auch zu gewährleisten, wenn Mehrfachkopien vorliegen, müssen die Aktualisierungen serialisiert werden, wobei die serialisierten Aktualisierungen an alle Kopien in gleicher Reihenfolge weitergegeben werden müssen. Für mehrfache Kopien von Daten können zwei Konsistenzniveaus definiert werden.

Starke Konsistenz bedeutet, daß alle Kopien gleichzeitig aktualisiert werden. Starke Konsistenz ist sehr wünschenswert, weil alle Kopien der Daten zu jedem Zeitpunkt den gleichen Aktualisierungsgrad aufweisen, doch ist damit immer ein beträchtliches Maß an Antwortzeitverzögerung verbunden, weil die Aktualisierung für alle Datenkopien mit Hilfe von globalen Verriegelungen simultanisiert werden muß.

Schwache Konsistenz liegt vor, wenn die verschiedenen Datenkopien zwar im Verlauf einer gewissen Zeitspanne den gleichen Aktualisierungsstand erreichen, aber zu einem bestimmten Zeitpunkt verschiedene Aktualisierungsniveaus aufweisen. Im allgemeinen reduzieren sich dadurch die Verzögerungen und die Datenressourcen werden besser genutzt, doch sind immer einige Daten höher aktualisiert als andere.

Kohärenz können wir definieren als das Maß der Differenzen zwischen den Datenkopien zu einem bestimmten Zeitpunkt.

Promptheit eines Systems ist definiert als die durchschnittliche Verzögerung bei der Vollendung von Aktualisierungen. Es liegen formale Definitionen für die Messung von Kohärenz und Promptheit vor 3).

Konvergent ist ein verteiltes Datensystem, wenn die Kohärenz nach der Aktualisierungseingabe die Einheit der Aktualisierung der Kopien erreicht.

Eine Art Heisenbergsche Unschärferelation

Ein System kann nicht gleichzeitig hohe Kohärenz und niedrige Promptheit aufweisen. Hier muß also immer eine Entscheidung getroffen werden. Es scheint hier eine Art Heisenbergsche Unschärferelation für das Gebiet der Informationsverarbeitung vorzuliegen, welche in der Physik postuliert, daß die Position und die Geschwindigkeit eines Gegenstands nicht gleichzeitig mit beliebig hoher Genauigkeit bestimmt werden kann.

Einige Anwendungen erfordern lediglich schwache Konsistenz, während andere starke Konsistenz brauchen. Diese können nebeneinander im gleichen System vorkommen und Zugriff zu den gleichen Daten erfordern, was einige interessante Systemkonstruktionsprobleme auf wirft.

Eine Reihe von Algorithmen ist für die Steuerung gleichzeitiger Aktualisierungen zur Erreichung der Konsistenz nach diesem schwächeren Kriterium vorgeschlagen worden'). Im einfachsten dieser Fälle werden alle Aktualisierungsanforderungen von ihrem Ursprungs-Knotenpunkt zu einem übergeordneten Knotenpunkt übermittelt, wo sie serialisiert und mit einer laufenden Nummer versehen werden. Die Aktualisierungen werden dann zu allen Zentren gesendet, wo sie in der Reihenfolge der laufenden Nummern realisiert werden 4), 5).

Andere Aktualisierungssteuerungen beruhen auf einem Zeitstempel, der bei Eingang der Aktualisierung durch eine Uhr am Ursprungsknotenpunkt aufgetragen wird. Die Zeitstempel kennen eindeutig gemacht werden. wenn jeder einzelne Knotenpunkt pro Uhrschritt nur eine Aktualisierung Vornehmen kann und der Zeitstempel zusätzlich mit der Kennziffer des Knotenpunkts versehen wird. Diese eindeutigen Zeitstempel können für eine Serialisierung der Aktualisierungen verwendet werden. Eine dieser Methoden beruht auf einem "Mehrheitskonsens"-Wert 6). Jede Aktualisierung unterliegt dabei einer Abstimmung durch alle Knotenpunkte. welche entscheiden, ob aufgrund der vorn ihnen bereits getätigten Aktualisierungen die neue Aktualisierung akzeptabel i ist. Aktualisierungen, die von einer Mehrheit von Knotenpunkten akzeptiert werden, werden in der Reihenfolge der Zeitstempel akzeptiert. Diese Lösung ist gegen Fehler im Verkehr oder in den

Eine weitere Lösung mit Zeitstempel klassifiziert die Aktualisierungen nach den von ihnen modifizierten Variablen. Ein bestimmter Knotenpunkt wird a priori mit der Aufgabe betraut, die Aktualisierungen mit Variablen erneut bestimmten Klasse sequentiell zu ordnen. Potentielle Konflikte zwischen Aktualisierungen verschiedener Klassen werden durch eine "Konflikttafel" gelöst, die durch eine Voranalyse des Systems erzeugt wird. Mit dieser Lösung werden rasch jene Situationen identifiziert, welche keine Steuerung erfordern, während alle Aktualisierungen, die zu einer Verminderung der Integrität führen können, eine sorgfältige Behandlung

einfahren.

Alle diese Methoden und weitere zur Zeit untersuchte Verfahren; sind geeignet, die Integrität der Daten zu erhalten. Je nach Anwendung kommen jedoch weitere Prioritäten in Betracht:

- Minimalisierung der Verzögerung;

- Vermeidung vorzugsmäßiger Behandlung von Knotenpunkten;

- Minimalisierung der Rückweisung von Aktualisierungen;

- Minimalisierung der Datenverkehrskosten.

Jeder Aktualisierungs-Algorithmus muß für die in Frage stehende Anwendung bewertet werden, um eine optimale Gewichtung dieser Parameter zu gewährleisten.

Stillstand (Dead-lock)

Die gleichen Stillstandsprobleme, die in zentralisierten Mehrprogrammsystemen auftauchen können, sind auch in verteilten Systemen möglich. Auf logischem Niveau bleiben sich die allgemeinen Lösungsmethoden gleich. Auf physischer Basis sind sie jedoch komplizierter, weil die physischen und die Datenresourcen verteilt sind.

Bei der Bewältigung von Stillständen kommen drei prinzipielle Techniken in Frage, und zwar sowohl bei zentralisierten als auch bei verteilten Systemen:

- Verhütung,

- Vermeidung,

- Erkennung und Lösung.

Im Falle der Verhütung müssen alle für eine Transaktion benötigten Ressourcen zu Beginn der Transaktion angefragt werden. Dies ist sehr schwierig, weil die Ressourcenanforderungen oft datenabhängig und zu Beginn der Transaktion unbekannt sind. Die Erfassung aller möglichen Ressourcen zu Beginn wäre sehr ineffizient vom Standpunkt der Ruhehaltung der Ressourcen als auch der Verminderung der System-Simultanität.

Die Stillstandsvermeidung erfordert weitergehende Kenntnis des Ressourcengebrauchs der Transaktionen, um an jedem Punkt bestimmen zu können, ob eine gültige Aktionssequenz der begonnenen Transaktionen vorhanden ist, damit sie vollendet werden können. In verteilten Systemen ist diese Lösung ebenfalls sehr unattraktiv, weil die notwendige vorgängige Information zur Vermeidung von Stillstand entweder gar nicht vorhanden ist oder aber so breit verteilt ist, daß eine bedeutende Menge zusätzlicher Schritte und Verzögerungen auftreten müßten.

Eine Stillstandserkennung ist möglich durch die Suche nach Zyklen in einer Statustafel des Ressourcengebrauchs wie in COFF 71 beschrieben. Sie wurde auf zentralisierte Systeme beschränkt (KING 74). In verteilten Systemen ist die Methode nicht effizient, da anders als in zentralisierten Systemen die Führung solcher globaler Statustafeln nicht sinnvoll durchzufahren ist. Es sind zwei Methoden für die Erkennung und Lösung von Stillständen in verteilten Systemen entwickelt worden, die auf globale Statustafeln verzichten (MENA 78): eine hierarchische und eine verteilte. Beide erkennen erwiesenermaßen alle Stillstände.

1) ESWAR 76, The Notions of Consistency and Predicate Locks in a Database System, by Eswaran, Gray, Lorie, and Traiger, CACM, November 1976.

2) GRAY 75, Granularity of Locks and Degrees of Consistency in a Shared Database, by Gray, Lorie, Putzolu, and Traiger, Report from IBM San Jose Laboratory, 1975.

3) GELEN 78, Analysis of Update Synchronization for Multiple Copy Data Bases, by Gelenbe and Sevcik, Proceedings of the Third Berkeley Workshop on Distributed Data Management and Computer Networks, August 1978, pp. 69--90

4) ALSBE 76, A Principle for Resilient Sharing of Distributed Resources, by Alsberg and Day, Proceedings of the Second Conference on Software Engineering, October 1976.

5) GRAPA 77, Techniques for Update Synchronization in Distributed Data Rases, by E. Grapa and G.G. Belford, Center for Advanced Computation Report, University of Illinois, 1977.

6) ROTHN 77, The Redundant Update Methology of SDD-1: A System for Distributed Databäses, by J B Rothnie, Goodman, Bernstein, and Papadimitriou, Technical Report No. CCA- 77-02, Computer Corporation of America, 1977.

7) THOTA 77, A Majority Concensus Approach to Concurrency Control for Multiple Data Bases, by R H Thomas, BBN Report No 3733, December 1977