Ein illustrierter Beweis des CAP-Theorems

Der CAP-Theorem ist ein fundamentaler Satz in verteilten Systemen, der besagt, dass jedes verteilte System höchstens zwei der folgenden drei Eigenschaften haben kann.

• Konsistenz
• Verfügbarkeit
• Partitionstoleranz

Dieser Leitfaden fasst Gilbert und Lynchs Spezifikation und den Beweis des CAP-Theorems mit Bildern zusammen!

Was ist der CAP-Theorem?

Der CAP-Satz besagt, dass ein verteiltes System nicht gleichzeitig konsistent, verfügbar und partitionstolerant sein kann. Klingt einfach genug, aber was bedeutet es, konsequent zu sein? verfügbar? partition tolerant? Heck, was genau meinst du überhaupt mit einem verteilten System?

In diesem Abschnitt stellen wir ein einfaches verteiltes System vor und erklären, was es bedeutet, dass dieses System verfügbar, konsistent und partitionstolerant ist. Eine formale Beschreibung des Systems und der drei Eigenschaften finden Sie in der Arbeit von Gilbert und Lynch.

Ein verteiltes System

Betrachten wir ein sehr einfaches verteiltes System. Unser System besteht aus zwei Servern, $ G_1 $ und $ G_2 $. Beide Server verfolgen dieselbe Variable, $ v $, deren Wert anfänglich $ v_0 $ ist. $G_1$ und $G_2$ können miteinander und auch mit externen Clients kommunizieren. So sieht unser System aus.

Ein Client kann von jedem Server schreiben und lesen anfordern. Wenn ein Server eine Anforderung empfängt, führt er alle gewünschten Berechnungen durch und antwortet dann dem Client. Zum Beispiel, hier ist, was ein Schreib aussieht.

Und so sieht eine Lektüre aus.

Nachdem wir unser System eingerichtet haben, wollen wir uns ansehen, was es bedeutet, dass das System konsistent, verfügbar und partitionstolerant ist.

Konsistenz

So beschreiben Gilbert und Lynch Konsistenz.

Jede Leseoperation, die nach Abschluss einer Schreiboperation beginnt, muss diesen Wert oder das Ergebnis einer späteren Schreiboperation zurückgeben

In einem konsistenten System erwartet ein Client, sobald er einen Wert auf einen Server schreibt und eine Antwort erhält, diesen Wert (oder einen frischeren Wert) von jedem Server zurückzuerhalten, von dem er liest.

Hier ist ein Beispiel für ein inkonsistentes System.

Unser Client schreibt $ v_1 $ in $ G_1 $ und $ G_1 $ bestätigt, aber wenn er von $ G_2 $ liest, erhält er veraltete Daten: $ v_0 $.

Andererseits ist hier ein Beispiel für ein konsistentes System.

In diesem System repliziert $ G_1 $ seinen Wert auf $ G_2 $, bevor eine Bestätigung an den Client gesendet wird. Wenn der Client also von $ G_2 $ liest, erhält er den aktuellsten Wert von $ v $: $ v_1 $.

Verfügbarkeit

So beschreiben Gilbert und Lynch die Verfügbarkeit.

Jede Anforderung, die von einem nicht fehlerhaften Knoten im System empfangen wird, muss zu einer Antwort führen

Wenn unser Client in einem verfügbaren System eine Anforderung an einen Server sendet und der Server nicht abgestürzt ist, muss der Server schließlich auf den Client antworten. Der Server darf die Anforderungen des Clients nicht ignorieren.

Partitionstoleranz

So beschreiben Gilbert und Lynch Partitionen.

Das Netzwerk darf beliebig viele Nachrichten verlieren, die von einem Knoten an einen anderen gesendet werden

Dies bedeutet, dass alle Nachrichten, die $ G_1 $ und $ G_2 $ aneinander senden, gelöscht werden können. Wenn alle Nachrichten gelöscht würden, würde unser System so aussehen.

Unser System muss trotz beliebiger Netzwerkpartitionen korrekt funktionieren können, um partitionstolerant zu sein.

Der Beweis

Nachdem wir uns nun mit dem Begriff der Konsistenz, Verfügbarkeit und Partitionstoleranz vertraut gemacht haben, können wir beweisen, dass ein System nicht alle drei gleichzeitig haben kann.

Angenommen, es existiert ein System, das konsistent, verfügbar und partitionstolerant ist. Das erste, was wir tun, ist unser System zu partitionieren. Es sieht so aus.

Als nächstes haben wir unsere Client-Anfrage, dass $ v_1 $ in $ G_1 $ geschrieben wird. Da unser System verfügbar ist, muss $G_1 $ antworten. Da das Netzwerk jedoch partitioniert ist, kann $ G_1 $ seine Daten nicht auf $ G_2 $ replizieren. Gilbert und Lynch nennen diese Ausführungsphase $\alpha_1 $.

Als nächstes haben wir unseren Client eine Leseanforderung an $ G_2 $ . Da unser System verfügbar ist, muss $ G_2 $ antworten. Und da das Netzwerk partitioniert ist, kann $ G_2 $ seinen Wert nicht von $ G_1 $ aktualisieren. Es gibt $ v_0 $ zurück. Gilbert und Lynch nennen diese Ausführungsphase $\alpha_2 $.

$ G_2 $ gibt $ v_0 $ an unseren Client zurück, nachdem der Client bereits $ v_1 $ in $ G_1 $ geschrieben hat. Dies ist inkonsistent.

Wir haben angenommen, dass ein konsistentes, verfügbares, partitionstolerantes System existiert, aber wir haben nur gezeigt, dass es eine Ausführung für ein solches System gibt, in dem das System inkonsistent handelt. Daher existiert kein solches System.