CAP Theorem nach 20 Jahren
Eric Brewer sprach im Jahr 2000 anläßlich seiner Keynote an der PODC Konferenz aus, was vor ihm schon andere beobachteten: Ein verteiltes Datenbanksystem kann nicht gleichzeitig hochverfügbar und ausfallsicher sein und auch noch konsistente Daten garantieren. Eine der drei Eigenschaften bleibt immer auf der Strecke.
Im Juni 2002 veröffentlichten Nancy Lynch und Seth Gilbert ihren theoretischen Beweis von Brewers Vermutung. Damit entstand das CAP Theorem und es begleitet uns seither auf Schritt und Tritt.
Wer sich mit der Verarbeitung und Analyse massiver Datenmengen befasst, also mit Big Data, ist täglich mit dem CAP Theorem konfrontiert. Wir untersuchen das CAP Theorem 20 Jahre nach dessen Beweis.
Big Data Cluster – physisch und logisch
Massive Datenmengen werden in verteilten Systemen gehalten. Und auch die Verarbeitung und Analyse erfolgt verteilt: die Programme werden zu den Daten geschickt, auf die einzelnen Server, wo die Daten lagern. Und jeder Server nimmt die Verarbeitung für diejenigen Daten vor, die dort lagern.
Die Abbildung veranschaulicht links ein Big-Data-Cluster, also einen Rechnerverbund, wie er physisch in einem Rechenzentrum aufgebaut wird.
Rechts sehen wir als Beispiel eine Master-Worker-Architektur. Sowohl Master als auch Worker sind Daemon-Prozesse, die auf einzelnen physischen oder virtuellen Servern laufen. Die Kommunikation erfolgt zwischen Master und Worker und im Rechenzentrum erfolgt sie entlang der physischen Netzwerkverbindungen zwischen den betroffenen Servern.
Kommunikation und Transaktion
Die Server kommunizieren ständig untereinander und befolgen dabei vorgegebene Protokolle. Sollen beispielsweise neue Daten geschrieben werden, dann erfolgt dies in einer Transaktion. Eine Transaktion hat einen wohldefinierten Start und ein wohldefiniertes Ende.
Und oft muss in einer Transaktion auf mehrere Server geschrieben werden. Was soll jetzt passieren, wenn zwei der beteiligten Server nicht mehr miteinander kommunizieren können?
Partition Tolerance
Wir erwarten Partitionstoleranz: Das Gesamtsystem soll weiter funktionieren, und zwar auch dann, wenn zwei Systemkomponenten gerade nicht miteinander kommunizieren können.
Die schreibende Transaktion aus unserem Beispiel soll also trotzdem fertig durchgeführt werden. Denn so kann das System als Ganzes weiter arbeiten und das erwarten wir heutzutage.
Doch diese schöne Eigenschaft kommt mit einem Preis: Der Preis ist entweder die Konsistenz oder die Hochverfügbarkeit. Beides ist nicht möglich, wenn wir Partitionstoleranz erwarten.
Hochverfügbarkeit
Wir erwarten gerne auch Hochverfügbarkeit des Gesamtsystems. Jede Anfrage ans Gesamtsystem erhält eine fehlerfreie Antwort. Die Transaktionen sollen nicht mit Rollback beendet werden, so wie wir das aus relationalen Systemen kennen.
Jede Transaktion, sei sie lesend, sei sie schreibend, soll ohne Fehler beendet werden. Die User sollten nicht warten müssen.
Eine Super-Eigenschaft eines verteilten Datensystems. Doch sie kommt mit einem Preis: die Daten können nicht gleichzeitig immer konsistent sein und die Partitionstoleranz kann auch nicht gleichzeitig sichergestellt sein. Nur eines geht gleichzeitig mit der Hochverfügbarkeit.
Konsistenz
Eine Selbstverständlichkeit, eigentlich: Jeder Lesebefehl erhält das Ergebnis des jüngsten Schreibbefehls oder eine Fehlermeldung.
Ein Szenario zur Erläuterung:
Das CAP Theorem filt im Fehlerfall
Das CAP Theorem ist irrelevant in einem nicht verteilten System und es ist auch irrelevant in einem ausnahmslos fehlerfrei funktionierenden verteilten System.
In der Abbildung sehen wir rechts ein typisches Szenario des Normalbetribs:
- Client1 kann einen Schreibbefehl nur an einen Master schicken.
- Der Master schreibt die Daten auf sein eigenes System und repliziert sie zu einem Worker.
- Der Worker schreibt die Daten auf sein eigenes System.
- Und erst jetzt wird die Transaktion Client1 gegenüber als erfolgreich bestätigt.
Client2 kann in diesem System die Daten auch vom Replikat lesen und erhält nur bestätigte Daten. So wird die Leselast im Gesamtsystem verteilt. Ein typisches Szenario.
Doch: Hardware fällt aus. Software auch. Wir müssen mit diesen Fehlern leben.
Wie soll das System reagieren im Fehlerfall? Jetzt kommt das CAP Theorem ins Spiel:
Soll das System hochverfügbar sein?
Dieser Fall ist in der Abbildung in der Mitte dargestellt. Wir nehmen an, der Master könne die Daten nicht zum Worker replizieren.
Hochverfügbarkeit steht in dem Fall vor Konsistenz der Daten und so leben wir damit, dass Client2 veraltete Daten liest.
Ein gutes verteiltes System wird bemerken, wenn die ausgefallene Verbindung wiederbelebt wird und wird die Replikation selbstständig nachholen. Die Daten werden also in hoffentlich nicht allzu ferner Zukunft konsistent werden.
Aber für oft kurze Zeit ist diese Konsistenz nicht garantiert – weil Hochverfügbarkeit vorgeht.
Konsistenz geht vor
Dieser Fall ist in der Abbildung rechts dargestellt. Wiederum kann der Master die Daten nicht replizieren.
Um jetzt die Datenkonsistenz jederzeit zu garantieren, muss der Master den Schreibbefehl zurückweisen. Das System ist also nicht mehr hochverfügbar, denn dann würden wir ja keine zurückgewiesenen Befehle sehen. Dafür garantiert das System jederzeit konsistente Daten.
Tunable Consistency
Seit Nancy Lynch und Setz Gilbert das CAP Theorem 2002 mit Hilfe der theoretischen Informatik bewiesen, wurde viel geforscht und manches wurde relativiert.
Lange wurden Big-Data-Systeme klassifiziert nach CA, AP, CP – je nachdem, welche der beiden Eigenschaften der drei Eigenschaften des Theorem sie aufwiesen.
Doch zwanzig Jahre sind in der IT eine sehr lange Zeit – die Entwicklungen überstürzen sich. Und so ist diese Klassifizierung der Systeme aus heutiger Sicht wenig sinnvoll.
Mit ‘tunable Consistency’ lassen moderne Big-Data-Systeme dem Anwender die Wahl für jede Transaktion:
Was ist wichtiger: Konsistenz des Systems in Bezug auf die betroffenen Daten oder Hochverfügbarkeit des Systems in Bezug auf die betreffende Transaktion.
Erfahre mehr über die Eigenschaften von Big Data Systemen im E-Mail Kurs:
