1 Jens Pflüger, 04.11.2005 Transaktionaler Schutz für Wartungsoperationen in Overlaynetzen Jens Pflüger 04. November 2005 Betreuender Professor: Prof

1

Jens Pflüger, 04.11.2005

Transaktionaler Schutz für Wartungsoperationen in

Overlaynetzen

Jens Pflüger

04. November 2005

Betreuender Professor:Prof. Dr. Ing. Klemens Böhm

Betreuender Mitarbeiter:Dipl. Inform. Michael Klein

DIPLOMARBEIT

Universität Karlsruhe, Institut für Programmstrukturen und Datenorganisation

2


Projekt-Kontext DIANE

Angebote & Nachfragen müssen:

beschrieben werden

zu einander kommen

abgeglichen werden

Geräte müssen zur Ressourcen- bereitstellung motiviert werden

Document ServiceIn: --Out: article on GROUP-BY operator

Mehr über SQL??

=

$$$

DIANE = „Dienste in Ad-hoc-Netzen“Dienstankündigung / Dienstsuche

3


Overlay-Netze

Logische Struktur über vorhandenem Netzwerk

Liefert „Mehrwert“ Eigenschaften:

Besitzen Struktur (dezentral verwaltet) Teilnahme-Status (Login / Logout) Adaption der Struktur wegen

Änderungen am physischen Netzwerk nötig

Vorteile bei der Dienstsuche: ohne Infrastruktur funktionsfähig Ressourcenschonend (Geschickte

Weiterleitung von Nachrichten) Für dynamische Umgebungen geeignet

BFD

A

C E

physisches Netz

Overlay

A

C E

4


Lanes - Overlay

1

2

3

4

5

6

7

8

9

10

11

12

Parallele Anordnung von Knoten-“Bahnen” ( Lanes)

Anycast-Routing in x-Richtung für Dienstsuche

Austausch und Speicherung von Dienstankündigungen innerhalb der Lane ( alle Lane-Mitglieder erscheinen von außen gleich)

Vorteil:Begrenzung der Dienstankündigungs- und -suchnachrichten gegenüber Fluten

Wartungsoperationen und Optimierungen zur Anpassung der Struktur:

Login, Logoff, Lane-Splitting, Lane- Merging, Lane-Reparatur, ...

anycast

anycast

Dienstankündigung

Dienstsuche

5


Schwierigkeiten

Algorithmen für die einzelnen Aufgaben zu entwickeln ist relativ einfach

Probleme treten bei paralleler Ausführung mehrerer Mechanismen oder bei Fehlern auf:

Gegenseitiges Überschreiben von Änderungen (Lost Updates)

Unerlaubtes Lesen der geschriebenen Werte (Dirty Reads, Non-Repeatable Reads)

Inkonsistenz der Struktur !!

Grundsätzliche Lösung: Fehler müssen erkannt werden Betroffene Operationen müssen abgebrochen

werden können Ihre Wirkung muss zurückgesetzt werden

6


Beispiel

1 2 3 4 5 6

Split-Request (1)Split-Complete (3)

7Login (2)

1 3 5

2 4 6

7

7


Stand der Forschung

LanesPastry, Chord, Bamboo CAN Tapestry

Beschriebene Probleme sind keine Lanes-spezifischen Phänomene

Wie gehen existierende Overlays damit um ?

Untersuchung existierender Overlay-Implementierungen,

die zur Dienstsuche verwendet werden (können)

8


Stand der Forschung (2)

Entwicklung protokollspezifischer Lösungen: komplex schwer zu überschauen schlecht wartbar Lösungsansätze nicht übertragbar

Minderung der Probleme durch: Fehlertolerante Strukturen

Routingtabellen keine speziellen Overlay-Strukturen (z.B. bei Tapestry) Nicht allgemein einsetzbar!

Periodische Reorganisationsmaßnahmen Internet-Bereich Temporäre Inkonsistenzen

Prioritätsbasierte Lösungen Globale Serialisierung Keine Parallelität, Timeouts

9


Eigener Ansatz

Transaktionaler Operationsschutz

10


Ansatz

Entwicklung eines allgemeinen Schutzsystems

Erkennung von Fehlern Abbrechen von betroffenen Operationen Zurücksetzen ihrer Wirkung

Generizität

Eigenständiges System Einfachere Entwicklung neuer Overlays

Grundüberlegung:

Die beschriebenen Probleme treten auch in Datenbank-systemen auf!

Transaktionen beheben dort diese Schwierigkeiten

Overlay-Operationen würden auch korrekt ablaufen, wenn sie transaktional geschützt sind

11


Transaktionales Schutzsystem

Verwendung eines verteiltem DBMS:

Unterschiede: nur wenige zu schützende Datenwerte geringe Zahl paralleler Operationen pro Knoten viele Knoten an einer Operation beteiligt A C I D - Eigenschaft Hohe Fehlerwahrscheinlichkeit DB-Metadaten Strukturdaten Eigene Fehlerbehandlung durch die Overlay-Mechanismen

