fehlertolerante Koordination in Clouds Flashcards
1
Q
Formen der Realisierung von Koordination
A
- Bibliothek, die ein Einigungsprotokoll realisiert bzw. eine Gruppenkommunikation bereitstellt
- Koordinationsdienst
- Beispiele: Chubby (Google) und ZooKeeper (Apache/Yahoo)
2
Q
Koordinationsdienste
A
Verteilte Algorithmen zur Koordination
- In der Regel recht schwierig zu implementieren
- Verwendung von Bibliothek auch nicht einfach bzw. oft substantielle Anpassung von Diensten notwendig
- Z.B.: Dienst muss eine deterministische Zustandsmaschine realisieren!
Koordinationsdienste
- Eine Dienstimplementierung lässt sich vielseitig einsetzen
- Einfache und verständliche Schnittstelle reduziert Anforderungen an Anwendungsentwickler
- Dienstinstanz kann durch viele Anwendungen gleichzeitig genutzt werden
- Z.B.: Für Chubby 90.000 Prozesse, die von einem Dienst koordiniert werden
Programmiermodell
- Ähnlich der Koordination mittels gemeinsamen Speichers
- Implementierungsbasis bilden verteilte Algorithmen
- Erlaubt Koordination von beliebig vielen Prozessen
Anforderungen
- Hohe Verfügbarkeit, Konsistenz und Performanz
3
Q
Chubby Grundlagen
A
Koordinierungsdienst für verteilte Anwendungen in Datenzentren
- Dateisystem-ähnliche Schnittstelle
- Ablage und Verwaltung von Datenobjekten (<256 KB)
- Optimiert für lesenden Zugriff
- Benachrichtigung über wichtige Ereignisse
- Z.B.: Änderung eines Datenobjekts
- Zwischenspeicherung von Dateien (mit starker Konsistenz)
- Zugriffskontrolle über ACL
- Unterstützung von langlebigen Locks
4
Q
Chubby langlebige & kurzlebige Locks
A
Eigenschaften von langlebigen Locks
- Reduziert Last des Koordinationsdiensts
- Geringere Verzögerungen bei Ausfällen des Diensts
- Locks überdauern Ausfälle des Diensts
- Annahme: Ausfälle sind nur kurzfristig (<30 sec)
- Geringe Anforderungen an die Verfügbarkeit des Diensts und damitauch eine geringere Anzahl von Replikaten notwendig
Eigenschaften von kurzlebigen Locks
- Höhere Last für den Dienst und größere Auswirkung für die Anwendungen bei Ausfällen
- Kurzlebige Locks können bzw. sollten durch die Anwendungen selbst implementiert werden
5
Q
Chubby Architektur
A
Dienstinstanz
- In der Regel besteht eine Dienstinstanz (Cell) aus 5 Replikaten
- Anführer wird durch den Paxos-Einigungsalgorithmus bestimmt
- Jedes Replikat unterhält eine Kopie des Dienstzustands
- Vergleichbar mit einer einfachen Datenbank; residiert im Hauptspeicher
- Schreibende Zugriffe müssen durch eine Mehrheit bestätigt werden
- Lesende Zugriffe werden nur vom Anführer bearbeitet
- Langfristig ausgefallene Replikate werden durch neue ersetzt
Anwendungen
- Verwenden die Chubby-Bibliothek
- Ermitteln Anführer der Dienstinstanz und kommunizieren fortan nur noch direkt mit diesem
- Bei längerfristigem Ausfall wird neuer Anführer gesucht
6
Q
Chubby Anwendungsschnittstelle & Programmierschnittstelle
A
Anwendungsschnittstelle: Einfache bzw. reduzierte Dateisystemschnittstelle
- Beispiel einer Chubby-Verzeichniswurzel:
- /ls/cs6464-cell/lab2/test
- ls: Dienstidentifikator
- cs6464-cell: Instanzkennung
- lab2: Verzeichnis
- test: Datenobjekt
- Spezialisierte Schnittstelle, die sowohl Daten als auch Metadatenoperationen unterstützt
- Explizit nicht unterstützte sonst bei Dateisystemen gebräuchliche Operationen
- Verschieben von Dateien
- Zugriffsrechte über Pfade
- Modifikations- bzw. Zugriffszeitstempel
Programmierschnittstelle
- Open()
- Übergabe eines vollständigen Pfads
- Überprüfung der Zugriffsrechte
- Registrierung für Ereignisse
- Konfiguration, ob Verzögerung von Zugriffen im Kontext von Ausfällen
- erforderlich ist
- Close() vs. Poison()
- Close() trennt/beendet eine Verbindung
- Poison() beendet alle aktuell laufenden Aufrufe
- Weitere Operationen
- GetContentsAndStat(), SetContents(), Delete(), Acquire(), TryAcquire(), Release(), GetSequencer(), SetSequencer(), CheckSequencer()
Verwendung der Programmierschnittstelle:
Wahl eines Anführers auf Anwendungsebene
- Mehrere Knoten versuchen das gleiche Datenobjekt zu öffnen und gleichzeitig das Lock anzufordern
- Nur ein Knoten gewinnt und schreibt seine Identität in das Datenobjekt (SetContents())
- Alle weiteren Knoten finden das Ergebnis der Wahl durch GetContentsAndStat() heraus; unter Umständen motiviert durch ein Ereignis
- Anführer fordert Sequencer an (GetSequencer())
7
Q
Chubby Daten- und Verwaltungsstrukturen
A
Datenobjekte und Verzeichnisse
- Zwei Formen von Objekten: kurzlebig und permanent
- Kurzlebige Objekte werden gelöscht sobald nicht mehr benötigt
- Metadaten
- Zugriffsrechte werden über 3 verschiedene ACL-Listen verwaltet– Lesen, Schreiben und Modifizieren der ACL-Listen
- Verschiedene Zähler für Modifikationen – Instanzidentifikator – Anzahl der Modifikationen – Anzahl der Lock-Vorgänge – Anzahl der ACL-Veränderungen
- Prüfsumme über den Objektinhalt
Handle
- Aufbau und Funktion ähnlich zu UNIX-Datei-Handle
- Erhalt auch bei Wechsel des Chubby-Anführers unterstützt
- Wird erreicht mittels Sequenznummer und Zugriffsmodusinformationen
8
Q
Chubby Koordinationsmechanismen
A
Locks und Sequencers
- Jedes Objekt des Diensts stellt ein potenzielles Lock dar
- Dabei kann zwischen Lese/Schreib-Lock und einfachem Lock unterschieden werden
- Locks sind nur eine Konvention um Zugriff zu koordinieren
- Eigentliche Zugriffskontrolle muss auf Seite der Anwendung erfolgen
- Erleichtert Fehleranalyse und administrativen Zugriff
- Um ein Lock zu belegen werden Schreibrechte für das Objekt benötigt
- Koordinierung in asynchronen Umgebungen ist komplex, da Nachrichten verzögert werden oder verloren gehen können …
- Verwendung von so genannten Sequencers im Kontext von Locks
- Sequencer
- Aus Sicht der Anwendung eine opake Zeichenkette
- Beschreibt den Zustand eines Locks nach der Belegung
- Wird innerhalb der Anwendung von Clients an Dienst übergeben; dieser überprüft mittels Chubby den Sequencer
- Alternative: Falls eine Anwendung nicht entsprechend angepasst werden kann, ist die Verzögerung der Vergabe eines Locks im Falle eines Client-Ausfalls möglich
Events
- Clients registrieren sich für bestimmte Ereignisse
- Ereignisse werden über Rückrufe an die Anwendung übermittelt
- Folgende Ereignisse werden unterstützt
- Modifikation eines Datenobjekts
- Verwaltungsoperationen innerhalb eines Verzeichnisses
- Übernahme durch einen neuen Chubby-Anführer
- Benachrichtigung über die Invalidierung eines Locks oder Handles
- Belegung eines Locks bzw. konfligierende Anforderungen
9
Q
CHubby Verbindungsmanagement
A
Sessions- und KeepAlive-Nachrichten
- Sessions werden durch KeepAlive-Nachrichten auf Funktion überprüft
- KeepAlive-Nachrichten werden indirekt genutzt, um die Gültigkeit von Handles, Locks und zwischengelagerten Daten zu überprüfen
- Wird gemeldet, dass Daten ungültig sind, muss dies durch die Anwendung quittiert werden
- Session wird entweder explizit getrennt oder durch Timeout eines Leases für beendet erklärt
- Session-Lease regelmäßig verlängert
- Quittierung von KeepAlive-Nachrichten
- Problem: Übernahme durch einen neuen Anführer
Behandlung der Session-Leases
- Anführer verlängern ein Lease erst kurz vor Ablauf
- Clients senden Aufforderung zur Verlängerung eines Lease unmittelbar nach der Verlängerung des letzten Lease (in Form einer KeepAlive-Nachricht)
Behandlung von Invalidierung
- Handles, Locks und zwischengelagerte Daten bleiben erhalten/aktuell bis eine Invalidierung durch den Anführer gemeldet wird
- Clients müssen solche Benachrichtigungen quittieren
- Invalidierungen werden im Kontext von KeepAlive-Nachrichten vermittelt
Behandlung der Leases
- Clients verwalten lokal das Session-Lease und überwachen das Timeout des Lease
- Konservative Abschätzungen sind hierzu notwendig, welche die Uhrzeitunterschiede mit einbezieht
- Bei Timeout des Lease wird der lokale Zwischenspeicher gesperrt
- Die Session wird für eine gewisse zusätzliche Zeit erhalten
- Sollte sich der Anführer wieder melden, erfolgt eine Aktualisierung des Zwischenspeichers
- Bei Erneuerung der Session wird die Anwendung informiert
10
Q
Chubby Zwischenlagerung
A
Anwendungen haben einen lokalen Zwischenspeicher
- Enthält Objektdaten und Metadaten
- Invalidierung
- Anführer führt Buch, welche Daten durch Clients gelagert werden
- Bei Schreibzugriffen sendet der Anführer zuerst Invalidierungsnachrichten
- Clients entfernen die Daten aus dem Zwischenlager und quittieren die Invalidierung mit KeepAlive-Nachrichten
- Lesende Zugriffe weiterhin möglich aber nur über den Dienst direkt
- Invalidierungen werden an Clients propagiert aber nicht Aktualisierung der neuen Daten
- Geschieht implizit bei der nächsten lesenden Anfrage
- Handles und Locks werden auch zwischengespeichert
- Sogar das Nichtexistieren von einmal angeforderten Datenobjekten wird registriert und zwischengespeichert
11
Q
CHubby Wechsel des Anführers
A
- Anführer verwirft seinen lokalen Zustand
- Informationen zu Sessions, Handels und Locks
- Lease-Timer wird angehalten
- Variante: Schneller Wechsel
- Wechsel ist vollzogen bevor das Lease ausläuft
- Variante: Langsamer Wechsel
- Client blockiert Zwischenspeicher und wartet eine gewisse Zeit
- Erlaubt den Erhalt von Sessions
Ablauf des Wechsels aus Sicht des neuen Anführers
- Beginn einer neuen Epoche
- Nötig um alte Anfragen zu identifizieren
- Initial wird nur auf Anfragen nach dem Anführer geantwortet
- Aufbau des Betriebszustands basierend auf den Daten aus der persistenten Datenbank
- Antworten auf KeepAlive-Nachrichten
- Aussenden von FailOver-Nachrichten an Clients
- Zwischenspeicher wird gelöscht
- Neuer Anführer wartet bis entsprechende Nachrichten beantwortet oder Sessions abgelaufen sind
- Übergang in Normalbetrieb
12
Q
Chubby Datenbank und Backup
A
Datenbank: Daten müssen konsistent und verfügbar abgesichert werden
- Initial: Verwendung einer replizierten Variante der BerkeleyDB
- Auf Grund von technischen Problemen Implementierung einer einfacheren Lösung basierend auf einem Einigungsprotokoll
Backup
- Alle paar Stunden wird ein Backup erstellt
- Abgelegt im GoogleFS an verschiedenen Orten
- Ermöglicht Behandlung von Katastrophen
- Schnelle Initialisierung von neuen Replikaten
13
Q
CHubby Spiegelung von Daten
A
Einfacher Transfer von Datenobjekten möglich
- In der Regel für Konfigurationsdaten genutzt
- Z. B.: Von /ls/global/master nach /ls/cell/slave
- global bildet hierbei eine Chubby-Instanz, die über verschiedene Datenzentren verteilt ist
- Verwaltete Daten: Zugriffsrechte auf Chubby, Lokation wichtiger Dienste (z. B. Bigtable)
14
Q
Chubby Verbesserung der Skalierbarkeit
A
Clients sind keine Maschinen sondern Prozesse
- Hohe Last von bis zu 90.000 Clients pro Dienst-Instanz
- Mit der Kapazität der Clients nimmt in der Regel auch die Kapazität der Server zu
- Es wird die gleiche Hardware verwendet!
- Um die Skalierbarkeit zu steigern ist die Reduktion von Kommunikation essentiell
- Bereitstellung von mehr Chubby-Instanzen
- Verlängerung der Lease-Zeit
- Rigorose Zwischenlagerung von Daten
Einführung von vermittelnden Proxy-Knoten
- Proxy-Knoten leiten Client-Anfragen an Chubby weiter
- Verarbeitung von lesenden Anfragen und KeepAlive-Nachrichten
- Schreibende Anfragen müssen weiterhin durch den Dienst behandelt werden
- Typischerweise sind Schreibanfragen nur <<1%
- Nachteile des Ansatzes
- Zusätzliche Latenz für schreibende Anfragen
- Zusätzliche Komplexität
Zustandspartitionierung
- Aufteilung des Namensdiensts auf verschiedene Chubby-Instanzen
- Daten unter D/C werden durch Hash über den Pfad abgebildet (P(D/C) = hash(D) mod N)
- Nachteil: Es gibt Kommunikation über Partitionsgrenzen hinweg
- Zwischenspeicherung reduziert dieses Problem
15
Q
Chubby Zusammenfassung
A
Chubby ist ein verteilter Koordinierungsdienst
- Unterstützt langlebige Locks
- Wird verwendet für GoogleFS und BigTable
Implementiert unter Verwendung bestehender Konzepten
- Einigungsprotokoll, Zwischenlagerung von Daten, Benachrichtigungen und Bereitstellung einer Dateisystemschnittstelle
Verwendungszwecke
- Bestimmung eines Anführers
- Namensdienst
- Hochverfügbarer Datenspeicher
16
Q
Apache ZooKeeper Grundlagen
A
- Fehlertoleranter Koordinierungsdienst für verteilte Systeme
- Anfangs entwickelt bei Yahoo!, jetzt Apache-Projekt
- Produktiveinsatz bspw. bei Twitter, eBay, Facebook, …
- Verwaltung von Daten
- Hierarchischer Namensraum: Baumstruktur Nutzdaten in jedem Knoten möglich
- Keine expliziten Sperren oder Transaktionen jedoch Gewährleistung bestimmter Ordnung bei konkurrierendencZugriffen
- Fehlertoleranz
- Replikation des Diensts auf mehreren Rechnern
- Replikatkonsistenz mittels Leader-Follower-Ansatz
- Open Source
- https://github.com/apache/zookeeper
22
Q
Apache ZooKeeper Anwendungsbeispiel (e): Wahl eines neuen Anführers
A
Problemstellung
- In einer Gruppe von ZooKeeper-Clients soll ein Anführer gewählt werden
- Bei Ausfall des Anführers muss ein neuer Anführer bestimmt werden
Umsetzung
- Erstellen eines „Verzeichnisknotens“ /leader für die Gruppe
Vorgehensweise beim Hinzukommen eines neuen Clients
- – Erstellen eines flüchtigen Kindknotens /leader/node-
- – Suche nach Kindknoten mit kleineren Sequenznummern
- – Existiert kein Kindknoten mit kleinerer Sequenznummer →neuer Leader
- – Sonst: Follower →Watch auf Knoten mit nächstkleinerer Seq.-Nr. setzen
Bei Knotenausfall
- – Automatische Löschung des zugehörigen flüchtigen Knotens
- →Genau ein Client wird per Watch über den Ausfall benachrichtigt
Weitere Anwendungsbeispiele:
- Konfigurationsmanagement
- Konfiguration als Payload von Knoten zc
- Replikate setzen Watches auf zc
- →Benachrichtigung über Veränderungen der Konfiguration
- Gruppenzugehörigkeit
- Knoten zg repräsentiert eine Gruppe
- flüchtige Kindknoten von zg stellen Gruppenzugehörigkeit dar
- Replikate setzen Watches auf zg
- →Benachrichtigung über Veränderung innerhalb der Gruppe
- Key-Value Store
- Knotennamen als Schlüssel, Payload als Wert
23
Q
Konsistenzwahrung in ZooKeeper
A
Problemstellung
- Replikation einer zustandsbehafteten Anwendung
- Replikatzustände müssen konsistent gehalten werden
- Beispiel für inkonsistente Zustände zweier Replikate R1 und R2
- – Zwei Anfragen A1 und A2, die einem Knoten /node neue Daten zuweisen
- Sicherstellung der Replikatkonsistenz in ZooKeeper
- Alle Replikate müssen Anfragen in der selben Reihenfolge bearbeiten
- Protokoll zur Erstellung einer Anfragenreihenfolge nötig
24
Q
Replikation in ZooKeeper
A
Anzahl der ZooKeeper-Replikate
- Annahme: Ein ausgefallenes Replikat wird zeitnah durch ein neues ersetzt
- 2f + 1 Replikate zur Tolerierung von höchstens f Fehlern/Ausfällen
- Beispiel für f = 2
Leader-Follower-Ansatz
- Leader gibt Reihenfolge vor
- Follower bearbeiten Anfragen in der vorgegebenen Reihenfolge
26
Q
Apache ZooKeeper - Zab
A
- Protokoll für zuverlässigen und geordneten Nachrichtenaustausch
- Von Apache ZooKeeper verwendet, aber nicht modular integriert
- Nachträgliche eigenständige Implementierung als Zab
- Totally Ordered Broadcast Protocol
- Leader-Follower-Ansatz
- Zwei Protokoll-Modi
- – Broadcast Normalbetrieb
- – Recovery Wahl eines neuen Leader
Zab: Broadcast-Modus:
- Ziel: Herstellung einer einheitlichen Reihenfolge aller Client-Anfragen
- Vorgehensweise
- PROPOSE Leader schlägt Sequenznummer (zxid) für Anfrage vor
- ACK Follower akzeptieren den Vorschlag
- COMMIT Leader bestätigt die Sequenznummer der Anfrage
Zab: Recovery-Modus:
- Abbruch des Broadcast-Modus
- Ausfall des Leader
- Leader hat keine Mehrheit mehr
- Eigenschaften des Recovery-Protokolls
- Eine Anfrage, die auf einem Knoten bestätigt wurde (COMMIT), wird (gegebenenfalls nachträglich) auf allen Knoten bestätigt
- Nichtbestätigte Vorschläge werden verworfen
- Wahl eines neuen Leader
- Ziel: Neuer Leader wird der Knoten, dem der Vorschlag mit der höchsten zxid bekannt ist; bei Gleichstand entscheidet die höhere Knoten-ID
- Rundenbasierte Abstimmung, in der jeder Knoten jedem anderen seinen aktuellen Kenntnisstand mitteilt
- Bei Fehlern während der Wahl: Neustart des Vorgangs nach Timeout
- Nach erfolgreicher Wahl
- Leader stellt verloren gegangene Vorschläge und Bestätigungen bereit
- Wiederaufnahme des Broadcast-Modus
