Write Skew verhindern und Deadlocks

Track Konzepte · Datenbanken und Nebenläufigkeit · ca. 45 Min.

Was du aus Teil a brauchst

Du kennst die vier Isolation Levels der MiniDB (read_uncommitted, read_committed, snapshot, serializable) und weißt, dass Snapshot Isolation Write Skew nicht verhindert: zwei Ärzte melden sich ab, jeder schreibt seine eigene Zeile. Mehr dazu in Teil 1.

Worum es geht

Du weißt jetzt, dass Write Skew passiert. In Teil 2 lernst du die drei Gegenmaßnahmen (Serializable mit Retry, Lock auf die gelesene Menge, materialisierter Konflikt) und ihren Preis. Der Preis von Locks ist der Deadlock: zwei Prozesse warten gegenseitig aufeinander. Am Ende kannst du Write Skew mit Serializable und Retry reparieren, einen Deadlock als Zyklus im Wait-for-Graph erkennen und ihn mit fester Sperrreihenfolge vermeiden.

Von JS/TS her gedacht

In JS fängt Promise.all einen Abbruch nicht von selbst auf: Wenn eine Operation fehlschlägt, musst du die ganze Folge “lesen, prüfen, schreiben” wiederholen, nicht nur den letzten Schritt. Das ist genau der Retry bei Serializable. Und zwei await-Ketten, die zwei Mutexe in entgegengesetzter Reihenfolge nehmen, hängen für immer, genau wie die Sperren unten.

Konzept

Schritt 1: Das Werkzeug aus Teil a

Dieselbe Mini-Datenbank (MiniDB, Tx), dieselben Sperren (SimLock) und derselbe Simulator lauf wie in Teil 1. Jeder Prozess ist ein Generator, jedes yield ein Umschaltpunkt, lauf ruft ohne seed reihum bei jedem Prozess einmal next auf.

Der Dienstplan aus Teil 1 (zwei Ärzte, Regel: mindestens einer bleibt im Dienst):

Schritt 2: Maßnahmen gegen Write Skew

Maßnahme Idee Preis
Serializable (Isolation Level) Datenbank prüft beim Commit, ob sich etwas geändert hat, das du gelesen hast, und bricht ab Du musst den Abbruch abfangen und die ganze Transaktion wiederholen (Retry)
Lock auf die gelesene Menge (pessimistisch, z. B. SELECT ... FOR UPDATE auf alle gelesenen Zeilen, bei Phantomen ein gröberes Lock) Wer die Menge liest, sperrt sie, der andere wartet Andere warten, Deadlock-Gefahr
Konflikt materialisieren / Constraint Beide schreiben dieselbe Zeile (z. B. ein Zähler mit CHECK (n >= 1)), dann greift der normale Schreibkonflikt oder der Constraint Die Regel muss sich als eine Zeile oder ein Constraint ausdrücken lassen

Serializable in MiniDB: Der zweite Committer wird abgewiesen.

Ausgabe: Abgebrochen: Serialisierungskonflikt: Dr1 hat sich nach meinem Start geändert und 1. Dr2 wurde abgewiesen, weil sich Dr1 (etwas, das Dr2 gelesen hat) nach seinem Start geändert hat. (Echte Datenbanken prüfen feiner. Hier ist es bewusst eine vereinfachte, vorsichtige Prüfung.) Der Retry hat immer dieselbe Form: eine Schleife, in der du jedes Mal eine neue Transaktion beginnst, die Daten neu liest, neu entscheidest und den Commit versuchst. Scheitert er mit Konflikt, geht es von vorn los. In Übung 1 baust du das.

Lock auf die gelesene Menge: Hier ein einziges SimLock für den ganzen Dienstplan. Wer abmeldet, nimmt zuerst die Sperre, liest dann.

Ausgabe: 1. Dr2 wartet, bis Dr1 committet hat, und sieht dann nur noch einen Arzt im Dienst.

Konflikt materialisieren: Beide Ärzte schreiben zusätzlich dieselbe Zeile zaehler. Dann greift der normale Schreibkonflikt von snapshot:

Ausgabe: Dr2 abgewiesen: Schreibkonflikt auf zaehler und {'Dr1': False, 'Dr2': True, 'zaehler': 1}. Der Preis: Die Regel “mindestens einer” musste in eine Zeile übersetzt werden.

Schritt 3: Deadlock

Pessimistisches Locking hat einen Preis. Zwei Prozesse nehmen zwei Sperren in entgegengesetzter Reihenfolge:

