Konsistenzmodelle, CAP und PACELC

Was „konsistent“ bedeutet, sobald Daten kopiert werden

Sobald ein System mehr als eine Kopie eines Datums hält, auf Replikaten in verschiedenen Zonen, in Caches oder in anderen Services, können die Kopien eine Zeit lang voneinander abweichen. Ein Konsistenzmodell ist der Vertrag, der festlegt, welche Abweichungen Clients beobachten dürfen. Es ist ein Versprechen darüber, was Lesevorgänge angesichts der erfolgten Schreibvorgänge liefern können, und damit ein Versprechen darüber, mit welchen Überraschungen der Anwendungscode umgehen muss.

Vorsicht beim mehrdeutigen Wort. Das C in ACID (Abschnitt 0.5) bedeutet, dass eine Transaktion die Datenbank von einem gültigen Zustand in einen anderen überführt und dabei Regeln einhält wie „ein Kontostand wird nie negativ“. Das C in CAP bedeutet etwas anderes und Engeres: Jeder Lesevorgang verhält sich so, als gäbe es eine einzige, aktuelle Kopie. Isolationsebenen von Datenbanken wie Serializable oder Read Committed sind eine dritte Familie, die gleichzeitige Transaktionen betrifft; sie werden unter Transaktionen und Isolation behandelt. In diesem Abschnitt geht es um die Garantien replizierter Daten.

Konsistenzmodelle vom stärksten zum schwächsten

Linearisierbarkeit, 1990 von Maurice Herlihy und Jeannette Wing definiert, ist das stärkste Modell für ein einzelnes Objekt. Jede Operation scheint zu einem Zeitpunkt zwischen ihrem Beginn und ihrem Ende augenblicklich wirksam zu werden, und alle Clients sehen dieselbe Reihenfolge, die die Echtzeit respektiert: Sobald ein Schreibvorgang abgeschlossen ist, sieht jeder danach beginnende Lesevorgang ihn oder etwas Neueres. Das System verhält sich, als gäbe es eine einzige Kopie. Beispiel aus der Essenslieferung: Zwei Kunden versuchen, den letzten Rabattcode einzulösen; mit einem linearisierbaren Speicher gelingt es genau einem, und der andere sieht, dass er weg ist, egal welches Replikat sie erreichen.

Sequenzielle Konsistenz, 1979 von Leslie Lamport für Multiprozessoren definiert, behält die eine globale Reihenfolge bei und hält die Operationen jedes Clients in der Reihenfolge, in der dieser Client sie ausgelöst hat, verzichtet aber auf die Echtzeitanforderung. Ein Client darf einen leicht veralteten Wert lesen, solange sich alle über die Reihenfolge aller Schreibvorgänge einig sind. In verteilten Datenbanken wird sie selten ausdrücklich angeboten, erklärt aber den Unterschied zwischen „eine vereinbarte Reihenfolge“ und „eine vereinbarte Reihenfolge, die zur Uhr passt“.

Kausale Konsistenz verlangt nur, dass kausal zusammenhängende Operationen von allen in derselben Reihenfolge gesehen werden: Hing das Schreiben von B davon ab, A gesehen zu haben, darf niemand B ohne A sehen. Gleichzeitige, voneinander unabhängige Schreibvorgänge dürfen von verschiedenen Clients in unterschiedlicher Reihenfolge gesehen werden. Beispiel: Ein Restaurant antwortet im Bestell-Chat auf die Frage eines Kunden „Ja, es ist glutenfrei“; niemand sollte je die Antwort ohne die Frage sehen. Kausale Konsistenz ist attraktiv, weil Jepsens viel genutzte Übersicht der Konsistenzmodelle sie als mit Sticky-Verfügbarkeit erreichbar einstuft: Sie kann während einer Partition weiterarbeiten, solange jeder Client beim selben Replikat bleibt.

Die Session Guarantees, 1994 von Douglas Terry und Kollegen beschrieben, sind schwächere Versprechen pro Client, die die verwirrendsten Anomalien beseitigen. Read-your-Writes: Nachdem ein Kunde die Lieferadresse geändert hat, zeigt sein nächster Lesevorgang die neue Adresse, auch wenn andere Nutzer sie erst später sehen. Monotonic Reads: Hat ein Client einmal den Bestellstatus „unterwegs“ gesehen, sieht er nie später „in Zubereitung“, weil ein späterer Lesevorgang ein nachhinkendes Replikat getroffen hat. (Zwei weitere Garantien, Monotonic Writes und Writes-Follow-Reads, schränken die Reihenfolge ein, in der die Schreibvorgänge eines Clients angewendet werden.)

Eventual Consistency, 2008 von Werner Vogels bekannt gemacht, ist die schwächste nützliche Garantie: Kommen keine neuen Schreibvorgänge, konvergieren alle Replikate irgendwann auf denselben Wert. Sie sagt nichts darüber, wie lange das dauert oder was in der Zwischenzeit gelesen werden kann, und eine einfache Implementierung, die widersprüchliche Schreibvorgänge löst, indem sie den mit dem jüngsten Zeitstempel behält, bekannt als Last Write Wins, verwirft den anderen stillschweigend. Stärkere Formen wie Strong Eventual Consistency mit konfliktfreien replizierten Datentypen (CRDTs) garantieren, dass Replikate, die dieselben Aktualisierungen erhalten haben, denselben Zustand halten, indem sie Datentypen nutzen, deren gleichzeitige Aktualisierungen sich immer zusammenführen lassen, etwa Zähler und Mengen.

