Prinzipien der Replikationskontrolle in verteilten Datenbanksystemen? [original]

Informatik Forsch. Entw. (1996) 11: 203–212

Springer-Verlag 1996

Prinzipien der Replikationskontrolle

in verteilten Datenbanksystemen?

T. Beuter, P. Dadam

Abteilung Datenbanken und Informationssysteme, Fakult¨

at f¨

ur Informatik, Universit¨

at Ulm, D-89069 Ulm

(e-mail: {beuter,dadam}@informatik.uni-ulm.de, WWW: http://www.informatik.uni-ulm.de/abt/dbis)

Eingegangen am 6. Februar 1996 / Angenommen am 12. September 1996

Zusammenfassung. Durch Datenreplikation k¨

onnen prin-

zipiell schnellere Zugriffszeiten und eine beliebig hohe Feh-

lertoleranz in verteilten Datenbanksystemen erreicht wer-

den. Anderseits erh¨

oht Replikation die Gefahr von Inkon-

sistenzen und den Aufwand von ¨

Anderungsoperationen. Zur

L¨

osung dieses Zielkonflikts wurden in der Literatur viele

unterschiedliche Replikationsverfahren vorgeschlagen. Die-

ser ¨

Uberblicksartikel beschreibt die den einzelnen Verfahren

zugrundeliegenden Prinzipien zur Replikationskontrolle. Da-

zu werden die durch den Kopieneinsatz resultierenden Pro-

bleme erl¨

autert, daraus Kriterien zur anschließenden Klassi-

fikation abgeleitet und danach ausgew¨

ahlte Replikationsver-

fahren n¨

aher vorgestellt.

Schl¨

usselw¨

orter: verteiltes (Datenbank-)System, Replika-

tion, Fehlertoleranz, Netzpartitionierung, 1-Kopie-Serialisier-

barkeit, Datenkonsistenz

Abstract. The replication of data promises better perfor-

mance and a high fault tolerance in distributed systems.

However, replication increases the risk of data inconsist-

encies and the cost of updates. In order to find an appropriate

solution for this trade-off many methods for the management

of replicated data have been proposed in the literature. In this

paper the underlying principles of these replication methods

are critically surveyed. The problems caused by data repli-

cation are described, a classification schema is derived, and

some important replication methods are critically discussed

in more detail.

Key words: distributed (database)system, replication, fault

tolerance, partitioned network, 1-copy serialisibility, data

consistency

CR Subject Classification: C.4, C.2.4, D.4.5, H.2.4

1 Einleitung und Motivation

In den letzten Jahren kann ein immer st¨

arkerer Trend zu ver-

teilten Datenbanksystemen beobachtet werden. Diese Ten-

denz l¨

aßt sich sowohl bei klassischen Datenbankanwendun-

?Diese Arbeit entstand im Rahmen eines von der Daimler-Benz-

Forschung Ulm gef¨

orderten Forschungsprojekts

gen (weg vom Mainframe, hin zu verteilten Client-Server-

Applikationen) als auch in vielen neuen Anwendungsge-

bieten (z.B.: mobile Computing, Concurrent Engineering,

Workflow-Management, Data Warehousing) feststellen, bei

denen die Verteilung schon anwendungsbedingt vorgegeben

ist. Eine Voraussetzung f¨

ur die bessere Fehlertoleranz und

den h¨

oheren Durchsatz eines verteilten Systems stellt viel-

fach die Replikation der Daten dar: Der Wert eines (Daten-)

Objekts wird hierbei auf mehrere (Rechner-) Knoten des ver-

teilten Datenbanksystems gespeichert. Durch einen dann rea-

lisierbaren Zugriff auf die lokal vorhandene bzw. auf eine

schnell erreichbare Kopie wird ein Weiterarbeiten auch bei

Ausfall datenhaltender Knoten erm¨

oglicht sowie der Durch-

satz erh¨

oht. Replikation ist deshalb besonders bei dateninten-

siven Anwendungen (z.B. Multi-Media) und bei verteilten

Systemen notwendig, die ¨

uber ein unsicheres Kommunikati-

onsnetzwerk mit geringer Bandbreite verf¨

ugen (z.B. mobile

Computing).

Allerdings f¨

uhrt Replikation bei der Ver¨

anderung eines

Objekts zu h¨

oherem Kommunikations- und Verwaltungs-

aufwand, da das Objekt in der Regel auf mehreren Kno-

ten aktualisiert werden muß. Dieser Aufwand erh¨

oht sich

noch, wenn gefordert wird, daß sich aus der Sicht der An-

wendung ein repliziertes Datenbanksystem wie ein nicht-

repliziertes System verhalten soll (sog. 1-Kopie- ¨

Aquivalenz

(1-copy equivalence) [4]). Das verteilte System muß dann

darauf achten, daß die Kopien eines replizierten Objekts

wechselseitig konsistent (mutual consistent) [14] sind. Die-

se Aufgabe wird durch das Auftreten von Rechner- und

Netzausf¨

allen erschwert. Besonders problematisch sind in

diesem Zusammenhang Partitionierungen, bei denen eine

verteilte Datenbank so in disjunkte Knotenmengen (Parti-

tionen) aufgeteilt wird, daß eine Kommunikation ¨

uber Par-

titionsgrenzen hinaus nicht mehr m¨

oglich ist. Dadurch kann

aus dem ”Nichterreichen“ eines Knotens nicht mehr auf des-

sen Ausfall und damit dessen Inaktivit¨

at geschlossen wer-

den: Er kann sich auch funktionsf¨

ahig in einer anderen

Partition befinden. Es besteht dann die Gefahr, daß Kno-

ten aus verschiedenen Partitionen ihre erreichbaren Kopien

unkoordiniert ver¨

andern und dadurch das verteilte Daten-

banksystem in einen inkorrekten (= inkonsistenten) Zustand

204

Ziel-

konflikt

der

Replikations-

kontrolle

und des effizienten Zugriffs

Erhöhung der Verfügbarkeit

kleine Kopienanzahl

Ziel: 1-Kopie-Äquivalenz

möglichst viele Kopien

synchron aktualisieren

(Kopien wechselseitig

konsistent halten)

Erhaltung der

Datenkonsistenz

Minimierung des

Aufwands einer

Änderungsoperation

möglichst wenige Kopien

kleine Kopienanzahl

synchron aktualisieren

große Kopienanzahl

Zugriff auf beliebige und

möglichst wenige Kopien

Abbildung 1. Zielkonflikt der Replikationskontrolle

uberf¨

uhren. Hier existiert ein Zielkonflikt zwischen maxima-

ler Verf¨

ugbarkeit und der Korrektheit des Gesamtsystems.

Es muß deshalb ein geeigneter Kompromiß gefunden

werden, der es erm¨

oglicht, die Vorteile der Datenreplikation

(h¨

ohere Verf¨

ugbarkeit, effizienterer Zugriff) zu nutzen, und

dabei ihre Nachteile (gr¨

oßerer ¨

Anderungsaufwand, Gefahr

von Dateninkonsistenzen) m¨

oglichst zu vermeiden. In der

Abbildung 1 werden dieser Zielkonflikt und die daraus re-

sultierenden Folgen f¨

ur die Verwaltung von Datenreplikaten

graphisch dargestellt.

Zur L¨

osung dieses Zielkonflikts werden in der Litera-

tur viele verschiedene Replikationsverfahren vorgeschlagen.

Ziel dieses ¨

Ubersichtsartikels ist es, durch eine kritische Be-

trachtung der verschiedenen Grundprinzipien zur Replika-

tionskontrolle, eine Klassifikation f¨

ur Replikationsverfahren

zu erstellen, um damit dem interessierten Leser den Einstieg

in dieses Gebiet zu erleichtern.

Diese Grundprinzipien werden in Kapitel 2 anhand der

verschiedenen Aufgaben der Replikationsverfahren erarbei-

tet, ihre jeweiligen Vor- und Nachteile kritisch beleuchtet

und dabei Kriterien zur Klassifikation der Replikationsme-

thoden abgeleitet. Im darauffolgenden Kapitel werden ei-

nige ausgew¨

ahlte Verfahren detaillierter beschrieben sowie

ihre spezifischen Vor- und Nachteile diskutiert. Kapitel 4

bildet mit einigen Bemerkungen ¨

uber verschiedene Kombi-

nationsm¨

oglichkeiten von Replikationsstrategien sowie mit

Hinweisen auf kommerzielle Datenbanksysteme, die Repli-

kationskomponenten enthalten, den Schluß dieses Papiers.

2 Klassifikation von Replikationsverfahren

Die Suche nach einem geeigneten Kompromiß f¨

ur den in

Abbildung 1 skizzierten Zielkonflikt f¨

uhrte in der Literatur

zu recht unterschiedlichen Vorschl¨

agen zur Replikationskon-

trolle. Diese Vorschl¨

age lassen sich am besten anhand der

folgenden Punkte klassifizieren:

1. Sicherung der Datenkonsistenz (Abschnitt 2.1)

2. Kopien-Update-Strategie (Abschnitt 2.2)

3. Behandlung von Netzpartitionierungen (Abschnitt 2.3)

2.1 Sicherung der Datenkonsistenz

Wie bei Datenbanksystemen ¨

ublich, wird auch bei replizier-

ten Datenbanken die Datenkonsistenz h¨

aufig ¨

uber die Se-

rialisierbarkeit beschrieben. Dieser Serialisierbarkeitsbegriff

muß zur Einhaltung der 1-Kopie- ¨

Aquivalenz erweitert wer-

den:

1-Kopie-serialisierbare Schedule:

Eine Schedule S einer replizierten Datenbank heißt 1-Kopie-

serialisierbar, wenn es mindestens eine serielle Ausf¨

uhrung

der Transaktionen dieser Schedule auf einer nicht replizier-

ten Datenbank gibt, welche, angewandt auf denselben An-

fangszustand, die gleiche Ausgabe sowie den gleichen Da-

tenbankendzustand erzeugt wie S auf der replizierten Daten-

bank [4, 14].

Die Einhaltung des verwendeten Korrektheitskriteriums

l¨

aßt sich auf zwei Arten realisieren:

Bei syntaktischen Verfahren, zu denen der Großteil der

Replikationsverfahren geh¨

ort [30, 27, 33, 20, 24, 1, 3, 17],

wird die Korrektheit eines Zugriffs einzig ¨

uber die Reihen-

folge der zugreifenden Transaktionen, also ¨

uber die Folge

ihrer Lese- und Schreiboperationen, bestimmt.

Dagegen n¨

utzen semantische Verfahren die Semantik der

Transaktionen, wie z.B. Kommutativit¨

at der Operationen

[6, 22, 26], bzw. die Semantik der Datenbank [18] aus,

um die Anzahl zul¨

assiger Ausf¨

uhrungsreihenfolgen (Sche-

dules) zu erh¨

ohen. Bei den semantischen Ans¨

atzen gibt es

Verfahren, bei denen die Korrektheit nur ¨

uber semantische

Integrit¨

atsbedingungen der Datenbank definiert wird ([18],

siehe Abschnitt 3.2.1). Daneben existieren aber auch Verfah-

ren, die semantisches Wissen zus¨

atzlich zur Ausf¨

uhrungsrei-

henfolge verwenden, um die Verf¨

ugbarkeit oder den Paral-

lelit¨

atsgrad der Datenbank zu erh¨

ohen ([6], [26] siehe Ab-

schnitt 3.2.2).

Im allgemeinen sind semantische Verfahren nicht so uni-

versiell einsetzbar wie syntaktische Ans¨

atze, da nicht je-

de Anwendung die f¨

ur den Einsatz des jeweiligen semanti-

schen Verfahrens notwendigen Voraussetzungen erf¨

ullt (z.B.

nur kommutative Datenmanipulationsoperationen). Ander-

seits sind semantische Verfahren gerade bei verteilten Syste-

men besonders attraktiv, da aufgrund der semantisch h¨

oheren

Operationen der erforderliche Kommunikations- und Syn-

chronisationsaufwand reduziert werden kann (siehe Ab-

schnitt 2.2).

Der jeweils zugrundegelegte Korrektheitsbegriff muß so-

wohl beim Kopien-Update (Abschnitt 2.2) als auch im Feh-

lerfall (Abschnitt 2.3) eingehalten werden.

2.2 Kopien-Update-Strategie

Bei replizierten Datenbanksystemen muß festgelegt werden,

welche und wieviele Kopien eines Objekts synchron mit

dem Commit einer ¨

Anderungstransaktion und welche Ko-

pien asynchron nach Beendigung der Transaktion aktuali-

siert werden. Aufgrund der geforderten Dauerhaftigkeit der

Anderungen einer mit Commit beendeten Transaktion muß

mindestens eine Kopie synchron aktualisiert werden. Je mehr

Kopien synchron ge¨

andert werden, desto mehr Kopien sind

wechselseitig konsistent, aber desto aufwendiger und feh-

205

leranf¨

alliger wird ein Transaktions-Commit.1Asynchrone

Anderungen blockieren dagegen das Commit einer Trans-

aktion nicht. Dadurch k¨

onnen Knoten- und Netzausf¨

alle wie

asynchrone ¨

Anderungsoperationen mit besonders langer zeit-

licher Verz¨

ogerung behandelt werden.

Je nach Update-Strategie variiert die Zahl der synchro-

nen ¨

Anderungen zwischen nur einer Kopie (manche seman-

tische bzw. absolutistische Verfahren) und (m¨

oglichst) allen

Kopien (Read-One-Copy-basierte Verfahren).

Um Datenbank-Inkonsistenzen zu vermeiden, muß eine

geeignete Kopien-Update-Strategie die folgenden Punkte si-

cherstellen:

Punkt 1. Konkurrierende Updates auf verschiedene Kopien

desselben Objekts m¨

ussen koordiniert werden (kopien¨

uber-

greifende Synchronisation). Die Art der kopien¨

ubergreifen-

den Synchronisation bestimmt im wesentlichen die Zahl der

notwendigen synchronen Updates.

Punkt 2. Ein Update muß stets auf einer aktuellen Kopie

basieren.

Bei der nun folgenden Beschreibung der verschiedenen

Kopien-Update-Strategien wird auch immer auf die jeweili-

ge Umsetzungen dieser Punkte eingegangen. Abschnitt 2.2.1

erl¨

autert die grunds¨

atzlichen Update-Strategien f¨

ur syntakti-

sche Verfahren. Abschnitt 2.2.2 zeigt, welche Vorteile se-

mantisches Wissen bei der Kopien-Update-Strategie bringen

kann.

2.2.1 Syntaktische Kopien-Update-Strategien

Bez¨

uglich der Kopien-Update-Strategie wurden f¨

ur syntakti-

sche Verfahren die folgenden zwei grunds¨

atzlichen Ans¨

atze,

absolutistische und Abstimmungsverfahren vorgeschlagen:

2.2.1.1 Absolutistische Verfahren. Beim absolutistischen An-

satz realisiert eine ausgezeichnete Kopie (primary copy [30],

Besitzer des tokens [27]) die kopien¨

ubergreifende Synchro-

nisation (Punkt 1). Will eine Transaktion ein Objekt ¨

andern,

so ben¨

otigt sie die Zustimmung dieser Kopie. In der Regel ist

diese Kopie auch die einzige, die synchron aktualisiert wird.

Da jedoch jeder Zugriff ¨

uber diese ausgezeichnete Kopie

erfolgt, basiert jedes Update auf dem aktuellen Objektwert

(Punkt 2).

Lesetransaktionen d¨

urfen, da sie den Datenbankzustand

nicht ver¨

andern, dagegen meist ohne Zugriff auf die Prim¨

ar-

kopie von einer beliebigen und idealerweise lokal vorhan-

denen Kopie lesen. Hierbei besteht jedoch die Gefahr, daß

die Kopie, auf die zugegriffen wird, aufgrund der asynchro-

nen ¨

Anderungen nicht den aktuellen Wert des Datenobjekts

widerspiegelt (running in the past [3]). Greift eine Lese-

transaktion auf mehrere verschiedene Objekte zu, so kann

sie auch inkonsistente Daten sehen, wenn die ¨

Anderungen

einer Schreibtransaktion auf nur einem Teil der gelesenen

Objekte durchgef¨

uhrt wurden. Absolutistische Ans¨

atze ga-

rantieren in dieser Form also keine 1-Kopien- ¨

Aquivalenz

f¨

ur Lesetransaktionen. Ist dies f¨

ur eine Lesetransaktion nicht

tolerierbar, so muß auch zum Lesen auf die jeweilige aus-

gezeichnete Kopie zugegriffen werden (Lesetransaktion als

1Beispielsweise zeigen Absch¨

atzungen, daß die Deadlock-Wahrschein-

lichkeit mit der vierten Potenz der Zahl an synchronen Updates w¨

achst [21],

Seite 429

Pseudo- ¨

Anderungstransaktion), wodurch der Vorteil des lo-

kalen Lesens im wesentlichen verlorengeht.

Die Verf¨

ugbarkeit eines logischen Objekts h¨

angt bei die-

sen Verfahren stark von der Verf¨

ugbarkeit der ausgezeich-

neten Kopie ab. F¨

allt diese aus, kann ein Stellvertreter die

Synchronisation ¨

ubernehmen. Dabei muß zur Vermeidung

von Inkonsistenzen sichergestellt werden, daß zu jedem Zeit-

punkt immer nur eine ausgezeichnete Kopie f¨

ur jedes Objekt

existiert. Kann dabei nicht zwischen Knotenausf¨

allen und

Netzwerkfehlern unterschieden werden, so ist die Bestim-

mung einer neuen ausgezeichneten Kopie aufwendig. Ein

weiterer Nachteil dieser Ans¨

atze besteht darin, daß jeder

andernde (und evtl. auch lesende) Zugriff ¨

uber die ausge-

zeichnete Kopie des Objekts erfolgen muß. Bei vielen Zu-

griffen kann diese Kopie dann zum Engpaß werden.

Die Attraktivit¨

at absolutistischer Verfahren liegt vor al-

lem in ihrer einfachen Realisierung. Im Prinzip kann je-

des der bei nicht-replizierten Datenbanksystemen verwen-

dete Synchronisationsverfahren (z.B. Sperrverfahren, opti-

mistische Verfahren) eingesetzt werden.

2.2.1.2 Abstimmungsverfahren. Einen ”demokratischeren“

Ansatz verfolgen die Abstimmungsverfahren [33, 20, 24, 1,

2], bei denen die kopien¨

ubergreifende Synchronisation der

Zugriffe (Punkt 1) durch Abstimmung (voting) erfolgt. Da-

zu erh¨

alt jede Kopie eine bestimmte Anzahl an Stimmen

(oft 1) zugeteilt. Der Zugriff einer Transaktion auf ein lo-

gisches Objekt wird nur dann erlaubt, wenn eine entschei-

dungsf¨

ahige Anzahl, ein sogenanntes Quorum, an Kopien

zustimmt. H¨

aufig wird dabei zwischen einem Lesequorum

QR, das zum lesenden Zugriff erlangt werden muß, und ei-

nem Schreibquorum QWf¨

ur den Schreibzugriff unterschie-

den. Werden bei der Wahl des Schreib- und Lesequorums

die folgenden ¨

Uberschneidungsregeln (vgl. z.B. [1]) einge-

halten, so k¨

onnen Dateninkonsistenzen nicht mehr auftreten:

•Schreib/Schreib- ¨

Uberschneidungsregel:

2∗QW>P¨

uber alle Stimmen

•Schreib/Lese- ¨

Uberschneidungsregel:

QW+QR>P¨

uber alle Stimmen

Durch die Schreib/Schreib- ¨

Uberschneidungsregel wer-

den parallele Schreibzugriffe ¨

uber die gemeinsame(n) Ko-

pie(n) synchronisiert (Punkt 1). Werden außerdem minde-

stens QWKopien beim Transaktions-Commit synchron ak-

tualisiert, so ist sichergestellt, daß jedes Update auf dem

aktuellen Objektwert basiert (Punkt 2). Zusammen mit der

Schreib/Lese- ¨

Uberschneidungsregel ist dann auch in jedem

Lesequorum mindestens eine aktuelle Kopie enthalten.

Zur Bestimmung einer aktuellen Kopie werden entwe-

der Versionsnummern oder Zeitstempel eingesetzt. Die Ver-

wendung von Zeitstempeln hat den Vorteil, daß die Schreib/

Schreib- ¨

Uberschneidungsregel entfallen kann, da die Syn-

chronisation der Schreibzugriffe ¨

uber die Zeitstempelreihen-

folge erfolgt [22].

Im Rahmen der ¨

Uberschneidungsregeln ist die f¨

ur eine

Lese- bzw. Schreibquorum ben¨

otigte Stimmenzahl frei w¨

ahl-

bar. Beim urspr¨

unglichen Vorschlag, dem Majority-Consen-

sus-Verfahren [33], wird f¨

ur Lese- und Schreibquorum je-

weils eine Stimmenmehrheit ben¨

otigt (QR=QW

206

=N÷2+1)

ahlt man dagegen eine asymmetrische

Quorumseinteilung, so kann eine Zugriffsoperation (z.B. die

in den meisten Anwendungen h¨

aufigere Leseoperation) auf

Kosten der anderen optimiert werden.

Durch eine unterschiedliche Verteilung der Stimmen auf

die Kopien (weighted voting [20]) k¨

onnen dar¨

uberhinaus

auch einzelne Kopien bevorzugt werden. Damit kann bei

gerader Kopienanzahl die Wahrscheinlichkeit, ein Quorum

zu erreichen, erh¨

oht werden: Wird beispielsweise ein Objekt

auf vier Knoten repliziert, so ben¨

otigt man mindestens die

Zustimmung von drei Knoten. Erh¨

alt jedoch ein (besonders

ausfallsicherer) Knoten zwei Stimmen, so gen¨

ugt schon die

Zustimmung eines weiteren Knotens zur Erlangung des Quo-

rums [7]. Kriterien f¨

ur eine geeignete Wahl eines Quorums

werden detailiert in [19] diskutiert.

Im Vergleich zu absolutistischen Verfahren sind Abstim-

mungsverfahren im fehlerfreien Fall aufwendiger, da zur

Synchronisation mehr Nachrichten ausgetauscht und mehr

Kopien synchron aktualisiert werden m¨

ussen. Daf¨

ur sind

Abstimmungsverfahren nicht mehr von der Verf¨

ugbarkeit

einzelner ausgezeichneter Kopien abh¨

angig. Bei der Ab-

stimmung kann der Ausfall einer Kopie jederzeit durch die

Stimme(n) einer beliebigen anderen Kopie kompensiert wer-

den, ohne daß zus¨

atzliche Ersetzungsalgorithmen notwendig

sind.3

Bei der Frage, wann welche Art der kopien¨

ubergrei-

fenden Synchronisation vorzuziehen ist, muß sicherlich die

Verf¨

ugbarkeit und Leistungsf¨

ahigkeit der einzelnen Kompo-

nenten des verteilten Systems ber¨

ucksichtigt werden. Unter-

scheiden sich die einzelnen Komponenten in diesen Punkten

stark (z.B. schneller Mainframe mit nahezu 100% Verf¨

ugbar-

keit, kleinere Abteilungs- oder Arbeitsplatzrechner mit

gr¨

oßeren Ausfallzeiten), so ist sicherlich ein absolutistischer

Ansatz, bei dem der Rechner mit der h¨

ochsten Verf¨

ugbarkeit

als ausgezeichnete Stelle fungiert, einem Abstimmungsver-

fahren vorzuziehen. Bei einer homogeneren Verteilung der

Ausfallzeiten ist dagegen die Gefahr der Nichtverf¨

ugbar-

keit der ausgezeichneten Kopie gr¨

oßer. Außerdem ist es

wichtiger, daß alle Knoten des verteilten Systems m¨

oglichst

gleichm¨

aßig belastet werden, um Leistungsengp¨

assen vorzu-

beugen. Deshalb ist bei einer solchen Systemkonfiguration

ein Abstimmungsverfahren meist besser geeignet.

Die in der Literatur vorgeschlagenen Abstimmungsver-

fahren (f¨

ur einen ¨

Uberblick siehe auch [7]) unterscheiden

sich haupts¨

achlich in der Strukturierung des Quorums und in

der M¨

oglichkeit, die Gr¨

oße des Quorums zu ver¨

andern. Die

Vorschl¨

age lassen sich deshalb bzgl. zweier zueinander or-

thogonalen Dimensionen einteilen. Die eine Dimension legt

den Aufbau (strukturiert, unstrukturiert) eines Quorums fest.

In der anderen Dimension wird unterschieden, ob die Gr¨

oße

des Quorums fest vorgegeben ist oder ob sie sich dynamisch

an die – aufgrund von Partitionierungen – ver¨

anderte Zahl

an Stimmberechtigten anpaßt. Aus Platzgr¨

unden werden im

folgenden die Unterschiede nur kurz skizziert. Eine ausf¨

uhr-

liche Beschreibung ist in [5] zu finden.

2N bezeichnet die Kopien- bzw. Stimmenanzahl; ÷entspricht der ganz-

zahligen Division

3Bei strukturierten Abstimmungsstrategien (siehe n¨

achster Abschnitt)

ist diese Fehlertoleranz eingeschr¨

ankt, da eine Kompensation ausgefalle-

ner Kopien nur entlang der bei diesen Verfahren vorgegebenen logischen

Struktur erfolgen kann

Unstrukturiertes vs. strukturiertes Quorum: Bei den unstruk-

turierten Ans¨

atzen [33, 20, 19, 24, 12, 32] wird ein Quorum

gebildet, indem man QRbzw. QWStimmen ansammelt, die

von beliebigen Kopien stammen k¨

onnen. Dagegen werden

bei den strukturierten Verfahren [1, 2, 25, 9, 8] die Kopien in

einer logischen Baum- oder Gitterstruktur angeordnet. Zur

Erlangung eines Quorums m¨

ussen dann entlang dieser Struk-

tur in lEbenen jeweils sStimmen4gesammelt werden. Die

Uberschneidungsregeln gelten dann sowohl f¨

ur die Ebenen

als auch f¨

ur die Stimmen in einer Ebene.

Der Vorteil der strukturierten Verfahren liegt bei den ge-

ringeren Zugriffskosten, da zum Erreichen eines Quorums

weniger Stimmen als im unstrukturierten Fall ben¨

otigt wer-

den, ohne daß die Ausfallsicherheit stark beeintr¨

achtigt wird.

Dieser Vorteil kommt besonders bei hohem Replikationsgrad

zur Geltung.

Nachteilig dagegen ist neben dem h¨

oheren Verwaltungs-

aufwand, daß die Stimmen nicht mehr bei beliebigen Ko-

pien, sondern nur noch entlang der vorgegebenen Struk-

tur gesammelt werden k¨

onnen. ¨

Ahnlich zu den absoluti-

stischen Ans¨

atzen werden die Anfragen damit nicht mehr

gleichm¨

aßig ¨

uber alle Knoten verteilt, sondern konzentrie-

ren sich insbesondere bei baumartigen Strukturen auf wenige

”strategische“ Knoten.

Das Prinzip eines auf einer logischen Baumstruktur ba-

sierenden Replikationsverfahrens wird in Abschnitt 3.1.1.2

n¨

aher beschrieben.

Dynamisches vs. statisches Quorum: Wird eine replizierte

Datenbank infolge von Verbindungsunterbrechungen mehr-

fach partitioniert, so wird es immer schwieriger, die zu einem

Quorum erforderliche Stimmenanzahl zu erreichen. Deshalb

ist es aus Gr¨

unden der Verf¨

ugbarkeit w¨

unschenswert, daß

sich ein Quorum dynamisch an die gerade verf¨

ugbare Ge-

samtstimmenanzahl anpaßt [24, 12, 2]. Um Inkonsistenzen

zu vermeiden, darf es dabei aber nicht vorkommen, daß in

zwei getrennten Partitionen jeweils ein Schreibquorum er-

reicht werden kann.

Auch bei einer Ver¨

anderung des Zugriffsverhaltens ist

eine andere Stimmverteilung w¨

unschenswert [22]. Damit

kann z.B. bei einer zeitweilig hohen Update-Rate das

Schreibquorum zu Lasten des Lesequorums verkleinert wer-

den.

Als typischer Vertreter dieser Art von Replikationsver-

fahren wird in Abschnitt 3.1.1.1 der Ansatz der dynamischen

Abstimmung detaillierter beschrieben.

2.2.1.3 Read-One-Copy-basierte Verfahren. Als Spezialfall

der Abstimmungsverfahren k¨

onnen die Read-One-Copy-

basierten Verfahren angesehen werden, bei denen im feh-

lerfreien Fall zum Lesen die Zustimmung einer beliebigen

Kopie gen¨

ugt (QR= 1). Dadurch kann durch den alleini-

gen Zugriff auf die lokale Kopie (falls vorhanden) der in

den meisten Anwendungen sehr viel h¨

aufigere Lesezugriff

optimiert werden.

Bei den anderen Abstimmungsverfahren m¨

ussen dagegen

im allgemeinen Fall f¨

ur den aktuellen Objektwert mehrere

Kopien konsultiert werden. Bei den absolutistischen Verfah-

ren gen¨

ugt es zwar, zum Lesen auf nur eine Kopie zuzugrei-

4bzw. alle Stimmen auf Ebene k, falls Ebene kweniger als sStimmen

besitzt

207

fen, diese ist f¨

ur konsistentes Lesen jedoch fest vorgeschrie-

ben (Kopie der ausgezeichneten Stelle), so daß in der Regel

ein entfernter Zugriff notwendig ist (Verlust des lokalen Le-

sens).

Die Basis aller Read-One-Copy-basierten Verfahren bil-

det die ROWA-Methode5(siehe z.B. [3]), bei der alle Kopien

synchron aktualisert werden m¨

ussen (write all). Dadurch

wird der Vorteil des rein lokalen Lesens mit dem Verlust der

Schreibverf¨

ugbarkeit bei Knotenausf¨

allen/Partitionierungen

erkauft.

Weitergehende Ans¨

atze versuchen diese schlechte

Schreibverf¨

ugbarkeit im Fehlerfall zu verbessern, indem sie

beim Schreiben nur die erreichbaren Kopien aktualisieren

([3, 16, 17], siehe Abschnitt 3.1.2) oder bei Nicht-Verf¨

ugbar-

keit einzelner Kopien auf ein anderes Replikationsverfahren

umschalten [15].

Neben der Verf¨

ugbarkeit kann auch der Durchsatz des

ROWA-Ansatzes verbessert werden, indem man die Lage

und die Anzahl der Kopien dynamisch dem Zugriffsverhal-

ten (Schreib/Leseoperationen pro Zeitraum) anpaßt [23].

Als Repr¨

asentant dieser Klasse von Verfahren wird in

Abschnitt 3.1.2 das Available-Copies-Verfahren n¨

aher be-

schrieben.

Der Einsatz Read-One-Copy-basierter Verfahren eignet

sich immer dann, wenn der Anteil an Lesetransaktionen

hoch und Fehlerf¨

alle selten sind, da die f¨

ur die Realisierung

des ”1-Kopien-Lesens“ zus¨

atzlichen Verwaltungsinformatio-

nen bei jedem Fehlerfall durch aufwendige Rekonfigurati-

onsalgorithmen aktualisiert werden m¨

ussen (siehe Abschnitt

3.1.2).

2.2.2 Semantische Kopien-Update-Strategien

Bei den bisher beschriebenen (syntaktischen) Kopien-

Update-Strategien m¨

ussen entweder mehrere Kopien (Ab-

stimmungs- und Read-One-Copy-basierte Verfahren) oder

die im allgemeinen entfernte ausgezeichnete Datenkopie (ab-

solutistische Ans¨

atze) synchron aktualisiert werden. Besitzt

das Replikationsverfahren jedoch semantische Kenntnisse

uber die durchzuf¨

uhrende Update-Operation (z.B. Operatio-

nen sind kommutativ), so kann im Idealfall eine Update-

Strategie gew¨

ahlt werden, bei der nur die jeweils lokale

Kopie mit dem Transaktions-Commit aktualisiert werden

muß. Das semantische Wissen kann damit die sonst not-

wendige kopien¨

ubergreifende Synchronisation (Punkt 1 in

Abschnitt 2.2) ersetzen. In Abschnitt 3.2.2 wird eine se-

mantische Update-Strategie vorgestellt, bei der es aufgrund

der Kenntnis ¨

uber die Kommutativit¨

at von Transaktionen

gen¨

ugt, die lokale Kopie synchron zu aktualisieren.

Neben der schon erw¨

ahnten begrenzten Einsatzf¨

ahig-

keit semantischer Verfahren kann, wegen der großen Anzahl

asynchroner Updates, das Lesen eines konsistenten Daten-

bankzustands erschwert oder sogar unm¨

oglich werden (siehe

Abschnitt 3.2.2).

Abbildung 2 zeigt als Zusammenfassung f¨

ur die jewei-

lige Update-Strategie die Zahl und Lage der synchron zu

aktualisierenden Kopien und ordnet die in Abschnitt 3 kon-

kreter beschriebenen Replikationsverfahren entsprechend der

hier erarbeiteten Klassifikationskriterien ein.

5Read-One-Write-All

basierte Verfahren

Read-One-Copy-

ROWA

Available-

Copies

dynamic

Voting

dynamisches

Quorum Quorum

statisches

Tree-Quorum

dynamisches

Quorum

Tree-Quorum

Reconfigurable

Quorum

statisches

Majority-

Consensus

Verfahren

semantischeabsolutistische

Verfahren

Copy

Primary mc-

Kompatibilität

Kopien-Update-Strategien

(möglichst) alle Kopien ausgewählte Kopien

Kopienquorum lokale Kopie

Abstimmungsverfahren

strukturiertes Quorumunstrukturiertes Quorum

ausgezeichnete Kopie

semantischsyntaktisch

Korrektheitsbegriff

Abbildung 2. Die Kopien-Update-Strategien im ¨

Uberblick: Die Abbildung

zeigt die Zahl der synchron zu aktualisierenden Kopien, die Kriterien zur

Klassifikation der verschiedenen Replikationsmethoden sowie die Einord-

nung konkreter Replikationsverfahren, die im Rahmen dieses Artikels n¨

aher

beschrieben werden. Außerdem wird das jeweilige Korrektheitskriterium

angegeben, auf dem die Verfahrensklasse basiert

2.3 Behandlung von Netzpartitionierungen:

Optimistische vs. pessimistische Verfahren

Die Gew¨

ahrleistung bzw. Erh¨

ohung der Verf¨

ugbarkeit im

Fehlerfall ist ein wichtiger Grund f¨

ur den Einsatz von Ko-

pien. Deshalb sollte ein Zugriff sowohl bei Knotenausf¨

allen

als auch bei Partitionierungen weiterhin m¨

oglich sein, oh-

ne dabei die Datenbankkonsistenz zu gef¨

ahrden. Knoten-

ausf¨

alle stellen dabei den weit einfacheren Fehlerfall dar, da

hier ein zeitweise ausgefallener Rechnerknoten durch einfa-

ches ”Nachziehen“ der in der Zwischenzeit stattgefundenen

Updates reintegriert werden kann. Lassen sich deshalb z.B.

aufgrund der Netztopologie Partitionierungen ausschließen

[29], so k¨

onnen auch einfachere Replikationsverfahren ein-

gesetzt werden, welche die Datenkonsistenz nur bei Rech-

nerausf¨

allen garantieren. Diese Voraussetzung trifft jedoch

in den meisten F¨

allen nicht zu. Die ¨

uberwiegende Mehrheit

der Replikationsverfahren ist deshalb so konzipiert, daß sie

auch Netzpartitionierungen tolerieren k¨

onnen. Die dazu in

der Literatur zu findenden Vorschl¨

age gehen von einer der

beiden folgenden Annahmen aus:

Optimistische Verfahren [13, 6, 18] gehen von der An-

nahme aus, daß Inkonsistenzen nur selten auftreten und

daß diese bei Aufhebung der Partitionierung erkannt und

aufgel¨

ost werden k¨

onnen. Deshalb besteht nicht die Not-

wendigkeit, im Partitionierungsfall den Datenzugriff einzu-

schr¨

anken. Optimistische Ans¨

atze unterscheiden sich unter-

einander haupts¨

achlich in der Art und Weise, wie die auf-

getretenen Inkonsistenzen behoben werden. Als Beispiel f¨

ein optimistisches Verfahren wird in Kapitel 3.2.1 das Prin-

zip des Data-Patch-Verfahrens n¨

aher beschreiben, bei dem

208

dynamic

Voting Tree-

Quorum Tree-Quorum

Reconfigurable Primary

Copy

mc-

Kompatibilität Data-

Patches

Abstimmungsverfahren absolutistische Verfahrenabsolutistische Verfahren

optimistischpessimistisch

syntaktisch semantisch

Korrektheitsbegriff

Majority-

Consensus

Behandlung von Netzpartitionierungen

Abbildung 3. Behandlungvon Netzpartitionierungenim ¨

Uberblick: Die Ab-

bildung zeigt die verschiedenen Prinzipien zur Behandlung von Netzpar-

titionen. Dabei wurden die in Abbildung 2 schon verwendeten Klassifika-

tionskriterien sowie die konkreten Verfahren wieder aufgegriffen und ent-

sprechend eingeordnet

schon beim Datenbankentwurf Regeln zur Konfliktaufl¨

osung

definiert werden.

Pessimistische Verfahren [30, 29, 16, 20, 1, 26, 22] ge-

hen von einer worst-case-Annahme aus: Falls es in den Par-

titionen zu Inkonsistenzen kommen kann, dann treten die-

se auch ein. Deshalb ist es besser, die Verf¨

ugbarkeit der

Daten im Partitionierunsfall zugunsten ihrer Konsistenz ein-

zuschr¨

anken. Ungehindertes Arbeiten mit einem Objekt ist

damit immer nur in einer Partition m¨

oglich, w¨

ahrend in den

anderen Partitionen allenfalls ein lesender Zugriff erlaubt

wird. Pessimistische Verfahren unterscheiden sich unterein-

ander haupts¨

achlich darin, wann und wie die Einschr¨

ankung

erfolgt. Das Zusammenf¨

ugen von Partitionen bei der Rein-

tegration ist dadurch nat¨

urlich problemlos m¨

oglich, da die

Anderungen nur in jeweils einer Partition erlaubt waren.

Diese m¨

ussen dann in den anderen Partitionen nachgezogen

werden.

Abbildung 3 beschreibt die Strategien der verschiedenen

(Klassen von) Replikationsverfahren im Partitionierungsfall.

3 Ausgew¨

ahlte Verfahren

Einige der zuvor allgemein beschriebenen Prinzipien der Re-

plikationskontrolle sollen nun anhand ausgew¨

ahlter Verfah-

ren exemplarisch veranschaulicht werden. Aus Platzgr¨

unden

konzentrieren wir uns hier jedoch in der Regel auf bestimm-

te Teilaspekte des jeweiligen Verfahrens. Eine detailliertere

und umfangreichere Beschreibung verschiedener Replikati-

onsmethoden ist in [5] zu finden.

3.1 Syntaktische Verfahren

3.1.1 Abstimmungsverfahren

In Kapitel 2 wurden f¨

ur die Abstimmungsverfahren zwei

orthogonale Kriterien (unstrukturiert/strukturiert bzw. sta-

tisch/dynamisch) beschrieben, mit denen sich die verschiede-

nen Verfahren in vier Bereiche einteilen lassen (siehe Abbil-

dung 2). Abgesehen vom Bereich der unstrukturierten, stati-

schen Abstimmungsverfahren, deren Grundprinzip bereits in

Abschnitt 2.2.1 vorgestellt wurde, wird nun aus jedem dieser

Bereiche ein Verfahren detaillierter beschrieben.

3.1.1.1 Die Dynamic-Voting-Methode: ein unstrukturiertes,

dynamisches Verfahren. Fortgesetzte und eventuell langdau-

ernde Partitionierungen f¨

uhren dazu, daß eine immer gr¨

oßere

Zahl an Knoten nicht erreichbar ist (und damit ihre potenti-

elle Zustimmung wegf¨

allt), wodurch die Bildung eines Quo-

rums erschwert oder sogar unm¨

oglich wird.

Beispiel 1: Probleme bei der Quorumsbildung mit dem

Majority-Consensus-Verfahren

Zerf¨

allt ein nach dem Majority-Consensus-Verfahren [33]

arbeitendes Datenbanksystem mit Replikationsgrad 20

zun¨

achst in zwei Partitionen mit 9 bzw. 11 Knoten und

anschließend die ”11er-Partition“ weiter in 5 und 6 Kno-

ten, so kann in keiner der drei resultierenden Partitionen die

f¨

ur das Quorum notwendige Stimmenanzahl mehr erreicht

werden.

Der Grund daf¨

ur ist, daß die Gr¨

oße eines Quorums

statisch durch die urspr¨

ungliche Gesamtzahl der Stimmen

festgelegt wird und deshalb nicht an die jeweils aktuell

verf¨

ugbare Zahl der Knoten angepaßt werden kann.

Einen flexibleren Ansatz in diesem Zusammenhang bie-

tet das Dynamic-Voting-Verfahren [24]6, bei dem die Ge-

samtzahl der stimmberechtigten Knoten bei jeder Abstim-

mung neu festgelegt wird: Nur die Knoten, die bei der letzten

Anderung teilgenommen haben, besitzen bei der n¨

achsten

Abstimmung Stimmrecht.

Beispiel 2: Quorumsanpassung beim Dynamic-Voting-Ver-

fahren

Haben in Beispiel 1 vor der ersten Partitionierung 11

Kopien einem Update zugestimmt, so sind nur noch diese 11

Kopien stimmberechtigt, d.h. bei weiteren Updates m¨

ussen

nur noch 11 ÷2 + 1 = 6 Kopien zustimmen. Dadurch kann

im Gegensatz zum statischen Majority-Consensus-Verfahren

die ben¨

otigte Stimmenanzahl auch noch nach der zweiten

Partitionierung erreicht werden.

Das Beispiel zeigt allerdings auch ein Problem auf.

Durch fortlaufende Partitionierungen der Mehrheitspartition7

sind immer weniger Knoten stimmberechtigt. Im Extremfall

kann dies zu einer ”2-Kopien-Mehrheitspartition“ f¨

uhren.

Kommt es zu einer Reintegration der restlichen 18 Kopien,

so ist mit diesen kein Arbeiten m¨

oglich, da sie solange kein

Stimmrecht mehr besitzen, bis sie an einer ¨

Anderung mit

den letzten beiden stimmberechtigten Kopien teilgenommen

haben [24, 7]. Diese Reduzierung der Verf¨

ugbarkeit kann

gem¨

aß des Vorschlags von Tang [32] dadurch begrenzt wer-

den, daß man eine untere Grenze f¨

ur die minimale Zahl der

Stimmberechtigten festlegt.

3.1.1.2 Das Tree-Quorum-Verfahren: ein strukturiertes, sta-

tisches Verfahren. Ein hoher Replikationsgrad f¨

uhrt bei einer

Quorumsbestimmung zu großem Kommunikationsaufwand.

Beispielsweise m¨

ussen bei 100 Kopien mindestens 51 Ko-

pien befragt werden, um mit dem Majority-Consensus-

Verfahren ein Quorum zu erhalten. Ordnet man dagegen die

Kopien ¨

uber eine logische Baumstruktur an [25, 1, 9] und

sammelt man die f¨

ur das (strukturierte) Quorum notwendi-

6Ein sehr ¨

ahnlicher Ansatz wurde von [12] vorgeschlagen

7Mit Mehrheitspartition wird die Partition bezeichnet, in der Updates

m¨

oglich sind

209

gen Stimmen entlang dieser Struktur, so m¨

ussen bedeutend

weniger Knoten angefragt werden (siehe Beispiel 3).

Die logische Baumstruktur wird ¨

uber zwei Parameter be-

schrieben: die H¨

ohe hund den Verzweigungsgrad d. Zur Ver-

einfachung der Darstellung wird von vollst¨

andigen B¨

aumen

ausgegangen. In [1] werden die erforderlichen Modifikatio-

nen f¨

ur unvollst¨

andige B¨

aume diskutiert.

Der von [1] vorgeschlagene (depth-first)-Algorithmus

konstruiert ein Quorum der Dimension hl, si, indem er bei

der Wurzel beginnt und in jeder Ebene des Baumes sbe-

liebige Knoten s0zur Stimmabgabe auffordert. Kommt ein

Knoten aus s0nicht innerhalb eines bestimmten Zeitraums

(timeout) der Abstimmungsaufforderung nach, so werden

stattdessen sseiner Kinder zur Stimmabgabe aufgefordert.

Das Quorum hl, sikonnte erfolgreich gebildet werden, wenn

auf insgesamt lEbenen jeweils sKnoten zugestimmt haben.

Beispiel 3: minimales Quorum der Dimension h2,2i

5 7 8 10 11 136 9 12

Ein Quorum der Dimension h2,2ikann im Beispiel 3 im

optimalen Fall durch die Wurzel 1 und zwei ihrer Kinder,

z.B. 2,3, gebildet werden (schraffierte Knoten). Ist Knoten

2 nicht erreichbar, so kann seine Stimme durch die Stim-

men zweier seiner Kinder, also z.B. 5 und 6, ersetzt wer-

den. Die meisten Knoten m¨

ussen befragt werden, wenn die

Wurzel nicht verf¨

ugbar ist. Dann ben¨

otigt man stattdessen

zwei Stimmen ihrer Kinder (z.B. 3 und 4) sowie noch je-

weils zwei von deren Kindern (z.B. 8,9 und 11,13), um das

notwendige Quorum zu erhalten.

F¨

ur die Einhaltung der 1-Kopie-Serialisierbarkeit m¨

ussen

die ¨

Uberschneidungsregeln aus Abschnitt 2.2.1 f¨

ur beide Di-

mensionen gelten:8

•Schreib/Schreib- ¨

Uberschneidungsregel:

2∗QW.l > h und 2 ∗QW.s>d

•Schreib/Lese- ¨

Uberschneidungsregel:

QW.l +QR.l > h und QR.s +QW.s>d

Das Quorum h2,2iaus Beispiel 3 erf¨

ullt diese Bedin-

gungen.

Im Vergleich zu unstrukturierten Abstimmungsverfahren

m¨

ussen weniger Kopien zur Stimmabgabe aufgefordert wer-

den (Gr¨

oßenordnung logNanstatt N÷2 beim Majority-

Tree-Verfahren), ohne daß die Verf¨

ugbarkeit stark reduziert

wird [1].

Neben der im Beispiel verwendeten Mehrheitsvertei-

lung im jeweiligen Quorum (Majority-Tree-Verfahren) wer-

den auch andere Verteilungen vorgeschlagen. Beispielswei-

se gen¨

ugt im fehlerfreien Fall beim Read-Root-Verfahren

(QR=h1,d÷2+1i,QW=hh, d÷2+1i) zum Lesen die Zu-

stimmung der Wurzel, w¨

ahrend zum Schreiben in jeder Ebe-

ne des Baumes jeweils eine Mehrheit der Kopien zustimmen

muß [1]. Ein Lesezugriff ist damit ¨

ahnlich g¨

unstig wie beim

ROWA-Protokoll. Die Schreibverf¨

ugbarkeit ist dabei jedoch

8bei jeweils 1 Stimme pro Knoten

mit dem Majority-Consensus-Verfahren vergleichbar [1]. Sie

h¨

angt allerdings v¨

ollig von der Verf¨

ugbarkeit der Wurzel ab.

Zur Abschw¨

achung dieser Abh¨

angigkeit von der Verf¨

ugbar-

keit der Wurzel wird in [9] vorgeschlagen, die Wurzel auf-

zusplitten: Aus einem Baum wird dann ein ”Wald“ von B¨

au-

men. Zum Lesen und zum Schreiben muß dann jeweils die

Mehrheit der Wurzeln bzw. deren Kinder zustimmen.

3.1.1.3 Das Tree-Quorum-Verfahren mit rekonfigurierbarer

Baumstruktur: ein strukturiertes, dynamisches Verfahren. Die

im vorherigen Abschnitt skizzierten Vorschl¨

age zur Verbes-

serung der Schreibverf¨

ugbarkeit beim Read-Root-Verfahren

verteuern unn¨

otigerweise den Lesezugriff im fehlerfreien

Fall. In [2] wird ein anderer Weg vorgeschlagen, der oh-

ne Erh¨

ohung der Lesekosten die Schreibverf¨

ugbarkeit ver-

bessert: Rekonfiguration. Ist aufgrund von Fehlern die Bil-

dung eines Schreibquorums in der gegenw¨

artigen logischen

Struktur nicht mehr m¨

oglich, so wird diese so ”umgebaut“

(rekonfiguriert), daß in der neuen Struktur ein Schreibquo-

rum wieder erreicht werden kann.

Zur Durchf¨

uhrung dieser Rekonfiguration muß ein (leich-

ter erreichbares) Rekonfigurationsquorum gesammelt wer-

den, das zur Konsistenzerhaltung die folgenden ¨

Uberschnei-

dungsregeln einhalten muß:

1. Rekonfiguration/Schreib- ¨

Uberschneidungsregel:

Damit in der rekonfigurierten Struktur auch ein Knoten

mit aktueller Kopie enthalten ist, muß sich ein Rekon-

figurationsquorum mit dem Schreibquorum ¨

uberschnei-

den.

2. Rekonfiguration/Rekonfiguration- ¨

Uberschneidungsregel:

Diese Regel stellt sicher, daß zu jedem Zeitpunkt nur

eine logische Struktur g¨

ultig ist.

Die Quorumsverteilung des fehlertoleranten Majority-

Tree-Verfahrens (Qreconfig =hh÷2+1,d÷2+1i, Abschnitt

3.1.1.2) erf¨

ullt beispielsweise diese ¨

Uberschneidungsregeln

f¨

ur das Read-Root-Verfahren.

Sind Fehler relativ selten, so kann damit ein leseop-

timiertes Verfahren beibehalten und trotzdem die Schreib-

verf¨

ugbarkeit verbessert werden. Bei h¨

oherer Fehlerwahr-

scheinlichkeit sind jedoch die Kosten f¨

ur die h¨

aufige Re-

konfiguration h¨

oher als ein Verfahren, das auch im fehler-

freien Fall mit einem nur ”suboptimalen“ Lesequorum (z.B.

Qr=h2,d÷2+1i,Q

w=hh−1,d÷2+1i) arbeitet.

Die Idee der Rekonfiguration zur Erh¨

ohung der Schreib-

verf¨

ugbarkeit wurde von den Autoren auch f¨

ur logische Git-

terstrukturen angewandt [2].

3.1.2 Die Available-Copies-Methode: ein

Read-One-Copy-basiertes Verfahren

Das Verfahren von Bernstein und Goodman [3] verbessert

die Schreibverf¨

ugbarkeit des ROWA-Ansatzes im Fehler-

fall, indem bei einer ¨

Anderungsoperation statt aller nur die

verf¨

ugbaren Kopien synchron aktualisiert werden m¨

ussen

(Read-One-Write-All-Available). Welche Kopien verf¨

ugbar

sind, wird in replizierten Verzeichnissen (directories) gespei-

chert. Vor jedem Lese/Schreibzugriff wird das lokale Ver-

zeichnis konsultiert, um die gegenw¨

artig verf¨

ugbaren Kopien

210

zu erhalten. Zum Lesen wird dann auf eine dieser verf¨

ugba-

ren Kopien zugegriffen. Beim Schreiben werden nur die

laut Verzeichnis verf¨

ugbaren Kopien aktualisiert. Sind die

Informationen in den Verzeichnissen aktuell, so kann da-

mit das Schreiben nicht blockieren. Stellt sich z.B. durch

das Mißlingen einer ¨

Anderungsoperation heraus, daß die in

den Verzeichnissen gehaltenen Informationen nicht mehr der

gegenw¨

artigen Verf¨

ugbarkeitssituation entsprechen, so wer-

den diese dynamisch ¨

uber Systemtransaktionen (status trans-

actions) angepaßt. Die Aktualisierung der replizierten Ver-

zeichnisse ist jedoch aufwendig, so daß das Verfahren nur

geeignet ist, wenn Knotenausf¨

alle selten sind [3, 29].

In dieser Grundform toleriert dieser Ansatz nur Knoten-

ausf¨

alle (vgl. Abschnitt 2.3). Zur Tolerierung von Netzparti-

tionierunen sind weitere Restriktionen notwendig. Ein inter-

essanter Vorschlag hierzu wurde von [16] mit dem Virtual-

Partition-Protokoll gemacht. Hier wird der Zugriff eines

Knotens nur dann erlaubt, wenn in seinem Verzeichnis eine

Mehrheit aller Knoten enthalten ist. F¨

ur eine korrekte Ar-

beitsweise m¨

ussen dazu jedoch alle Kopien einer Partiti-

on identische Verzeichniseintr¨

age besitzen. Daf¨

ur m¨

ussen

Anderungen im Verzeichnis ¨

uber ein aufwendiges Protokoll

[16, 5] ausgetauscht werden.

3.2 Semantische Verfahren

Die in diesem Kapitel beschriebenen Verfahren n¨

utzen se-

mantisches Wissen aus, um die in Kapitel 2 angesprochenen

Punkte bzgl. Datenkonsistenz, Kopien-Update-Verhalten und

Fehlerbehandlung realisieren zu k¨

onnen.

3.2.1 Das Data-Patch-Verfahren:

ein optimistisches Verfahren

Das Aufgabengebiet des Data-Patch-Verfahrens [18] be-

schr¨

ankt sich auf die Wiederherstellung eines konsistenten

Datenbankzustands nach Partitionierungen (Punkt 3). Da-

zu werden beim Entwurf der Datenbank f¨

ur jede Relation

zwei Regeln spezifiziert, wie aus den unterschiedlichen Ko-

pienwerten ein neuer einheitlicher, konsistenter Wert erzeugt

wird: Im folgenden wird zur einfacheren Beschreibung von

zwei Partitionen, P1und P2, ausgegangen.

Tupel-Einf¨

ugungsregel: Eine dieser Regeln wird angewandt,

wenn ein Tupel in nur einer Partition eingef¨

ugt wurde.

Keep-Regel: Wenn ein Tupel in nur einer Partition ein-

gef¨

ugt wurde, f¨

uge es auch in der anderen Partition ein.

Remove-Regel: Wenn ein Tupel in nur einer Partition

gefunden wurde, dann l¨

osche es wieder.

Program-Regel: Beauftrage das angegebene Programm

mit der Konfliktaufl¨

osung.

Notify-Regel: Benachrichtige den Datenbankadministra-

tor. Dieser muß den Konflikt dann manuell aufl¨

osen.

Tupel-Integrationsregel: Eine dieser Regeln wird verwendet,

wenn ein Tupel mit gleichen Schl¨

ussel sowohl in der Parti-

tion P1als auch in der Partition P2eingef¨

ugt oder ver¨

andert

wurde.

Latest-Regel: Das zuletzt eingef¨

ugte Tupel ist das g¨

ulti-

ge.

Primary-Regel: Das Tupel auf dem Knoten kist das kor-

rekte.

Arithmetic-Regel: Der Tupelwert berechnet sich nach

der folgenden Formel: neuer W ert =Wert(P

1)+

Wert(P

2)−alter W ert.

Program-Regel, Notify-Regel: siehe oben

Dabei ist es nat¨

urlich f¨

ur die Anwendung der Tupel-Integra-

tionsregel notwendig, daß jedes neu eingef¨

ugte Tupel auch

w¨

ahrend einer Partitionierung immer einen eindeutigen und

unver¨

anderbaren Schl¨

ussel erh¨

alt.

Beispiel 4: Konto-Relation bei einer Bank

Die Schemadefinition bei der Konto-Relation einer Bank

besteht vereinfachend aus:

Konto# Kunden- Konto- Einf.- Integ.-

Name stand regel regel

Key String Real Keep Arithmetic

Wird bei einer Partitionierung in irgendeiner Kopie ein

neues Tupel (= neues Konto) eingef¨

ugt, so wird dieses

Tupel aufgrund der Keep-Regel auch in den anderen Ko-

pien erg¨

anzt. Wird dagegen ein Tupel in mehreren Ko-

pien ver¨

andert, so erfolgt die Konfliktaufl¨

osung mittels der

Arithmetic-Regel.

Der Zustand, in dem sich die Datenbank nach Anwen-

dung aller Regeln befindet, ist im allgemeinen nicht mit dem

serialisierbaren Zustand identisch, der erreicht worden w¨

are,

wenn die Partitionierung nicht stattgefunden h¨

atte. Da sich

Daten¨

anderungen h¨

aufig auch außerhalb der Datenbank aus-

wirken (siehe folgendes Beispiel einer Geldauszahlung an

einen Bankkunden), ist das Erreichen dieses serialisierbaren

Datenbankzustands nicht von allergr¨

oßter Wichtigkeit.

Beispiel 5: Transaktion mit Integrit¨

atsbedingung

D¨

urfen Kunden ihr Konto nicht ¨

uberziehen, so wird eine

Auszahlungstransaktion ¨

uber eine Integrit¨

atsbedingung den

auszuzahlenden Betrag mit dem momentanen Kontostand

vergleichen und bei einer Konto¨

uberziehung die Auszahlung

ablehnen. Wird in zwei verschiedenen Partitionen jeweils das

gesamte Guthaben abgehoben, so f¨

uhrt dies aufgrund fehlen-

der Informationen aus der anderen Partition zu einem nega-

tiven Kontostand und somit zur Verletzung der Integrit¨

ats-

bedingung. Die Wiederherstellung der Integrit¨

atsbedingung

(Kontostand ≥0DM) und damit eines serialisierbaren Da-

tenbankzustands entspricht aber nicht mehr der Realit¨

at, da

tats¨

achlich zweimal das gesamte Guthaben ausgezahlt wur-

de.

3.2.2 Die Multi-Copy-Kompatibilit¨

Wie in Abschnitt 2 erw¨

ahnt, kann durch Einbeziehung von

Anwendungssemantik der Durchsatz und die Verf¨

ugbarkeit

erh¨

oht werden. Ein gutes Beispiel daf¨

ur ist die von Kumar

und Stonebraker [26] vorgeschlagene Methode der Multi-

Copy-Kompatibilit¨

at (mc-Kompatibilit¨

at, mc-compatibility),

bei der die Kommutativit¨

at einzelner Transaktionen aus-

gen¨

utzt wird. Kommutative Transaktionen erm¨

oglichen es,

Updates in unterschiedlicher Reihenfolge auf den einzel-

nen Kopien durchzuf¨

uhren, ohne die Datenbankkonsistenz

zu gef¨

ahrden.

Da jedoch die wenigsten Anwendungen aus nur kom-

mutativen Transaktionen bestehen, werden bei diesem Ver-

211

fahren9die Transaktionen in eine kommutative (C-TA) und

eine nicht-kommutative (NC-TA) Klasse eingeteilt. Bei einer

Bankanwendung sind z.B. Ein- bzw. Auszahlungstransak-

tionen TEA(k, ea)=k+ea kommutativ, Zinsberechnungs-

transaktionen TZ(k, p)=k+pk dagegen nicht.

F¨

ur jede Klasse von Transaktionen wird nun eine eigene

Update-Strategie angewandt:

Aufgrund ihrer Kommutativit¨

at kann bei den C-TAs eine

rein lokale Update-Strategie realisiert werden, bei der oh-

ne kopien¨

ubergreifenden Synchronisation nur die lokale Ko-

pie synchron aktualisiert werden muß. Die restlichen Kopien

werden asynchron ¨

uber ein Spoolprogramm [26] aktualisiert.

F¨

ur NC-TAs muß dagegen ein restriktiveres Abstim-

mungsverfahren zum Kopien-Update eingesetzt werden, d.h.

es m¨

ussen alle Kopien im Schreibquorum synchron aktuali-

siert werden. Um wenigstens das Update der restlichen Ko-

pien asynchron und konsistent durchf¨

uhren zu k¨

onnen, muß

die NC-TA durch eine zur ihr ”¨

aquivalente“ C-TA ersetzt

werden. Beispielsweise kann die obige Zinsberechnungs-

transaktion TZnach Berechnung des Zinses Z=pk durch

die ¨

aquivalente Transaktion TEA(k, Z)=k+Zersetzt wer-

den. Diese C-TA nennt man dann mc-kompatibel zu der ent-

sprechenden NC-TA.

Durch Ausnutzung der Kommutativit¨

at kann also im Ver-

gleich zu einem rein syntaktischen Replikationsverfahren ein

h¨

oherer Transaktionsdurchsatz erzielt werden. Da außerdem

die Update-Reihenfolge von kommutativen Transaktionen

unerheblich ist, sind auch w¨

ahrend Partitionierungen Up-

dates in allen Partitionen m¨

oglich. Diese optimistische Par-

titionierungsbehandlung erh¨

oht damit auch die Verf¨

ugbar-

keit. Der Durchsatz- und Verf¨

ugbarkeitsgewinn ist nat¨

urlich

abh¨

angig vom Anteil der kommutativen Transaktionen am

Gesamtvolumen der Transaktionen.

Das Verfahren besitzt jedoch auch einen schwerwiegen-

den Nachteil, der bei vielen Anwendungen einen Praxis-

einsatz fraglich erscheinen l¨

aßt: Aufgrund der asynchronen

und verteilten Ausf¨

uhrung der C-TAs ist im laufenden Be-

trieb nie sichergestellt, daß eine Kopie tats¨

achlich alle Up-

dates und damit einen aktuellen Datenbankzustand wider-

spiegelt. Damit ist auch nicht sicher, daß das Quorum einer

NC-TA eine Kopie enth¨

alt, die den aktuellen Objektwert be-

sitzt. Es kann deshalb beispielsweise vorkommen, daß die

Einzahlung (C-TA) eines Kunden bei einer wenig sp¨

ater

stattfindenden Zinsberechnung (NC-TA) noch nicht ber¨

uck-

sichtigt wird. Die hieraus resultierenden Inkonsistenzen wer-

den wohl nur f¨

ur wenige Anwendungen tolerierbar sein.

4 Abschließende Bemerkungen

Erst durch die Replikation von Daten ist ein verteiltes Sy-

stem bzgl. der Verf¨

ugbarkeit einem zentralen System ¨

uber-

legen. Daneben profitiert meist auch der Datendurchsatz von

der Existenz von Kopien. Andererseits ben¨

otigen replizierte

Systeme zus¨

atzliche Synchronisationsmechanismen – reali-

siert durch sogenannte Replikationsverfahren – zur Sicher-

stellung der Datenkonsistenz.

In diesem Papier wurden zuerst die verschiedenen Punkte

diskutiert, die ein Replikationsverfahren zu realisieren hat.

9im Gegensatz zu vielen anderen ”kommutativen“ Replikationsverfahren

Anhand dieser Punkte wurden die verschiedenen prinzipi-

ellen L¨

osungsvorschl¨

age klassifiziert sowie ihre Vor- und

Nachteile kritisch beleuchtet. Anschließend erfolgte eine Be-

schreibung einiger der klassifizierten Verfahren.

Der inh¨

arente Zielkonflikt zwischen Verf¨

ugbarkeit/

Durchsatz einerseits sowie Datenkonsistenz andererseits wird

dabei von den verschiedenen Verfahren sehr unterschied-

lich gel¨

ost. Die Unterschiede basieren zum einen an dem

den einzelnen Verfahren zugrundeliegenden Korrektheitskri-

terium. Dieses kann rein syntaktisch definiert (z.B. 1-Kopie-

Serialisierbarkeit), unter Zuhilfenahme von semantischen

Wissen (z.B. Kommutativit¨

at) oder allein ¨

uber die Anwen-

dungssemantik bestimmt werden.

Da die Replikationsverfahren nicht alle in Kapitel 2 be-

schriebenen Aufgabenfelder abdecken, sind hier auch Kom-

binationen von Verfahren mit unterschiedlichen Korrekt-

heitsbegriffen denkbar. Beispielsweise kann die syntaktische

Available-Copies-Methode (siehe Abschnitt 3.1.2) mit dem

semantischen Data-Patch-Verfahren (siehe Abschnitt 3.2.1)

kombiniert werden, um damit auch Partitionierungen tole-

rieren zu k¨

onnen: Das Sperren aller verf¨

ugbaren Kopien

beim Schreiben garantiert dann innerhalb einer Partition

die 1-Kopie-Serialisierbarkeit. Die durch Partitionierungen

m¨

oglichen Inkonsistenzen werden dann auf der Basis der

semantischen Regeln des Data-Patch-Verfahrens aufgel¨

ost.

Damit wird dann ein anwendungssemantisch korrekter, aber

nicht notwendigerweise 1-Kopie-serialisierbarer Datenbank-

zustand erreicht.

Der Available-Copies-Ansatz zeigt auch, daß sich die Re-

plikationsverfahren bzgl. der unterst¨

utzten Fehlersemantiken

[11] unterscheiden. W¨

ahrend einige wenige Verfahren nur

Knotenausf¨

alle tolerieren, erhalten andere die Datenbank-

konsistenz auch im Falle von Partitionierungen.

Inzwischen bieten einige kommerzielle Datenbanksyste-

me Replikationsm¨

oglichkeiten an: Sybase Replication Ser-

ver [10], Oracle [31], Ingres Replicator, Adabas Entire SQL,

Informix, DB2. H¨

aufig basieren diese Verfahren auf dem

im Abschnitt 2.2.1.1 vorgestellten Primary-Copy-Prinzip,

da die Kopien in einer Master-Slave-Beziehung [28] zu-

einander stehen: Eine ¨

Anderung ist nur ¨

uber die Master-

Kopie m¨

oglich. Die meist asynchron ¨

uber Trigger aktuali-

sierten Slave-Kopien stehen nur f¨

ur einen Lesezugriff zur

Verf¨

ugung.

Ingres und Oracle bieten dagegen auch eine Peer-to-Peer

Replikationsmethode [28] an, bei der ¨

Anderungen ¨

uber jede

Kopie m¨

oglich sind. Da auch hier die ¨

Anderungspropagie-

rung asynchron ¨

uber Trigger erfolgt (optimistische Ans¨

atze)

sind Inkonsistenzen nicht ausgeschlossen, die dann ¨

uber vom

Anwender zu definierende Regeln aufgel¨

ost werden (vgl.

Abschnitt 3.2.1).

Ein kurzer ¨

Uberblick ¨

uber den derzeitigen Stand an kommer-

ziellen Systemen mit Replikationsm¨

oglichkeiten ist in [28]

zu finden.

Danksagung. Wir danken Daniela Beuter, Christian Heinlein sowie Manfred

Reichert f¨

ur ihre wertvollen Hinweise und Ratschl¨

age beim Entstehen dieser

Ausarbeitung. Außerdem geb¨

uhrt unser Dank den Gutachtern f¨

ur ihre sehr

hilfreichen Anregungen zur Verbesserung des Beitrags.

212

References

1. Agrawal, D., El Abbadi, A.: The generalized tree quorum protocol:

An efficient approach for managing replicated data. ACM Trans. on

Database Systems 17, 689–717 (1992)

2. Agrawal, D., El Abbadi, A.: Resilient logical structures for efficient

management of replicated data. In: Proc. 18th Int’l Conf. on Very

Large Data Bases (VLDB) pp. 151–162, Vancouver (1992)

3. Bernstein, P. A., Goodman, N.: An algorithm for concurrency con-

trol and recovery in replicated distributed databases. ACM Trans. on

Database Systems 9, 596–615 (1984)

4. Bernstein, P. A., Hadzilacos, V., Goodman, N.: Concurrency Control

and Recovery in Database Systems. New York: Addison-Wesley, 1987

5. Beuter, T., Dadam, P.: Prinzipien der Replikationskontrolle in ver-

teilten Systemen. Ulmer Informatik Berichte 95–11, Universit¨

at Ulm

(1995)

6. Blaustein, B. T., Kaufman, C. W.: Updating replicated data during

communications failures. In: Proc. 11th Int’l Conf. on Very Large

Data Bases (VLDB), pp. 49–58, Stockholm (1985)

7. Borghoff, U. M.: Fehlertoleranz in verteilten Dateisystemen: Eine

Ubersicht ¨

uber den heutigen Entwicklungsstand bei den Votierungs-

verfahren. GI Informatik Spektrum 14, 15–27, (1991)

8. Cheung, S. Y., Ahamad, M., Ammar, M. H.: Multi–dimensional vo-

ting: A general method for implementing sychronization in distributed

systems. In: Proc. 10th Int’l Conf. on Distributed Computing Systems,

pp. 362–369, Paris (1990)

9. Chung, S. M.: Enhanced tree quorum algorithm for replica control

in distributed database systems. Data & Knowledge Engineering 12,

63–81, (1994)

10. Colton, M.: Replicated data in a distributed environment. In: Proc.

ACM SIGMOD Int’l Conf. on Management of Data, pp. 464–466,

Washington, DC (1993)

11. Cristian, F.: Understanding fault-tolerant distributed systems. Com-

munications of the ACM 34, 56–78 (1991)

12. Davcev, D.: A dynamic voting scheme in distributed systems. IEEE

Trans. on Software Engineering 15, 93–97, (1989)

13. Davidson, S. B.: Optimism and consistency im partitioned distributed

database systems. ACM Trans. on Database Systems 9, 456–481 (1984)

14. Davidson, S. B., Garcia-Molina, H., Skeen, D.: Consistency in parti-

tioned networks. ACM Computing Surveys 17, 341–370 (1985)

15. Eager, D. L., Sevcik, K. C.: Achieving robustness in distributed data-

base systems. ACM Trans. on Database Systems 8, 354–381 (1983)

16. El Abbadi, A., Skeen, D., Cristian, F.: An efficient, fault–tolerant

protocol for replicated data management. In: Readings in Databa-

se Systems, Stonebraker, M. (ed.), pp. 259–273. San Mateo: Morgan

Kaufmann 1988

17. El Abbadi, A., Toueg, S.: Maintaining availability in partitioned re-

plicated databases. ACM Trans. on Database Systems 14, 264–290

(1989)

18. Garcia-Molina, H.: Data–patch: Integrating inconsistent copies of a

database after a partition. In: Proc. 3rd Symp. on Reliable Distributed

Systems, pp. 38–48, New York (1983)

19. Garcia-Molina, H., Barbar´

a, D.: How to assign votes in a distributed

system. Journal of the ACM 32, 841–860 (1985)

20. Gifford, D. K.: Weighted voting for replicated data. In: Proc. 7th

ACM Symp. on Operating Systems Principles (SIGOPS), pp. 150–159,

Pacific Grove, California (1979)

21. Gray, J., Reuter, A.: Transaction Processing: Concepts and Techniques.

San Mateo: Morgan Kaufmann 1993

22. Herlihy, M.: A quorum–consensus replication method for abstract data

types. ACM Trans. on Computer Systems 4, 32–53 (1986)

23. Huang, Y., Wolfson, O.: A competitive dynamic data replication al-

gorithm. In: Proc. 9th Int’l Conf. on Data Engineering, pp. 310–317,

Vienna, (1993)

24. Jajodia, S., Mutchler, D.: Dynamic voting algorithms for maintaining

the consistency of a replicated database. ACM Trans. on Database

Systems 15, 230–280 (1990)

25. Kumar, A.: Hierarchical quorum consensus: A new algorithm for ma-

naging replicated data. IEEE Trans. on Computers C-40, 996–1004

(1991)

26. Kumar, A., Stonebraker, M.: Semantics based transaction management

techniques for replicated data. In: Proc. ACM SIGMOD Int’l Conf. on

Management of Data, pp. 117–125, Chicago (1988)

27. Minoura, T., Wiederhold, G.: Resilient extended true–copy token sche-

ma for a distributed database system. IEEE Trans. on Software Engi-

neering SE–8, 173–188 (1982)

28. Ofer, U.: Was Sie schon immer ¨

uber Replication Server wissen wollten.

Datenbank Fokus 6, 31–36 (1994)

29. Paris, J.-F.: A highly available replication control protocol using vo-

latile witnesses. In: Proc. 14th Int’l Conf. on Distributed Computing

Systems, pp. 536–543, Pittsburgh, Pennsylvania (1994)

30. Stonebraker, M.: Concurrency control and consistency of multiple

copies of data in distributed INGRES. IEEE Trans. on Software Engi-

neering SE–5, 188–194 (1979)

31. St¨

urmer, G.: Oracle 7 A User’s and Developer’s Guide. Including

Release 7.1. London: Thomson 1995

32. Tang, J.: Voting class – an approach to achieving high availability for

replicated data. In: Proc. 2nd Int’l Conf. on Databases in Parallel and

Distributed Systems, pp. 146–156, Dublin, Ireland (1990)

33. Thomas, R. H.: A majority consensus approach to concurrency control

for multiple copy databases. ACM Trans. Database Systems 4, 180–

209 (1979)

Thomas Beuter seit Oktober 1992 wiss.

Mitarbeiter an der Universit¨

at Ulm, Ab-

teilung Datenbanken und Informations-

systeme. Diplom-Informatiker (Techni-

sche Universit¨

at M¨

unchen, 1992). Seit

1995 Mitarbeiter im Forschungsprojekt

Concurrent Engineering (in Kooperation

mit der Daimler–Benz–Forschung Ulm).

Aktuelle Arbeitsgebiete: Architekturen

f¨

ur Workflow–Management–Systeme,

Replikationsstrategien, erweiterte Trans-

aktionskonzepte

Peter Dadam seit 1990 Professor f¨

Informatik an der Universit¨

at Ulm

und Leiter der Abteilung Datenban-

ken und Informationssysteme. Diplom-

Wirtschaftsingenieur, Fachrichtung In-

formatik/Operations Research (Univer-

sit¨

at Karlsruhe,1978), wiss. Mitarbei-

ter an der Universit¨

at Dortmund und

der FernUniversit¨

at Hagen, Promotion

zum Dr. rer. nat. (FernUniversit¨

at Ha-

gen, 1982). Ab 1982 Mitarbeiter am

Wissenschaftlichen Zentrum der IBM

in Heidelberg, ab 1985 Leiter der Ab-

teilung Advanced Information Manage-

ment.

Aktuelle Arbeitsgebiete: Verteilte, ko-

operative Informationssysteme, Workflow–Management, Datenbanktech-

nologie f¨

ur und Datenbankanwendungen in medizinischen und tech-

nisch/wissenschaftlichen Anwendungsgebieten.

This article was processed by the author using the L

TEX style file gpljour2

from Springer-Verlag.