Ausgabe: Hängt fest (Deadlock?) {'l1': 'A', 'l2': 'B'}. A hält l1 und wartet auf l2, B hält l2 und wartet auf l1. Beide warten ewig. Als Wait-for-Graph (wer wartet auf wen) ist das ein Zyklus:

graph LR
    A[Prozess A] -->|wartet auf l2, gehalten von B| B[Prozess B]
    B -->|wartet auf l1, gehalten von A| A

Zwei Strategien:

  • Erkennen (detection): Das System baut den Wait-for-Graph, sucht Zyklen und bricht eine der Transaktionen ab (Übung 2). Einen Zyklus findest du so: Du gehst von einem Prozess aus Kante für Kante weiter und merkst dir den Weg. Kommst du bei einem Prozess an, der schon auf diesem Weg liegt, ist der Weg ab dort ein Zyklus.
  • Vermeiden (prevention): Alle nehmen Sperren in derselben globalen Reihenfolge. Dann kann kein Zyklus entstehen (Übung 3).

Mit gleicher Reihenfolge läuft dasselbe Szenario durch:

Ausgabe: läuft durch False False.

Falle

  1. Serializable ohne Retry. Der Abbruch beim Commit ist kein Fehler im Code, sondern das normale Verhalten. Wer ihn nicht fängt und die ganze Transaktion (inklusive Lesen) wiederholt, verliert Anfragen.
  2. Lock nur auf die gelesenen Zeilen, aber das Problem ist die Menge. Ein neuer Arzt (Phantom) steht nicht in den gesperrten Zeilen. Bei Regeln über Mengen brauchst du ein gröberes Lock, Serializable oder einen Constraint.
  3. Locks in wechselnder Reihenfolge. Jeder Code für sich sieht korrekt aus, erst die Kombination deadlockt.

Übungen

Übung 1: Write Skew reparieren mit Serializable und Retry (ca. 12 Min.)

Zurück zum Bereitschaftsdienst (Regel: mindestens ein Arzt bleibt). neuer_dienstplan(n) und im_dienst(db) stehen bereit. Schreibe abmelden_sicher(db, name) mit Level serializable. Es gilt:

  • Wer die Menge der Ärzte im Dienst liest und nur noch einen sieht, tut nichts (und beendet die Transaktion mit tx.rollback()).
  • Sonst: yield, eigene Zeile schreiben (tx.schreibe(name, {"im_dienst": False})), tx.commit().
  • commit kann Konflikt werfen. Dann ist die Transaktion abgebrochen, und du wiederholst alles von vorn.

Die Prüfung testet 2 und 3 Ärzte reihum und in 40 zufälligen Reihenfolgen. Am Ende muss genau einer im Dienst sein.

Wann soll die Schleife enden, und wann weitermachen? Zwei Ausgänge: erledigt und nichts zu tun. Ein Konflikt gehört nicht dazu. Denk daran, dass jeder neue Versuch seine Entscheidung auf frisch gelesenen Daten trifft.

def abmelden_sicher(db, name):
    def prozess():
        while True:
            tx = db.begin("serializable")
            wer = tx.lies_alle(lambda z: z["im_dienst"])
            if len(wer) < 2:
                tx.rollback()
                return
            yield
            tx.schreibe(name, {"im_dienst": False})
            try:
                tx.commit()
                return
            except Konflikt:
                yield        # Retry: neue Transaktion, Menge neu lesen
    return prozess
abmelden_sicher

Wer abgewiesen wird, liest neu. Hat der andere Arzt sich inzwischen abgemeldet, sieht der Verlierer nur noch einen im Dienst und tut nichts. Das ist der Sinn des Retry: Die Entscheidung wird auf aktuellen Daten neu getroffen.

Übung 2: Deadlock im Wait-for-Graph finden (ca. 12 Min.)

Der Graph ist ein Dict: Schlüssel ist ein Prozess, Wert ist die Liste der Prozesse, auf die er wartet. {"A": ["B"], "B": ["A"]} heißt: A wartet auf B und B auf A, das ist ein Deadlock. Schreibe finde_zyklus(wartet). Rückgabe: eine Liste der Prozesse, die den Zyklus bilden (in Wartereihenfolge, jede Drehung ist erlaubt, z. B. ["A", "B"]), oder None, wenn es keinen Zyklus gibt. Beachte:

  • Prozesse können nur als Ziel vorkommen (kein eigener Schlüssel), dann warten sie auf nichts.
  • Ein Prozess kann in den Zyklus hineinführen, ohne selbst Teil davon zu sein: Bei {"A": ["B"], "B": ["C"], "C": ["B"]} ist der Zyklus ["B", "C"].
  • Zwei Wege zum selben Prozess sind kein Zyklus: {"A": ["B", "C"], "B": ["D"], "C": ["D"]} hat keinen Deadlock.

