Quorum: Eine Mindestzahl an Bestätigungen verlangen

Verteilte Systeme

Quorum

Eine Mindestzahl an Bestätigungen verlangen

Die Idee und ihr Nutzen

Eine Versicherung speichert ihre Schadenfälle in einer Datenbank, die jeden Datensatz als Kopie auf drei Rechnern hält. So gehen die Daten nicht verloren, wenn ein Rechner ausfällt, und auf den zwei übrigen Rechnern liegen weiterhin zwei Kopien, die eine Änderung bestätigen können. Setzt der Schadendienst, das Programm für die Bearbeitung der Schadenfälle, den Status von Fall 4711 auf „freigegeben“, muss festgelegt sein, ob diese Änderung schon als gespeichert gilt, wenn eine einzige Kopie sie angenommen hat, oder erst, wenn alle drei Kopien sie haben. Die Datenbank verlangt deshalb eine feste Mindestzahl von Kopien, die eine Änderung bestätigen oder eine Leseanfrage beantworten müssen, zum Beispiel zwei von drei. Damit übersteht die Datenbank den Ausfall eines einzelnen Rechners, ohne eine bestätigte Änderung zu verlieren. Eine solche Mindestzahl heißt Quorum.

Bausteine: Schadendienst: setzt Fall 4711 auf „freigegeben“; Datenzugriff: wartet auf 2 von 3 Bestätigungen; Kopie 1: hat gespeichert; Kopie 2: hat gespeichert; Kopie 3: gerade im Neustart. Verbindungen: Schadendienst — Datenzugriff (Änderung); Schadendienst — Datenzugriff (gespeichert); Datenzugriff — Kopie 1; Datenzugriff — Kopie 2 (Änderung); Datenzugriff — Kopie 2 (Bestätigung); Datenzugriff — Kopie 3. Der Datenzugriff meldet eine Änderung als gespeichert, sobald zwei der drei Kopien sie bestätigt haben.

Wie funktioniert es?

Der Schadendienst schickt seine Schreib- und Leseanfragen nicht direkt an die drei Kopien von Fall 4711, sondern an den Datenzugriff, den Teil der Datenbank, der die Anfragen an die Kopien verteilt und ihre Antworten auswertet. Kopie 1, Kopie 2 und Kopie 3 liegen auf je einem eigenen Rechner. Der Schadendienst gibt die Änderung „Status 4711 = freigegeben“ an den Datenzugriff. Der Datenzugriff schickt die Änderung mit der Versionsangabe 5 an alle drei Kopien. Die Versionsangabe ist eine fortlaufende Nummer, die jeder gespeicherte Wert trägt. Der bisherige Status „offen“ von Fall 4711 trägt zum Beispiel die Versionsangabe 4. Kopie 3 startet gerade neu und ist nicht erreichbar. Kopie 1 und Kopie 2 speichern die Änderung und bestätigen. Mit diesen zwei Bestätigungen ist das Schreibquorum erreicht, also die Mindestzahl von Kopien, die eine Änderung bestätigen müssen, bevor die Änderung als gespeichert gilt. Der Datenzugriff meldet dem Schadendienst „gespeichert“, obwohl Kopie 3 den neuen Stand noch nicht hat. Später fragt ein Sachbearbeiter den Status von Fall 4711 ab. Der Datenzugriff schickt die Leseanfrage an zwei Kopien, an Kopie 2 und an die inzwischen wieder erreichbare Kopie 3. Auch für das Lesen gilt eine Mindestzahl von zwei, das Lesequorum. Kopie 2 meldet „freigegeben, Version 5“, Kopie 3 noch den alten Status „offen, Version 4“. Anhand der Versionsangabe wählt der Datenzugriff den neueren Wert und meldet dem Sachbearbeiter „freigegeben“. Danach überträgt der Datenzugriff den neueren Wert an Kopie 3, wie es viele Datenbanken bei einer solchen Leseanfrage tun.

