Zum Inhalt
wannacode

Trade-offs

Kurz gesagt: Das CAP-Theorem sagt: Wenn die Verbindung zwischen Knoten abbricht, wählt ein System zwischen Konsistenz (CP, es lehnt ab) und Verfügbarkeit (AP, es nimmt an und gleicht später ab).

Problem

Die letzte Kaffeemaschine und zwei Käufer

Der Shop hat jetzt zwei Lager, in Sofia und in Varna. Jedes führt seine eigene Kopie des Bestands: Die Seiten antworten schnell, und ein Lager arbeitet weiter, wenn das andere langsam ist. Eine Kaffeemaschine für 349 € ist noch da.

Am Freitagabend bricht die Verbindung zwischen den beiden Lagern für zehn Minuten ab. In diesen Minuten bestellt Maria die Maschine, und ihre Bestellung landet in Varna. Jonas bestellt dieselbe Maschine, und seine landet in Sofia.

Was soll der Shop tun? Egal, was du wählst: Jemand verliert. Entweder werden beide abgelehnt, während die Maschine im Regal steht. Oder beide bezahlen für eine Maschine. Eine dritte Möglichkeit gibt es nicht, und genau darum geht es in dieser Lektion.

Die Idee

CAP in der Praxis

Wenn das Netz das System in Teile spaltet (eine Partition, P), antwortet jeder Teil für sich. Dann wählt er eines von zwei:

  • Konsistenz (C): Jede Antwort ist die neueste Wahrheit. Wenn der Teil nicht sicher sein kann, lehnt er ab;
  • Verfügbarkeit (A): Jede Anfrage bekommt eine Antwort, auch aus einer Kopie, die alt sein kann.

Eine Partition wählst du nicht: Netze fallen aus, ob es das Netz zwischen zwei Lagern ist oder zwischen zwei Zonen in der Cloud. Wählen kannst du nur, was du tust, wenn es passiert. Das ist der Trade-off zwischen Konsistenz und Verfügbarkeit, bekannt als CAP-Theorem. Du hast ihn in der Lektion „Replikation, Sharding und CAP“ von der Seite der Datenbanken gesehen. Hier siehst du ihn von der Seite des Shops: Wer verliert und wie viel.

In den Programmen ist ein Lager ein Objekt, die Verbindung ein Flag linkUp und die Zeit ein Takt. So laufen die beiden Entscheidungen nebeneinander, ohne Netz.

class Warehouse(string name, int stock)
{
    public string Name { get; } = name;
    public int Stock { get; set; } = stock;
    public List<Sale> Sales { get; } = [];
}


record Sale(string Buyer, int Tick);

Sieh es dir an

CP: lieber eine Ablehnung als eine Lüge

Ein CP-Lager verkauft nur, wenn auch das andere bestätigt. Ohne Verbindung kann es das nicht prüfen, also lehnt es ab:

// CP: verkauft nur, wenn auch das andere Lager bestätigt
static string SellCP(Warehouse here, Warehouse other,
                     bool linkUp, string buyer)
{
    if (!linkUp)
        return $"{buyer}: abgelehnt, {here.Name}"
            + $" hat keine Verbindung zu {other.Name}";
    if (here.Stock == 0) return buyer + ": ausverkauft";
    here.Stock--;
    other.Stock--;
    return buyer + ": verkauft";
}
var sofia = new Warehouse("Sofia", 1);
var varna = new Warehouse("Varna", 1);
bool linkUp = false; // die Verbindung ist unterbrochen
Console.WriteLine(SellCP(varna, sofia, linkUp, "Maria"));
Console.WriteLine(SellCP(sofia, varna, linkUp, "Jonas"));
linkUp = true; // die Verbindung ist wieder da
Console.WriteLine(SellCP(varna, sofia, linkUp, "Maria"));
Console.WriteLine($"Bestand: {sofia.Name} {sofia.Stock}, {varna.Name} {varna.Stock}");
Ausgabe
Maria: abgelehnt, Varna hat keine Verbindung zu Sofia
Jonas: abgelehnt, Sofia hat keine Verbindung zu Varna
Maria: verkauft
Bestand: Sofia 0, Varna 0

