Replikation, Sharding und CAP
Kurz gesagt: Replikation hält Kopien der Daten auf mehreren Servern, Sharding teilt die Daten zwischen ihnen auf, und das CAP-Theorem sagt, worauf du verzichtest, wenn das Netz getrennt wird.
Problem
Ein Server für den ganzen Shop
Der Shop wächst. Am Freitagabend wird der Katalog 20.000-mal pro Minute geöffnet, und fast alles davon ist Lesen: Produkte, Preise, Bestand. Die Datenbank liegt auf einem Server, und sein Prozessor ist bei 100 %. In der Nacht vor Samstag fällt seine Platte aus, und der Shop steht bis zum Morgen.
Eine Maschine ist zugleich die Decke der Geschwindigkeit und der einzelne Punkt, an dem alles stehen bleiben kann. Du brauchst mehr Maschinen mit Kopien der Daten.
Die Idee
Leader und Follower
Replikation heißt, dieselben Daten auf mehreren Servern (Knoten) zu halten. Das häufigste Schema hat einen Leader (in PostgreSQL der Primary): Nur er nimmt Schreibvorgänge an. Die anderen Knoten sind Follower (Replikate). Sie bekommen jeden Schreibvorgang vom Leader und wenden ihn bei sich an. Ein Lesevorgang kann an jeden Knoten gehen, drei Knoten nehmen also dreimal so viele Lesevorgänge auf.
Das Feld ist ein Simulator eines Clusters aus drei Knoten, und der Leader ist A. Der Bestand an Weißkäse (Produkt 7) ist 18 und liegt auf allen drei. Die Zeit im Simulator steht still: Ein Schreibvorgang verlässt den Leader und erreicht die Follower beim nächsten tick. Jeder Wert hat eine Version (v1, v2), damit du siehst, welche Kopie neuer ist. Unter der Ausgabe ist das Bild: die Knoten, ihre Kopien und was noch unterwegs ist.
write auf A liefert sofort OK: Der Leader hat bei sich geschrieben und wartet auf niemanden. Das ist asynchrone Replikation. Solange der Schreibvorgang unterwegs ist, sagt B noch 18. Diese Verzögerung ist die Replikationsverzögerung (replication lag). Sie liegt meist bei Millisekunden und unter Last bei Sekunden.
Genauer, für Neugierige
Die Befehle write, read, tick und die anderen in dieser Lektion gehören zum Simulator, nicht zu einer bestimmten Datenbank. tick stellt seine Uhr um einen Takt vor, während in einer echten Datenbank die Replikation ständig läuft. PostgreSQL macht dasselbe mit der Streaming-Replikation: Der Leader sendet den Followern sein Protokoll der Änderungen (das WAL), und sie wenden es der Reihe nach an. MySQL sendet sein Binärprotokoll. In beiden ist die Replikation standardmäßig asynchron, und die Follower nehmen nur Lesevorgänge an.
Probier es aus
Ich habe meine Stadt geändert, und die Seite zeigt die alte
Simona (Kunde 17) zieht von Ruse nach Plovdiv. Sie speichert die neue Stadt in ihrem Profil, und die Seite, die sich als Nächstes öffnet, sagt noch Ruse:
Der Schreibvorgang ist durchgegangen, aber die Seite hat von B gelesen, und B hat ihn noch nicht. Andere Kunden sehen die neue Stadt einen Moment später, und für sie macht das keinen Unterschied. Für Simona sieht es aus, als wäre die Änderung verloren gegangen, und sie tippt sie noch einmal ein. Hier braucht es die Garantie Read-your-writes: Wer geschrieben hat, sieht den eigenen Schreibvorgang. Die übliche Lösung ist, dass die Lesevorgänge dieses Kunden eine Zeit lang nach einer Änderung (sagen wir eine Minute) zum Leader gehen. Dieselbe veraltete Kopie hast du beim Cache in der Lektion über Key-Value gesehen.
Speichere Simonas neue Stadt und lies sie sofort, damit sie Plovdiv sieht.
Lösung
write customer:17:city = Plovdiv on A
read customer:17:city from A
read customer:17:city from A: Der Leader hat jeden bestätigten Schreibvorgang. Ein tick und danach ein Lesevorgang von B zeigt auch Plovdiv, aber in einer echten Datenbank weißt du nicht, wie lange du warten musst. Ein Lesevorgang von B oder C direkt nach dem Schreiben liefert Ruse.
Die Idee
Synchrone Replikation und ihr Preis
Fällt der Leader aus, bevor der Schreibvorgang die Follower erreicht, liegt er nur auf dem Leader. Du kannst ihn also warten lassen. Bei synchroner Replikation sagt der Leader OK erst, wenn die Follower bestätigen, dass sie den Schreibvorgang haben. Dann liegt der bestätigte Schreibvorgang auf jedem Knoten.
Der Preis ist doppelt. Jeder Schreibvorgang wartet auf den langsamsten Follower, und zwischen zwei Rechenzentren bedeutet das Millisekunden bei jedem Schreiben. Und ein toter Follower stoppt alle Schreibvorgänge, weil der Leader niemanden hat, von dem er eine Bestätigung bekommt. In der Praxis mischt man deshalb beides: Ein Follower ist synchron, die anderen asynchron. Fällt der synchrone aus, übernimmt ein anderer seinen Platz.
Genauer, für Neugierige
In PostgreSQL werden die synchronen Follower mit synchronous_standby_names festgelegt. FIRST 1 (b, c) wartet auf den ersten verfügbaren aus der Liste, und ANY 1 (b, c) wartet auf einen der beiden. Kann niemand bestätigen, hängt die Transaktion, bis ein Follower auftaucht oder sich die Einstellung ändert. Der Simulator hängt nicht: Er lehnt den Schreibvorgang sofort ab und sagt, warum. MySQL hat semi-synchrone Replikation: Der Leader wartet, bis mindestens ein Follower bestätigt, dass er den Schreibvorgang erhalten hat.
Sieh es dir an
Der Leader fällt aus
Die Replikation ist asynchron. Ein Kunde kauft Weißkäse, A senkt den Bestand auf 17 und sagt OK. Einen Moment später bleibt A stehen, bevor der Schreibvorgang hinausgeht:
B und C sind Follower und nehmen keine Schreibvorgänge an, der Shop steckt also fest, bis es einen neuen Leader gibt. elect wählt unter den Knoten, die einander sehen, den mit den neuesten Daten. Dafür braucht es mindestens zwei der drei, eine Mehrheit. Jede Wahl hat eine Nummer (den Term). Der neue Leader hat Term 2, und wenn der alte zurückkommt, erfährt er, dass er nicht mehr der Leader ist. Der Wechsel des Leaders heißt Failover.
Aber B hat die 17 nie bekommen. Der bestätigte Verkauf verschwindet: A verwirft ihn, wenn es zurückkommt, weil der neue Leader ihn nicht hat. Das ist die Falle der asynchronen Replikation: Beim Failover können die zuletzt bestätigten Schreibvorgänge verloren gehen. Bei synchroner Replikation hätte B ihn gehabt.
Genauer, für Neugierige
MongoDB wechselt den Leader (den Primary) selbst: Hören die Follower 10 Sekunden lang (Standard) nichts von ihm, stimmen sie ab, und ein Knoten mit der Mehrheit der Stimmen gewinnt. Die Schreibvorgänge des alten Primary, die die Mehrheit nicht erreicht haben, werden zurückgerollt, wenn er wieder beitritt. Deshalb werden wichtige Schreibvorgänge mit writeConcern: { w: "majority" } gesendet: Sie sind erst bestätigt, wenn die Mehrheit sie hat. PostgreSQL wechselt den Leader nicht selbst. Externe Werkzeuge wie Patroni tun das, und von Hand wird ein Follower mit pg_promote() zum Leader. Im Simulator ist die Wahl ebenfalls manuell (elect).
Die Idee
Das Netz wird getrennt: CAP und Quorum
Einen toten Server kann man wenigstens erkennen. Kniffliger ist es, wenn alles läuft, aber die Knoten einander nicht sehen, zum Beispiel wenn die Verbindung zwischen zwei Rechenzentren abreißt. Das ist eine Netzwerkpartition. Der Knoten auf der anderen Seite weiß nicht, ob die anderen ausgefallen sind oder er sie nur nicht hört.
Hier hilft ein anderes Schema, eines ohne Leader. Jeder Knoten nimmt Schreibvorgänge an und sendet sie an die anderen. Ein Schreibvorgang wartet auf W Bestätigungen, und ein Lesevorgang fragt R Knoten und nimmt die neueste Version. Gibt es N Knoten und gilt W + R > N, fragt jeder Lesevorgang mindestens einen Knoten, der den letzten Schreibvorgang hat. Das ist ein Quorum. Bei N = 3, W = 2 und R = 2 treffen sich ein Schreib- und ein Lesevorgang immer in mindestens einem Knoten:
Bei W = 1 und R = 1 fragt der Lesevorgang von C nur C, und C hat den neuen Schreibvorgang noch nicht. Bei W = 2 und R = 2 fragt C auch A und nimmt v3.
Jetzt die Unterbrechung: C ist von A und B abgeschnitten.
A und B sind eine Mehrheit und machen weiter. C erreicht zwei Knoten nicht und lehnt sowohl das Lesen als auch das Schreiben ab: keine Antwort ist besser als eine falsche. Bei W = 1 und R = 1 antwortet C, aber es sagt 18, während die Wahrheit 17 ist.
Das ist CAP, genau formuliert. Solange das Netz getrennt ist (P, partition), wählt der Knoten. Entweder lehnt er ab, damit er keinen alten Wert zurückgibt und keinen Schreibvorgang annimmt, den die anderen nicht kennen (Konsistenz, C). Oder er antwortet mit dem, was er hat (Verfügbarkeit, A). Beides zugleich geht nicht. CAP heißt nicht „wähle zwei von drei“: Die Partition wählt man nicht, sie passiert. Ohne Partition ist die Wahl eine andere, und das sagt PACELC: Else (E) wählt die Datenbank zwischen Latenz (L) und Konsistenz (C), weil synchrone Replikation und Quorum bei jedem Schreiben warten.
Genauer, für Neugierige
Die Idee des Quorums stammt aus dem Dynamo-Paper von Amazon (2007). Cassandra folgt ihr: Jede Abfrage sagt, wie viele Knoten sie braucht (ONE, QUORUM, ALL). Die Versionen sind dort Zeitstempel, und bei einem Konflikt gewinnt der neuere Schreibvorgang (last write wins). Der Simulator zählt Versionen mit einem Zähler. Lesevorgänge in DynamoDB sind standardmäßig eventuell konsistent, können also einen alten Wert liefern, und mit ConsistentRead sind sie konsistent. Die Konsistenz in CAP ist nicht das C in ACID. In CAP heißt sie, dass jeder Lesevorgang den zuletzt bestätigten Schreibvorgang sieht, als gäbe es eine Kopie. In ACID heißt sie, dass die Regeln der Datenbank gelten. CAP wurde 2000 von Eric Brewer formuliert und 2002 von Gilbert und Lynch bewiesen.
Die Idee
Sharding: jeder Knoten mit seinem eigenen Teil
Replikation vervielfacht das Lesen, aber jeder Schreibvorgang erreicht trotzdem jeden Knoten, und jeder Knoten hält alles. Passen die Daten oder die Schreibvorgänge nicht auf eine Maschine, teilst du sie auf: Jeder Knoten hält seinen eigenen Teil. Der Teil heißt Shard, das Aufteilen Sharding. Welche Zeile auf welchen Shard geht, entscheidet der Shard-Schlüssel, meist eine Spalte wie die Kundennummer.
Nach Bereich: Kunden 1 bis 7 auf A, 8 bis 14 auf B, 15 und aufwärts auf C. where sagt, auf welchem Knoten ein Kunde liegt, und query, welche Shards eine Abfrage fragen muss:
Eine Abfrage über benachbarte Nummern fragt nur zwei Shards. Aber jeder neue Kunde hat eine höhere Nummer und geht nach C. Alle Anmeldungen von heute treffen einen Knoten, während A und B ruhen. Das ist ein Hotspot.
Nach Hash: Aus dem Schlüssel wird eine Zahl berechnet, und sie bestimmt den Shard. Im Simulator ist der Hash der Rest der Division durch 3:
Die neuen Kunden gehen der Reihe nach nach A, B und C. Der Preis ist, dass eine Abfrage über einen Bereich jetzt jeden Shard fragt, weil benachbarte Nummern verstreut sind.
Und wenn der Schlüssel die Stadt ist? Die Abfrage „die Kunden aus Sofia“ fragt einen Shard. Aber alle aus Sofia sind an einem Ort:
A hat 9 der 20 Kunden: die sechs aus Sofia, der größten Stadt, dazu Burgas und den Kunden ohne Stadt. Ihre Bestellungen und die Last gehen mit den Kunden. Auch der Shard lässt sich nicht teilen: Alle aus Sofia haben denselben Schlüssel. Und eine Abfrage nach der Nummer fragt jetzt jeden Shard. Ein guter Schlüssel hat viele verschiedene Werte und verteilt sowohl die Daten als auch die Last gleichmäßig.
Noch etwas: Eine in Shards geteilte Tabelle liegt nicht mehr an einem Ort. Ein JOIN eines Kunden mit seinen Bestellungen ist nur schnell, wenn sie auf demselben Shard liegen. Deshalb werden Bestellungen meist nach der Kundennummer geshardet, wie der Kunde. Eine Transaktion, die in zwei Shards schreibt, braucht eine verteilte Transaktion (Two-Phase-Commit). Sie ist langsamer, und fällt ihr Koordinator auf halbem Weg aus, warten die Shards.
Genauer, für Neugierige
Im Simulator sind die drei Knoten entweder Kopien oder Shards. In einer echten Datenbank ist jeder Shard seine eigene Gruppe von Kopien. In MongoDB ist jeder Shard ein Replica Set, und ein Router (mongos) schickt die Abfrage über den Schlüssel an den Shard. MongoDB shardet nach Bereich oder nach Hash, und ein Stück der Daten mit einem einzigen Wert des Schlüssels, das zu groß wird, lässt sich nicht teilen (ein Jumbo-Chunk). Cassandra hasht den Schlüssel mit Murmur3 und platziert die Knoten auf einem Ring (Consistent Hashing): Ein neuer Knoten übernimmt einen Teil der Schlüssel, ohne alle zu verschieben. Der Rest der Division durch 3 im Simulator ist nicht so: Mit einem vierten Knoten würde fast jeder Kunde den Shard wechseln. Der „Hash“ einer Stadt im Simulator ist die Nummer der Stadt in einer Liste. Für PostgreSQL gibt es Sharding mit der Erweiterung Citus, für MySQL mit Vitess.
Übung
Ein Ausfall, ein Quorum und neue Kunden
1. Der Bestand an Weißkäse ist 18 und liegt auf allen drei Knoten. Der Leader A fällt aus, und seine Platte muss ersetzt werden.
A kommt nicht so bald zurück. Sorge dafür, dass der Cluster wieder Schreibvorgänge annimmt, und schreibe den neuen Bestand an Weißkäse: 17.
Lösung
elect
write stock:7 = 17 on B
elect, dann write stock:7 = 17 on B. B und C haben dieselben Daten, und bei Gleichstand nimmt der Simulator den ersten nach dem Namen. Ohne Wahl lehnt B den Schreibvorgang ab, weil es ein Follower ist. start A ist kein Ausweg: A kommt nicht zurück.
2. Der Cluster hat keinen Leader und drei Knoten.
Wähle W und R so, dass ein Lesevorgang von jedem Knoten direkt nach einem Schreibvorgang den neuen Wert sieht und Schreibvorgänge weiter durchgehen, wenn ein Knoten ausgefallen ist.
Lösung
quorum write 2 read 2
quorum write 2 read 2. 2 + 2 > 3, also trifft ein Lesevorgang immer einen Knoten mit dem letzten Schreibvorgang. Ist ein Knoten ausgefallen, bleiben zwei, genug für W und R. Bei W = 3 stoppen die Schreibvorgänge mit dem ersten toten Knoten. Bei W + R ≤ 3 kann ein Lesevorgang den neuen Schreibvorgang verpassen, und bei R = 3 stoppen die Lesevorgänge.
3. Der Shop schaltet Werbung und erwartet hunderte neue Kunden mit den Nummern 21, 22, 23 und aufwärts.
Wähle den Shard-Schlüssel der Kunden so, dass sich die neuen Kunden auf die drei Knoten verteilen, statt zu einem zu gehen.
Lösung
shard customers by id hash
shard customers by id hash. Nach Bereich liegen alle neuen Nummern über 15 und gehen nach C. Nach Stadt würden die neuen Kunden aus Sofia trotzdem zu einem Shard gehen, und der Simulator kennt ihre Städte nicht einmal.
Die Idee
Was wann
- Replikation braucht man fast immer: Eine Kopie auf einer anderen Maschine schützt vor einem Ausfall, und die Follower nehmen die Lesevorgänge auf. Asynchron ist der Standard. Ist der Verlust der letzten Schreibvorgänge nicht hinnehmbar (Zahlungen), ist mindestens ein Follower synchron.
- Lesen von einem Follower ist gut für den Katalog, die Berichte und die Suche. Es ist nicht gut für das, was der Kunde gerade geändert hat: Dann liest der Leader.
- Sharding ist der letzte Schritt, nicht der erste. Eine größere Maschine, Indizes, ein Cache wie Redis und Lese-Replikate reichen für die meisten Shops. Sharding macht jede Abfrage und Transaktion schwerer, die Shards überschreitet.
- CAP wird für jede Operation einzeln entschieden. Der Bestand und die Zahlung wollen Konsistenz. Der Warenkorb und „zuletzt angesehen“ können verfügbar bleiben und ein wenig veraltet sein.
Genauer, für Neugierige
Drei Knoten sind der kleinste Cluster, der seinen Leader selbst wechselt: Bei zwei Knoten ist ein allein gebliebener Knoten keine Mehrheit. Deshalb empfiehlt MongoDB eine ungerade Anzahl stimmberechtigter Mitglieder in einem Replica Set. Google Spanner und CockroachDB führen Transaktionen über Shards mit Konsensalgorithmen aus (Paxos in Spanner, Raft in CockroachDB). Der Preis ist die Latenz bei jedem Schreiben, das ist PACELC in der Praxis.
Test