Algorithmen des Konsenses

1) Was ist Konsens und warum ist er notwendig?

Konsens - Aushandlung des gleichen Werts/der gleichen Wertfolge zwischen mehreren Knoten bei Ausfällen und Verzögerungen. Traditionell wird das Problem der Zustandsreplikation (State Machine Replication, SMR) gelöst: Es gibt eine deterministische Zustandsmaschine und eine allgemeine Reihenfolge der Operationen.

• Consensus (SMR): eine einzige Gesamtreihenfolge von Befehlen → linearer Speicher/Registrierung, Cluster-Metadaten, Transaktionskoordinatoren.
• Quorum-Operationen ohne totale Ordnung (Dynamo-like, CRDT): ermöglichen Divergenz und anschließende Fusion; ersetzen keinen Konsens, wo eine globale Serialisierung notwendig ist.

2) Zeit- und Fehlermodell

2. 1 Zeitmodell

Asynchrones Netzwerk: Verzögerungen sind unbegrenzt; Das FLP-Theorem ⇒ Es ist unmöglich, sowohl Sicherheit als auch Gelassenheit ohne zusätzliche Annahmen zu garantieren.
Teilsynchron (oft in der Praxis): Nach einem unbekannten T „verhält“ sich das System synchron - darauf verlassen sich die meisten Algorithmen (Raft, Paxos).
Synchron: starre Zeitlimits für Kanäle (selten in der Produktion, außer bei speziellen Netzwerken/PTPs).

2. 2 Fehlermodell

Crash-fault tolerant (CFT): Knoten können fallen/hängen, verhalten sich aber nicht böswillig.
Byzantine-fault tolerant (BFT): Knoten können lügen/Nachrichten fälschen. Es erfordert 3f + 1 Knoten für die Toleranz gegenüber f byzantinischen.

3) Eigenschaften des Konsenses

Sicherheit: Konsistenz (zwei korrekte Knoten lösen keine unterschiedlichen Werte).
Lebendigkeit: Wenn das Netzwerk „gesund“ ist, ist die Lösung erreicht.
Linearisierung (Linearität): Operationen werden als atomar in einer einzigen Reihenfolge „gesehen“.
Langlebigkeit: Getroffene Entscheidungen werden nicht zurückgenommen (Schutz durch Log/Quorum).

4) Quoren, Mehrheiten und Schnittmengen

In der CFT-Welt der Klassiker: Quorum> N/2. Die Aufzeichnungen und die Wahl des Führers nutzen die Schnittmenge der Quoren, so dass die beiden „gültigen“ Operationen nicht kollidieren.
In der BFT-Welt: Die Quoren 2f + 1 von 3f + 1 bieten eine Kreuzung von mindestens f + 1 ehrlichen Knoten.

Durchdringungsregel: Jedes Quorum muss einen ≥1 gemeinsamen ehrlichen Knoten (CFT) oder ≥f+1 (BFT) haben.

5) Statusreplikation (Protokoll + Anwendung)

• Schnappschüsse (Zustandsschnitt, nach dem frühe Einträge gelöscht/kompiliert werden können).
• Zeitschriftenkomposition und Logtriim.
• Determinismus-Checks (gleiche Code-/Config-Version).

6) Führungs- und Nicht-Leadership-Systeme

Leadership (Raft, Multi-Paxos, ZAB): Ein Leader serialisiert Einträge → einfacher mental und operativ, besser latency auf einem stabilen Leader.
Leaderless/Multilider (EPaxos, Caesar): mehr Parallelität und Toleranz gegenüber dem Führer, aber schwieriger Umsetzung und Konflikt-Lösung; Gewinne sind bei kleinen Konflikten der Teams sichtbar.

7) Klassische CFT-Algorithmen

7. 1 Paxos/Multi-Paxos (und Praxis)

Die Idee: zwei Phasen (prepare/propose), Akzeptorversprechen, Mehrheitsbeschlüsse. Multi-Paxos hinterlässt einen „stabilen Führer“ und verwandelt den Betrieb nach dem „Aufwärmen“ in einen Ein-Runden-Betrieb (für Neuaufnahmen).

• Ein flexibles, aber schwer umsetzbares Modell.
• Re-Konfigurationen durch spezielle Einträge (joint consensus).
• In der Praxis - Bibliotheken/Engines (Chubby/Spanner-Generation).

7. 2 Raft

Zerlegt für Lernfähigkeit: Leader-Auswahl, Logreplikation, Re-Konfiguration.

Wahl: gelegentliche Zeiträume, Abstimmung über die Thermen; ein Führer pro Amtszeit.
AppendEntries: Leader streamt Einträge, überwacht Präfixübereinstimmung (Index/Term), Commit durch Mehrheitsfixierung.
Read-path: lease-reads (mit einem starken Leader) oder read-index für lineare Lesungen.
Reconfig: „joint configuration“ (joint) - Knoten stimmen in zwei Clustern vor dem Übergang ab.

