Globale Snapshots und Zustände

Ein globaler Snapshot erfasst eine konsistente Ansicht des Zustands einer verteilten Berechnung – den lokalen Zustand jedes Prozesses plus die Nachrichten im Transit –, ohne das System anzuhalten.

Definition

Ein konsistenter globaler Zustand ist eine Sammlung lokaler Prozesszustände und Kanalinhalte, die einem konsistenten Schnitt entsprechen – einem, bei dem für jeden aufgezeichneten Nachrichtenempfang auch der entsprechende Sendevorgang aufgezeichnet wird –, sodass der Zustand während der Berechnung hätte entstehen können, auch wenn kein globaler Zeitpunkt beobachtet wurde.

Scope

Dieses Thema behandelt den Begriff eines konsistenten globalen Zustands und des ihn definierenden Schnitts, den Marker-basierten Snapshot-Algorithmus von Chandy-Lamport und seine Annahmen (FIFO-Kanäle, zuverlässige Zustellung) sowie die Anwendung von Snapshots zur Erkennung stabiler Eigenschaften wie Terminierung und Deadlock-Erkennung und zur verteilten Checkpoint-Erstellung und Wiederherstellung.

Core questions

• Was macht einen aufgezeichneten globalen Zustand konsistent und nicht unmöglich?
• Wie kann ein solcher Zustand aufgezeichnet werden, während die Berechnung weiterläuft?
• Wie werden stabile Eigenschaften wie Terminierung und Deadlock aus Snapshots erkannt?

Key theories

Konsistente Schnitte

Ein globaler Zustand entspricht einem Schnitt durch die Ereignissequenzen der Prozesse; der Schnitt ist genau dann konsistent, wenn er unter der Happened-Before-Beziehung abgeschlossen ist, wodurch sichergestellt wird, dass keine Nachricht empfangen wird, bevor sie im aufgezeichneten Zustand gesendet wurde.

Chandy-Lamport Snapshot-Algorithmus

Ein Initiator zeichnet seinen Zustand auf und sendet einen Marker auf jedem ausgehenden Kanal; jeder Prozess, der zum ersten Mal einen Marker empfängt, zeichnet seinen Zustand auf und zeichnet dann eingehende Nachrichten auf anderen Kanälen auf, bis deren Marker eintreffen, wodurch Kanalinhalte erfasst werden.

Erkennung stabiler Eigenschaften

Da Snapshots einen Zustand erfassen, in dem sich das System hätte befinden können, ist jede stabile Eigenschaft (eine, die wahr bleibt, sobald sie gilt, wie Terminierung oder Deadlock), die in einem Snapshot erkannt wird, tatsächlich gültig, was Snapshots zu einem allgemeinen Erkennungswerkzeug macht.

Clinical relevance

Snapshot-Algorithmen ermöglichen die verteilte Checkpoint/Restart-Funktion zur Fehlerbehebung, einschließlich des asynchronen Snapshotting, das von modernen Stream-Processing-Engines verwendet wird, um Exactly-Once-Garantien zu bieten, sowie die Deadlock- und Terminierungserkennung in langlaufenden Berechnungen.

History

Der Algorithmus von Chandy und Lamport aus dem Jahr 1985 lieferte die erste praktische Methode zur Aufzeichnung eines konsistenten globalen Zustands, ohne das System anzuhalten; Mattern und andere verallgemeinerten die zugrunde liegende Schnitttheorie, und die Technik wurde später grundlegend für die fehlertolerante Stream-Verarbeitung.

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

Erfordert die Erstellung eines Snapshots das Anhalten des Systems?

Nein. Der Chandy-Lamport-Algorithmus zeichnet einen konsistenten globalen Zustand auf, während die Berechnung fortgesetzt wird, indem Marker entlang der Kanäle verbreitet werden; der aufgezeichnete Zustand ist einer, in dem sich das System hätte befinden können, auch wenn es nie global angehalten wurde.