PACELC Theorem
Abwägung zwischen Konsistenz und Antwortzeit auch im Normalbetrieb
Die Idee und ihr Nutzen
Eine Versicherung speichert die Adressen ihrer Kunden in einer Datenbank, die drei Kopien der Daten auf drei Rechnern hält, hier Kopie A, B und C genannt. Auf jedem der drei Rechner läuft dasselbe Datenbankprogramm mit einer vollständigen Kopie aller Adressen. Ändert ein Kunde seine Adresse und speichert die Datenbank die Änderung zuerst auf Kopie A, muss festgelegt sein, wann die Datenbank dem Kunden die Änderung bestätigt. Die Datenbank kann sofort antworten, dann liefert Kopie B für kurze Zeit vielleicht noch die alte Adresse. Oder die Datenbank wartet, bis weitere Kopien die neue Adresse übernommen haben, dann dauert die Antwort länger. Diese Abwägung zwischen kurzer Antwortzeit und stets aktuellem Stand im Normalbetrieb beschreibt das PACELC-Theorem, ein Lehrsatz über Datenbanken mit mehreren Kopien. Es ergänzt das CAP-Theorem, das nur den Störungsfall betrachtet, in dem die Verbindung zwischen den Rechnern unterbrochen ist und Kopie A die Kopien B und C nicht erreicht.
Wie funktioniert es?
Ein Kunde der Versicherung ändert seine Adresse, und Kopie A speichert die neue Adresse. Im Normalbetrieb kann Kopie A die Änderung sofort bestätigen, ohne auf Kopie B und Kopie C zu warten. Erst danach schickt Kopie A die Änderung weiter. Liest ein anderes Programm kurz danach die Adresse bei Kopie B, ist die Änderung bei Kopie B womöglich noch nicht angekommen, und Kopie B liefert die alte Adresse. Kopie A kann die Änderung aber auch zuerst an Kopie B und Kopie C schicken und auf Bestätigungen warten. Kopie B bestätigt die Änderung, und erst danach bestätigt Kopie A sie dem Kunden; damit kennt die Mehrheit der drei Kopien die neue Adresse. Die Antwort an den Kunden dauert länger, dafür liefern die bestätigten Kopien danach die neue Adresse. Bei einer Störung ist die Verbindung zwischen den Rechnern unterbrochen, und Kopie A erreicht die Kopien B und C nicht. Fragt ein anderes Programm jetzt bei Kopie B nach der Adresse, kann Kopie B mit ihrem letzten bekannten Stand antworten, der womöglich veraltet ist. Das reicht für die Anzeige der Adresse im Kundenportal. Kopie B kann die Anfrage aber auch abweisen, bis die Störung behoben ist. Diese strengere Regel nutzt die Versicherung für das Lesen der Bankverbindung vor einer Auszahlung. Vor einer Überweisung braucht die Versicherung sicher den neuesten bestätigten Stand.
Eine Datenbank, die Kopien derselben Daten auf mehreren Rechnern hält, heißt verteilte Datenbank. Die Rechner sind über ein Netz verbunden, über das jede Änderung von einer Kopie zu den anderen übertragen wird. Diese Übertragung braucht Zeit, besonders wenn die Rechner in verschiedenen Rechenzentren oder Ländern stehen. Ist die Verbindung zwischen den Rechnern unterbrochen, spricht man von einer Netztrennung (englisch Partition). Der Name PACELC steht für zwei Entscheidungen. Bei einer Netztrennung (P) wählt die Datenbank zwischen Verfügbarkeit (Availability, A) und Konsistenz (Consistency, C). Sonst (Else, E), also im Normalbetrieb, wählt die Datenbank zwischen kurzer Antwortzeit (Latency, L) und Konsistenz (C). Verfügbarkeit heißt, dass jede erreichbare Kopie weiter antwortet, auch wenn ihr Stand veraltet sein kann. Konsistenz heißt, dass die Datenbank nur Antworten gibt, die zum neuesten bestätigten Stand passen, und Anfragen sonst ablehnt. Das sofortige Bestätigen durch Kopie A ist also die Wahl EL, das Warten auf die Bestätigungen die Wahl EC. Das Antworten von Kopie B während der Netztrennung ist die Regel PA, das Abweisen die Regel PC. Aus den Buchstaben ergeben sich Kurzbezeichnungen, die beide Entscheidungen zusammenfassen. PC/EC heißt: Die Datenbank lehnt bei einer Netztrennung Anfragen eher ab, als veraltete Daten zu liefern, und wartet im Normalbetrieb auf Bestätigungen weiterer Kopien, bevor sie antwortet. PA/EL heißt: Die Datenbank antwortet bei einer Netztrennung weiter und im Normalbetrieb, ohne auf weitere Kopien zu warten, und die Kopien können kurzzeitig unterschiedliche Stände zeigen. PA/EC und PC/EL sind Mischformen. PA/EC heißt zum Beispiel: Bei einer Netztrennung antwortet Kopie B weiter mit ihrem letzten bekannten Stand, im Normalbetrieb wartet Kopie A aber auf die Bestätigung von Kopie B, bevor sie dem Kunden antwortet.
Wie viele Bestätigungen eine Datenbank abwartet und welche Zusagen für das Lesen daraus folgen, legt jedes Datenbanksystem anders fest. Viele Datenbanksysteme bieten für verschiedene Lese- und Schreibvorgänge unterschiedliche Einstellungen an. Die Kurzbezeichnungen beschreiben deshalb Entscheidungen für einzelne Vorgänge mit einer bestimmten Einstellung und keine vollständige Bewertung eines Produkts. Dieselbe Datenbank kann beim Lesen der Adresse für das Kundenportal nach EL arbeiten und beim Lesen der Bankverbindung nach EC. Das Theorem schreibt keine Einstellung vor und macht keine Datenbank schneller oder konsistenter. Es benennt nur, zwischen welchen Zielen eine Datenbank im Störungsfall und im Normalbetrieb wählen muss.
PACELC: schnell oder aktuell im Normalbetrieb, verfügbar oder konsistent bei Netztrennung
Wann ist es sinnvoll und wann nicht?
Das PACELC-Theorem hilft
- Ein Team wählt eine verteilte Datenbank aus oder legt ihre Einstellungen fest. Dasselbe gilt für einen verteilten Zwischenspeicher. Ohne diese Abwägung übernimmt das Team womöglich die Standardeinstellung und bemerkt erst im Betrieb, dass Kopie B kurz nach einer Änderung die alte Adresse liefert. Mit dem Theorem entscheidet das Team bewusst, wann die Datenbank eine Änderung bestätigt: Dass Kopie B bei der Wahl EL kurz die alte Adresse liefern kann, ist dann gewollt und kein Zufall.
- Mehrere Programme lesen aus derselben Datenbank und brauchen unterschiedlich aktuelle Daten. Statt „immer aktuell und immer schnell“ zu verlangen, legt das Team je Datenart fest, welche Daten sofort aktuell sein müssen und wo ein kurz veralteter Stand ausreicht. Die Versicherung entscheidet so für die Adressanzeige im Kundenportal und für das Lesen der Bankverbindung getrennt, statt für alle Daten dieselbe Einstellung zu verwenden. Mit derselben Einstellung für alle Daten wäre entweder die Bankverbindung vor einer Auszahlung womöglich veraltet, oder jede Adressanzeige im Kundenportal würde auf Bestätigungen weiterer Kopien warten.
- Die Kopien stehen in verschiedenen Rechenzentren oder Ländern, und das Warten auf Bestätigungen verlängert jede Änderung spürbar. Das Team plant die längere Antwortzeit bei der Wahl EC dann von Anfang an ein, statt sie erst im Betrieb zu bemerken.
Das PACELC-Theorem hilft nicht
- Das System hat eine einzige Datenbank ohne Kopien. Dann muss das Team nichts abwägen: Die Datenbank bestätigt eine Änderung, sobald sie gespeichert ist, und jedes Lesen liefert danach den neuen Stand.
- Ein Produkt soll pauschal bewertet werden. Je nach Einstellung verhält sich dasselbe Produkt anders. Dann prüft das Team in der Dokumentation des Produkts, welche Einstellungen es für Schreiben und Lesen anbietet, und bewertet das Produkt mit den Einstellungen, die das Team selbst verwenden will. So verlässt sich das Team nicht auf eine Einordnung, die nur für die Standardeinstellung gilt.
- Das Team braucht die genauen Zusagen eines Datenbanksystems, etwa ob Kopie C nach einer bestätigten Änderung schon die neue Adresse liefert. Das Theorem sagt dazu nichts, weil jedes Datenbanksystem selbst festlegt, wie viele Bestätigungen es abwartet. Dann liest das Team diese Zusagen in der Dokumentation des jeweiligen Systems nach. Dort steht zum Beispiel, wie viele Kopien einen Schreib- oder Lesevorgang bestätigen müssen. Eine solche Mindestzahl heißt Quorum.
- Es ist nur das Verhalten bei einer Netztrennung zu entscheiden, etwa weil die Versicherung für das Lesen der Adresse im Normalbetrieb schon die Wahl EL getroffen hat. Der Teil des Theorems über den Normalbetrieb bringt dann nichts Neues. Das Team entscheidet dann mit dem CAP-Theorem nur, ob Kopie B während der Netztrennung mit ihrem letzten bekannten Stand antwortet oder Anfragen abweist.
Nachteile und typische Fehler
Auch PACELC vereinfacht. Zwischen „sofort überall aktuell“ und „schnell, aber vielleicht veraltet“ gibt es viele Abstufungen. Ein Beispiel ist die Zusage, dass jeder Nutzer zumindest seine eigenen Änderungen sofort wieder sieht. Die zusätzliche Wartezeit hängt stark von der Entfernung zwischen den Kopien ab. Im selben Rechenzentrum dauert das Warten auf eine Bestätigung oft nur Millisekunden, zwischen Kontinenten 100 Millisekunden und mehr. Unterschiedliche Einstellungen je Vorgang passen besser zum jeweiligen Zweck, machen die Anwendung aber aufwendiger: Für jeden Lese- und Schreibvorgang muss festgelegt, dokumentiert und getestet werden, welche Einstellung gilt.
Typische Fehler und woran man sie erkennt:
- Pauschale Produktzuordnung: Das Team wählt ein Produkt, weil ein Fachartikel es als PC/EC einordnet. Diese Einordnung gilt nur für die Standardeinstellung des Produkts. Das Team stellt das Produkt so ein, dass eine einzige Kopie jeden Lesevorgang beantwortet, damit das Lesen schneller geht. Kopie B liefert dann kurz nach einer Änderung noch die alte Adresse. Erkennbar ist das an veralteten Lesergebnissen, obwohl das Team einen stets aktuellen Stand erwartet hat.
- Bankverbindung wie die Adresse gelesen: Der Kunde ändert seine Bankverbindung, und Kopie A bestätigt die Änderung sofort. Kurz danach liest das Programm für Auszahlungen die Bankverbindung bei Kopie B, mit derselben Einstellung, mit der das Kundenportal die Adresse liest. Bei Kopie B ist die Änderung noch nicht angekommen, und die Versicherung überweist das Geld an die alte Bankverbindung. Erkennbar ist das an Auszahlungen auf eine Bankverbindung, die der Kunde kurz vorher geändert hatte.
- Unterschätzte Wartezeit: Das Team wählt EC für alle Vorgänge und testet mit Kopien im selben Rechenzentrum. Im Betrieb stehen die Kopien auf verschiedenen Kontinenten. Jede Änderung wartet dann auf eine Bestätigung von einem anderen Kontinent, also 100 Millisekunden und mehr statt weniger Millisekunden. Speichert ein Vorgang 20 Änderungen nacheinander, dauert er dadurch mindestens 2 Sekunden länger als im Test. Erkennbar ist das an Änderungen, die im Betrieb deutlich länger dauern als im Test.
- Fehlende Regel für die Netztrennung: Die Versicherung legt nur fest, was im Normalbetrieb gilt. Bei einer Netztrennung folgt die Datenbank ihrer Standardeinstellung, und diese lässt Kopie B mit ihrem letzten bekannten Stand antworten. Erkennbar ist das erst während einer Störung. Dann liefert zum Beispiel Kopie B vor einer Auszahlung eine veraltete Bankverbindung.
Weiterführend
Verwandte Ansätze
- Eventual Consistency: die Zusage, dass alle Kopien ohne neue Änderungen irgendwann denselben Stand erreichen. Ob ein System diese Zusage gibt, folgt nicht allein aus der Bezeichnung „EL“.
- Replication: erklärt, wie Kopien übertragen werden und worin sich das Warten auf Bestätigungen vom sofortigen Antworten unterscheidet.
Beispiele zur Einordnung
Das Theorem ist kein Werkzeug, sondern ein Denkmodell. An den folgenden Datenbanksystemen lässt sich die Abwägung einstellen oder beobachten:
- Apache Cassandra: lässt für jeden einzelnen Lese- und Schreibvorgang festlegen, wie viele Kopien antworten müssen.
- etcd: bestätigt eine Änderung erst, wenn die Mehrheit der Rechner sie gespeichert hat. Ist keine Mehrheit erreichbar, nimmt etcd keine neuen Änderungen an.
- PostgreSQL: bietet mehrere Stufen, auf welche Bestätigung einer Kopie der Hauptrechner, der alle Änderungen annimmt, vor seiner Antwort wartet. Ob eine Lesekopie eine bestätigte Änderung schon anzeigt, hängt davon ab, ob die Lesekopie die Änderung bereits übernommen hat, und nicht nur davon, ob sie die Änderung empfangen hat.
- YugabyteDB: überträgt Änderungen mit einem Mehrheitsverfahren. Neben stets aktuellem Lesen bietet YugabyteDB unter bestimmten Bedingungen schnellere Lesevorgänge an, die einen etwas älteren Stand liefern können.
Quellen
- Daniel J. Abadi: Consistency Tradeoffs in Modern Distributed Database System Design: Aufsatz von 2012 in der Zeitschrift Computer der IEEE Computer Society, der PACELC als Ergänzung zu CAP darstellt und Systeme wie Dynamo, Cassandra und PNUTS nach ihren Standardeinstellungen einordnet.
- Martin Kleppmann: A Critique of the CAP Theorem: zeigt die Grenzen von CAP als Werkzeug für die Praxis und schlägt vor, Vorgänge danach zu beurteilen, wie stark ihre Antwortzeit von Verzögerungen im Netz abhängt.