Vorteile: einfacher zu entwickeln/debag, starke Invarianten der Ordnung. Nachteile: Der Führer ist ein Druckpunkt.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: Leader sendet Transaktionen, Wiederherstellungsphase, zxid (Epoche + Index).
VRR: „views“ (Ansichten) mit primärem Replikat, ähnlich wie Multi-Paxos im Geiste.

8) Nichtlider/Multilider CFTs

8. 1 EPaxos

Kein ständiger Anführer: Jeder Knoten kann ein Team initiieren.
Konfliktbefehle erhalten eine Teilreihenfolge; konfliktfrei - Commit in 1-2 RTT lokal.
Gewinn an Geo-Verteilung bei geringem Konflikt, aber komplexen Abhängigkeits-/Graph-Codes.

8. 2 Caesar, Mencius

Variationen, die Latenz/Balancing und Betrieb im WAN optimieren.

9) BFT-Algorithmen und PoS-Familie

9. 1 PBFT (Practical BFT)

Drei Phasen (pre-prepare/prepare/commit), erfordert 3f + 1 Knoten.
Geringe Latenz auf lokalen Netzwerken, Straßen durch mehrstufige und O (N ²) Nachrichten.

9. 2 Tendermint (BFT-PoS-Stil)

Runden mit Proposal und zwei Abstimmungen (prevote/precommit).
Deterministischer Vorschlagsvalidierer, Timeouts, partielle Synchronität.
Gut für permissioned/PoS-Netzwerke mit Dutzenden/Hunderten von Validatoren.

9. 3 HotStuff (und Derivate)

Das dreiphasige Schema wurde in „Pakete“ mit Quorum-Zertifikaten (QC) vereinheitlicht.
Die lineare Komplexität der Kommunikation, die Unterstützung von Paketierung und paralleler Paipline, ist praktisch für Implementierungen in Blockchains (z. B. Diem/Move-Ökosystem).
Mit Schwellensignaturen (threshold signatures) wird der Datenverkehr reduziert.

9. 4 PoW/kumulativer Konsens (in Kürze)

Nicht BFT im engeren Sinne, sondern probabilistische Konvergenz (die Kette mit der größten Arbeit). Vorteile: Einfachheit/Offenheit; Nachteile: Energie, ~ Sekunden-Minuten bis zur Finalität.

10) Lesungen: linear, sequentiell und zwischengespeichert

Lineare Lesungen: Leader mit aktiver Lease oder über Read-Index (Raft) → Quorum-Bestätigung.
Konsistent: Kann von jedem Knoten gelesen werden, jedoch ohne Frischegarantien.
Follower liest: zulässig bei schwachen Anforderungen; für Caches - ok.

11) Re-Konfiguration (Änderung der Clusterzusammensetzung)

Es erfordert zwei überlappende Konfigurationen (joint consensus): Alle Commits durchlaufen die Quoren beider Konfigurationen → ohne „Löcher“.
Eins nach dem anderen hinzufügen/entfernen, Quorumgröße beachten.
Die Übertragung der Führung (Leadership Transfer) reduziert Pausen.

12) Leistung und Tuning

12. 1 Verzögerungen

Leadership-Algorithmen: 1 RTT pro Aufnahme (mit stabilem Leader) + Replikation.
Geo-Distribution: WAN RTT dominiert → Verwenden Sie lokale Regionen + regionale Replikation oder EPaxos/HotStuff-Ansätze.

12. 2 Durchsatz

Batching (Gruppierung von Befehlen), parallele AppendEntries, Log-Page-Cache, parallele Anwendung (wenn Operationen geschaltet werden).
Laufwerke: NVMe/Log auf separatem Gerät,'O _ DIRECT '/AIO, großes' fsync '-Interview mit SLA-Einschränkungen (Durability/Latency-Kompromiss).

12. 3 Schwänze p99

Vermeiden Sie heiße Knoten (der Anführer ist ständig allein): periodische Rotation oder Read-Offload auf Follower.
Überwachen Sie GC-Pausen (JVM/Go), CPU-Pins, NUMA.

13) Geographie und Topologien

1 Region, 3 Zonen: klassischer CFT-Cluster (N = 3/5).
2 Regionen: vermeiden - kein verlässliches Quorum bei 1-1 Trennung.
3 + Regionen: führend in der „Mitte“ oder führerlose Algorithmen; Regionale Proxies/lokale Fronten mit asynchronem Log sind möglich.

14) Praktische Fragen der Ausbeutung

14. 1 Schnappschüsse und Erholung

Schwellenwert für Protokollgröße/Anzahl der Transaktionen.
Übertragung des Schnappschusses an neue Knoten; Überprüfung der Prüfsummen.

14. 2 Überwachung

Führung: Wer die Führungskraft ist, wie viele Begriffe (term/epoch) gewechselt haben.
Лаги: `append_latency`, `commit_index - applied_index`.

Quorum-Gesundheit: „Lebt die Mehrheit/2f + 1?“