1

2

3

4

5

T

T

K TA

Knoten DBMS

Overlay-Netz verteiltes DBMS

Overlay-Operation verteilte TA

12


Systemaufbau

ZustandsdatenZustandsdaten

Teilnehmer 2

Lanes-Handler

Teilnehmer 1

Lanes-Handler

Lanes-Protokoll

ZustandsdatenZustandsdaten

Sperren-verwaltung

Tra

nsak

tion

Log-Manager

Transaktionsmanager

checkout, checkin, peek, remove

start, commit, abort

Exceptions

read, write

Sperren-verwaltung

Tra

nsak

tion

Log-Manager

Transaktionsmanager

checkout, checkin, peek, remove

start, commit, abort

Exceptions

read, write

Commit-Protokoll

Lokale Konsistenz

Globale Konsistenz

13


Lokale Konsistenz

Verwendung gängiger Schedule-Protokolle Strenge Sequentialität 2-Phasen-Sperr-Protokoll Vorabsperrendes Protokoll Optimistisches Vorgehen …

Leichte Austauschbarkeit und Erweiterung Gemeinsame Schnittstelle Vorgegebene Infrastruktur:

Sperrenverwaltung Deadlock-Vermeidung Deadlock-Erkennung Log-Management (nicht dauerhaft)

14


Globale Konsistenz

Teilnehmer

PrepareMessage / ReadyMessage

CommitMessage / Ack

PrepareMessage ||Timeout / NotReadyMessage

AbortMessage / Ack

Prepare

AbortingCommiting

MissingResultMessage/ MissingResultAnswerMessage[Commit]

Timeout / ConnectionLostException

Timeout / -

MissingResultMessage/ MissingResultAnswerMessage[Abort]

Termination

Tim

eout /

Missing

Resu

ltMessage

Mis

sing

Re

sultA

nsw

erM

essa

ge

[Ab

ort]

/ -

MissingR

esultA

nswerM

essa

ge[C

omm

it] / -

Timeout / -

2-Phasen-Commit-Protokoll:

15


2PC-Anpassungen

Koordinator = Initiator der Operation Allen Teilnehmern bekannt

Koordinator lernt Teilnehmer erst über Abstimmungs-nachrichten kennen (s.u.)

keine initialen Abstimmungsaufforderungen

Get-To-Know-Protokoll:

Jeder Knoten protokolliert automatisch sämtliche Nachrichten einer Operation mit. „Korrespondenz-Adressen“ werden mit Stimme übermittelt

1

2

3 4optional

C

Partitionierung

True2, (4)True

1, 3

True-

True2

Problem: System soll so generisch wie möglich sein(d.h. so wenig zusätzliche Informationen„von oben“ wie möglich!)

16


Aufwandsbetrachtung

Commit-Protokoll ist aufwändig: prinzipiell 4(n-1) Nachrichten 3(n-1) Nachrichten bei zuverlässigem Transportprotokoll

(keine expliziten Acks) n bei einigen Operationen groß! (z.B. Login)

Verbesserungen: Anpassungen des 2-Phasen-Commits (Get-To-Know-

Protokoll) nur noch 2(n-1) Nachrichten

Nur Schutz der strukturkritischen Operationen und Operationsteile

Ping/Pong

Dienst-aktualisierung

Timeout

TimeoutReparaturerfolgreich

LaneBrokentransaktionalgeschützter Kern

Vorbereitung

Nachbearbeitung

SessionID: 2

SessionID: 3

SessionID: 1

17


Evaluation - Szenario

Verwendung der Diane-Service-Benchmark SB6:

25 Knoten Erstes Angebot: U(60, 1000) s Angebotszahl: max. 5 Angebotsfrequenz: U(120, 240) s Suchfrequenz: U(60, 120) s

Modifikationen:

Simulationsdauer: 1000 s Erster Login: U(30, 1000) s Logouts möglich (nach 40 s Idle-Zeit) Relogins (min. 10 s nach Logout) Entfernen von Angeboten (Haltezeit: 120 s)

Einstellungen bei Lanes:

Lane-Größe: 3-10 Ping-Intervall: 15 s

18


Live-Demo

19


Effizienz

300 Simulations-läufe

beschr. Szenario:

Zusatzaufwand durch Trans-aktionen: 19%

Verhältnis TA-Sonstige: 39%

var. Netznutzung:

Untersuchung anhand versch. Logout-Raten

Zusatzaufwand: 7,5 – 22%

31

20

49

19

0

20

40

60

80

100

120

1

Nachrichtenverteilung

%

Dienst-Nachrichten Ping-Nachrichten

Sonstige Nachrichten transaktionale Nachrichten

0

5

10

15

20

25

25/0 35/9 34/13 39/20 43/27 60/40 65/40 70/40

Netznutzung (Logins/Logoffs pro 1000s)

%

Nachrichtenverteilung / Zusatzaufwand

