1 Jens Pflüger, 04.11.2005 Transaktionaler Schutz für Wartungsoperationen in Overlaynetzen Jens...

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Beispiel

1 2 3 4 5 6

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

7Login (2)

1 3 5

2 4 6

7

7

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Eigener Ansatz

Transaktionaler Operationsschutz

10

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Live-Demo

19

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Live-Demo (2)

22

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Ende

Vielen Dank für die Aufmerksamkeit!

Fragen ?

24

Jens Pflüger, 04.11.2005

Anhang

25

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Tapestry

3228

43FE

4664

437A

4361

4B4F

E391

4A6D

57ECAA93

4377

Buch „XY“(4378)

Buch „XY“(4378)

PublizierungObjektpointerAnfrage

30

Jens Pflüger, 04.11.2005

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

Jens Pflüger, 04.11.2005

Lineares 2PC

Teilnehmer 1Koordinator

Abort, Ack

Ready

Teilnehmer 2

Abort, Ack

Ready

Teilnehmer n

Abort, Ack

Ready

...

32

Jens Pflüger, 04.11.2005

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