Verteilte Systeme (Teil 4)

Ein verteiltes System ist im Prinzip der Zusammenschluss mehrerer Rechner zur Lösung einer gemeinsamen Aufgabe. Eines der größten verteilten Systeme ist das Internet mit seinen Applikationen. Teil 4 behandelt die Zeit in verteilten Systemen, Replikation, Konsistenz und Fehlertoleranz.

Skript-Anfang	VS_1_So2014 – Seite 1
Skript-Ende	VS_6_So2014 – Seite 70

Algorithmen und Verfahren

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. Somit können sie zur Ausführung in einem Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.

Zeit in verteilten Systemen

Welche Motivation steckt dahinter?

• Korrekte Uhrzeit
• Korrekte Reihenfolge von Ereignissen
• Abhängigkeit von Ereignissen

Physikalische Zeit

Was ist physikalische Zeit?

• Genutzt zur Synchronisation
• Typische Implementierung ist NTP
• Genauigkeit abhängig von Netzwerkeigenschaften
• Abschätzung der Nachrichtenlaufzeit

Was ist Universal Time, Coordinated (UTC)?

• Basiert auf internationaler Atomzeit
• Physikalische Zeit

Wie lässt sich die Atomzeit empfangen?

• Jeder Rechner bekommt einen Atomzeitempfänger (einfach, teuer)
• Innerhalb einer Gruppe bekommt ein Rechner einen Atomzeitempfänger (komplex, günstig)

Was macht man, wenn die Systemuhr zu langsam war?

• Uhr vorstellen

Was macht man, wenn die Systemuhr zu schnell war?

• Uhr verlangsamen

Was ist Christian’s Algorithm?

• Ein Rechner mit Atomzeitempfänger synchronisiert eine Gruppe von Rechnern
• Alle δ/2ρ Zeiteinheiten wird Nachricht mit C_UHR an Zeitserver gesendet
• C_UHR > C_UTC → Client-Uhr wird verlangsamt
• C_UHR < C_UTC → C_UHR = C_UTC
• Immer C_UHR = C_UHR + 1/2 RTT
• round-trip time (RTT) = (+ Client-Empfang – Client-Absenden – Server-Absenden + Server-Empfang)/2

Was ist das Network Time Protocol (NTP)?

• Standard zur Synchronisierung von Uhren in Computersysteme
• Hierarchisch aufgebautes Netzwerk aus Rechnern
• Primärserver synchronisieren sich gegenseitig und mit dem UTC
• NTP-Dämon auf jedem System (Wählt beste Quelle aus festem Pool aus)
• NTP nutzt also mehrere Server zum Abgleich
• Kriterien sind Erreichbarkeit, Antwortzeit und Schwankungsbreite der Antworten
• Ebene n (aka Stratum) korrigiert Ebene n+1
• Läuft über UDP-Port 123

Wie korrigiert NTP die Zeit?

• NTP speichert Paare von Offset und RTT
• Der Offset mit der kleinsten RTT wird genommen

Wie berechnet NTP die RTT?

• δ = t₃ – t₀ – t₂ + t₁

Wie berechnet NTP den Offset?

• θ = t₂ +δ/2 – t₃

Was ist der Berkeley Algorithmus?

• Verwendet keine Atomzeit
• Ein zentraler Zeitserver

Wie wird die Zeit bei Berkeley synchronisiert?

• Zeitserver übermittelt seine Zeit an die Clients
• Clients liefern die Differenz an den Server
• Server berechnet den Durchschnittswert
• Durchschnittswert wird an die Clients übermittelt
• Alle Systeme aktualisieren ihre Zeit (inkl. Server)

Spielt die Nachrichtenlaufzeit auch bei Berkeley’s Algorithmus eine Rolle?

• Ja, die Laufzeit zwischen Anfrage und Rückgabe beeinflusst den Durchschnitt

Welchen weiteren Nachteil hat Berkeley’s Algorithmus?

• Ohne zentralen Server gibt es keine Synchronisierung
• Anderer Rechner muss diese Rolle dann übernehmen

Logische Zeit

Was ist logische Zeit?

