1 Agenten und verteilte Anwendungen Synchronisation und Konsistenzerhaltung in verteilten Anwendungen 13. März 2003

1

Agenten und verteilte Anwendungen

Synchronisation und Konsistenzerhaltung in verteilten Anwendungen

13. März 2003

2

Gliederung

• Grundlagen verteilter Anwendungen

• Einfache Verfahren zur

Nebenläufigkeitskontrolle

• Spezielle Verfahren zur


• Zusammenfassung


3

Grundlagen verteilter Anwendungen

• Definition von verteilten Anwendungen nach [BS2000, Seite 59]:

... application, whose functionality is split into a set of cooperating, interacting functional units...

... these functional units can be assigned to different machines...

... the functional units communicate with each other...


4

Aufbau von Verteilten Systemen


Verteiltes Rechensystem

Netzwerk Netzwerk

Verteiltes Ablaufsystem(Verwaltung der Systemobjekte auf die die Komponenten der Anwendung abgebildet werden) evtl. verteiltes BS

Verteilte AnwendungKomponente 1 Komponente n

...Komponente 2

5

Konsistenz (traditionell) (1)

• Aus Datenbanktechnik: Serialisierbarkeit als Korrektheitskriterium des Transaktionskonzeptes


Def.: Eine Transaktion ist eine Folge von Operationen, die die Datenbank von einem konsistenten Zustand in einen neuen Zustand überführen, wobei das ACID-Prinzip eingehalten werden muss.

• Atomicity

• Consistency

• Isolation

• Durability

6

Konsistenz (traditionell) (2)

• ABER:– Nicht alle Eigenschaften des Konsistenzkonzeptes

der Datenbanken bei verteilten Anwendungen erwünscht:

• Isolation der Benutzer• Hohe Verfügbarkeit eventuell wichtiger


7

Operationsgranularität

• Globale Daten (d.h. Daten mehrerer Komponenten)• Nebenläufige Zugriffe auf globale Daten führen

eventuell zu Inkonsistenz• Datei als globales Datum mögliche Zugriffseinheit

– Ganze Datei oder– Kapitel oder– Buchstabe usw.


• feine Granularität hoher Netzwerkverkehr

• grobe Granularität geringer Grad an Nebenläufigkeit

8

Konsistenz (erweitert)

• One-Copy-Serializable– Serialisierbarkeit im traditionellen Sinn bezüglich

eines Replikats– Zwei Operationen, die im Konflikt stehen, werden

auf allen Replikaten in der gleiche Reihenfolge ausgeführt.

• Mutual Consistency– alle Replikate eines Datums identisch oder – konvergieren zum gleichen Zustand


9

Nebenläufigkeitskontrolle (CC)

• Wichtig um Daten konsistent zu halten• Jedoch Erweiterung bei geographischer

Verteilung der Rechner:– Absturz einzelner Rechner Verfügbarkeit von

Daten– Ausfall von Kommunikationsverbindungen


Probleme bei verteilten Anwendungen, da häufig eine sehr hohe Verfügbarkeit gewünscht wird.

10

Partitionierung

schwer zu erkennenhöchstens in einer Partition darf

geschrieben werden


Partition 1 Partition 2

11

Gliederung


• Einfache Verfahren zur Nebenläufigkeitskontrolle (CC)



• Zusammenfassung


12

Klassifikation der Verfahren


optimistische pessimistische

zentrale Kontrolle dezentrale Kontrolle

13

Optimistische Verfahren

• Erlauben inkonsistente Zustände– Bei Datenbank: versucht alle Transaktionen nebenläufig

abzuhandeln. Bei Fehler wird Transaktion im Nachhinein abgebrochen

Je grober die Granularität, desto mehr KonflikteJe mehr Komponenten, desto mehr Konflikte

Konflikt kann bei verteilten Anwendungen nicht immer durch Anwendung behandelt werden (evtl. Benutzeraktion notwendig)


14

Pessimistische Verfahren

• Inkonsistente Datenbestände werden nicht geduldet

• Klassifikation:



Zentrale Kontrolle Dezentrale Kontrolle

Ausgezeichnete Kontrolleinheit

Token-Verfahren

15

Ausgezeichnete Kontrolleinheit

• Basiert auf Konzept der Zentralisierung• Eine Kontrolleinheit (KE) verantwortlich für alle

(Schreib-) zugriffe


DATEN

Nachteile:

• Keine weiteren Zugriffe bei Ausfall der KE.

• Bei Partitionierung auch Lesezugriffe nur in Partition mit KE.

16