Zwei Kopien, die geschrieben haben, und zwei Kopien, die gelesen werden, können bei drei Kopien nicht völlig verschieden sein. Mindestens eine Kopie gehört zu beiden Gruppen und kennt daher die bestätigte Änderung, bei Fall 4711 die Kopie 2. Das Team, das die Datenbank einrichtet, wählt die beiden Mindestzahlen deshalb oft so, dass Schreibquorum und Lesequorum zusammen größer sind als die Zahl der Kopien. Dann gehört zu jeder Leseanfrage mindestens eine Kopie, die die letzte bestätigte Änderung gespeichert hat. Bei fünf Kopien kann die Datenbank zum Beispiel drei Antworten verlangen. Die Überschneidung allein reicht aber nicht aus, um immer den neuesten Stand zu lesen, denn die gelesenen Kopien können verschiedene Stände melden, wie Kopie 2 und Kopie 3 bei Fall 4711. Deshalb braucht der Datenzugriff die Versionsangabe.

Ein Quorum legt nur fest, wie viele Kopien antworten müssen. Es legt nicht fest, welcher Wert gilt, wenn zwei Programme gleichzeitig verschiedene Werte schreiben. Ein Quorum bringt auch einen ausgefallenen Rechner nicht von selbst auf den neuesten Stand. Beides muss die Datenbank mit eigenen Regeln lösen. Das Nachziehen von Kopie 3 beim Lesen ist eine solche Regel. Ob eine Leseanfrage immer den zuletzt bestätigten Wert liefert, hängt deshalb vom jeweiligen Datenbanksystem ab.

Sind weniger als zwei Kopien erreichbar, kommt das Schreibquorum nicht zustande. Der Schreibvorgang scheitert dann, und der Schadendienst erhält eine Fehlermeldung. Die Fehlermeldung beweist aber nicht, dass keine Kopie die Änderung gespeichert hat. Eine einzelne Kopie kann die Änderung angenommen haben, ohne dass das Schreibquorum zustande kam.

Beteiligte: Schadendienst: setzt Fall 4711 auf „freigegeben“; Datenzugriff: Schreib- und Lesequorum: je 2 von 3; Kopie 1: Datenkopie; Kopie 2: Datenkopie; Kopie 3: gerade im Neustart; Sachbearbeiter: fragt den Status ab. Ablauf: 1. Der Schadendienst gibt die Änderung „Status 4711 = freigegeben“ an den Datenzugriff. 2. Der Datenzugriff schickt die Änderung an alle drei Kopien, zuerst an Kopie 1. 3. Kopie 2 erhält die Änderung ebenfalls. Jeder Wert trägt eine Versionsangabe, die neue Änderung trägt die Versionsangabe 5. 4. Kopie 3 startet gerade neu und ist nicht erreichbar. 5. Kopie 1 hat die Änderung gespeichert und bestätigt. 6. Kopie 2 hat die Änderung ebenfalls gespeichert und bestätigt. Mit zwei von drei Bestätigungen ist das Schreibquorum erreicht. 7. Der Datenzugriff meldet „gespeichert“, obwohl Kopie 3 den neuen Stand noch nicht hat. 8. Ein Sachbearbeiter fragt den Status von Fall 4711 ab. 9. Der Datenzugriff schickt die Leseanfrage an zwei Kopien, zuerst an Kopie 2. 10. Die Leseanfrage geht auch an Kopie 3, die nach dem Neustart wieder erreichbar ist. 11. Kopie 2 meldet „freigegeben, Version 5“ und kennt damit die bestätigte Änderung. 12. Kopie 3 meldet noch den alten Status „offen, Version 4“. 13. Anhand der Versionsangabe wählt der Datenzugriff den neueren Wert. 14. Der Datenzugriff überträgt den neueren Wert gleich an Kopie 3.

Wann ist es sinnvoll und wann nicht?

Ein Quorum lohnt sich

