Verteilter Commit und Konsens

Verteilte Commit- und Konsensprotokolle ermöglichen es mehreren Datenbankknoten, atomar über das Ergebnis einer Transaktion und eine konsistente Reihenfolge von Operationen zu entscheiden, selbst wenn Knoten und Netzwerke ausfallen können.

Definition

Atomares Festschreiben (Atomic Commitment) ist das Problem, sicherzustellen, dass alle teilnehmenden Knoten in einer verteilten Transaktion entweder dem Commit oder dem Abbruch zustimmen; Konsens ist das allgemeinere Problem, dass verteilte Knoten trotz Ausfällen über einen einzigen Wert oder ein geordnetes Log übereinstimmen, was zur Konsistenz von Datenbankrepliken verwendet wird.

Scope

Dieses Thema behandelt das atomare Festschreiben von Transaktionen, die mehrere Standorte umfassen – das Zwei-Phasen-Commit-Protokoll, seine blockierende Schwäche und das nicht-blockierende Drei-Phasen-Commit – sowie die Konsensprotokolle (Paxos, Raft), die verwendet werden, um replizierte Zustandsmaschinen und Commit-Logs konsistent zu halten. Es behandelt diese Mechanismen in ihrer Datenbankrolle zur Gewährleistung von Atomarität und Replika-Übereinstimmung. Die allgemeine Theorie verteilter Systeme zu Konsens, Fehlermodellen und Unmöglichkeitsergebnissen wird auf Themen der verteilten Datenverarbeitung verschoben, indem sie zitiert und nicht dupliziert wird.

Core questions

• Wie erreicht das Zwei-Phasen-Commit eine atomare Festschreibung über Knoten hinweg?
• Warum kann das Zwei-Phasen-Commit blockieren, und wie begegnet das Drei-Phasen-Commit diesem Problem?
• Wie halten Konsensprotokolle wie Paxos und Raft Repliken in Übereinstimmung?
• Wie hängt Konsens mit dem atomaren Festschreiben in replizierten Datenbanken zusammen?
• Wie beeinflussen Ausfälle und Netzwerkpartitionen die Garantien, die diese Protokolle bieten?

Key concepts

• atomares Festschreiben
• Zwei-Phasen-Commit (2PC)
• Koordinator und Teilnehmer
• Blockierung und das Koordinator-Ausfallproblem
• Drei-Phasen-Commit (3PC)
• Paxos
• Raft
• repliziertes Log / Zustandsmaschinenreplikation

Key theories

Zwei-Phasen-Commit

Ein Koordinator fordert alle Teilnehmer auf, sich vorzubereiten (abzustimmen) und weist sie dann, nur wenn alle zustimmen, an, die Transaktion festzuschreiben; das Protokoll garantiert Atomarität, blockiert jedoch, wenn der Koordinator ausfällt, während die Teilnehmer unsicher sind.

Nicht-blockierendes Festschreiben

Das Drei-Phasen-Commit fügt eine Vor-Commit-Phase hinzu, sodass die Teilnehmer auch bei Ausfall des Koordinators eine konsistente Entscheidung treffen können, wodurch das blockierende Verhalten des Zwei-Phasen-Commits unter bestimmten Ausfallannahmen beseitigt wird.

Konsens für replizierten Zustand

Paxos und das verständlichere Raft ermöglichen es einer Reihe von Repliken, sich trotz Abstürzen auf ein geordnetes Log von Operationen zu einigen, wodurch die fehlertolerante Übereinstimmung bereitgestellt wird, die moderne Datenbanken zur Replikation von Commit-Entscheidungen und Konfigurationen verwenden.

Clinical relevance

Verteilter Commit und Konsens sind die Grundlage für die Zuverlässigkeit von Multi-Knoten-Datenbanken: Sie stellen sicher, dass eine Transaktion, die mehrere Shards betrifft, entweder überall oder nirgendwo festgeschrieben wird und dass replizierte Systeme nach Ausfällen nicht divergieren, was für die Korrektheit in Finanz- und global verteilten Datensystemen unerlässlich ist.

History

Das Zwei-Phasen-Commit war der frühe Standard für verteilte Atomarität; Skeen und Stonebraker analysierten 1983 sein blockierendes Verhalten und motivierten das Drei-Phasen-Commit. Lamports Paxos (veröffentlicht 1998) lieferte fehlertoleranten Konsens, und Raft (Ongaro und Ousterhout, 2014) bot eine verständlichere Alternative; beide untermauern heute die Replikation in weit verbreiteten verteilten Datenbanken.

Debates

Atomares Festschreiben versus Konsens für replizierte Transaktionen

Das Zwei-Phasen-Commit garantiert Atomarität, blockiert aber bei Koordinatorausfall, während die konsensbasierte Replikation Ausfälle zu höheren Kosten toleriert; Systemdesigner diskutieren, wie Commit und Konsens kombiniert werden können, um sowohl Atomarität als auch Verfügbarkeit über replizierte, partitionierte Daten hinweg zu erreichen.

Key figures

• Leslie Lamport
• Dale Skeen
• Diego Ongaro
• John Ousterhout

Seminal works

• lamport1998
• skeen1983
• ongaro2014

Frequently asked questions

Warum blockiert das Zwei-Phasen-Commit, und ist das ein Problem?

Wenn der Koordinator ausfällt, nachdem die Teilnehmer dem Commit zugestimmt haben, aber bevor sie die Entscheidung erfahren, bleiben diese Teilnehmer mit gesperrten Ressourcen zurück und können nicht sicher selbst festschreiben oder abbrechen. Dieses Blockieren bindet Ressourcen, bis der Koordinator wiederhergestellt ist, weshalb Drei-Phasen-Commit und konsensbasierte Ansätze entwickelt wurden, um dies zu reduzieren oder zu beseitigen.

Wie unterscheidet sich Konsens vom atomaren Festschreiben?

Atomares Festschreiben erfordert eine einstimmige Zustimmung zum Commit – jede einzelne Ablehnung oder jeder Ausfall kann einen Abbruch erzwingen. Konsens erfordert nur eine Mehrheit, um sich auf einen Wert zu einigen, und kann trotz einer Minderheit ausgefallener Knoten Fortschritte machen. Datenbanken verwenden atomares Festschreiben für Cross-Shard-Transaktionen und Konsens, um die Repliken jedes Shards konsistent zu halten.