Denk an den Weg aus Schritt 2. Unterscheide “liegt auf meinem aktuellen Weg” von “habe ich irgendwann schon gesehen”. Welcher der drei Hinweisfälle in der Aufgabe (Raute) zeigt, warum das nicht dasselbe ist? Für Tiefensuche (depth-first search) ist eine Rekursion der natürliche Weg.

def finde_zyklus(wartet):
    fertig = set()
    def dfs(knoten, pfad):
        if knoten in pfad:
            return pfad[pfad.index(knoten):]
        if knoten in fertig:
            return None
        for nachbar in wartet.get(knoten, []):
            zyklus = dfs(nachbar, pfad + [knoten])
            if zyklus:
                return zyklus
        fertig.add(knoten)
        return None
    for start in list(wartet):
        zyklus = dfs(start, [])
        if zyklus:
            return zyklus
    return None
finde_zyklus

“Schon besucht” reicht nicht, denn in der Raute wird D zweimal erreicht. Entscheidend ist, ob der Knoten im aktuellen Pfad liegt. Ein Datenbanksystem würde nun eine Transaktion aus dem Zyklus als Opfer wählen und abbrechen (Details, welche, hängen vom System ab, bitte prüfen).

Übung 3: Deadlock vermeiden mit fester Sperrreihenfolge (ca. 10 Min.)

Überweisungen zwischen Konten brauchen die Sperren beider Konten. sperren ist ein Dict Kontoname -> SimLock, konten ein Dict Kontoname -> Stand. Schreibe ueberweisung(konten, sperren, von, nach, betrag) (liefert einen Prozess), sodass gegenläufige Überweisungen (A nach B und gleichzeitig B nach A) nie deadlocken:

  1. Beide Sperren nehmen, mit yield from sperren[name].acquire(von), in einer festen, für alle gleichen Reihenfolge.
  2. Beide Stände lesen, yield (die Bank rechnet), dann beide Stände schreiben.
  3. Beide Sperren wieder freigeben.

Die Prüfung testet fünf Überweisungen über drei Konten reihum und in 40 zufälligen Reihenfolgen.

Die Reihenfolge darf nicht davon abhängen, wer von und wer nach ist. Welche Eigenschaft der beiden Konten ist in beiden Richtungen dieselbe und taugt zum Ordnen? Und vergiss nicht, am Ende beide Sperren freizugeben.

def ueberweisung(konten, sperren, von, nach, betrag):
    def prozess():
        erste, zweite = sorted([von, nach])
        yield from sperren[erste].acquire(von)
        yield from sperren[zweite].acquire(von)
        stand_von, stand_nach = konten[von], konten[nach]
        yield
        konten[von] = stand_von - betrag
        konten[nach] = stand_nach + betrag
        sperren[zweite].release()
        sperren[erste].release()
    return prozess
ueberweisung

Wenn alle Sperren in aufsteigender Namensreihenfolge nehmen, kann kein Zyklus im Wait-for-Graph entstehen: Wer auf eine Sperre wartet, hält nur “kleinere”, und auf die wartet niemand, der eine “größere” hält. (Jede feste Ordnung funktioniert, auch absteigend.)

Merksatz

Gegen Write Skew hilft Serializable mit Retry, ein Lock auf die gelesene Menge oder ein materialisierter Konflikt. Locks kosten Deadlock-Gefahr: Erkennen als Zyklus im Wait-for-Graph, vermeiden mit einer festen globalen Sperrreihenfolge.

Prüfstein

Was ist Write Skew, wie reproduzierst du ihn, und welche Maßnahmen verhindern ihn? Wie entsteht ein Deadlock, und wie vermeidest du ihn?

Zurück zu Teil 1.

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “5. Datenbanken” (Locking); quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 5 “Isolation und Anomalien” (Write Skew, Serializable) und “Concurrency Control” (optimistisches vs. pessimistisches Locking, Deadlock-Erkennung; Prüfstein zu Write Skew).

Über die Quelle hinaus (allgemeines Fachwissen, MiniDB ist ein vereinfachtes Lehrmodell, kein Abbild einer echten Datenbank): die vereinfachte Serializable-Prüfung, Write-Skew-Gegenmaßnahmen (Lock auf Menge, materialisierter Konflikt, Constraint), Wait-for-Graph und feste Sperrreihenfolge, Opferwahl bei Deadlock-Erkennung (bitte prüfen).