CAP: was es tatsächlich besagt

Eric Brewer stellte die CAP-Idee im Jahr 2000 in seiner Keynote auf dem ACM Symposium on Principles of Distributed Computing (PODC) als Vermutung vor. 2002 veröffentlichten Seth Gilbert und Nancy Lynch einen formalen Beweis, der sie für ihre präzisen Definitionen zu einem Theorem machte. Konsistenz bedeutete Linearisierbarkeit. Verfügbarkeit bedeutete, dass jede Anfrage, die ein nicht ausgefallener Knoten erhält, zu einer Antwort führen muss. Partitionstoleranz bedeutete, dass das System seine Versprechen auch dann hält, wenn das Netzwerk beliebig viele Nachrichten zwischen Knoten verliert.

Genau gelesen ist das CAP-Theorem eng. Es besagt, dass ein repliziertes System, wenn eine Netzwerkpartition auftritt, sodass manche Knoten andere nicht erreichen, für jede Anfrage zwischen Konsistenz und Verfügbarkeit wählen muss. Ein Knoten, der von den neuesten Schreibvorgängen abgeschnitten ist, kann entweder die Antwort verweigern (oder warten, bis die Partition behoben ist) und so die Konsistenz wahren, oder mit dem antworten, was er hat, und so die Verfügbarkeit wahren, mit dem Risiko, veraltete Daten zu liefern oder widersprüchliche Schreibvorgänge anzunehmen. Das Diagramm zeigt das Dilemma für ein Ticketsystem, das Platz 14C verkauft.

Mehrere verbreitete Lesarten sind falsch. „Wähle zwei beliebige von dreien“ legt nahe, Partitionstoleranz sei optional, doch in jedem System, das über ein Netzwerk kommuniziert, treten Partitionen auf, ob Sie sie wählen oder nicht; die einzige echte Wahl ist, wie sich das System dann verhält. Ein sogenanntes „CA“-System ist eines, das nicht entschieden hat, was bei einer Partition geschehen soll; vertretbar ist das nur dort, wo Partitionen praktisch unmöglich sind, etwa auf einem einzelnen Knoten. „Unsere Datenbank ist CP (oder AP)“ ist meist ungenau: CAP-Verfügbarkeit ist eine sehr starke Eigenschaft, die viele als hochverfügbar vermarktete Systeme nicht haben, und viele als CP bezeichnete Systeme sind auch nicht linearisierbar. Martin Kleppmann argumentierte 2015, Datenbanken sollten überhaupt nicht als CP oder AP etikettiert werden, weil die meisten keine der beiden Definitionen erfüllen und ihr Verhalten von der Konfiguration abhängt. „CAP erklärt unsere Latenz“ ist ebenfalls falsch: CAP sagt nichts darüber, was geschieht, wenn keine Partition vorliegt, also die meiste Zeit.

CAP zwölf Jahre später

2012 erklärte Brewer selbst in einem Artikel in IEEE Computer mit dem Titel „CAP Twelve Years Later: How the Rules Have Changed“, dass die Formel „zwei von dreien“ in die Irre geführt habe. Partitionen sind selten, daher kann ein System fast immer sowohl Konsistenz als auch Verfügbarkeit bieten; die Wahl gilt nur während einer Partition und nur für die betroffenen Operationen. Die Wahl muss auch nicht global sein: Verschiedene Operationen und verschiedene Daten können unterschiedlich entscheiden.

Brewer empfahl, in drei Schritten ausdrücklich für Partitionen zu entwerfen: die Partition erkennen, in einen expliziten Partitionsmodus wechseln, in dem manche Operationen eingeschränkt sind (zum Beispiel Bestellungen annehmen, aber Rückerstattungen aufschieben), und danach einen Wiederherstellungsprozess ausführen, der den Zustand zusammenführt und Fehler aus der Zeit der Partition kompensiert. Er wies auch darauf hin, dass das C von CAP Single-Copy-Konsistenz ist, eine strengere Teilmenge dessen, was das C von ACID schützt, und dass Invarianten wie „nie überverkaufen“ unter Umständen nachträglich repariert werden müssen. Diese Sichtweise führt direkt zu den fachlichen Kompensationen der Sagas: Eine Fluggesellschaft, die einen Flug überbucht, entschädigt den Fluggast, statt während einer Netzwerkstörung alle Buchungen abzulehnen.

PACELC: die Abwägung, die Sie jeden Tag bezahlen

Daniel Abadi wies 2010 in einem Blogbeitrag und 2012 in einem Artikel in IEEE Computer, „Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story“, darauf hin, dass CAP die Abwägung ignoriert, vor der Entwerfende tatsächlich die meiste Zeit stehen. PACELC liest sich so: Gibt es eine Partition, wähle zwischen Verfügbarkeit (Availability) und Konsistenz (Consistency); andernfalls (Else), im Normalbetrieb, wähle zwischen Latenz (Latency) und Konsistenz (Consistency).