Eine Datenbank hält Kopien derselben Daten auf mehreren Rechnern, und das Team will bewusst zwischen kurzer Antwortzeit, Schutz vor Ausfällen und aktuellem Datenstand abwägen. Mit kleineren Mindestzahlen wartet der Datenzugriff auf weniger Antworten und meldet ein Ergebnis früher. Mit größeren Mindestzahlen steigt die Wahrscheinlichkeit, den neuesten Stand zu lesen. Ohne Quorum bleibt nur die Wahl, auf eine einzige Kopie oder auf alle Kopien zu warten.
Die Datenbank soll Lese- und Schreibvorgänge auch dann annehmen, wenn ein einzelner Rechner ausgefallen ist oder neu startet. Der Schadendienst muss nicht warten, bis alle drei Kopien erreichbar sind. Würde die Datenbank immer alle drei Kopien verlangen, wäre sie schon beim Ausfall eines einzigen Rechners lahmgelegt.
Eine bestätigte Änderung darf nicht verloren gehen, wenn genau der Rechner ausfällt, der sie zuerst angenommen hat. Meldete die Datenbank eine Änderung schon nach einer einzigen Bestätigung als gespeichert, wäre die Änderung beim Ausfall dieses Rechners verloren. Mit dem Schreibquorum von zwei steht der neue Status von Fall 4711 auch dann noch auf Kopie 2, wenn der Rechner von Kopie 1 ausfällt.
Die Kopien sind im Alltag nicht in jedem Augenblick gleich. Eine Kopie hat zum Beispiel die letzte Änderung noch nicht, weil die Übertragung noch läuft. Ohne Lesequorum fragt der Datenzugriff womöglich nur Kopie 3 und meldet dem Sachbearbeiter „offen“, obwohl Fall 4711 schon freigegeben ist. Mit einem Lesequorum von zwei fragt der Datenzugriff immer auch eine Kopie, die die bestätigte Änderung gespeichert hat.

Ein Quorum ist nicht das Richtige

Jede Leseanfrage muss garantiert den neuesten Wert liefern. Zwei Bestätigungen garantieren das nicht. Ob eine Leseanfrage bei gleichzeitigen Änderungen und veralteten Kopien den zuletzt bestätigten Wert liefert, hängt von den eigenen Regeln des Datenbanksystems ab. Dann wählt das Team ein Datenbanksystem, das in seiner Dokumentation ausdrücklich zusagt, beim Lesen immer den zuletzt bestätigten Wert zu liefern. So zeigt keine Leseanfrage einen Schadenfall als „offen“, der schon freigegeben ist.
Bei einem Datenbestand ist ein Ausfall von einigen Stunden hinnehmbar, und gegen Datenverlust genügt eine nächtliche Sicherung. Ein Quorum setzt dagegen Kopien auf mehreren Rechnern voraus, die hier niemand braucht. Dann betreibt das Team die Datenbank auf einem einzigen Rechner, und die Datenbank meldet jede Änderung sofort als gespeichert. Die zwei zusätzlichen Rechner entfallen, und kein Schreibvorgang wartet auf eine zweite Bestätigung.
Mehrere Programme ändern denselben Datensatz häufig gleichzeitig, und keine bestätigte Änderung darf verloren gehen. Ein Quorum legt nicht fest, welche von zwei gleichzeitigen Änderungen gilt. Die Zusatzregel, dass die Änderung mit dem neuesten Zeitstempel gilt, also mit der jüngsten Uhrzeit, zu der sie geschrieben wurde, verwirft die ältere der beiden Änderungen. Dann setzt das Team eine Datenbank mit einem Konsensverfahren ein: Die Rechner einigen sich auf eine gemeinsame Reihenfolge aller Änderungen, und keine bestätigte Änderung geht unbemerkt verloren.
Viele Leseanfragen sollen auf mehrere Rechner verteilt werden, und eine Leseanfrage darf für kurze Zeit einen älteren Stand liefern. Mit einem Lesequorum von zwei müsste der Datenzugriff jede Leseanfrage an zwei Kopien schicken und die Versionsangaben vergleichen. Dann richtet das Team Read Replicas ein: Ein einziger Hauptrechner nimmt alle Änderungen an und gibt sie an Lesekopien auf den übrigen Rechnern weiter. Jede Leseanfrage geht dann an nur eine Lesekopie. Fällt der Hauptrechner aus, muss ein neuer Hauptrechner bestimmt werden, etwa per Leader Election.