Die Größe der Zeitschrift/Geschwindigkeit kompakzii, die Reihe snapschotow.
Für BFT: Stimmenanteil, Hintertür der Unterzeichner, QC-Verzögerungen.

14. 3 Sicherheit/Konsistenz des Codes

Protokollversionsfähigkeit auf Draht, Migration mit Protokollkompatibilität.
Fencing-Token auf externe Effekte (siehe "Distributed Locks'): Führungsbegriff (term) an CRON/Jobs übertragen.

15) Anti-Muster

Setzen Sie einen Konsens „um der Mode willen“, wo ein DBMS oder Quorumlesungen ohne Serialisierung ausreichen.
Mischen Sie CP und AP ohne klare Grenzen (CAP) → unvorhersehbare UX.
Neubewertung von PoW/PoS für Unternehmensaufgaben mit Dutzenden von Knoten (schwierig/teuer).
Ignorieren Sie die Re-Konfiguration und die „sich überschneidenden Quoren“, wenn sich die Zusammensetzung ändert.
Mangel an Read-Barrier (Lease/Read-Index) → „schmutzige“ Lesungen.
2-Knoten-Cluster ausführen (keine Mehrheit).
Disketten- und fsync-Unterschätzung: „Alles fliegt im Speicher“ - bis zum ersten Neustart.

16) Checkliste der Wahl

1. Fehlermodell: CFT (Crashs) oder BFT (böswillig)?
2. Geographie: Eine Region/drei Zonen oder WAN? RTT entscheidet.
3. Semantik der Lesungen: Braucht man lineare Lesungen? Lease/read-index/follower-rides.
4. Last: Erwartungen nach p50/p99, throughput; Wir brauchen Multi-Leadership.
5. Betriebsschwierigkeit: Bibliothek/fertige Engine (etcd/ZK/Consul/Raft-libs) gegen eigene Implementierung.
6. Rekonfiguration: Häufig? Wir brauchen einen gemeinsamen Konsens und Instrumente der Migration.
7. Integrationen: Externe Nebenwirkungen - gibt es Fencing nach epoch/term?
8. Sicherheit: Knotenauthentifizierung, Kanalverschlüsselung, Protokollversionskontrolle.
9. Test-Playbooks: Partition, GC-Stop, Kill Leader, Slow Disk, Clock Skew.
10. Beobachtbarkeit: Leader/Lags/Log-Metriken und Alerts werden angepasst.

17) Mini-Handbuch: Wann was zu nehmen ist

etcd/Raft-Cluster für DC-interne Konfigurationen/Sperren/Koordination.
ZooKeeper/ZAB für Dienste, die bereits an ZK gebunden sind (alte Stacks, Warteschlangen, Führung).
Multi-Paxos durch fertigen Service/Bibliothek in hochspezialisierten Systemen.
EPaxos bei Geo-Verteilung und geringer Konflikte der Befehle.
Tendermint/HotStuff für permissioned networks/PoS-Leier mit Dutzenden bis Hunderten von Validatoren und Finalitätsanforderungen.
Dynamo-like/CRDTs, wenn kein Konsens erforderlich ist, sondern Verfügbarkeit/Skalierung mit anschließender Fusion wichtig ist.

18) Beispiele für Schnittstellen (Pseudo)

18. 1 Commit-Aufnahme (Raft-Stil)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Read-Index für lineares Lesen (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Gemeinsame Konfiguration

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff-approximiert)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

F: Warum nicht zwei Knoten und einen Tie-Breaker verwenden?
A: Zwei Knoten ohne einen dritten Schiedsrichter geben kein Quorum bei der Trennung. Sie benötigen ≥3 (CFT) oder 3f + 1 (BFT).

F: Warum ist Raft „einfacher“ Paxos?
A: Klare Zerlegung, verständliche Invarianten von Log und Konfiguration; leichter umzusetzen und zu begleiten.

Q: Wie man schnell liest, ohne den Führer zu belasten?
A: Follower-reads (sequentiell) für unkritische oder lease-reads/read-index für lineare; zwischenspeichern.

F: Was tötet p99?
A: WAN-RTT, Scheibe fsync, GC-Füße, überhitzter Führer, große Schnappschüsse in der „Hauptverkehrszeit“.

F: Ist ein Konsens für den Cache/das Verzeichnis erforderlich?
A: Wenn die tatsächliche Consistency ausreicht, nicht. Wenn transaktionale Invarianten erforderlich sind, ja.

20) Ergebnisse

Konsens ist ein Instrument für strikte Kohärenz und Ordnung. Wählen Sie einen Algorithmus basierend auf dem Fehlermodell und der Geographie; Stellen Sie Quorumschnittpunkte, korrekte Re-Konfiguration, lineare Lesungen, wo es kritisch ist, und Beobachtbarkeit zur Verfügung. Vergessen Sie nicht das Fencing für externe Effekte, Snap-Shots und die Disziplin von Zeitschriften. Dann ist die Replikation des Status vorhersehbar und die Vorfälle sind selten und verständlich.