Die „Else“-Hälfte ist die wichtige Ergänzung. Um einen Lesevorgang konsistent zu machen, muss ein repliziertes System koordinieren: den Schreibvorgang an andere Replikate senden und auf Bestätigungen warten, jeden Lesevorgang an einen Leader leiten oder mehrere Replikate kontaktieren und vergleichen. Jedes davon kostet Netzwerk-Roundtrips, und über Regionen hinweg kann ein Roundtrip Dutzende oder sogar Hunderte Millisekunden kosten. Ein System, das ohne Koordination vom nächstgelegenen Replikat antwortet, ist schneller, aber möglicherweise veraltet. Diese Abwägung wird bei jeder Anfrage bezahlt, mit oder ohne Partition.

PACELC-Einstufungen werden oft zitiert, etwa PA/EL für Systeme, die auf Geschwindigkeit und Verfügbarkeit ausgelegt sind, und PC/EC für Systeme, die immer Konsistenz bevorzugen. Behandeln Sie sie als Beschreibungen einer Konfiguration, nicht eines Produkts: Dieselbe Datenbank kann in einem Deployment PA/EL und in einem anderen PC/EC sein, je nach Einstellungen, die pro Tabelle, pro Abfrage oder pro Anfrage gewählt werden.

Quoren: Konsistenz mit Arithmetik einstellen

Leaderlose replizierte Speicher nach dem Vorbild von Amazons Dynamo-Paper (2007) lassen jede Operation wählen, wie viele Replikate sie einbezieht. Bei N Replikaten eines Eintrags gilt ein Schreibvorgang als bestätigt, wenn W Replikate ihn gespeichert haben, und ein Lesevorgang sammelt Antworten von R Replikaten und liefert die neueste Version darunter. Gilt R + W > N, überschneidet sich jede Lesemenge mit jeder Schreibmenge in mindestens einem Replikat, sodass ein Lesevorgang mindestens eine Kopie des neuesten bestätigten Schreibvorgangs einschließt.

Die Wahl von R und W wägt Konsistenz, Latenz und Verfügbarkeit gegeneinander ab. Niedrigere Werte bedeuten, auf weniger und schnellere Replikate zu warten und mehr Ausfälle zu tolerieren, um den Preis möglicher veralteter Lesevorgänge. Höhere Werte bedeuten das Gegenteil. Schreibvorgänge werden meist ohnehin an alle N Replikate gesendet; W entscheidet nur, auf wie viele Bestätigungen der Client wartet.

Die Überschneidung der Quoren ist für aktuelle Lesevorgänge notwendig, aber für sich genommen keine Linearisierbarkeit. Gleichzeitige Schreibvorgänge können nach Zeitstempeln von Uhren geordnet werden, die nicht übereinstimmen, sodass ein späterer Schreibvorgang unter Last-Write-Wins verlieren kann. Ein Schreibvorgang, der scheiterte, nachdem er einige Replikate erreicht hatte, kann auf diesen noch sichtbar sein. „Sloppy“ Quoren, die während Ausfällen Schreibvorgänge auf Ersatzknoten annehmen, heben die Überschneidung auf. Und zwei Lesevorgänge, die sich mit einem noch laufenden Schreibvorgang überschneiden, können erst neue, dann alte Werte sehen, sofern der Lesende nachhinkende Replikate nicht vor der Rückgabe repariert. Speicher, die echte Compare-and-Set-Semantik brauchen, ergänzen für genau diese Operationen ein Konsensprotokoll, etwa die auf Paxos basierenden Lightweight Transactions in Apache Cassandra.

Wie sich bekannte Datenbanken konfigurieren lassen

Reale Produkte sitzen selten an einem einzigen Punkt der Leiter. Sie bieten Einstellungen, und die richtige Beschreibung lautet „wie dieses Deployment konfiguriert ist“. Es folgen vier gängige Beispiele; prüfen Sie die aktuelle Dokumentation der Version, die Sie betreiben, denn Standardwerte ändern sich zwischen Releases.

Konsistenz je Anwendungsfall wählen

Die nützlichste Gewohnheit ist, nicht mehr zu fragen „Ist unser System konsistent?“, sondern für jedes Datum und jede Operation: Was geht schief, wenn ein Client einen veralteten oder umgeordneten Wert sieht, und was kostet das? Geldbewegungen, eindeutige Ressourcen und Invarianten rechtfertigen meist starke Konsistenz und ihre Latenz. Zähler, Feeds, Empfehlungen und Analysen meist nicht. Viele für Nutzer sichtbare Anomalien verschwinden schon mit den Session Guarantees, die günstig sind: Leiten Sie die Lesevorgänge eines Nutzers für einige Sekunden nach dessen Schreibvorgang an den Primary, oder führen Sie ein Versions-Token in der Session mit und warten Sie, bis das Replikat damit gleichgezogen hat.