Zusatzaufwand bei variabler Netzlast

20


Effektivität Je 50 Simulationsläufe

Netzlast 1: wie im Szenario beschrieben Netzlast 2: 50 Knoten, Logout nach 30 s

Nach jedem Simulationslauf:

Test der Konsistenz der aufgebauten Lanes-Struktur (Inter- und Intra-Lanes-Verbindungen)

Test des „schutzlosen“ Systems durch speziellen Scheduler

44

2

66

4

0

10

20

30

40

50

60

70

ohne Schutz mit Schutz

%

Netzlast 1

Netzlast 2

Testlaufanteil mitinkonsistentemErgebnis

21


Live-Demo (2)

22


Zusammenfassung & Ausblick

Probleme bei parallelen Wartungsoperationen in Overlays: Lost Updates Non-Repeatable Reads Dirty Reads

Entwicklung eines transaktionalen Schutzsystems Große Ähnlichkeit zu verteilten Datenbanksystemen Eigenständige Komponente Erhebliche Fehlerreduktion bei Mehraufwand bis ca. 22%

Ausblick: Einsatz für andere Overlays Funktionsfähige, korrekte, individuelle Lanes-Realisierung Weitere Commit- und Scheduleprotokolle

23


Ende

Vielen Dank für die Aufmerksamkeit!

Fragen ?

24


Anhang

25


Lokale Konsistenz - Datenspeicherung

Gruppenzuordnungen (Anycast-adressen) werden von einem dem Netzwerk nahem Overlay verwaltet

kein direkter Schutz möglich

Verwendung eines optimistischen Ansatzes:

Durchführung von Änderungen in TA- lokalem Bereich

Festschreiben der Änderungen erst nach erfolgreichem Abschluss

Abschlussprüfung auf zwischenzeitliche Änderungen

Alle anderen Strukturdaten verwaltet das Overlay selbst

Phys. Schicht

Sicherung

Netzwek

Transport

Overlay

Benutzer

Scheduler

Anycast-Overlay

26


Pastry

Neighborhood-Set

13021022 02212102

10200230 22301203

11301233 31203203

31301233 33213321

Leaf-Setkleiner größer

10233033 10233120

10233021 10233122

10233001 10233230

10233000 10233232

Knoten ID10233102

Routing-Tabelle

02212102 22301203 31203203

11301233 12230203 13021022

10031203 10132102 10323302

10200230 10211302 10222302

10230322 10231000 10232121

...

d4213f

d462bad46a01

d471f1

d46a1c

65a1fc

Route(d46a1c)

0 2128-1

d1a08e

27


CAN – Content Addressable Network

01 110 111

00

1 2

3

4

5

x

y

10

VID

0 1

10 10

105 1 3

2 4

28


Chord

0

1

2

4

35

6

7

Start Int. Nachf.

7 [7,0) 0

0 [0,2) 0

2 [2,6) 3

Start Int. Nachf.

1 [1,2) 1

2 [2,4) 3

4 [4,0) 6

Start Int. Nachf.

2 [2,3) 3

3 [3,5) 3

5 [5,1) 6

Start Int. Nachf.

4 [4,5) 6

5 [5,7) 6

7 [7,3) 0

29


Tapestry

3228

43FE

4664

437A

4361

4B4F

E391

4A6D

57ECAA93

4377

Buch „XY“(4378)

Buch „XY“(4378)

PublizierungObjektpointerAnfrage

30


Evaluation - Ergebnisse

transaktionale Nachrichten

16%

Dienst-Nachrichten

26%Ping-Nachrichten

17%

Sonstige Nachrichten

41%

0102030405060708090

100

25/0 35/9 34/13 39/20 43/27 60/40 70/40

Netznutzung (Logins/Logoffs)

%

erfolgreiche Transaktionen

abgebrochene Transaktionen

Verhältnis TA-Nachrichten zu Wartungsnachrichten

Transaktions-Gesamtaufwand

31


Lineares 2PC

Teilnehmer 1Koordinator

Abort, Ack

Ready

Teilnehmer 2

Abort, Ack

Ready

Teilnehmer n

Abort, Ack

Ready

...

32


3PC

Koordinator

Prepare Aborting

NotReadyMessage || Missing ReadyMessages / AbortMessage

PreCommit

CommitCall / PrepareMessage

All ReadyMessages received / PreCommitMessage

CommitingMissing PreAcks / AbortMessageAll PreAcks received /

CommitMessage

All Acks received / - All Acks received / -

PrepareMember

PreCommitMember

PrepareMessage / ReadyMessage

PreCommitMessage / PreAck

CommitMessage / Ack

PrepareMessage / NotReadyMessage

AbortMessage / Ack

AbortMessage / Ack

Teilnehmer

Documents

1 Jens Pflüger, 04.11.2005 Transaktionaler Schutz für Wartungsoperationen in Overlaynetzen Jens Pflüger 04. November 2005 Betreuender Professor: Prof