Zustandsautomatenreplikation

Die Zustandsautomatenreplikation macht einen Dienst fehlertolerant, indem sie deterministische Repliken ausführt, die dieselben Befehle in derselben Reihenfolge ausführen, sodass überlebende Repliken den Ausfall anderer maskieren.

Definition

Zustandsautomatenreplikation ist eine Technik, bei der ein Dienst als deterministischer Zustandsautomat modelliert und über mehrere Server repliziert wird, die alle dieselbe geordnete Sequenz von Client-Befehlen anwenden, wodurch sichergestellt wird, dass fehlerfreie Repliken in identischen Zuständen bleiben und ausgefallene ersetzen können.

Scope

Dieses Thema behandelt das Zustandsautomatenmodell eines Dienstes, die Anforderung, dass Repliken deterministisch sein müssen, die Verwendung von Totalordnungs- (atomarem) Broadcast oder Konsens zur Einigung über die Befehlssequenz und den Kontrast zur primär-sekundären (passiven) Replikation. Es behandelt auch den Umgang mit Nicht-Determinismus, die Rekonfiguration von Repliken und die Erweiterung auf byzantinische Repliken.

Core questions

• Warum müssen Repliken deterministisch sein und Befehle in einer identischen Reihenfolge verarbeiten?
• Wie wird die vereinbarte Befehlsreihenfolge durch Konsens oder atomaren Broadcast erzeugt?
• Wie unterscheidet sich die aktive (Zustandsautomaten-)Replikation von der passiven primär-sekundären Replikation?

Key theories

Der Zustandsautomatenansatz

Jeder deterministische Dienst kann fehlertolerant gemacht werden, indem er repliziert und jede Replik mit demselben geordneten Befehlsstrom versorgt wird; vorausgesetzt, weniger als die tolerierte Anzahl von Repliken fällt aus, bleibt der Dienst korrekt und verfügbar.

Ordnung durch Konsens

Die erforderliche Gesamtordnung der Befehle ist genau ein atomarer Broadcast, der dem Konsens entspricht, sodass replizierte Zustandsautomaten typischerweise auf einem Konsensprotokoll wie Paxos oder Raft aufbauen.

Byzantinische Zustandsautomatenreplikation

Die Erweiterung des Ansatzes zur Tolerierung beliebiger Fehler erfordert eine Einigung unter mehr als zwei Dritteln der Repliken und eine Ergebnisabstimmung durch Clients, wie sie in der praktischen byzantinisch fehlertoleranten Replikation realisiert wird.

Clinical relevance

Die Zustandsautomatenreplikation ist die Standardmethode zum Aufbau eines hochverfügbaren, stark konsistenten Dienstes; replizierte Protokolle, Koordinationsdienste und viele verteilte Datenbanken sind Zustandsautomaten, die von einem konsensgeordneten Befehlsstrom gesteuert werden.

History

Lamports Artikel über logische Uhren skizzierte die Idee des replizierten Zustandsautomaten 1978; Schneiders Tutorial von 1990 machte es zum kanonischen Rahmenwerk für fehlertolerante Dienste; und Castros und Liskovs PBFT von 1999 erweiterte es auf den byzantinischen Kontext, eine Linie, die später Blockchain-Designs beeinflusste.

Debates

Aktive versus passive Replikation

Die aktive (Zustandsautomaten-)Replikation führt Befehle auf allen Repliken für schnelles Failover aus, verschwendet aber Arbeit und erfordert Determinismus; die passive primär-sekundäre Replikation wird nur auf einem Primärsystem ausgeführt und überträgt den Zustand, was Arbeit spart, aber eine Failover-Verzögerung und einen einzigen Ausführungspunkt mit sich bringt.

Key figures

• Fred Schneider
• Leslie Lamport
• Miguel Castro
• Barbara Liskov

Seminal works

• schneider1990
• lamport1998
• castro1999

Frequently asked questions

Warum muss der replizierte Dienst deterministisch sein?

Wenn Repliken bei gleicher Eingabe unterschiedliche Entscheidungen treffen könnten – aufgrund von Zufälligkeit, Timing oder Thread-Scheduling –, würden ihre Zustände trotz identischer Befehle divergieren. Determinismus garantiert, dass derselbe geordnete Befehlsstrom überall denselben Zustand erzeugt.