10 Begriffe der Verlässlichkeit (dependability)
Verfügbarkeit (availability)
= Wahrscheinlichkeit, dass System zu willkürlichem Zeitpunkt korrekt arbeitet
System kann sofort verwendet werden
Zuverlässigkeit (reliability)
System kann in gg. Zeitintervall ohne Fehler laufen
99% pro Stunde = (0.99)^24 = 78,5% pro Tag
Sicherheit (safety)
trotz Ausfalle geschieht keine Katastrophe
Wartbarkeit (mantainability)
wie einfach ein System nach Ausfall repariert werden kann
i.S.v. gute Wiederherstellbarkeit
Ausfall (Failure)
wenn System Versprechen nicht erfüllen kann
also wenn es einen Service nicht anbieten kann
System macht nicht, was es soll
Error (Fehler)
Teil des Systemzustands, der zu einem Ausfall führen kann
Zustand, der nicht vorkommen soll
Fehler (Fault)
Ursache fuer einen Error
Fehlertoleranz
System kann Service bieten trotz vorhandener Fehler
bsp. Fehlerkorrigierende Codes bei Übertragungen
safety property = nichts schlechtes passiert
liveness property = irgendwann passiert was gutes
Fehler (Fault) - 3 Arten und 2 Beispiele
Bsp.:
Übertragungsmedium
Programmierer
Arten:
transient
treten einmal auf und verschwinden dann
einfach Operation wiederholen
bsp. Vogel bei Mikrowellen-Übertragung
intermittent
tritt auf, verschwindet wieder, tritt wieder auf, ...
bsp. Wackelkontakt
permanent
bleibt bis Fehlerkomponente ersetzt wird
5 Ausfallmodelle
Crash Failure
Omission Failure
Timing Failure
Response Failure
Arbitrary Failure
Was ist Crash Failure
System hält an, bis dahin läuft es korrekt
nach Anhalten, reagiert Server nicht mehr
einzige Lösung: Reboot (bei OS)
Was ist Omission Failure
2 Arten
System antwortet nicht auf eingehende Anfrage
Receive Omission
nimmt keine Nachricht an
z.B. Server bekam Nachricht nicht
Send Omission
schickt keine Nachricht
z.B. bei send buffer overflow
Was ist Timing Failure
System antwortet außerhalb eines bestimmten Zeitintervalls
z.B. Streamingdienst liefert mehr Daten als Buffer aufnehmen kann
Leistungsfehler, wenn zu spät
Was ist Response Failure
Antwort ist falsch
Value Failure
Wert der Antwort ist falsch
z.B. Suchmaschine liefert unpassende Seiten
State-Transition failure
Abweichung vom korrekten Kontrollfluss
z.B. wenn Server mit Anfrage nichts anfangen kann
Was ist Arbitrary failure
auch "Byzantine failures"
willkürliche Antworten zu willkürlichen Zeiten
2 Arten:
a) omission failure
.= Komponente macht nicht, was es soll
b) commission failure
.= Komponente macht, was es nicht soll
2 Arten von Systemen - wozu gehört VS
asynchrone Systeme
keine Annahmen über Zeit für Nachrichtenübertragung
oder Ausführungszeit von Prozessen
-> erhält Prozess P keine Antwort von Q, kann keine Schlussfolgerung gezogen werden
könnte gecrashed sien
oder nur langsam
oder Nachrichten verloren
synchrone Systeme
Zeit für Prozesse und Nachrichtenübermittlung sind zeitbeschränkt
reagiert Q nicht auf Anfragen von P
kann man schlussfolgern, dass Q gecrashed ist
pure synchrone Systeme nur theoretisch
VS ist partially synchronous
meist verhält es sich synchron
keine zeitliche Einschränkung, wann es sich asynchron verhält
-> man kann timeouts verwenden, um zu bestimmen, dass Server gecrashed ist
manchmal kann die Schlussfolgerung aber falsch sein
5 Arten von Halte-Fehler
(von wenigstens zum gravierendsten)
P versucht zu erkennen, dass Q gecrashed ist
Fail-stop failure
reliabel festellbarer crash-failure
Kommunikationsverbindung ist nicht fehlerhaft
P kennt worst-case-delay bei Kommunikation mit Q
Fail-noisy failure
wie fail-stop
P kommt aber nur "eventually" zum Ergebnis, dass Q gecrashed ist
Zeit steht nicht im vornhinein fest
Fail-silent failure
Kommunikation nicht fehlerhaft
P kann crash failures nicht von omission failures unterscheiden
Fail-safe failures
willkürliche Fehler von Prozess Q
Fehler können keinen Schaden anrichten
Fail-arbitrary failures
willkürliche Fehler von Q
failures können unbeobachtbar sein
und korrektes Verhalten anderer Prozesse schaden
3 Techniken für Fehlertoleranz
Failure masking by redundancy
Prozess Resilienz
Failure masking and replication
3 Arten des Failure masking by redundancy
information redundancy
Extra-Bits hinzufügen, um beschädigte Bits zu kompensieren
z.B. Hamming code
time redundancy
Handlung wird bei Bedarf wiederholt
Transaktionen nutzen den Ansatz
oder Anfragen an Server erneut senden
besonders bei transient oder intermittent failures
physical redundancy
Extra-Geräte oder Prozesse verwenden
Was ist Prozess-Resilienz?
durch Prozess-Gruppen erreicht
mehrere identische Prozesse einer Gruppe zuordnen
alle Mitglieder der Gruppe erhalten eine Nachricht, die an die Gruppe ging
Gruppen können dynamisch sein
Gruppen erstellen/ löschen
Prozess kann gruppe während der Laufzeit wechseln
Prozess kann Mitglied in verschiedenen Gruppen sein
für Sender sehen Gruppen wie ein logischer Prozess aus
2 Arten von Gruppen bei Prozessgruppen
flache
kein single-point of failure
schwieriger, Entscheidungen zu treffen
hierarchisch
z.B. mit Koordinator
geht Koordinator kaputt, funktioniert ganze Gruppe nicht mehr
Koordinator kann allein Entscheidungen treffen
wenn Koordinator ausfällt, wählen restliche Server neuen
Was ist Failure masking and replication
a) primary based
primary-backup protocol
Prozesse hierarchisch organisiert
primary koordiniert alle writes
b) replicated-write
in flachen Gruppen
aktive Replikation
und quorum-basierte Protokolle
Was ist k-fault tolerant?
ein System, dass Ausfälle in k Komponenten übersteht
Was ist das Einigungsproblem - allgemein?
Gruppe von Prozessen verhalten sich wie einzelner, sehr robuster Prozess
jeder Prozess in der Gruppe führt die gleichen Operationen aus, in der gleichen Reihenfolge
-> Prozesse müssen sich einigen, welche Operationen sie ausführen
Fehlerfreie Prozesse finden in endlicher Zeit Konsens
Fehler machen Abstimmung schwierig
4 unabhängige Aspekte beim Einigungsproblem
synchron vs. asynchrone Prozesse
asynchron = Prozesse können beliebig viel mehr arbeiten
synchron = es gibt Konstante c, so dass jeder Prozess mindestens einen Schritt macht, wenn ein anderer c + 1 Schritte macht
Beschränkte vs. unbeschränkte Verzögerung (bounded/ unbounded)
es gibt globale Maximalzeit für Nachrichtenzustellung
Geordnete Auslieferung
ungeordnet: Nachrichten eines Senders können sich überholen
geordnet: Nachrichten eines Senders kommen in der Reihenfolge des Sendens an
Unicast vs. Multicast
unicast = Nachrichten nur an einen Empfänger
multicast = Nachrichten an alle Prozesse der Gruppe gleichzeitig
-> 2^4 = 16 Fälle
Wann ist eine Einigung möglich?
Einigung möglich, wenn:
synchron und beschränkt
synchron und geordnet
multicast und geordnet
Was ist flooding consensus
Algorithmus arbeitet in Runden
in jeder Runde schickt Prozess P_i Liste von Befehlen, die er bisher gesehen hat, zu jedem anderen Prozess
am Ende der Runde verbinden die Prozesse alle erhaltenen Listen zu einer
von der Liste wird nächster Befehl deterministisch bestimmt
Auswahlalgorithmus ist für alle Prozesse gleich
bemerkt ein Prozess, dass ein anderer gecrashed ist, wartet er bis zur nächsten Runde
vielleicht konnte ein anderer Prozess vor dem Crash noch Nachrichten von dem fehlerhaften Prozess bekommen
Wieviele Prozesse braucht man, wenn k ausfallen?
k+1 wenn mindestens eine gut funktionieren soll
2k + 1 für Fehlertoleranz
wenn die Prozesse böswillig Agieren - dann muss man sich einigen
3k + 1 für willkürliche Fehler
Bedingungen für Einigung
n Gruppenmitglieder
man braucht 3k + 1 Gruppenmitglieder, um Einigung zu finden
k = Anzahl der fehlerhaften Prozesse
Beispiel mit 3 Prozessen
einer spinnt
mit 2 kann man keine Mehrheit bilden - unentschieden
Prozess P ist primary
n-1 sind backups
Annahmen:
Client sendet Wert v (entweder wahr oder falsch) zu Primary
Nachrichten können verloren gehen
Verlust von Nachrichten wird erkannt
corrupted messages werden erkannt und nicht beachtet
Empfänger kann Sender erkennen
Bedingungen für byzantine agreement:
Jeder nicht-fehlerhafte Backup-Prozess speichert den gleichen Wert
Ist P nicht-fehlerhaft, dann speichert jeder Backup-Prozess, was P gesandt hat
-> wenn P nicht fehlerhaft, impliziert 2 1
-> wegen 1: Backups können den gleichen Wert speichern, der aber nicht der Wert ist, den client gesandt hat
Allgemein 3 Bedingungen für Einigung
Prozesse produzieren gleichen Ausgabewert
jeder Ausgabewert muss valide sein
jeder Prozess muss irgendwann Ausgabe erzeugen
Einigungsalgorithmus - Allgemein
3 Bedingungen
Annahme: synchron und beschränkt
Gruppe von n Prozessen P_i
einige arbeiten inkorrekt oder böswillig
jeder Prozess i macht Vorschlag für Einigung und teilt den allen anderen Prozessen mit
nach geg. Zeit entscheidet jeder Prozess und teilt Entscheidung allen anderen mit
Bedinungen an Einigungsalgorithmus:
Terminierung - jeder korrekte Prozess entscheidet
Einigung - alle korrekten Prozesse einigen sich gleich
Integrität - haben alle Prozesse denselben Wert vorgeschlagen, entscheiden sich alle auch dafür
Algorithmus von Attiya und Welch
Annahmen
Vorgehen
Korrektheit
maximale Anzahl f < n von möglichen Ausfällen festlegen
n Prozesse arbeiten rundenweise zusammen
eine Runde besteht aus 2 Schritten:
Prozess erzeugt Nachricht und schickt ihn mit multicast an Gruppe
alle ankommenden Nachrichten werden empfangen und zu neuen Informationen verarbeitet
neue Runde startet, wenn alle ihre letzte Runde beendet haben oder ausgefallen sind
Einigungsalgorithmus braucht f + 1 Runden
Vorgehen:
1. Schritt Runde 1: jeder Prozess überlegt sich Vorschlag und teilt ihn anderen Prozessen mit
2. Schritt Runde 1: jeder Prozess empfängt Vorschläge der anderen Prozesse und sammelt sie in Menge
in jeder weiteren Runde sendet jeder Prozess im ersten Schritt Vorschläge, die er noch nicht gesendet hat und empfängt im zweiten Schritt die Vorschläge der anderen
nach f + 1-ten Runde entscheidet Prozess für Minimum der ihm bekannten Vorschläge
Korrektheit:
bei f +1 Runden mit f Ausfällen gibt es mindestens eine Runde, in der alle Prozesse korrekt liefen
funktionierende Prozesse in sauberer Runde haben auch in allen vorherigen Runden funktioniert
-> alle in der Runde haben die gleichen Vorschläge gesammelt
-> daran kann sich in folgenden Runden nichts ändern
-> am Ende entscheiden sich alle für selben Vorschlag
Terminierung klappt -> Rundenzahl vorher festgelegt
Einigung klappt -> siehe Korrektheit
Integrität klappt -> alle Prozesse von Anfang an dabei -> haben dasselbe Minimum
Byzantisches Problem
Allgemein
Voraussetzunen
Ziel
Allgemein:
wie Generäle die entscheiden müssen, ob sie gemeinsam angreifen oder sich zurückziehen
Kommunikation durch zuverlässige Boten
Kommandeure können Verräter sein
Voraussetzungen:
es gibt 1 Befehlshaber
n-1 Generäle
Befehlshaber gibt Befehl - Angreifen oder Zurückziehen
durch Kommunikation sollen sich die Generäle einigen, welchen Befehl sie bekommen haben
Möglichkeiten:
Befehlshaber ist Verräter -> er gibt Generälen widersprüchliche Befehle
ein General der Verräter -> er lügt teilweise, welchen Befehl er bekommen hat
Ziel:
sich auf Vorgehen einigen
Nicht: herausfinden wer oder wieviele Verräter sind
Terminierung -> durch Rundenzahl
Einigung -> wie oben bei Korrektheit
Integrität -> wenn Befehlshaber kein Verräter, entscheiden sich alle Generäle für seinen Befehl
Fault Tolerance und Performanz
keine Annahmen über fehlerhafte Server
Sender können erkannt werden
Wann gibt es beim byzantinischen Problem keine Lösung?
für n = 3 gibt es kein korrektes Vorgehen
es müssen mehr als 2/3 der Drittel der Generäle korrekt handeln
f < n/3
sonst keine Eingung möglich
Byzantinisches Problem
Protokoll
prepare messages
commit essages
Ausführen und Antwort an Client
Byzantine agreement protocol (BAP)
braucht f + 1 Runden
1. Runde - Befehlshaber gibt Befehl
2. Runde - jeder General berichtet jedem anderen, welchen Befehl er bekommen hat
3+ in jeder weiteren Runde berichten Generäle einander, was sie in vorheriger Runde gehört haben
Generäle speichern alles in Baumstruktur
Entscheidung am Ende rekursiv durch Mehrheitsregeln der im Baum gespeicherten Nachrichten
Befehlshaber selbst stimmt nicht mit ab
bei Tabelle werden fehlerhafte Prozesse rausgehaltenClient nimmt Antwort die von min k +1 Replikas geschickt wurde
Was besagt das CAP Theorem?
jedes Netzwerksystem mit geteilten Daten hat nur zwei der folgenden drei Eigenschaften:
Consistency = replizierte Daten erscheinen als einzige, aktuelle Kopie
Availability = Updates werden immer irgendwann ausgeführt
P - Tolerant to partitioning of process group = z.B. weil Verbindungen ausfallen
Wie funktioniert Failure detection?
a) durch Anfragen "are your alive?"
b) durch warten auf Nachrichten
wenn es genug Kommunikation gibt
-> immer Timout-Mechanismus für Entscheidung
Semantiken bei Server-Ausfall
(bei RPC Ausfällen)
was bei Serverausfall garantiert werden kann
Ziel: weder Anfragen verloren gehen, noch mehrmals ausführen
5 Fehlerarten bei RPC
Client findet Server nicht
-> Transparenz geht verloren
Möglicher Umgang: exception
z.B. wenn Client Software nicht up to date
nicht alle Sprachen haben Exceptions
Nachricht vom Client zum Server geht verloren
Client hat Timer
keine Antwort? -> Nachricht nochmal senden
gehen zu viele verloren -> Server nicht auffindbar
Server crashes nach Nachrichtenerhalt
Unterschied ob Server Nachricht schon verarbeiten konnte oder nicht
Nachricht vom Server zum Client geht verloren
mit Timer herausfinden und nochmal anfragen
Sequenznummern verwenden, dass Server Wiederholungen erkennt
so Dopplungen vermeiden
bei zweiter Anfrage einfach Antwort schicken
Client crashes nach Nachrichtenversand
orphan (computation)
wenn Anfragender Prozess (parent) nicht mehr vefügbar ist für Antwort
Folgen:
Ressourcen verschwendet
Dateien/ Ressourcen blockiert
Client rebootet und bekommt gleich orphan-Antwort
4 Semantiken, wenn Server nach Nachrichtenerhalt ausfällt
at-least-once semantics
Client wartet auf Reboot des Servers oder verbindet sich mit anderem
versuchen, bis mindenstens eine Antwort kam
at-most-once semantics
gleich Fehler zurückmelden
nichts garanieren
Client bekommt weder Hilfe, noch Versprechen bei Servercrash
einfach zu implementieren
exactly-once semantics
Wunschziel
kann nicht garantiert werden
Was ist idempotent?
= Anfrage, die mehrmals ausgeführt werden kann ohne (negative) Folgen/ Seiteneffekte
4 Lösungen für Client-Ausfall nach Nachrichtenversand
a) orphan extermination
Client hält log vor RPC-Aufrufen
nach Reboot alle orphans töten
nicht gut
b) reincarnation
Zeit in sequenziell geordnete Epochen aufteilen
bei Reboot schickt Client Nachricht an Server mit aktueller Epoche
Server töten rpc
c) gentle reincarnation
bei Epoch-Nachricht suchen Server Clients für RPCs
und töten nur die, für die sie keine Besitzer finden
d) expiration
jeder RPC bekommt Standardzeit für Ausführung
braucht er mehr, muss er fragen
Kausales Multicasting - 2 Bedingungen und Folge
Bedingungen
ts(m)[i] <= VC_j[i] + 1
kein Prozess j verarbeitet Nachricht von Prozess i, ohne die Vorgängernachricht von i verarbeitet zu haben
ts(m)[i] <= VC_j[k]
Prozess j verarbeitet Nachricht von Prozess i nur, wenn er alle Nachrichten verarbeitet hat, die i beim Absenden der Nachricht verarbeitet hatte
=> müsste bei allen Prozessen dieselbe Ausführungsreihenfolge erzwingen
Was ist feedback implosion?
wenn alle Empfänger Empfangsbestätigung schicken wird Sender überlastet
besonders wichtig bei Replikation für Performanz (weniger für Fehlertoleranz)
3 Lösungen für Skalierbarkeit (bei Multicast und geordnete Auslieferungsreihenfolgen)
Nonhierarchical feedback control
feedback suppression
im Scalable Reliable Multicasting (SRM) Protokoll
keine Bestätigung durch Empfänger
nur Rückmeldung bei fehlenden Nachrichten
Feedback an gesamte Gruppe
Feedback mit willkürlicher Verzögerung
andere Gruppenmitglieder unterdrücken dann eigenes Feedback
fehlende Nachricht wieder multicast
Hierarchical feedback control
Empfängergruppe in Untergruppen eingeteilt
Untergruppen bilden Baum
innerhalb Untergruppe reliables multicast für kleine Gruppen
jede Untergruppe hat lokalen Koordinator
Kommunikation innerhalb Subgruppen wie gewohnt
Kommunikation zwischen Gruppen über Koordinatoren
Nachricht wird immer an benachbartete Koordinatoren weitergegeben
außer Koordinator der Nachricht geschickt hat
Baum-Verwaltung ist sehr aufwändig
meist wird Multicasting auf Anwendungsebene implementiert
Gossip-based scalable reliable multicasting
z.B. push-pull anti-entropy scheme (Section 4.4)
node P wählt willkürlich node Q und tauscht Updates mit ihr
pushes Updates die Q nicht kennt
holt sich Updates die P nicht kennt
Verteilung von Updates im System wird langsamer
Was ist atomic multicasting?
6 Arten
2 Möglichkeiten des Crashes eines Prozesses
= virtuell synchron reliable multicasting mit vollkommen geordneter Zustellung
Entweder Nachricht zu allen Gruppenmitgliedern oder zu keinem
Beispiel mit aktiver Replikation
Prozesse führen Operationen lokal auf Daten aus
Nachrichten bekommen Zeitstempel, kommen und Queue und Zeitstempel entscheidet über Ausführen
2 Möglichkeiten für Crash von P
a) nach Abschluss des Multicast
b) vor Anfrage für Update
6 Arten:
Was ist virtual synchrony?
group view
= Nachricht m ist mit Liste von Prozessen assoziiert, die es liefern sollen
an Anwendungen
Sicht auf Prozesse in der Gruppe, die Sender hatte beim Versenden
jeder Prozess in der Gruppe hat die gleiche Sicht
view change
Prozess kommt dazu oder geht
während Nachricht versandt wird
vc
-> Nachricht muss durch alle Prozesse weitergeleitet werden, entweder vor vc oder gar nicht
Fehlgeschlagener Versand von m nur erlaubt, wenn der Sender von m ausfällt
= reliabler multicast nur garantiert für nicht fehlerhaften Prozessen in G
-> multitasks passieren in Epochen, die durch vc getrennt sind
4 Arten Nachrichten zu ordnen
Nicht geordnet
virtuell synchron
keine Garantie bzgl. Ordnung
-> Prozesse erhalten Nachrichten in unterschiedlicher Ordnung
FIFO
Nachrichten vom gleichen Prozess immer in gleicher Reihenfolge
von unterschiedlichen Prozessen egal
Kausal geordnet
kausale Abhängigkeit auch bei unterschiedlichen Sendern gewahrt
z.B. mit Vektor-Zeitstempeln
Vollkommen geordnet
alle Gruppenmitglieder erhalten alle Nachrichten in gleicher Reihenfolge
und dann in Kombination mit (1), (2) oder (3)
Was sind Commit-Protokolle
3 Arten
distribut commit Problem
allgemeineres Problem des atomic mutlicasting
= Operation von jedem Mitglied in Prozessgruppe ausführen lassen oder von keinem
3 Arten:
(1-Phasen-Protokoll)
es gibt Koordinator
der sagt allen Teilnehmern, was sie zu tun haben
Nachteil:
Teilnehmer können Koordinator nicht sagen, wenn sie Operation nicht ausführen können
2-Phasen-Protokoll
3-Phasen-Protokoll
Wie funktioniert das 2-Phasen Protokoll?
auch "blocking commit protocol"
Ablauf
Phase 1 - WAHL
Schritt 1
Koordinator schickt VOTE-REQUEST zu allen Teilnehmern
Schritt 2
Teilnehmer erhällt VOTE-REQUEST
und schickt:
VOTE-COMMIT, wenn er Operation ausführen kann
VOTE-ABORT, wenn nicht
Phase 2 - ENTSCHEIDUNG
Schritt 3
Koordinator sammelt Stimmen von Teilnehmern
Alle zugestimmt? -> schickt GLOBAL-COMMIT
min einer nicht zugestimmt? -> schickt GLOBAL-ABORT
Schritt4
handelt je nach GLOBAL-COMMIT vs. GLOBAL-ABORT
Probleme
Koordinator und Teilnehmer haben blockierte Zustände, während sie auf Nachrichten warten
-> Prozesse könnten unendlich warten, wenn sie auf Antwort eines ausgefallenen Prozesses warten
Time-Out Mechanismen verwenden
Wie funktioniert das 3-Phasen Protokoll?
kann im Gegensatz zum 2-Phasen Protokoll auch Ausfall des Koordinators verkraften
hier auch Koordinator und mehrere Teilnehmer
Zustand von Koordinator und Teilnehmer erfüllt 2 Bedingungen:
Es gibt keinen Zustand, von dem man direkt zu COMMIT oder ABORT kommt
Kein Zustand in dem man finale Entscheidung treffen kann und von dem man zum COMMIT Zustand kommen kann
Ablauf:
Koordinator schickt VOTE-REQUEST
Schickt Teilnehmer ABORT, schickt Koordinator GLOBAL-ABORT
sonst PREPARE-COMMIT
jeder Teilnehmer muss Prepare-commit anerkennen
Koordinator schickt GLOBAL-COMMIT
wartet Koordinator in PREPARE-COMMIT
und antwortet ein Teilnehmer nicht
kann er GLOBAL-COMMIT schicken
weil der Teilnehmer hatte VOTE-REQUEST beantwortet
gecrashter Teilnehmer kann mit seinem Recovery-Protokoll den bestätigten Commit nachholen
kein Teilnehmer kann im Zustan PRECOMMIT sein, wenn ein anderer nicht dort ist
Was ist Wiederherstellung
= nach einem Fehler wieder zu einem korrekten Zustand kommen
Arten
Vorwärts
von gegenwärtigen fehlerhaften Zustand
in neuen fehlerfreien Zustand bringen, von dem System aus weiterarbeiten kann
-> man muss auftretende Fehler vorher kennen
Bsp. erasure correction
verloren geganges Paket wird aus erfolgreich übermittelten Paketen konstruiert
Rückwärts
vom gegenwärtigen fehlerhaften Zustand
zu einem vorherigen fehlerfreien Zustand bringen
-> man muss Systemzustand von Zeit zu Zeit festhalten
mit Checkpoints
Bsp. verloren gegangene Pakete wieder schicken
bietet keine volle Transparenz
Was sind distributed snapshot?
= consistent global state
wenn P den Erhalt einer Nachricht gespeichert hat, gibt es einen Prozess Q, der das Versenden der Nachricht gespeichert hat
am besten zum letzten snapshot zurückkehren
= recovery line
Was ist checkpointing
coordinated checkpointing
alle Prozesse speichern gleichzeitig ihren Zustand
gespeicherte Zustände sind automatisch global konsistent
einfach: mit 2-Phasen blockierendem Protokoll
1. Koordinator schickt CHECKPOINT-REQUEST zu allen Prozessen
-> Prozesse speichern Zustand und legen alle einkommenden Nachrichten in eine Queueu
und schicken Koordinator Bestätigung
3. Koordinator schickt CHECKPOINT-DONE der allen Prozessen erlaubt weiterzumachen
Verbesserung: incremental snapshot
Checkpoint requests nur an Prozesse schicken, die auf Recovery vom Koordinator angewiesen sind
sind die Prozesse, die eine Nachricht erhalten haben, die kausal abhängigen von einer Nachricht des Koordinators seit dem letzten Checkpoint
independent checkpointing
jede Prozess nimmt ab und zu snapshot
domino effect
nach Fehler zurück zu einem global konsistenten Zustand
wenn letzte Snapshots nicht passen, weiter zurück
-> Erinnerung: Empfangen einer Nachricht braucht Senden
kann bis zum initial state gehen
viel komplizierter als coordinated checkpointing
bei jeder Nachricht mitschicken, wann der letzte eigene Checkpoint war
Was ist message logging?
braucht man weniger Checkpoints (besser für Performanz)
letzten Checkpoints + Nachrichten bis vor dem Fehler
sender-based logging
Prozess speichert Nachrichten vor dem Versand
receiver-based logging
Nachricht wird vor dem Weiterleiten zur Anwendung gespeichert
Annahme: piecewise deterministic execution model
Ausführung eines Prozesses als Abfolge von Intervallen, in denen Ereignisse stattfinden
Intervall endet mit letzten Ereignis vor einem nicht-deterministischem Ereignis
-> wenn man alle nicht-deterministischen Ereignisse speichert, kann man die gesamte Ausführung wiederholen
orphan process
Prozess, der Crash eines anderen Prozesses überlebt
aber dessen Zunstand inkonsistent mit Zustand des gecrashten Prozesses nach dem Recovery ist
Worauf muss man beim Recovery achten?
jede empfangene Nachricht muss einen Absender haben
sonst muss der Empfänger-Prozess ebenfalls zu seinem letzten Checkpoint zurück
kann zu einem Dominoeffekt führen
Last changeda year ago