Solange die Verbindung unterbrochen ist, kauft niemand. Sobald sie wieder da ist, kauft Maria, und beide Lager sagen 0. Die Daten stimmen die ganze Zeit. Der Preis liegt in der anderen Qualität: In diesen zehn Minuten verkauft der Shop nichts, und die Kunden sehen einen Fehler.

Sieh es dir an

AP: jetzt verkaufen, später abgleichen

Ein AP-Lager verkauft aus der eigenen Kopie und hält den Verkauf fest. Wenn die Verbindung wieder da ist, sammelt der Abgleich die Verkäufe beider Lager, ordnet sie nach Zeit und verteilt die echten Stücke:

// AP: verkauft aus der eigenen Kopie, ohne zu fragen
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": ausverkauft";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: verkauft ({here.Name})";
}


// Abgleich: die Verkäufe beider Lager, nach Zeit
static void Reconcile(int real, Warehouse a, Warehouse b)
{
    var all = a.Sales.Concat(b.Sales).OrderBy(s => s.Tick);
    foreach (var s in all)
    {
        bool ok = real > 0;
        if (ok) real--;
        string result = ok ? "bestätigt" : "Gutschein 20 €";
        Console.WriteLine(
            $"{s.Buyer} (Takt {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
var sofia = new Warehouse("Sofia", 1);
var varna = new Warehouse("Varna", 1);
// die Verbindung ist unterbrochen: jedes Lager verkauft aus der eigenen Kopie
Console.WriteLine(SellAP(varna, "Maria", 3));
Console.WriteLine(SellAP(sofia, "Jonas", 5));
// die Verbindung ist wieder da
Reconcile(1, sofia, varna);
Console.WriteLine("Bestand: " + sofia.Stock);
Ausgabe
Maria: verkauft (Varna)
Jonas: verkauft (Sofia)
Maria (Takt 3): bestätigt
Jonas (Takt 5): Gutschein 20 €
Bestand: 0

Beide hören „verkauft“. Später stellt sich heraus, dass es eine Maschine gibt. Maria war zuerst da und bekommt sie. Jonas bekommt eine Entschuldigung und einen Gutschein über 20 €. AP bezahlt mit einer Entschädigung und mit Code für den Abgleich.

Die beiden Kopien wichen zehn Minuten lang voneinander ab und trafen sich wieder, sobald die Verbindung zurück war. Das ist Eventual Consistency: Die Kopien dürfen eine Weile abweichen, aber wenn keine neuen Änderungen mehr kommen, erreichen sie denselben Stand. Versprochen wird, dass sie sich treffen, nicht wann.

Sieh es dir an

Die beiden Entscheidungen untereinander

// AP: verkauft aus der eigenen Kopie, ohne zu fragen
static string SellAP(Warehouse here, string buyer,
                     int tick)
{
    if (here.Stock == 0) return buyer + ": ausverkauft";
    here.Stock--;
    here.Sales.Add(new Sale(buyer, tick));
    return $"{buyer}: verkauft ({here.Name})";
}


// Abgleich: die Verkäufe beider Lager, nach Zeit
static void Reconcile(int real, Warehouse a, Warehouse b)
{
    var all = a.Sales.Concat(b.Sales).OrderBy(s => s.Tick);
    foreach (var s in all)
    {
        bool ok = real > 0;
        if (ok) real--;
        string result = ok ? "bestätigt" : "Gutschein 20 €";
        Console.WriteLine(
            $"{s.Buyer} (Takt {s.Tick}): {result}");
    }
    a.Stock = real;
    b.Stock = real;
}
Schritt für Schritt, in Worten
  1. Die letzte Kaffeemaschine für 349 €. Zwei Lager führen je eine Kopie des Bestands: 1 und 1. Zwei Shops untereinander: Der obere wählt CP, der untere AP.
  2. Die Verbindung zwischen Sofia und Varna bricht ab. Maria ist in Varna, Jonas in Sofia. Jedes Lager muss allein entscheiden.
  3. CP verkauft nur, wenn das andere Lager bestätigt. Es gibt keine Verbindung, also werden beide abgelehnt. Die Daten bleiben richtig, aber der Shop verkauft nichts.
  4. AP verkauft aus der eigenen Kopie. Maria kauft in Takt 3, Jonas in Takt 5. Beide Kopien zeigen 0, doch verkauft wurden zwei von einem.
  5. Die Verbindung ist wieder da. Der Abgleich sammelt die Verkäufe, nicht die Zahlen, und ordnet sie nach Zeit.
  6. Maria war zuerst da und bekommt die Maschine. Jonas bekommt eine Entschuldigung und einen Gutschein über 20 €. CP hat mit entgangenen Verkäufen bezahlt, AP mit einer Entschädigung.

Der obere Shop ist CP, der untere AP. Dieselbe Partition, dieselben Käufer. Oben verliert der Shop (Verkäufe); unten verliert ein Kunde (das Stück), und der Shop bezahlt mit einem Gutschein und mit Zeit im Support.

Probier es aus

Sag die Ausgabe voraus

Es gibt zwei Stück. Die Verbindung ist unterbrochen, und die Lager verkaufen AP: Jonas in Sofia im Takt 1, Maria in Varna im Takt 4, Elena in Sofia im Takt 2. Was gibt der Abgleich aus?

var sofia = new Warehouse("Sofia", 2);
var varna = new Warehouse("Varna", 2);
SellAP(sofia, "Jonas", 1);
SellAP(varna, "Maria", 4);
SellAP(sofia, "Elena", 2);
Reconcile(2, sofia, varna);
Antwort

Probier es aus

Ergänze

Wonach werden die Verkäufe beim Abgleich geordnet?

var all = a.Sales.Concat(b.Sales).OrderBy(s => s.);

Probier es aus

Finde den Fehler

Ein Kollege schreibt einen kürzeren Abgleich: Jedes Lager nimmt die kleinere der beiden Zahlen. Nach der Partition sagen beide Lager 0, niemand bekommt einen Gutschein, und Jonas wartet auf eine Maschine, die es nicht gibt. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Jede Qualität wird mit einer anderen Qualität bezahlt

CAP ist der bekannteste Trade-off, aber nicht der einzige. Architektur heißt zu wählen, welche Qualität welche bezahlt:

  • Konsistenz gegen Verfügbarkeit bei einer Partition, wie du gesehen hast;
  • Konsistenz gegen Latenz auch ohne Partition: Die Bestätigung vom anderen Lager ist bei jedem Verkauf ein weiterer Weg über das Netz;
  • Verfügbarkeit gegen Korrektheit: AP braucht Entschädigungen, einen Abgleichprozess und Menschen im Support;
  • Sicherheit gegen Tempo und Bequemlichkeit: Eine Prüfung mehr kostet mehr Zeit, ein Schritt mehr beim Login;
  • Skalierung gegen Einfachheit: Zwei Lager mit Kopien sind komplizierter als eine Datenbank.

Die Wahl gilt nicht für den ganzen Shop, sondern für jede Art von Daten einzeln. Der Warenkorb passt zu AP: Wenn ein Stück verloren geht, legt der Kunde es neu hinein, und der Warenkorb ist immer da. Die letzten Stück, die Zahlung und die Konten gehören zu CP: Ein verkauftes Stück, das es nicht gibt, oder eine doppelte Zahlung kosten Geld und Vertrauen. Der Katalog mit seinen Beschreibungen verträgt Daten, die Minuten alt sind.

Das Business entscheidet, und der Architekt nennt ihm den Preis jeder Variante in Zahlen: wie viele Minuten pro Jahr ohne Verkäufe bei CP, wie viele Gutscheine bei AP. Die Entscheidung und ihre Folgen kommen in ein ADR.

Die Idee

Wann es wehtut

  • Eventual Consistency, wenn Nutzer ihre eigene Aktion nicht sehen. Der Kunde bezahlt, die Seite liest aus einer Kopie, die es noch nicht weiß, und sagt „Du hast keine Bestellungen“. Er bezahlt noch einmal. Dasselbe hast du bei den Replikaten in der Lektion über Skalierung gesehen. Wo ein Mensch liest, was er gerade geschrieben hat, lies von dort, wo geschrieben wurde.
  • Wenn es keine Entschädigung gibt. Geld, das schon doppelt abgebucht ist, ein Medikament mit begrenzter Stückzahl, ein Ticket für einen Sitzplatz im Flugzeug. Hier ist AP keine Wahl, sondern ein Fehler.
  • Ein Abgleich, der komplizierter ist als sein Nutzen. Wenn eine Partition einmal im Jahr für eine Minute vorkommt, ist eine Ablehnung billiger als Abgleichcode, den jemand verstehen muss.
  • Verteilte Daten, obwohl du sie nicht brauchst. Eine Datenbank mit Transaktionen stellt diese Frage gar nicht (die Lektion über Transaktionen). Eine Kopie in einem anderen Lager oder einem anderen Land legt man an, wenn ein NFR sie mit einer Zahl verlangt.
Genauer, für Neugierige

CAP genauer. Das Theorem (Brewer, bewiesen von Gilbert und Lynch) spricht von einem Wert, vielen Kopien und einer Partition. „Wähle 2 von 3“ führt in die Irre: P ist keine Wahl. Genauer gesagt wählst du bei einer Partition C oder A. PACELC ergänzt die zweite Hälfte: Else, du wählst zwischen Latency und Consistency.

Zeit. Hier sehen alle denselben Taktzähler. Die Uhren echter Maschinen laufen auseinander, darum entscheidet man „wer zuerst war“ mit logischen Uhren: Lamport-Uhren, Vektoruhren, hybride logische Uhren. Googles Spanner nutzt Uhren mit Atomreferenzen und GPS und wartet, bis die Unsicherheit vorbei ist.

CRDTs (Conflict-free Replicated Data Types) sind Strukturen, die sich ohne Koordination immer zum selben Ergebnis zusammenführen lassen: Zähler, Mengen, Listen. Amazons Warenkorb im Dynamo-Paper ist ein Beispiel für AP, bei dem Hinzufügen nie Stücke verliert.

Quoren. Bei N Kopien, Schreiben auf W und Lesen von R sieht ein Lesen immer den letzten Schreibvorgang, wenn W + R > N. Du hast sie in der Lektion über Replikation kennengelernt. Cassandra und DynamoDB lassen dich die Konsistenzstufe für jede Anfrage wählen.

Mehrere Services. Der Abgleich hier gilt für ein Stück in zwei Lagern. Wenn eine Geschäftsoperation durch mehrere Services geht und bei einem Fehler Schritt für Schritt rückgängig gemacht werden muss, wird daraus ein Muster mit eigenem Namen. Es kommt später in diesem Modul.

OrderBy ist ein stabiles Sortieren aus LINQ und gibt eine neue Sequenz zurück; die Listen der Lager werden nicht verändert.

Übung

CP für die letzten Stück, AP für den Rest

Löse die Aufgabe in deinem eigenen Editor.

Die beiden Lager verkaufen Kaffeemaschinen (je 1) und Kaffeefilter (je 500). Schreibe Sell, das Kaffeemaschinen nur mit Bestätigung vom anderen Lager verkauft (CP) und Filter aus der eigenen Kopie (AP). Die Verbindung ist unterbrochen. Maria in Varna will eine Maschine und Filter, Jonas in Sofia will Filter.

Ausgabe
Maria, Kaffeemaschine: abgelehnt, Varna hat keine Verbindung zu Sofia
Maria, Filter: verkauft (Varna)
Jonas, Filter: verkauft (Sofia)

Weitere Aufgaben

  • Ein Schwellenwert. Nimm statt einer Liste „wichtiger“ Produkte einen Schwellenwert: AP, solange die Kopie mehr als 3 Stück hat, CP für die letzten 3. Was passiert, wenn beide Lager während der Partition je 3 verkaufen?
  • Der Warenkorb. Der Warenkorb hat zwei Kopien. In der einen hat der Kunde Tassen hinzugefügt, in der anderen die Filter entfernt. Schreibe einen Abgleich der Operationen „hinzufügen“ und „entfernen“, geordnet nach Takt.

Test

Teste dich

1. Die Verbindung zwischen den beiden Lagern ist unterbrochen. Was kann jedes Lager wählen?
2. Was bedeutet „Eventual Consistency“?
3. Warum sammelt der Abgleich die Verkäufe und nicht die Bestandszahlen?
4. Was ist für den Online-Shop sinnvoll?
5. Wann tut Eventual Consistency am meisten weh?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·