Nachteile und typische Fehler

Je mehr Bestätigungen ein Schreibvorgang abwarten muss, desto länger dauert er. Jede Leseanfrage mit einem Lesequorum von zwei fragt doppelt so viele Rechner wie eine Leseanfrage an einen einzigen Rechner. Das Team muss die Mindestzahlen passend zur Zahl der Kopien einstellen und anpassen, wenn Kopien hinzukommen. Für gleichzeitige Änderungen braucht die Datenbank zusätzlich Versionsangaben und eine Regel, welcher von zwei gleichzeitig geschriebenen Werten gilt, oder ein Konsensverfahren.

Typische Fehler und woran man sie erkennt:

Keine Überschneidung: Schreibquorum und Lesequorum sind zu klein gewählt, etwa je eins von drei. Der Datenzugriff meldet die Änderung dann schon nach der Bestätigung von Kopie 1 als gespeichert. Kurz danach liest der Datenzugriff nur Kopie 3, die den alten Status noch hat. Erkennbar ist das an Leseanfragen, die kurz nach einer bestätigten Änderung noch den alten Status liefern.
Fehlende Versionsangabe: Kopie 2 und Kopie 3 melden verschiedene Werte ohne Versionsangabe. Der Datenzugriff kann die gemeldeten Werte nicht nach ihrem Alter ordnen und gibt zufällig den Wert einer befragten Kopie zurück. Erkennbar ist das an einem Status, der bei wiederholter Abfrage zwischen „offen“ und „freigegeben“ wechselt.
Gleichzeitige Änderungen: Zwei Programme schreiben fast gleichzeitig verschiedene Werte für Fall 4711, und beide erreichen ihr Schreibquorum. Mindestens eine Kopie erhält beide Änderungen und behält nur die zuletzt eingetroffene. Ohne Regel, welcher der beiden Werte gilt, setzt sich beim Lesen und Nachziehen einer der beiden Werte durch, und die andere Änderung geht unbemerkt verloren. Erkennbar ist das an Änderungen, die bestätigt wurden und danach fehlen.
Nicht erreichtes Quorum: Bei einer Netzstörung ist nur eine oder keine Kopie erreichbar, und jeder Schreibvorgang scheitert. Erkennbar ist das an Fehlermeldungen beim Speichern, die alle Schreibvorgänge zur selben Zeit treffen.
Dauerhaft veraltete Kopie: Ein zurückgekehrter Rechner erhält den fehlenden Stand nie, weil die Datenbank veraltete Kopien nicht nachzieht. Der freigegebene Status von Fall 4711 liegt dann dauerhaft nur auf Kopie 1 und Kopie 2. Fallen danach die Rechner von Kopie 1 und Kopie 2 aus, ist die bestätigte Änderung verloren, obwohl der Rechner von Kopie 3 noch läuft. Erkennbar ist das an Kopien, deren Versionsangaben dauerhaft hinter den anderen liegen.

Weiterführend

Quellen

Apache Cassandra: Dynamo: offizielle Dokumentation einer verbreiteten Datenbank mit einstellbaren Mindestzahlen wie ONE, QUORUM und ALL. Sie erklärt, dass sich Schreib- und Lesequorum bei QUORUM überschneiden, dass der Wert mit dem neuesten Zeitstempel gilt und dass Kopien beim Lesen nachgezogen werden können.
Unmesh Joshi: Patterns of Distributed Systems: Buch von 2023, Verlagsseite bei Pearson. Es beschreibt unter anderem die Muster Majority Quorum und Versioned Value, also Mehrheitsbestätigungen und Versionsangaben an gespeicherten Werten.