CAP Theorem
Bei Netztrennung Konsistenz oder Verfügbarkeit wählen
Die Idee und ihr Nutzen
Eine Versicherung speichert ihre Kundendaten in zwei Rechenzentren, in Köln und in Frankfurt, und hält an beiden Orten eine Kopie derselben Daten. Fällt die Leitung zwischen den Rechenzentren aus, kommen Änderungen aus Frankfurt nicht mehr in Köln an, und umgekehrt. Für diese Zeit muss festgelegt sein, wie das Datenbanksystem reagiert. Während der Störung ändert zum Beispiel ein Kunde in Frankfurt seine Bankverbindung, und kurz darauf gibt eine Sachbearbeiterin in Köln eine Auszahlung an diesen Kunden frei. Entweder lehnt das Datenbanksystem in Köln die Auszahlung vorerst ab, damit kein veralteter Stand verwendet wird; oder es beantwortet an beiden Orten weiter alle Anfragen, liefert in Köln die alte Bankverbindung und gleicht die Unterschiede später ab. Dass bei einer solchen Netztrennung kein System zugleich alle Anfragen beantworten und überall den aktuellen Stand liefern kann, beschreibt das CAP-Theorem, ein 2002 bewiesener Lehrsatz der Informatik.
Wie funktioniert es?
Der Standort Frankfurt bedient das Kundenportal, der Standort Köln die Sachbearbeitung. Beide Standorte halten eine eigene Kopie derselben Kundendaten, jeweils in einem Exemplar desselben Datenbanksystems, und beide nehmen Änderungen an. Das Datenbanksystem überträgt jede Änderung an einem Standort über eine Netzleitung zum anderen Standort, damit beide Kopien wieder übereinstimmen. Um 14 Uhr fällt die Leitung zwischen Köln und Frankfurt aus, zum Beispiel durch Bauarbeiten oder ein defektes Netzgerät. Beide Standorte laufen weiter, aber Nachrichten zwischen ihnen kommen nicht mehr an. Um 14:05 Uhr ändert ein Kunde über das Kundenportal seine Bankverbindung, und der Standort Frankfurt speichert die neue Bankverbindung in seiner Kopie. Die Übertragung der Änderung zum Standort Köln scheitert. Um 14:10 Uhr gibt eine Sachbearbeiterin am Standort Köln eine Auszahlung an diesen Kunden frei. Der Standort Köln erreicht den Standort Frankfurt nicht und kann deshalb nicht bestätigen, dass seine Kopie aktuell ist. Wie der Standort Köln jetzt antwortet, hängt von einer Wahl ab, die das Entwicklungsteam vorher für Bankverbindungen getroffen hat. In der ersten Variante lehnt der Standort Köln die Auszahlung vorerst ab, und die Sachbearbeiterin sieht die Meldung „Bankverbindung derzeit nicht prüfbar“. Nach dem Ende der Störung gibt die Sachbearbeiterin die Auszahlung erneut frei. Der Standort Köln liest jetzt die neue Bankverbindung, und die Auszahlung wird ausgeführt. In der zweiten Variante antwortet der Standort Köln mit seiner eigenen, veralteten Kopie, und die Auszahlung geht auf das alte Konto. Nach der Störung tauschen die Standorte die Änderungen wieder aus. Beim Abgleich erkennt das System, dass sich die Bankverbindung während der Trennung geändert hat. Ob das Geld zurückgeholt werden muss, klärt die Fachabteilung.
Ein System aus mehreren Rechnern, die sich über ein Netz abstimmen, heißt verteiltes System. Das CAP-Theorem ist kein Bauplan, sondern ein Lehrsatz über solche Systeme, der eine Grenze beschreibt, die keine Datenbank umgehen kann. Das CAP-Theorem benennt drei Eigenschaften nach ihren englischen Anfangsbuchstaben:
- C steht für Consistency, auf Deutsch Übereinstimmung: Jede Leseanfrage erhält den zuletzt bestätigten Stand, egal an welchem Standort sie gestellt wird. Das System verhält sich so, als gäbe es nur eine einzige Kopie der Daten.
- A steht für Availability, auf Deutsch Verfügbarkeit: Jede Anfrage an einen laufenden Rechner erhält eine inhaltliche Antwort. Eine Fehlermeldung wie „derzeit nicht möglich“ zählt nicht als Antwort.
- P steht für Partition Tolerance, den Umgang mit Netztrennung: Das System arbeitet weiter, auch wenn Nachrichten zwischen seinen Rechnern verloren gehen, weil die Leitung unterbrochen ist. Eine solche Unterbrechung heißt Netztrennung.
Das C des CAP-Theorems ist nicht dasselbe wie das C in ACID, der Abkürzung für die Grundeigenschaften einer Datenbanktransaktion. Eine Datenbanktransaktion ist ein Bündel von Änderungen, das ganz oder gar nicht ausgeführt wird. In ACID meint das C, dass eine Transaktion keine in der Datenbank hinterlegte Regel verletzt, etwa die Regel, dass jeder Vertrag zu einem vorhandenen Kunden gehört.
Netztrennungen lassen sich in verteilten Systemen nicht völlig ausschließen. Tritt eine ein, kann das System für die betroffenen Anfragen nicht zugleich Übereinstimmung und Verfügbarkeit zusagen. Die erste Variante der Auszahlung heißt CP, Übereinstimmung vor Verfügbarkeit: Ein Standort beantwortet keine Anfrage mehr, deren Ergebnis vom anderen Standort abhängen könnte, und meldet stattdessen einen Fehler. Wer eine Antwort erhält, bekommt den bestätigten Stand, aber manche Nutzer bekommen vorübergehend gar keine Antwort. Die zweite Variante heißt AP, Verfügbarkeit vor Übereinstimmung: Beide Standorte beantworten weiter alle Anfragen, notfalls mit ihrem eigenen, möglicherweise veralteten Stand. Nach dem Ende der Trennung müssen die unterschiedlichen Stände dann nach einer festgelegten Regel zusammengeführt werden. Das Entwicklungsteam trifft diese Wahl vorher und für jede Art von Daten getrennt. Ein Beispiel sind die Festlegungen „Bankverbindungen: Übereinstimmung“ und „Vertragsübersicht: Verfügbarkeit“. Für eine Auszahlung ist CP meist die richtige Wahl, auch wenn Sachbearbeiter dann kurz warten müssen. Für die Vertragsübersicht, auf der Kunden ihre Verträge ansehen, kann AP besser sein, weil ein kurz veralteter Stand dort keinen Schaden anrichtet. Ohne Netztrennung kann ein System sowohl übereinstimmende Daten liefern als auch verfügbar sein.
CAP: Auszahlung während einer Netztrennung
Wann ist es sinnvoll und wann nicht?
Das CAP-Theorem hilft
- Das Entwicklungsteam wählt eine verteilte Datenbank aus oder legt fest, wie sich ein System bei einer Netztrennung verhalten soll. Bei der Auswahl prüft das Entwicklungsteam, ob eine Datenbank während einer Trennung die Abfrage einer Bankverbindung in Köln ablehnt oder mit der eigenen Kopie beantwortet und ob sich dieses Verhalten für einzelne Abfragen einstellen lässt. Ohne diese Frage vergleicht das Entwicklungsteam die Datenbanken nur im Normalbetrieb, in dem jede Datenbank übereinstimmende Daten liefert und verfügbar ist.
- Kopien derselben Daten liegen an mehreren Orten, und mehr als ein Ort nimmt Änderungen an. Ist das Verhalten bei einer Netztrennung nicht vorher festgelegt, entscheidet die Voreinstellung der Datenbank. Das Entwicklungsteam erfährt dann erst im Störungsfall, welches Verhalten diese Voreinstellung bewirkt. Mit dem CAP-Theorem legt das Entwicklungsteam vorher fest, dass der Standort Köln eine Auszahlung ablehnt, wenn er die Bankverbindung nicht bestätigen kann.
- Eine Fachabteilung fordert pauschal „immer aktuell und immer erreichbar“. Ohne Klärung verspricht das Entwicklungsteam damit etwas, das bei einer Netztrennung kein System halten kann. Das CAP-Theorem hilft dann, für jede Art von Daten getrennt festzulegen, was im Störungsfall gelten soll. Die Fachabteilung weiß so vorher, ob sie im Störungsfall die Meldung „Bankverbindung derzeit nicht prüfbar“ in Kauf nimmt oder eine Auszahlung auf das alte Konto, die sie später klären muss.
Das CAP-Theorem hilft nicht
- Die Frage ist, warum ein System auch ohne Störung zwischen kurzer Antwortzeit und aktuellem Stand abwägen muss. Dann nutzt das Entwicklungsteam das PACELC Theorem. Das PACELC Theorem beschreibt zusätzlich die Abwägung im Normalbetrieb, über die das CAP-Theorem nichts sagt.
- Die Daten liegen nur in einer einzigen Datenbank ohne Kopie. Dann gibt es keine Kopien, die sich während einer Trennung widersprechen könnten, und das Entwicklungsteam muss keine Wahl für den Störungsfall treffen. Ist die Datenbank nicht erreichbar, fehlt die Antwort ganz.
- Gesucht ist eine Begründung für eine bestimmte Abstufung zwischen strenger Übereinstimmung und reiner Verfügbarkeit. Ein Beispiel ist die Zusage, dass ein Kunde seine eigene Änderung sofort wieder sieht. Solche Abstufungen unterscheidet das CAP-Theorem nicht. Dann schreibt das Entwicklungsteam die gewünschte Zusage einzeln auf und prüft in der Beschreibung der Datenbank, ob die Datenbank sie einhält. So muss das Entwicklungsteam nicht jede Abfrage auf strenge Übereinstimmung einstellen, nur weil das CAP-Theorem keine Zwischenstufe kennt.
- Die Leitung zwischen den Standorten fällt häufig aus, und die Ausfälle sollen seltener werden. Das CAP-Theorem sagt nur, wie sich das System während einer Netztrennung verhalten kann, und macht Ausfälle nicht seltener. Dann lässt das Betriebsteam der Versicherung eine zweite, unabhängig verlegte Leitung zwischen Köln und Frankfurt einrichten. Fällt eine Leitung aus, übertragen die Standorte die Änderungen über die andere weiter. Ausschließen lassen sich Netztrennungen damit nicht, und die Wahl für den Störungsfall bleibt nötig.
Nachteile und typische Fehler
Viele Datenbanken lassen sich für jede einzelne Abfrage auf Übereinstimmung oder auf Verfügbarkeit einstellen. Die Einordnung einer Datenbank als „CP“ oder „AP“ beschreibt deshalb oft nur ihre Voreinstellung, und das Entwicklungsteam muss die Einstellung jeder wichtigen Abfrage selbst festlegen und prüfen. Beide Möglichkeiten haben Nachteile. Wer Übereinstimmung wählt, nimmt in Kauf, dass Sachbearbeiter während der Störung warten und abgelehnte Vorgänge danach erneut anstoßen müssen. Wer Verfügbarkeit wählt, muss Regeln festlegen, wie widersprüchliche Änderungen nach der Störung zusammengeführt werden, und braucht ein fachliches Verfahren für Folgen wie eine Auszahlung auf das alte Konto.
Typische Fehler und woran man sie erkennt:
- Fehlende Zusammenführungsregel: Das Entwicklungsteam wählt Verfügbarkeit, legt aber nicht fest, wie widersprüchliche Änderungen nach der Störung zusammengeführt werden. Ändern beide Standorte während der Trennung denselben Kundendatensatz, behält das Datenbanksystem beim Abgleich nur die zuletzt eingetroffene Änderung und verwirft die andere. Erkennbar ist das an Kunden, deren Änderung aus der Zeit der Störung nach dem Abgleich wieder verschwunden ist.
- Ungeprüfte Voreinstellung: Das Entwicklungsteam verlässt sich auf die Einordnung der Datenbank als „CP“, während einzelne Abfragen mit einer Einstellung laufen, die nur eine Kopie fragt. Während einer Netztrennung beantwortet der Standort Köln eine solche Abfrage mit seiner eigenen, möglicherweise veralteten Kopie. Erkennbar ist das an Tests mit künstlich unterbrochener Leitung, in denen der Standort Köln die alte Bankverbindung liefert.
- Pauschale Wahl: Das ganze System ist auf Übereinstimmung eingestellt, auch die Vertragsübersicht. Während des Leitungsausfalls lehnt der Standort Frankfurt dann auch Anfragen an die Vertragsübersicht ab. Erkennbar ist das an Störungsmeldungen von Kunden, die während des Leitungsausfalls nur ihre Verträge ansehen wollten.
- Vergessene Wiederholung: Der Standort Köln lehnt die Auszahlung während der Störung ab, aber nach der Störung gibt niemand die Auszahlung erneut frei. Erkennbar ist das an Auszahlungen, die nach dem Ende der Störung weiter als abgelehnt stehen.
Weiterführend
Verwandte Ansätze
- Eventual Consistency: beschreibt, wie Kopien nach einer Störung wieder denselben Stand erreichen. Systeme, die Verfügbarkeit wählen, arbeiten meist so.
- Quorum und Consensus: Verfahren, mit denen Systeme, die Übereinstimmung wählen, festlegen, welcher Teil bei einer Trennung weiterarbeiten darf, nämlich der Teil mit der Mehrheit der Rechner.
Beispiele zur Einordnung
An diesen Systemen lässt sich die Wahl beobachten:
- etcd und Apache ZooKeeper: Rechner, die bei einer Trennung nicht zur Mehrheit gehören, nehmen keine Änderungen mehr an. Diese Systeme wählen also Übereinstimmung.
- Apache Cassandra: lässt für jede Lese- und Schreibanfrage einstellen, wie viele Kopien antworten müssen. Genügt eine Kopie, bleiben bei einer Trennung mehr Anfragen möglich, aber Leseanfragen können ältere Stände erhalten. Verlangt man die Mehrheit der Kopien, können Anfragen während einer Trennung scheitern.
- Apache CouchDB: lässt bei einer Trennung an beiden Orten weiter schreiben und bewahrt widersprüchliche Änderungen danach als Konflikte auf, die eine Anwendung auflösen muss.
Quellen
- Seth Gilbert, Nancy Lynch: Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services: der Beweis von 2002, mit den genauen Begriffen von Übereinstimmung und Verfügbarkeit.
- Eric Brewer: CAP Twelve Years Later: How the „Rules“ Have Changed: Rückblick des Urhebers, der die Wahl auf die Zeit der Trennung und einzelne Vorgänge eingrenzt und das Zusammenführen nach der Trennung beschreibt.