• Definiert eine Reihenfolge von Ereignisse
• Genauer Zeitpunkt von Ereignissen ist unwichtig
• Wichtiger ist, ob a vor b oder b vor a stattfindet (Welche Kopie ist aktueller?)
• Lamport-Zeit (mit globaler Ordnung)
• Vektorzeit (Wenn 2 Ereignisse definitiv nacheinander stattfinden)
• Synchronisation und Sperre von gemeinsamen Ressourcen

Wo könnten sich die logischen Uhren in einem verteilten System befinden?

• Unter der Anwendungsschicht und über der Netzwerkschicht
• Sie liegen in der Middleware-Schicht
• Vor dem Senden werden Nachrichten mit einem Zeitstempel versehen
• Nach dem Empfangen von Nachrichten wird die Uhr justiert

Was ist die Relation „happened before“?

• Kausale Ordnung der Ereignisse
• a → b (a findet vor b statt)
• a → b und b → c = a → c (Transitiv)

Wann gilt „happened before“?

• a und b müssen zum gleichen Prozess gehören
• a ist das Sendeereignis und b ist das Empfangsereignis

Wann gilt „happened before“ nicht?

• Wenn a und b unabhängig sind
• Dies gilt wenn a → b und b → a
• Dann sind a || b nebenläufig

Was ist der Algorithmus von Lamport?

• Jeder Prozess hat eine eigene logische Zeit
• Nachrichten werden beim Senden mit einem logischen Zeitstempel versehen
• Beim Eintreffen wird die lokale logische Zeit angepasst
• Korrekturen werden nur durchgeführt, wenn der neue Wert größer ist

Was ist die totale Ordnung von Ereignissen?

• Globale Ordnung aller Nachrichten
• Auslieferung von Nachrichten abhängig von globaler Reihenfolge des Eintreffens

Wie kann man die Lamport-Zeit erweitern, um eine globale Ordnung herzustellen?

• Totalordnung durch Einbeziehung von eindeutigen und total geordneten Knotenkennungen
• Jedes Ereignis bekommt zusätzlich eine (Prozessor-)ID als Wert
• Wenn L(a)=L(b) dann wird PID_p und PID_q verglichen
• Vorgetäuschte Ordnung (PID ist zufällig)

Was ist die Vektorzeit?

• Alle Prozesse beginnen bei 0
• Für jeden Prozess gibt es eine Dimension im Vektor
• Jedes Ereignis inkrementiert den Vektor um 1
• Es wird nur die Dimension des Prozesses erhöht
• Benötigt viel Speicher

Wie sind die Relationen definiert?

• u ≤ v ⇔ u[i] ≤ v[i] für alle i=1,…,n
• u < v ⇔ u[i] ≤ v[i] und u ≠ v
• u || v ⇔ ¬(u ≤ v) und ¬(v ≤ u)
• e → e‘ ⇔ V(e) < V(e‘)
• e || e‘ ⇔ V(e) || V(e‘)

Was wird z.B. jeweils über die Reihenfolge von c und g ausgesagt? Was über d und g ?

• L(c) || L(g)
• V(c) || V(g)
• L(c) < L(d)
• V(c) < V(d)

Ereignis	Lamport	Vektor
a	1	(1,0,0)
b	2	(2,0,0)
c	3	(3,0,0)
d	4	(3,1,0)
e	5	(3,2,0)
f	1	(0,0,1)
g	3	(2,0,2)
h	6	(3,2,3)
i	7	(3,2,4)
j	8	(4,2,4)
k	9	(5,2,4)
l	10	(5,3,4)

Wechselseitiger Ausschluss

Wie kann man wechselseitigen Ausschluss realisieren?

• Jeder Prozess verwaltet die Warteschlange mit Anfragen
• Logische Zeit mit Totalordnung zur Sortierung der Warteschlange
• Nachrichten werden verlustfrei und in der richtigen Reihenfolge übertragen (TCP)

Wie läuft der Ausschluss ab?

• REQUEST mit Zeitstempel an alle anderen via Broadcast
• Anfragen werden mittels Totalordnung in Warteschlange eingereiht
• Empfangsbestätigung via ACK an den Absender
• Wenn man Vorne in der Warteschlange steht → Zugriff
• Wenn Zugriff abgeschlossen → RELEASE via Broadcast
• Wenn RELEASE empfangen → Eintrag aus der Warteschlange entfernen
• Es gibt also 3*(n-1) Nachrichten

Wie funktioniert der wechselseitige Ausschluss nach Ricart/Agrawala?

• RELEASE und ACK werden durch REPLY ersetzt
• Absender greift erst auf Ressource zu, nachdem er alle REPLY erhalten hat
• Nach einem REQUEST wird REPLY sofort verschickt, falls kein eigenes Interesse besteht
• Nach einem REQUEST wird REPLY sofort verschickt, falls der REQUEST einen älteren Zeitstempel als der eigene hat
• Nach einem REQUEST wird REPLY nicht sofort verschickt, wenn der eigene REQUEST einen älteren Zeitstempel hat
• Der älteste REQUEST setzt sich immer durch

Kann es bei Lamport bzw. Ricart/Agrawala zum Deadlock kommen?

• Nein, da alle Prozesse die Warteschlange mit den Anfragen in logischer Reihenfolge kennen

Wie oft muss beim Algorithmus von Ricart/Agrawala ein Prozess einem anderen maximal „den Vortritt“ lassen?

• Bei n Prozessen muss maximal n-1 mal der Vortritt gelassen werden

Replikation

Was ist Replikation?

• Objekt kommt mehr als einmal im verteilten System vor
• Ohne Replikation ist Konsistenz einfach
• Latenz-Optimierung durch Caching
• Lastverteilung durch mehrere Server bzw. Threads
• Fehlertoleranz durch mehrere Standorte

Was ist Caching?

• Server speichert Anfragen und die passenden Antworten
• Lokale Kopie auf einem System zwischen Client und Server
• Server liefert gespeicherte Antworten auf identische Anfragen

Wo findet man solche Caches?

• Webcaches (Auf Client, Server, Proxy oder Firewall)
• Content Distribution Networks (CDN)
• REST ist statuslos und ermöglicht Caching

Was ist besser, hot oder cold stand-by?

• Es kommt ganz auf den Anwendungszweck an

Wie funktionieren Cluster für Fehlertoleranz?

• 1 Hauptserver und n Replikate
• Replikate springen nur bei Ausfall ein
• Hot stand-by = Der Replikatserver steht immer bereit
• Cold stand-by = Der Replikatserver muss erst bereitgestellt und hochgefahren werden

Wie funktionieren Cluster zur Lastverteilung?

• Cluster aus replizierten Server bietet Lastverteilung und Fehlertoleranz
• Loadbalancer verteilt die Anfragen nach Algorithmus (Round Robin)
• Mehrere Loadbalancer sorgen für Ausfallsicherheit

Wie kann man ein Cluster implementieren?

• n-Tier (Zentrale Datenbank synchronisiert im Hintergrund)
• Master-slave (Master schreibt und verteilt die Daten)
• Verteilte master-slaves (Jeder Server ist für bestimmte Teile ein Master)

Wie kann Lastverteilung durch den Client geschehen?

• Client bekommt mehrere Adressen
• Client wählt zufällige Adresse aus
• Wenn der Zugriff nicht klappt wird ein anderer Server gewählt

Kann es bei Webservern zu Konsistenzproblemen kommen?

• Reine Lesezugriffe sind kein Problem

Welches Problem stellt sich bei der Implementierung?

• Alle Server benötigen dieselben Statusinformationen (Login)

Welchen Einfluss hat das Transportprotokoll in einer solchen Architektur?

• TCP ist nicht statuslos (keine Migrationstransparenz)

Warum könnte man eine Migration einer TCP Verbindung wollen?

• Reparieren einer TCP-Verbindung nach IP-Adresswechsel bzw. Serverausfall

Wie werden temporäre Daten gespeichert?

• Datenbanken sind zu langsam
• Cache im Hauptspeicher des Webservers
• Cache auf separaten Rechnern
• Zuordnung mittels Hash-Funktion

Was sind Pipelines?

• Client schickt mehrere Anfragen in einer Nachricht
• Anfragen werden sequentiell beantwortet
• Werden in HTTP, FTP und TCP realisiert

Ist Pipelining auch als Verfahren innerhalb eines Servers mit Threads sinnvoll?

• Die Implementierung von Pipelining ist nicht sinnvoll in diesem Zusammenhang

Was ist Map-Reduce?