Token-Verfahren (1)

• Verschiedene Rechner verantwortlich für Konsistenz

• Token wandert in virtuellem Ring zwischen den Rechnern umher

• Rechner mit Token verantwortlich


17

Token-Verfahren (2)

• Nachteile:– Schwierige Handhabe des Rechnerrings– Erweiterbarkeit des Rings– Ring muss dynamisch rekonfigurierbar sein (falls

Ausfall einzelner Rechner oder Partitionierung)– Verlust des Tokens (erkennen und beheben)

• Vorteil:– Höhere Verfügbarkeit als Verfahren mit

ausgezeichneter KE


18

mit dezentraler Kontrolle



Zentrale Kontrolle Dezentrale Kontrolle Ausgezeichnete Kontrolleinheit Token-Verfahren

ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahren

19

Einfache Sperrverfahren

• Anfordern und Setzen der Sperre kostet Zeit• Sperrgranularität hat entscheidenden Einfluss

auf den Grad an Nebenläufigkeit• Je nach Art des Systems (z.B: WYSIWIS)

muss geklärt werden, ab wann eine Sperre zu setzen ist

• Zwei Alternativen:– Tickle lock– Probabilistic lock


20

Tickle lock

Nachteil:• Absturz des Rechners der die Sperre besitzt

gesperrter Teil bleibt bis zu Neustart des Rechners gesperrt


• Sperre nur so lange wie benötigt

• Sobald Benutzer nichts mehr tut, wird Sperre automatisch frei gegeben

21

Probabilistic lock

• Sperre mit automatischem Time-out• Ist das Setzen bis zu einem Time-out nicht

möglich Benutzer muss entscheiden(Inkonsistenzen werden in Kauf genommen)

• gesetzte Sperre bleibt für feste Zeitspanne gesetzt


Nachteil:

Zeitweise nicht Einhalten der Konsistenz, aufgrund von Kommunikationsverzögerungen.

22

Floor-Passing-Verfahren

• Verfahren mit wechselnder Kontrolle• Sperrmechanismen werden nicht benötigta) explizites:

Kontrolle wird aktiv vom Benutzer weitergegeben

b) implizites:Vergabe der Kontrolle durch Koordinator


Vorteil: keine Benachteiligung von Komponenten

Nachteil: Ausfall des Koordinators

Nachteile: Benachteiligung anderer Komponenten

Ausfall der Einheit mit Kontrolle

23

Transformationsverfahren (1)

• Von Vorteil bei CSCW-Systemen mit WYSIWIS Eigenschaft

• Basiert auf Transformation von Operationen

• Implementationbeispiel:GROVE-Algorithmus (Group outline viewing editor): siehe [BS2000, Seite 202ff]


24


• Problemstellung:


t t

„abcd“

„abxcd“

„abcd“

„abcyd“

„abxcyd“„abxycd“

O1=insert(x,3) O2=insert(y,4)

Ohne Anpassung der Operationen hängt das Ergebnis von der Reihenfolge der Operationsausführung ab.

Benutzer 1 Benutzer 2

25


• Operationstransformation, so dass:O`1° O2 = O`2 ° O1

• man benötigt:– Prioritäten von Operationen

(pi = Priorität von Aktion i)– Transformationsmatrix T


(insert(xi, Posi), insert(xj, Posj),pi,pj)

(delete(Posi), insert(xj,Posj),pi,pj)

(insert(xi,Posi), delete(Posj),pi,pj)

(delete(Posi), delete(Posj),pi, pj)

26


• Implementierung der Konfliktpaare von TT11: if (Posi<Posj) then Oì := insert(xi,Posi);

elsif (Posi>Posj) then Oì := insert(xi,Posi+1);

elsif (xi = xj) then Oì := no-op; elsif (pi > pj) then Oì := insert(xi,Posi+1);

else O‘i := insert(xi,Posi);

T12: usw.


Seien wieder O1=insert(x,3) und O2=insert(y,4). Index als Priorität.

O`1 = insert(x,3) bzw. O`2 = insert(y,5)

O`1° O2 („abcd“) = „abxcyd“ = O`2 ° O1(„abcd“)

27

Gliederung






• Zusammenfassung


28

Spezielle Verfahren




ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahrenKodierungsverfahrenGitterprotokoll

Mit Mehrheitsentscheidunggewichteteswrite-all-read-anymit ZeugenAvailable-Copydynamisches

Aus dem Bereich der verteilten Dateisysteme

29

Gitterprotokoll

• Logische Organisation der dateibesitzenden Rechner

