Konsensalgorithmen in verteilten Systemen verstehen
Praktischer Leitfaden zu Konsensalgorithmen: Raft, Paxos und Leader Election, mit Beispielen, wann und warum verteilte Systeme sie brauchen.
Wenn mehrere Server sich auf einen einzigen Wert einigen müssen — welcher Knoten der Leader ist, wie der aktuelle Zustand eines replizierten Logs aussieht, ob eine Transaktion committet werden soll — brauchen sie einen Konsensalgorithmus. Ohne Konsens zerfallen verteilte Systeme in Partitionen, die sich über die Realität uneinig sind, und deine Nutzer sehen veraltete Daten, doppelte Operationen oder komplette Ausfälle.
Konsens ist das Fundament unter jeder replizierten Datenbank, jeder verteilten Queue und jedem Koordinationsdienst. Wer ihn versteht, denkt anders über die Systeme nach, die darauf aufbauen.
Warum Konsens schwer ist
In einem Ein-Server-System gibt es eine einzige Quelle der Wahrheit. In einem verteilten System verschwindet diese Garantie. Server stürzen ab, Netzwerke werden partitioniert, Nachrichten kommen in falscher Reihenfolge an oder gar nicht. Das FLP-Unmöglichkeitsresultat beweist, dass kein deterministischer Algorithmus Konsens in einem asynchronen System garantieren kann, in dem auch nur ein einziger Prozess ausfallen könnte.
Praktische Konsensalgorithmen umgehen das mit Timeouts und Randomisierung — sie opfern theoretische Garantien für Zuverlässigkeit in der Praxis.
// The fundamental problem consensus solves
interface ConsensusScenario {
nodes: string[];
proposedValues: Map<string, string>;
outcome: 'agree' | 'disagree' | 'stuck';
}
// ❌ Without consensus — each node believes something different
const withoutConsensus: ConsensusScenario = {
nodes: ['A', 'B', 'C'],
proposedValues: new Map([
['A', 'commit'], // A thinks the transaction committed
['B', 'abort'], // B thinks it aborted
['C', 'commit'], // C agrees with A but B disagrees
]),
outcome: 'disagree', // Split brain — data corruption
};
// ✅ With consensus — all nodes converge on one value
const withConsensus: ConsensusScenario = {
nodes: ['A', 'B', 'C'],
proposedValues: new Map([
['A', 'commit'],
['B', 'commit'], // B accepted the majority decision
['C', 'commit'],
]),
outcome: 'agree', // All nodes agree — consistency preserved
};Raft: Konsens verständlich gemacht
Raft wurde gezielt so entworfen, dass es verständlich ist. Es zerlegt Konsens in drei Teilprobleme: Leader Election, Log-Replikation und Safety. Jeder Teil lässt sich unabhängig nachvollziehen.
// Simplified Raft node state
type NodeRole = 'follower' | 'candidate' | 'leader';
interface RaftNode {
id: string;
role: NodeRole;
currentTerm: number;
votedFor: string | null;
log: LogEntry[];
commitIndex: number;
lastApplied: number;
}
interface LogEntry {
term: number;
index: number;
command: string;
}
// Leader election state machine
function handleElectionTimeout(node: RaftNode): RaftNode {
// Follower hasn't heard from leader — become candidate
return {
...node,
role: 'candidate',
currentTerm: node.currentTerm + 1,
votedFor: node.id, // Vote for self
};
}
function handleVoteRequest(
node: RaftNode,
candidateId: string,
candidateTerm: number,
candidateLogLength: number
): { granted: boolean; updatedNode: RaftNode } {
// Reject if candidate's term is stale
if (candidateTerm < node.currentTerm) {
return { granted: false, updatedNode: node };
}
// Grant vote if we haven't voted yet and candidate's log
// is at least as up-to-date as ours
const canVote = node.votedFor === null || node.votedFor === candidateId;
const logUpToDate = candidateLogLength >= node.log.length;
if (canVote && logUpToDate) {
return {
granted: true,
updatedNode: {
...node,
currentTerm: candidateTerm,
votedFor: candidateId,
role: 'follower',
},
};
}
return { granted: false, updatedNode: node };
}Die Wahl läuft in Runden ab, die Terms genannt werden. Wenn ein Follower innerhalb seines Election-Timeouts keinen Heartbeat vom Leader erhält, erhöht er seinen Term und fordert Stimmen an. Ein Kandidat, der Stimmen von einer Mehrheit erhält, wird Leader. Da pro Term nur ein Leader gewinnen kann, hat der Cluster immer höchstens einen Leader.
Log-Replikation in der Praxis
Sobald ein Leader gewählt ist, nimmt er Client-Anfragen entgegen und repliziert sie an die Follower. Ein Log-Eintrag gilt erst als committet, wenn eine Mehrheit der Knoten ihn in ihre Logs geschrieben hat.
// Leader replicating entries to followers
interface AppendEntriesRequest {
term: number;
leaderId: string;
prevLogIndex: number;
prevLogTerm: number;
entries: LogEntry[];
leaderCommit: number;
}
interface AppendEntriesResponse {
term: number;
success: boolean;
matchIndex: number;
}
function leaderReplicateEntry(
leader: RaftNode,
command: string,
followers: string[]
): void {
const entry: LogEntry = {
term: leader.currentTerm,
index: leader.log.length,
command,
};
// Append to leader's own log immediately
leader.log.push(entry);
// Send to all followers in parallel
const ackCount = 1; // Leader counts as one acknowledgment
const majority = Math.floor((followers.length + 1) / 2) + 1;
// When majority acknowledges:
// leader.commitIndex = entry.index;
// Apply command to state machine
// Respond to client with success
console.log(
`Entry ${entry.index} needs ${majority} acks ` +
`(have ${ackCount}, waiting for ${majority - ackCount} more)`
);
}// ❌ Committing before majority acknowledgment
function unsafeCommit(leader: RaftNode, entry: LogEntry): void {
leader.commitIndex = entry.index; // Committed with only leader's copy
applyToStateMachine(entry); // Could lose data if leader crashes
}
// ✅ Committing only after majority acknowledgment
function safeCommit(
leader: RaftNode,
entry: LogEntry,
ackCount: number,
clusterSize: number
): boolean {
const majority = Math.floor(clusterSize / 2) + 1;
if (ackCount >= majority) {
leader.commitIndex = entry.index;
applyToStateMachine(entry);
return true; // Safe to respond to client
}
return false; // Not yet committed — keep waiting
}
function applyToStateMachine(entry: LogEntry): void {
console.log(`Applying: ${entry.command}`);
}Die Mehrheitsanforderung macht Raft fehlertolerant. In einem 5-Knoten-Cluster können 2 Knoten ausfallen, und die verbleibenden 3 bilden immer noch eine Mehrheit. Die committeten Einträge überleben garantiert, weil mindestens ein Knoten jeder zukünftigen Mehrheit sie besitzt.
Timing der Leader Election
Election-Timeouts müssen randomisiert sein, um geteilte Stimmverhältnisse (Split Votes) zu verhindern — also den Fall, dass zwei Kandidaten gleichzeitig Wahlen starten und keiner eine Mehrheit bekommt.
// Election timeout configuration
interface ElectionConfig {
minTimeoutMs: number;
maxTimeoutMs: number;
heartbeatIntervalMs: number;
}
// Rule: heartbeat << election timeout
// This ensures followers hear from the leader
// well before they start unnecessary elections
const config: ElectionConfig = {
minTimeoutMs: 150, // Minimum election timeout
maxTimeoutMs: 300, // Maximum election timeout
heartbeatIntervalMs: 50, // Leader sends heartbeats at this interval
};
function randomElectionTimeout(config: ElectionConfig): number {
const range = config.maxTimeoutMs - config.minTimeoutMs;
return config.minTimeoutMs + Math.floor(Math.random() * range);
}
// In production systems like etcd:
// - Heartbeat interval: 100ms
// - Election timeout: 1000-2000ms
// - The 10x ratio gives plenty of margin for network delaysDie Randomisierung bricht die Symmetrie. Würden alle Knoten denselben Timeout verwenden, würden alle gleichzeitig Kandidaten, die Stimmen würden sich teilen, der Timeout liefe erneut ab, und das Spiel wiederholte sich — ein Livelock. Randomisierte Timeouts sorgen dafür, dass in der Regel ein Knoten zuerst in den Timeout läuft und die Wahl gewinnt, bevor andere starten.
Wann Konsens sinnvoll ist — und wann nicht
Konsens ist teuer — er erfordert Netzwerk-Roundtrips und Mehrheitsquoren. Nicht jedes System braucht ihn.
# When consensus IS needed:
leader_election:
examples: ["database primary selection", "distributed lock service"]
why: "Only one node should act as leader at a time"
replicated_state_machine:
examples: ["etcd", "ZooKeeper", "CockroachDB"]
why: "All replicas must apply the same operations in the same order"
distributed_transactions:
examples: ["two-phase commit coordinator", "saga orchestrator"]
why: "All participants must agree on commit or abort"
# When consensus is OVERKILL:
caching:
alternative: "Eventual consistency — stale cache entries are acceptable"
analytics:
alternative: "Approximate counts — exact agreement not required"
event_streaming:
alternative: "At-least-once delivery — consumers handle duplicates"
dns_propagation:
alternative: "Eventual consistency — TTLs handle staleness"Wenn dein System vorübergehende Uneinigkeit zwischen Knoten tolerieren kann, brauchst du keinen Konsens. Eventual Consistency mit Konfliktauflösung ist einfacher, schneller und verfügbarer. Reserviere Konsens für Fälle, in denen Uneinigkeit Korrektheitsverletzungen verursacht — etwa wenn zwei Knoten gleichzeitig glauben, der Datenbank-Primary zu sein.
Die wichtigsten Erkenntnisse
- Konsens löst das Einigungsproblem — mehrere Knoten konvergieren trotz Abstürzen und Netzwerkfehlern auf einen einzigen Wert
- Raft zerlegt Konsens in Leader Election, Log-Replikation und Safety — jeder Teil ist unabhängig verständlich
- Mehrheitsquoren sorgen für Fehlertoleranz — ein 5-Knoten-Cluster übersteht 2 Ausfälle bei erhaltener Konsistenz
- Randomisierte Election-Timeouts verhindern Split Votes — Symmetriebruch ist essenziell für Liveness
- Konsens ist teuer — reserviere ihn für Fälle, in denen Uneinigkeit Korrektheitsprobleme verursacht, nicht Performanceprobleme
- Produktivsysteme (etcd, ZooKeeper, CockroachDB) übernehmen die Komplexität — verstehe die Prinzipien, damit du sie richtig konfigurierst