• Lastverteilung durch Parallelverarbeitung
• Funktioniert nur bei trivialen Partitionierungen
• Geschwindigkeitssteigerung
• Fehlertoleranz (Bei timeout wird Job dem nächsten Worker gegeben)
• Skalierbarkeit (beliebige Menge an Workern)
• Häufigkeit von Links in Webseiten
• Zuordnung von Links zu Webseiten

Wie läuft Map-Reduce ab?

1. Partitionieren der Eingabe
2. map = Ein Worker erstellt eine map mit Key und Value-Paaren
3. Combine im gleichen Worker
4. Ausgabe der reduzierten maps in einer Datei
5. reduce = Ein Worker bearbeitet einen Key und fasst zusammen

Konsistenz

Was ist Konsistenz?

• Alle Kopien eines Objektes sind identisch
• Ohne Replikation ist Konsistenz einfach
• Lesender Prozess soll aktuellsten Wert bekommen (Was ist der aktuellste?)
• Konsistenzanforderungen für jeden Dienst unterschiedlich
• Ein Konsistenzmodell beschreibt, wie Konsistenz von Daten aussehen kann
• Konsistenzprotokoll ist die Implementierung eines Konsistenzmodells

Wie sieht die Notation aus?

• R(x)a – Ein Prozess liest aus einer Variablen x den Wert a
• W(x)a – Ein Prozess schreibt in eine Variable x den Wert a

Was ist strikte Konsistenz?

• Jedes Read liefert den letzten Writes
• Nicht implementierbar (Wegen der Zeit)

Was ist sequentielle Konsistenz?

• Schwächere Bedingungen
• Jede Kombination bzw. Vermischung von Read und Write ist akzeptabel
• Alle Prozesse müssen die gleiche Reihenfolge sehen

Was sind urbildbasierte Protokolle?

• Implementieren sequentielle Konsistenz
• Eine Replik gilt als Urbild bzw. primary master

Was ist entferntes Schreiben?

• Urbilder bleiben immer am selben Ort
• Master verteilt Updates nach jedem Schreiben
• Alle Schreibvorgänge auf demselben Urbild werden serialisiert

Was ist lokales Schreiben?

• Urbilder wandert zum Ort mit den meisten Schreibzugriffen
• Dies beschleunigt die Zugriffe

Was ist ACID?

• Atomarität – Nur ganze Operationen
• Konsistenz – Wechsel nur zwischen konsistenten Zuständen
• Isolation – Transaktionen beeinflussen sich nicht
• Dauerhaftigkeit – Nach einer Transaktion ist alles gespeichert

Was ist der 2 Phasen Commit (2PC)?

• Besteht aus 1 Transaktionsverwalter und n Ressourcenverwaltern
• Transaktionsmechanismus, um verteilte Kopien von Daten zu aktualisieren
• Fehlertoleranz (toleriert Ausfälle durch timeout)
• Blockiert, wenn nach timeout alle anderen Teilnehmer in Ungewissheit sind
• Teilnehmer blockieren in der Periode in der Ungewissheit
• Benötigt mindestens 3 (+1xACK) und maximal 5 Runden (Terminierung)
• Teilnehmer verwalten ein eigenes Log mit Ereignissen

Was ist der 3PC?

• Einführung einer zusätzlichen Phase
• COMMIT wird erst gesendet, wenn alle Teilnehmer Bereitschaft signalisieren
• Verhindert, dass ein Teilnehmer den COMMIT durchführt, bevor andere diesen empfangen haben

Was ist der Quorum Algorithmus?

• Nur auf einer Auswahl von Repliken wird gelesen und geschrieben
• QW = Schreiben
• QR = Lesen
• Verteilung erfolgt später im Hintergrund
• Quorum anfordern, aktualisieren und mittels 2PC freigeben

RPCs, RMI, CORBA arbeiten mit request/reply. Wie kann man in dieser Umgebung Fehler behandeln?

• Client-Auftrag ging verloren – Wiederholung des Auftrags
• Server-Antwort ging verloren – Zwischenspeicherung der Ergebnisse beim Server, Bereitstellung bei Anfrage
• Serverabsturz – Neustart des Servers und exponential backoff beim Client
• Langsamer Server – Regelmäßige Statusnachrichten vom Server