• Lesender Zugriff: min. 1 Rechner pro Spalte• Schreibender Zugriff: + alle Rechner einer Spalte


30

Votierungsverfahren

• Rechner stimmen über einen Lese- oder Schreibwunsch ab

• Hoher Kommunikationsbedarf• Korrekte Verwendung der Sperren wird

vorausgesetzt• Gut bei großen Datenblöcken


31

Datenblock


Datenblocknummer

Versionsnummer

Sperrzustand

Datenblockinhalt

32

Gebrauch des Datenblocks (1)


k

5

...

„ XX „

k

6

...

k

6

...

„ YY „ „ YY „

Rechner 1 Rechner 2 Rechner 3

Zustand vor Lesen

33

Gebrauch des Datenblocks (2)


k

7

...

„ ZZ „

k

7

...

k

6

...

„ ZZ „ „ YY „

Rechner 1 Rechner 2 Rechner 3

Zustand nach Schreiben

34

Votum und Quorum

• Votum: Stimmzahl der Rechner, die den Zugriff gestatten (d.h. erreichbar und keine Sperre gesetzt)

• Quorum: untere Schranke bei deren Erreichen oder Übertreffen der Zugriffswunsch gestattet wird


35

Votieren mit Mehrheitsentscheidung

• Jeder Rechner hat genau eine Stimme

Bsp.: Rechnernetz mit 4 Rechnern und vollständig repliziertem Datenbestand QU = 3 {{R1,R2,R3},{R1,R2,R4},{R1,R3,R4},{R2,R3,R4}}


1 1

11R1 R2

R4R3

36

• Unterschiedliche Stimmgewichte si für die Rechner

(S = ∑i si)

• Für Lesequorum (QUl) und Schreibquorum (QUs) gilt:

QUl + QUs > S

2 * QUs > S

Vorteile: • Null-Votum (Rechner mit si=0) wirkt leistungs-erhöhend beim

Lesen (schneller Zugriff)• QUl und QUs können auf erwartete Zugriffshäufigkeiten

abgestimmt werden

Gewichtetes Votieren


37

Gewichtetes Votieren: Beispiel

QU = 3{{R1,R2},{R1,R3},{R1,R4},{R1,R2,R3}}


1 1

12R1 R2

R3 R4

38

write-all-read-any

• Jeder Rechner hat Stimmgewicht = 1• QUl = 1

• QUs = n

Vorteil: schneller Lesezugriff

Nachteil: schwierig bei Änderungen


39

Votieren mit Zeugen

• Rechner ohne Datenblock, aber mit Stimmberechtigung

Vorteile:– Höhere Verfügbarkeit– Geringer Speicherplatzbedarf– Bei Ausfall eines Rechners erweiterbar zu voller

KopieNachteil:

– Stimmmehrheit erreichbar, aber aktuellste Version nicht dabei (Zeuge hat höchste Versionsnummer), d.h. nur Schreiben möglich


k

7

...

40

Available-Copy-Verfahren (1)

• Schreibt nur aktuell erreichbare Datenblockkopien fort• Abgestürzte Rechner aktualisieren sich bei Neustart• Jeder Rechner hat Stimmgewicht = 1• QUl = 1

• 1 ≤ QUs ≤ n


Problem:

Im Falle einer Partitionierung werden nicht erreichbare Datenblockkopien nicht fortgeschrieben und bei einer Vereinigung der Partitionen werden diese Kopien nicht aktualisiert.

Nur für LANs geeignet

41

Gliederung






• Zusammenfassung


42

Zusammenfassung

• Grundlagen verteilter Anwendungen• Konsistenz Nebenläufigkeit• Verteilte Anwendungen häufig eingebettet in verteilte

Systeme ( weitere Möglichkeiten der Synchronisation, z.B. Multicast-Synchronisationsprotkolle, Arbeiten mit Zeitstempeln, usw.)

• Verschiedene Verfahren, die verteilte Anwendungen benutzen können

• Verfahren abhängig von Anwendung (Replikation, gewünschter Grad an Nebenläufigkeit, Anzahl der Teilnehmer, Anwendungsbereich (LAN, WAN,...),...)


43

Verfahren


Pessimistische


ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahrenGitterprotokoll

Mit MehrheitsentscheidungGewichtetesWrite-all-read-anyMit ZeugenAvailable-Copy

Optimistische

44

FRAGEN

?Synchronisation und Konsistenzerhaltung in verteilten Anwendungen

Documents

1 Agenten und verteilte Anwendungen Synchronisation und Konsistenzerhaltung in verteilten Anwendungen 13. März 2003