Upload
lenz-karp
View
114
Download
0
Embed Size (px)
Citation preview
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