Jeder für sich im Recht: Snapshot Isolation, Write Skew und was Serializable wirklich bedeutet

Der Aufhänger: Zwei Transaktionen, beide korrekt, zusammen falsch

Stellen Sie sich einen Bereitschaftsdienst vor. Die Regel ist einfach und steht so in der Betriebsvereinbarung: Mindestens eine Person muss immer eingetragen sein. In der Datenbank ist das eine Tabelle bereitschaft mit einer Spalte eingetragen. Die Anwendung prüft die Regel sauber, so wie man es lernt:

BEGIN;
SELECT count(*) FROM bereitschaft WHERE eingetragen = true;  -- ergibt 2
-- 2 > 1, also darf ich mich austragen
UPDATE bereitschaft SET eingetragen = false WHERE person = 'Anna';
COMMIT;

Der Code ist nicht naiv. Er liest den Zustand, prüft die Invariante, handelt nur, wenn sie erhalten bleibt. In einer Einzelbenutzer-Welt ist er beweisbar richtig.

Nun tun Anna und Bernd dasselbe gleichzeitig. Annas Transaktion liest 2 und entscheidet: in Ordnung. Bernds Transaktion liest, zur selben Zeit, ebenfalls 2 und entscheidet: in Ordnung. Anna trägt sich aus. Bernd trägt sich aus. Beide Transaktionen committen erfolgreich. Es ist niemand im Dienst.

Und jetzt der Teil, der diesen Artikel trägt: Auf den Isolationsstufen, mit denen die meisten Produktionssysteme laufen, ist das kein Bug, sondern dokumentiertes Verhalten. Kein Lost Update, kein Dirty Read, kein Phantom im Sinne des SQL-Standards. Beide Transaktionen haben einen in sich vollständig konsistenten Zustand der Datenbank gesehen. Beide haben korrekt gerechnet. Es gibt nur keine Reihenfolge, in der man sie hintereinander ausführen könnte und dasselbe Ergebnis erhielte – denn wer von beiden zweitens liefe, hätte 1 gelesen und abgebrochen.

Diese Anomalie hat einen Namen, sie ist seit 1995 formal beschrieben, und sie heißt Write Skew. Sie ist der Grund, warum die Frage „auf welcher Isolationsstufe läuft das?" keine Datenbank-Administrations-Frage ist, sondern eine Architekturfrage – und warum die Antwort „SERIALIZABLE, also sicher" in zwei der verbreitetsten Datenbanken der Welt historisch falsch war.

Teil 1: Was Isolation eigentlich verspricht

Das I in ACID wird meistens mit einem Satz erklärt: Transaktionen sollen sich nicht gegenseitig in die Quere kommen. Das ist richtig, aber zu unscharf, um daraus etwas ableiten zu können. Die präzise Fassung heißt Serialisierbarkeit:

Eine nebenläufige Ausführung einer Menge von Transaktionen ist serialisierbar, wenn ihr Ergebnis identisch ist mit dem Ergebnis irgendeiner Ausführung derselben Transaktionen hintereinander, eine nach der anderen.

Das ist eine starke und sehr nützliche Garantie, weil sie etwas über Beweise sagt. Wenn jede einzelne Transaktion, für sich allein betrachtet, eine Invariante erhält, und wenn die Ausführung serialisierbar ist, dann erhält auch die nebenläufige Ausführung die Invariante – per Induktion über die serielle Reihenfolge. Serialisierbarkeit ist die Eigenschaft, die es Anwendungsentwicklern erlaubt, einzeilig zu denken: Prüfe die Invariante in deiner Transaktion, und die Datenbank sorgt dafür, dass niemand dir dazwischenfunkt.

Die PostgreSQL-Dokumentation definiert die Verletzung dieser Garantie als eigenständiges Phänomen, und zwar exakt so:

„serialization anomaly: The result of successfully committing a group of transactions is inconsistent with all possible orderings of running those transactions one at a time."

Der Preis ist der Grund, warum die Geschichte überhaupt kompliziert wird. Der klassische Weg zur Serialisierbarkeit ist das strikte Zwei-Phasen-Sperren (S2PL): Lesen nimmt eine Lesesperre, Schreiben eine Schreibsperre, alle Sperren werden bis zum Commit gehalten. Das funktioniert, ist beweisbar korrekt – und bedeutet, dass Leser Schreiber blockieren. In einem OLTP-System mit Berichten, Dashboards und langen analytischen Abfragen ist das nicht praktikabel. Also hat die Industrie Abkürzungen gebaut, und der SQL-Standard hat sie nachträglich zu Stufen erklärt.

Teil 2: Der Standard und sein Konstruktionsfehler

Die vier Stufen und die drei Phänomene

ANSI SQL-92 definiert vier Isolationsstufen – in der Aufzählung des Standards: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE – und charakterisiert die drei unteren über das, was sie verhindern. Die drei Phänomene lauten im Original:

• P1 (Dirty Read): „Transaction T1 modifies a data item. Another transaction T2 then reads that data item before T1 performs a COMMIT or ROLLBACK."
• P2 (Fuzzy/Non-repeatable Read): „Transaction T1 reads a data item. Another transaction T2 then modifies or deletes that data item and commits."
• P3 (Phantom): „Transaction T1 reads a set of data items satisfying some <search condition>. Transaction T2 then creates data items that satisfy T1's <search condition> and commits."

Daraus ergibt sich die bekannte Matrix: READ UNCOMMITTED erlaubt alle drei, READ COMMITTED verhindert P1, REPEATABLE READ verhindert P1 und P2, SERIALIZABLE verhindert alle drei.

Die Kritik, die den Standard aufgebrochen hat

1995 erschien auf der SIGMOD in San Jose eine Arbeit, die diesen Standard systematisch auseinandernahm: Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil und Patrick O'Neil – A Critique of ANSI SQL Isolation Levels. Die Autorenliste ist bemerkenswert: Microsoft, Sybase und Jim Gray, der Turing-Preisträger für Transaktionsverarbeitung. Es ist keine akademische Randnotiz, sondern eine Korrektur der Industrie an sich selbst.

Die Arbeit macht drei Dinge, die bis heute die Begriffe prägen.

Erstens: Die Phänomene waren zweideutig formuliert. Die Autoren zeigen, dass man die englischen Sätze auf zwei Weisen formalisieren kann. In ihrer Notation – w1[x] ist ein Schreiben von T1 auf x, r2[x] ein Lesen von T2, c1/a1 sind Commit und Abort – gibt es eine strikte Lesart, die nur die tatsächlich eingetretene Anomalie verbietet:

A1:  w1[x] ... r2[x] ... (a1 und c2 in beliebiger Reihenfolge)
A2:  r1[x] ... w2[x] ... c2 ... r1[x] ... c1
A3:  r1[P] ... w2[y in P] ... c2 ... r1[P] ... c1

und eine lockere Lesart, die das ganze Muster verbietet, unabhängig davon, wie es ausgeht:

P1:  w1[x] ... r2[x] ... ((c1 oder a1) und (c2 oder a2) in beliebiger Reihenfolge)
P2:  r1[x] ... w2[x] ... ((c1 oder a1) und (c2 oder a2) beliebig)
P3:  r1[P] ... w2[y in P] ... ((c1 oder a1) und (c2 oder a2) beliebig)

Der Unterschied ist nicht pedantisch. Die Autoren konstruieren die Überweisungs-Historie

H1: r1[x=50] w1[x=10] r2[x=10] r2[y=50] c2 r1[y=50] w1[y=90] c1

in der T1 fünfzig Einheiten von x nach y bucht und T2 zwischendurch eine falsche Summe liest. Diese Historie verletzt P1, aber keines von A1, A2, A3. Wer den Standard strikt liest, muss sie also auf READ COMMITTED zulassen – obwohl T2 einen Zustand gesehen hat, der nie existiert hat. Das Urteil der Arbeit ist unmissverständlich (Remark 4): „Strict interpretations A1, A2, and A3 have unintended weaknesses. The correct interpretations are the Loose ones."

Zweitens: Ein Phänomen fehlte ganz. Die Autoren ergänzen P0 (Dirty Write): w1[x] ... w2[x] ... (c1 oder a1) – zwei Transaktionen überschreiben einander, bevor eine committed ist. Remark 3: „ANSI SQL isolation should be modified to require P0 for all isolation levels." Das klingt selbstverständlich, war es aber nicht; ohne P0 kann man nicht einmal garantieren, dass ein Rollback den vorherigen Wert wiederherstellt.

Drittens, und das ist der konzeptionell wichtigste Punkt: Die Stufen des Standards sind keine Eigenschaften, sondern Beschreibungen einer Implementierung. Die Arbeit sagt es offen: „P0, P1, P2, and P3 are disguised redefinition's of Locking behavior." Die vier Stufen sind im Kern die Antwort auf die Frage, wie lange ein sperrenbasierter Scheduler welche Sperren hält. Für ein System, das gar nicht sperrt, sind sie bestenfalls eine Analogie.

Genau dieses dritte Problem wurde dann dringend – weil die Industrie anfing, nicht mehr zu sperren.

Teil 3: Snapshot Isolation – die Abkürzung, die zu gut funktioniert hat

Der Mechanismus

Die Idee der Mehrversionen-Nebenläufigkeitskontrolle (MVCC) ist einfach und radikal: Ein UPDATE überschreibt nichts, sondern schreibt eine neue Version der Zeile. Alte Versionen bleiben liegen, solange noch jemand sie braucht. Damit kann ein Leser eine beliebig alte, aber in sich konsistente Sicht auf die Datenbank bekommen – ohne eine einzige Sperre und ohne irgendwen zu blockieren.

Berenson et al. formalisieren die daraus entstehende Isolationsstufe und geben ihr den Namen, der heute Standard ist. Die Definition im Original:

„A transaction executing with Snapshot Isolation always reads data from a snapshot of the (committed) data as of the time the transaction started, called its Start-Timestamp."

„A transaction running in Snapshot Isolation is never blocked attempting a read as long as the snapshot data from its Start-Timestamp can be maintained."

Der entscheidende Teil ist die Commit-Regel:

„When the transaction T1 is ready to commit, it gets a Commit-Timestamp, which is larger than any existing Start-Timestamp or Commit-Timestamp. The transaction successfully commits only if no other transaction T2 with a Commit-Timestamp in T1's interval [Start-Timestamp, Commit-Timestamp] wrote data that T1 also wrote. Otherwise, T1 will abort."

„This feature, called First-committer-wins prevents lost updates (phenomenon P4)."

Man kann das ganze Verfahren in zwei Sätzen zusammenfassen, und es lohnt sich, sie sich zu merken:

1. Gelesen wird aus der Vergangenheit. Jede Transaktion sieht die Datenbank, wie sie bei ihrem Start aussah. Punkt. Nichts, was danach committed wird, ist für sie sichtbar.
2. Geschrieben wird mit Konfliktprüfung – aber nur auf Schreiben. Wenn zwei nebenläufige Transaktionen dieselbe Zeile schreiben, verliert eine. Wenn sie verschiedene Zeilen schreiben, gewinnen beide, egal was sie gelesen haben.

Punkt 2 ist die ganze Geschichte in einem Satz. Die Konfliktprüfung ist eine Schreib-Schreib-Prüfung. Lese-Schreib-Beziehungen tauchen in ihr nicht auf.

Warum SI so erfolgreich wurde

Weil Punkt 1 im Alltag fantastisch ist. Leser blockieren nie Schreiber, Schreiber blockieren nie Leser. Ein Bericht, der zwanzig Minuten über einer Milliarde Zeilen läuft, sieht einen sauberen Stand von vor zwanzig Minuten und hält dabei kein einziges OLTP-UPDATE auf. Deadlocks werden selten. Die Antwortzeiten werden vorhersagbarer. Für Systeme mit gemischter Last ist das nicht eine Optimierung, sondern der Unterschied zwischen funktionierend und nicht funktionierend.

Dazu kommt, dass SI auf den Phänomenen des Standards erstaunlich gut dasteht. Berenson et al. zeigen in Remark 8 „READ COMMITTED « Snapshot Isolation" und begründen: „first-committer-wins precludes P0 (dirty writes), and the timestamp mechanism prevents P1 (dirty reads), so Snapshot Isolation is no weaker than READ COMMITTED." Sie nennen SI ausdrücklich „surprisingly strong, even stronger than READ COMMITTED". Kein Dirty Read, kein Non-repeatable Read, kein Lost Update, und auch keine Phantome im Lesepfad – denn aus einem Schnappschuss kann nichts auftauchen, was dort nicht schon war.

Es sieht aus wie SERIALIZABLE. Und es ist nicht serialisierbar. Die Arbeit sagt auch das in einem Satz, und es ist der präziseste Satz über SI, den ich kenne:

„Snapshot Isolation is non-serializable because a transaction's Reads come at one instant and the Writes at another."

Teil 4: Die beiden Anomalien, die den Namen bekamen

Berenson et al. führen zwei neue Anomalien ein, weil die drei des Standards nicht ausreichen, um SI zu charakterisieren.

A5A: Read Skew

A5A:  r1[x] ... w2[x] ... w2[y] ... c2 ... r1[y] ... (c1 oder a1)

„Suppose transaction T1 reads x, and then a second transaction T2 updates x and y to new values and commits. If now T1 reads y, it may see an inconsistent state."

Das ist der klassische Fall des halb gelesenen Transfers: Man liest das Konto vor der Buchung und das Gegenkonto nach der Buchung, und die Summe stimmt nicht. Snapshot Isolation verhindert diese Anomalie vollständig – das ist genau der Punkt, der SI stärker macht als READ COMMITTED, wo sie möglich bleibt.

A5B: Write Skew

A5B:  r1[x] ... r2[y] ... w1[y] ... w2[x] ... (c1 und c2 treten ein)

Das Beispiel der Arbeit (Historie H5) ist die Bank mit einer Invariante über zwei Konten:

H5: r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2

Die Nebenbedingung ist „x + y should be positive", und die Autoren erläutern:

„Write Skew (A5B) could arise from a constraint at a bank, where account balances are allowed to go negative as long as the sum of commonly held balances remains non-negative."

Vorher: 50 + 50 = 100, die Invariante hält. Jede Transaktion hebt 90 von ihrem Konto ab und prüft dabei korrekt, dass die Summe positiv bleiben wird – gegen den Stand, den sie gelesen hat. Nachher: −40 + −40 = −80. Beide haben richtig gerechnet. Die Datenbank hat beide Rechnungen gegen verschiedene, jeweils in sich konsistente Realitäten durchgeführt.

Und hier greift der Mechanismus aus Teil 3 nicht, aus einem ganz banalen Grund: T1 und T2 haben unterschiedliche Zeilen geschrieben. T1 schrieb y, T2 schrieb x. Die First-Committer-Wins-Prüfung findet keine Überschneidung, weil es keine gibt. Der Konflikt steckt nicht im Schreiben, sondern in der Beziehung zwischen dem Lesen der einen und dem Schreiben der anderen Transaktion. Diese Beziehung prüft SI konstruktiv nicht.

Das Bereitschaftsdienst-Beispiel vom Anfang ist genau diese Figur, nur mit count(*) statt mit Kontosalden. Und sie kommt in realen Systemen so oft vor, dass es lohnt, die Form zu kennen:

Was alle Zeilen gemeinsam haben: Die Invariante betrifft eine Menge von Zeilen, geprüft wird mit einem SELECT, und geschrieben wird in eine andere Zeile als die geprüfte.

Der böse Spezialfall: Write Skew über Phantome

Fekete et al. (2005) führen eine Variante vor, die praktisch wichtiger ist als die mit zwei Konten, weil sie den naheliegenden Workaround aushebelt. Die Invariante sei: ein Mitarbeiter darf pro Tag nicht mehr als acht Stunden eingeplant werden. Die Prüfung ist ein SELECT sum(stunden) ... WHERE mitarbeiter = ? AND tag = ?. Zwei Transaktionen planen gleichzeitig je vier Stunden ein, beide lesen die Summe 4, beide fügen eine neue Zeile ein.

Der Standardreflex gegen Write Skew ist, die gelesenen Zeilen zu sperren – in SQL SELECT ... FOR UPDATE. Hier geht das nicht, und die Arbeit sagt auch, warum: Es gibt die Zeile, die man sperren müsste, noch nicht. Im Original:

„it is not possible to avoid this anomaly by performing Select For Update on any set of data items involved."

Das ist dieselbe Stelle, an der sperrenbasierte Systeme Prädikatsperren brauchen – nur dass man sie hier als Anwendungsentwickler nicht hat. Die Lösung der Autoren ist eine Entwurfsänderung: eine Tabelle total_work_hours mit genau einer Zeile pro Mitarbeiter und Tag, die mitgeführt werden muss. Damit wird aus dem Lese-Schreib-Konflikt ein Schreib-Schreib-Konflikt – und den sieht SI.

Teil 5: Der konzeptionelle Umbau – Adyas implementierungsunabhängige Definitionen

Bevor es zur Lösung geht, braucht es noch eine Zwischenstufe, denn sonst versteht man nicht, womit man die Lösung beweist.

Das dritte Problem aus Teil 2 – die Stufen beschreiben Sperrverhalten, nicht Eigenschaften – wurde im Jahr 2000 auf der ICDE von Atul Adya, Barbara Liskov und Patrick O'Neil in Generalized Isolation Level Definitions adressiert. Die Begründung steht so im Abstract:

„as stated in [8], these definitions were simply ‚disguised versions of locking' and therefore disallow optimistic and multi-version mechanisms. […] Thus, these definitions fail to meet the goals of ANSI-SQL with respect to implementation-independence."

Der Ausweg ist ein Graph. Die Autoren definieren den Direct Serialization Graph (DSG): Knoten sind committete Transaktionen, Kanten sind direkte Konflikte, und es gibt genau drei Arten davon:

• ww (write-dependency): „A transaction Tj directly write-depends on Ti if Ti installs a version xi and Tj installs x's next version (after xi) in the version order."
• wr (read-dependency): Tj liest eine Version, die Ti geschrieben hat.
• rw (anti-dependency): Tj überschreibt eine Version, die Ti gelesen hat.

Die rw-Antidependenz ist der eigentliche Fortschritt. Sie ist die einzige der drei Kanten, bei der die Information „rückwärts" fließt: Nicht T2 erfährt etwas von T1, sondern T2 macht etwas ungültig, das T1 gesehen hat. Genau diese Kante fehlt in der Konfliktprüfung von Snapshot Isolation.

Mit dem Graphen werden die Anomalien zu Zyklen, nicht zu Mustern:

• G0 (Write Cycles): „A history H exhibits phenomenon G0 if DSG(H) contains a directed cycle consisting entirely of write-dependency edges."
• G1a/G1b: Lesen aus abgebrochenen bzw. aus nicht-finalen Zwischenversionen.
• G1c (Circular Information Flow): „A history H exhibits phenomenon G1c if DSG(H) contains a directed cycle consisting entirely of dependency edges."
• G2 (Anti-dependency Cycles): „A history H exhibits phenomenon G2 if DSG(H) contains a directed cycle with one or more anti-dependency edges."

Daraus werden die portablen Stufen PL-1 (verbietet G0), PL-2 (verbietet G1), PL-2.99 (verbietet G1 und G2-item) und PL-3 (verbietet G1 und G2) – wobei die Autoren festhalten: „our PL-3 conditions provide what is normally considered as serializability."

Der Gewinn dieser Umstellung ist nicht Eleganz, sondern Entscheidbarkeit. „Verhindert diese Stufe Phantome?" ist eine Frage über Formulierungen. „Enthält der Abhängigkeitsgraph einen Zyklus mit mindestens einer Antidependenz-Kante?" ist eine Frage über ein Objekt, das man konstruieren und prüfen kann. Und aus genau dieser Umstellung folgt fünf Jahre später die Lösung.

Teil 6: Die gefährliche Struktur – der Satz, der alles ändert

2005 erschien in den ACM Transactions on Database Systems, Vol. 30, No. 2, Seiten 492–528, die Arbeit, die aus der Diagnose eine Therapie macht: Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil und Dennis Shasha – Making Snapshot Isolation Serializable.

Der Ansatzpunkt ist eine Beobachtung über die Graphen, die SI überhaupt erzeugen kann. Unter SI ist die Versionsordnung durch die Commit-Zeiten festgelegt – im Original: „the version order is defined by the temporal sequence of the commit times of the transactions that produced the versions". Das schränkt die möglichen Zyklen stark ein. Und dann kommt der zentrale Satz. Die Nachfolgearbeit von Cahill et al. zitiert ihn so:

„any cycle must have two rw-dependency edges that occur consecutively, and further, each of these edges is between two concurrent transactions."

In Worten: Jede nicht-serialisierbare Ausführung unter Snapshot Isolation enthält zwei unmittelbar aufeinanderfolgende rw-Antidependenz-Kanten zwischen jeweils nebenläufigen Transaktionen. Eine solche Kante heißt vulnerable edge, das Muster aus zwei aufeinanderfolgenden heißt dangerous structure, und die Transaktion in der Mitte – die eine eingehende und eine ausgehende verwundbare Kante hat – heißt Pivot. Cahill et al. fassen die Konsequenz zusammen: „The theory of [9] shows that there is a pivot in any non-serializable execution allowed by SI."

Ich halte das für einen der schönsten Sätze der Datenbanktheorie, und zwar wegen seiner Richtung. Er behauptet nicht: „diese Muster sind schlecht". Er behauptet: Alles, was schiefgehen kann, hat eine gemeinsame, lokal erkennbare Signatur. Man muss nicht den ganzen Graphen auf Zyklen prüfen – man muss nur nach einer einzigen Transaktion suchen, bei der zwei Flaggen gleichzeitig gesetzt sind.

Was man damals schon damit anfangen konnte

Die Arbeit ist von 2005, und zu diesem Zeitpunkt gab es keine Datenbank, die das umgesetzt hätte. Die Autoren richten sie deshalb an Anwendungsentwickler, und ihre beiden Rezepte sind bis heute die Notfall-Werkzeuge für jeden, der auf SI festsitzt:

Promotion – aus einem Lesen ein Schreiben machen:

„One way to do this is to require in the transactional program that each Read of X and Y to update Y give the impression of a Write of X (this is possible in Oracle using the Select For Update statement)."

Materialisierung des Konflikts – die Invariante ein eigenes Datum geben:

„Another approach requires that each constraint on the sum of two accounts X and Y be materialized in another data item Z, and insists that all updates of X and Y must keep Z up to date."

Beide Rezepte tun dasselbe: Sie verwandeln eine rw-Kante, die SI nicht sieht, in eine ww-Kante, die SI sieht. Das ist der ganze Trick, und man kann ihn in jedem ORM anwenden.

Und dann steht im Abstract ein Befund, der erklärt, warum die Welt mit SI so lange gut gefahren ist:

„SI does not guarantee serializability in all cases, but the TPC-C benchmark application [TPC-C], for example, executes under SI without serialization anomalies."

TPC-C, der Industriestandard für OLTP-Benchmarks, läuft unter Snapshot Isolation anomaliefrei. Nicht weil die Datenbank etwas verhindert, sondern weil die Struktur dieser Anwendung keine gefährliche Struktur erzeugen kann. Das ist die statistische Erklärung für ein Phänomen, das jeder Betreiber kennt: Write Skew ist kein häufiger Fehler, sondern ein seltener – und deshalb einer, der erst in Produktion und unter Last auffällt.

Teil 7: Von der Theorie ins Produkt

Cahill 2008: die Laufzeiterkennung

Auf der SIGMOD 2008 in Vancouver zeigten Michael J. Cahill, Uwe Röhm und Alan D. Fekete in Serializable Isolation for Snapshot Databases, dass man den Pivot zur Laufzeit erkennen kann – mit zwei Bits pro Transaktion. Im Original:

„T.inConflict indicates whether there is an rw-dependency from another concurrent transaction to T, and T.outConflict indicates whether there is an rw-dependency from T to another concurrent transaction. Thus a potential non-serializability is detected when T.inConflict and T.outConflict are both true."

Um die Kanten überhaupt zu bemerken, braucht es eine Buchführung über Lesevorgänge. Die Arbeit führt dafür eine neue Sperrart ein, deren entscheidende Eigenschaft ist, dass sie nicht sperrt:

„We also introduce a new lock mode called SIREAD. This remembers the fact that an SI transaction has read a version of an item. However, obtaining the SIREAD lock does not cause any blocking, even if a WRITE lock is held already…"

„the presence of both SIREAD and WRITE locks on an item is a sign of an rw-dependency, and so we set the appropriate inConflict and outConflict flags."

Die Korrektheitsargumentation ist drei Zeilen lang und besteht genau aus dem Satz von Fekete plus Vollständigkeit der Erkennung plus dem Abbruch:

„1. Non-serializable executions under SI consist of a cycle including two consecutive rw-dependencies. 2. Our algorithm detects every rw-dependency. 3. When two consecutive rw-dependencies are detected, at least one transaction is aborted which breaks the cycle."

Zwei Dinge sind an dieser Arbeit bemerkenswert. Erstens ist das Verfahren konservativ, und die Autoren sagen das ausdrücklich: „However, we do sometimes make false positive detections; for example, an unnecessary detection may happen because we do not check whether the two rw-dependency edges occur within a cycle." Man prüft nur die lokale Signatur, nicht den globalen Zyklus. Das kostet unnötige Abbrüche und spart die Zyklensuche. Zweitens war der Eingriff winzig: Implementiert „in Oracle Berkeley DB version 4.6.21", und „In total, only 692 lines of code (LOC) were modified out of a total of over 200,000 lines of code in Berkeley DB."

PostgreSQL 9.1: die erste Produktionsimplementierung

2012 erschien in den Proceedings of the VLDB Endowment, Vol. 5, No. 12, die Arbeit, die daraus ein Produkt machte: Dan R. K. Ports (MIT CSAIL) und Kevin Grittner (Consolidated Court Automation Programs, Wisconsin Supreme Court) – Serializable Snapshot Isolation in PostgreSQL. Der Anspruch steht im Abstract:

„This is the first implementation of SSI in a production database release as well as the first in a database that did not previously have a lock-based serializable isolation level."

„In the latest PostgreSQL 9.1 release, we introduced a serializable isolation level that retains many of the performance benefits of snapshot isolation while still guaranteeing true serializability."

Die Beiträge über Cahill hinaus sind im Wesentlichen das, was aus einem Paper-Prototyp ein betreibbares System macht:

• Ein eigener Sperrmanager für Lese-Abhängigkeiten: „Lacking this infrastructure, we were required to build a new lock manager. Our lock manager is specifically optimized for tracking SSI read dependencies…"
• Begrenzter Speicherverbrauch durch Zusammenfassung alter Transaktionen: „we describe a transaction summarization technique that ensures that the SSI implementation uses a bounded amount of RAM without limiting the number of concurrent transactions."
• Safe Retry – die Regel, dass ein unmittelbar wiederholter Versuch nicht wieder an derselben Stelle scheitert: „We also introduce a safe retry rule, which resolves conflicts by aborting transactions in such a way that an immediately retried transaction does not fail in the same way."
• Safe Snapshots und deferrable Transaktionen für Nur-Lese-Last: „which allow certain read-only transactions to execute without the overhead of SSI by identifying cases where snapshot isolation anomalies cannot occur." Die Definition: „A read-only transaction T has a safe snapshot if no concurrent read/write transaction has committed with a rw-antidependency out to a transaction that committed before T's snapshot, or has the possibility to do so."

Und der Satz, der die Diskussion über die Kosten beendet hat – aus der Einleitung der Arbeit:

„Our experiments with a transaction processing and a web application benchmark show that our serializable mode has a performance cost of less than 7% relative to snapshot isolation, and outperforms two-phase locking significantly on some workloads."

Weniger als sieben Prozent gegenüber Snapshot Isolation, für echte Serialisierbarkeit. Das ist der Grund, warum die alte Abwägung „Korrektheit oder Performance" bei dieser Frage seit 2011 nicht mehr gilt.

Teil 8: Die Landkarte – was Ihre Datenbank wirklich tut

Hier wird die Theorie unangenehm konkret, denn der Name einer Isolationsstufe sagt nicht, was sie leistet.

PostgreSQL

Die Dokumentation ist in diesem Punkt vorbildlich offen. Drei Sätze genügen:

„In PostgreSQL, you can request any of the four standard transaction isolation levels, but internally only three distinct isolation levels are implemented, i.e., PostgreSQL's Read Uncommitted mode behaves like Read Committed."

„The Repeatable Read isolation level is implemented using a technique known in academic database literature and in some other database products as Snapshot Isolation."

„The Serializable isolation level is implemented using a technique known in academic database literature as Serializable Snapshot Isolation, which builds on Snapshot Isolation by adding checks for serialization anomalies."

REPEATABLE READ ist Snapshot Isolation. Entsprechend führt die Dokumentation „Serialization Anomaly" als eigene Spalte und markiert sie für READ UNCOMMITTED, READ COMMITTED und REPEATABLE READ als „Possible", nur für SERIALIZABLE als „Not possible". Das heißt im Klartext: Write Skew ist auf der Stufe mit dem beruhigenden Namen REPEATABLE READ möglich.

Ein Detail mit Geschichte: „Prior to PostgreSQL version 9.1, a request for the Serializable transaction isolation level provided exactly the same behavior described here." Wer vor 2011 SERIALIZABLE angefordert hat, bekam Snapshot Isolation.

Das Beispiel in der Dokumentation ist die Write-Skew-Figur in Reinform: Tabelle mytab mit (class, value) = (1,10), (1,20), (2,100), (2,200). Transaktion A liest SELECT sum(value) WHERE class = 1 (= 30) und fügt 30 als Zeile der Klasse 2 ein; B liest die Summe der Klasse 2 (= 300) und fügt 300 als Zeile der Klasse 1 ein. Unter REPEATABLE READ committen beide. Unter SERIALIZABLE scheitert eine mit ERROR: could not serialize access due to read/write dependencies among transactions. Die Begründung der Dokumentation: „if A had executed before B, B would have computed the sum 330, not 300".

Betrieblich wichtig sind drei Punkte. Erstens: Die Prädikatsperren blockieren nicht – „In PostgreSQL these locks do not cause any blocking and therefore can not play any part in causing a deadlock" (sichtbar in pg_locks als SIReadLock). Zweitens: Man braucht einen Wiederholungsmechanismus – „it is important that an environment which uses this technique have a generalized way of handling serialization failures (which always return with an SQLSTATE value of '40001')". Drittens: Die Empfehlungen zur Performance sind ungewohnt – READ ONLY deklarieren wo möglich, Transaktionen klein halten, Verbindungen poolen, und ausdrücklich: „Eliminate explicit locks, SELECT FOR UPDATE, and SELECT FOR SHARE where no longer needed due to the protections automatically provided by Serializable transactions." Dazu ein Fallstrick, der echte Systeme trifft: „A sequential scan will always necessitate a relation-level predicate lock" – wenn der Planer einen Seq Scan wählt, wird die Prädikatsperre so grob, dass die Abbruchrate steigt.

SQL Server

Hier heißt die Stufe, was sie ist: SNAPSHOT, und sie ist nicht standardmäßig aktiv, sondern muss pro Datenbank eingeschaltet werden (ALTER DATABASE … SET ALLOW_SNAPSHOT_ISOLATION ON). Die Versionen liegen im Version Store, laut Dokumentation in tempdb – oder, mit Accelerated Database Recovery, in der Datenbank selbst. Davon getrennt gibt es READ_COMMITTED_SNAPSHOT ON: damit nutzt das vorhandene READ COMMITTED Zeilenversionen und liefert Statement-Konsistenz statt Transaktions-Konsistenz, ohne den Code zu ändern.

Der Schreibkonflikt äußert sich als Fehler 3960: „Snapshot isolation transaction aborted due to update conflict. … Retry the transaction or change the isolation level for the update/delete statement." Das ist First-Committer-Wins, operationalisiert. Die Dokumentation nennt auch den Workaround aus Teil 6 – „You can avoid this by using UPDLOCK hints for SELECT statements that access data to be modified" – also Promotion. Was SQL Server nicht anbietet, ist SSI: Die Stufe SERIALIZABLE ist hier sperrenbasiert (mit Range Locks), mit den entsprechenden Blockierungs- und Deadlock-Eigenschaften. Die Wahl ist also eine andere als in PostgreSQL: Snapshot mit Write Skew, oder Sperren mit Wartezeiten.

Die Zusammenfassung in einer Tabelle

Die praktische Konsequenz: Dieselbe Anwendung, dieselbe IsolationLevel-Konstante im C#-Code, zwei völlig verschiedene Garantien. Und in beiden Fällen ist die Standardstufe READ COMMITTED – die schwächste, auf der Write Skew möglich ist.

Teil 9: Die verteilte Grenze – warum SI nicht hochverfügbar sein kann

Es gibt noch ein Resultat, das erklärt, warum Snapshot Isolation nicht nur eine bequeme Abkürzung, sondern in verteilten Systemen manchmal die stärkste erreichbare Stufe ist – und manchmal eine zu starke.

In den Proceedings of the VLDB Endowment, Vol. 7, No. 3, Seiten 181–192, untersuchen Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein und Ion Stoica in Highly Available Transactions: Virtues and Limitations, welche Garantien mit Hochverfügbarkeit im CAP-Sinn vereinbar sind. Das Ergebnis, aus der Einleitung:

„besides serializability, Snapshot Isolation and Repeatable Read isolation are not HAT-compliant, while most other isolation levels are achievable with high availability."

Erreichbar sind unter anderem Read Uncommitted, Read Committed, Monotonic Atomic View, Item und Predicate Cut Isolation, Monotonic Reads und Writes; mit „sticky" Verfügbarkeit zusätzlich Read Your Writes, PRAM und kausale Konsistenz. Nicht erreichbar sind Cursor Stability, Snapshot Isolation, Repeatable Read, One-Copy Serializability und Linearisierbarkeit.

Die Begründung für SI ist kurz und bündig – zwei Clients auf verschiedenen Seiten einer Netzpartition erhöhen denselben Wert:

„Each client's respective server might try to detect that another write occurred, but this requires knowing the version of the latest write to x. In our example, this reduces to a requirement for linearizability, which is, via Gilbert and Lynch's proof of the CAP Theorem, provably at odds with high availability."

Das ist die tiefere Pointe: Snapshot Isolation scheitert in verteilten Systemen nicht am Lesen – ein Schnappschuss ist billig und lokal beantwortbar –, sondern genau an der einen Prüfung, die sie überhaupt macht, nämlich der Schreib-Schreib-Erkennung. First-Committer-Wins braucht eine globale Reihenfolge, und eine globale Reihenfolge braucht Koordination. Der Preis dafür ist messbar: Die Arbeit gibt für Amazon EC2 von São Paulo nach Singapur „362.8ms RTT (95th percentile: 649ms)" an und beobachtet in ihren Experimenten über fünf Rechenzentren, dass die Latenz der koordinierenden Variante „increases to nearly 800ms per transaction".

Die zentrale Erkenntnis zum Mitnehmen

1. Der Name einer Isolationsstufe ist kein Vertrag. REPEATABLE READ in PostgreSQL ist Snapshot Isolation und erlaubt Serialisierungsanomalien; SERIALIZABLE war dort vor Version 9.1 dasselbe. Wer Garantien braucht, liest die Dokumentation seines konkreten Systems, nicht den Standard.
2. Snapshot Isolation prüft Schreiben gegen Schreiben – nicht Lesen gegen Schreiben. Alles, was SI falsch macht, folgt aus diesem einen Satz. Wenn Ihre Invariante über eine Menge von Zeilen geht und Sie in eine andere Zeile schreiben als die geprüfte, sind Sie in der Write-Skew-Figur.
3. Jede nicht-serialisierbare SI-Ausführung hat eine lokal erkennbare Signatur. Fekete et al. haben gezeigt, dass zwei aufeinanderfolgende rw-Antidependenzen nötig sind – und erst dieser Satz hat SSI möglich gemacht. Das ist das Muster: Erst die implementierungsunabhängige Theorie (Adya), dann der strukturelle Satz, dann die billige Laufzeitprüfung.
4. Korrektheit kostet hier weniger, als die Folklore behauptet. Ports und Grittner messen „less than 7%" gegenüber Snapshot Isolation. Das Gegenargument gegen SERIALIZABLE in PostgreSQL ist nicht mehr der Durchsatz, sondern die Pflicht, Serialisierungsfehler (SQLSTATE 40001) zu wiederholen.
5. Wenn Sie auf SI festsitzen, verwandeln Sie Lesen in Schreiben. Promotion (SELECT … FOR UPDATE) oder Materialisierung der Invariante in eine eigene Zeile machen aus der unsichtbaren rw-Kante eine sichtbare ww-Kante. Für die Phantom-Variante hilft nur die Materialisierung – sperren kann man eine Zeile nicht, die es noch nicht gibt.

Konkreter Handlungsanstoß für diese Woche: Suchen Sie in Ihrer Codebasis nach dem Muster Lesen – Prüfen – Schreiben innerhalb einer Transaktion. In C# mit Entity Framework ist das jede Methode, die erst eine Any()-, Count()- oder Sum()-Abfrage macht, dann eine Bedingung auswertet und dann SaveChangesAsync() aufruft. Nehmen Sie eine solche Stelle und beantworten Sie drei Fragen schriftlich:

1. Auf welcher Isolationsstufe läuft diese Transaktion tatsächlich? (Nicht: welche ist konfiguriert, sondern welche ist in dieser Datenbank wirksam – der Default ist fast immer READ COMMITTED.)
2. Schreibe ich in genau die Zeilen, die ich gelesen habe? Wenn nein, ist Write Skew möglich.
3. Was passiert, wenn die Invariante verletzt wird – fällt es auf, oder bleibt es als stiller Datenfehler liegen?

Wenn Frage 2 mit „nein" und Frage 3 mit „bleibt liegen" beantwortet wird, haben Sie eine der drei Lösungen: die Invariante als Datenbankbedingung (UNIQUE, CHECK, Exclusion Constraint), die Materialisierung in eine Aggregatzeile, oder SERIALIZABLE mit Retry-Schleife. Die Reihenfolge ist absichtlich: Eine Bedingung, die die Datenbank selbst durchsetzt, ist der einzige dieser drei Wege, der auch dann hält, wenn jemand künftig die Isolationsstufe ändert.

Reflexionsfrage: Der Fortschritt in dieser Geschichte kam nicht von einem schnelleren Algorithmus, sondern davon, dass jemand aufgehört hat, Korrektheit über verbotene Muster zu definieren, und angefangen hat, sie über ein mathematisches Objekt zu definieren, in dem man suchen kann. Erst dann war beweisbar, dass alle Fehler eine gemeinsame, lokale Signatur haben – und erst dann war die Prüfung billig. Welche Korrektheitsregel in Ihrem eigenen System ist heute eine Liste verbotener Fälle, die bei jedem neuen Feature länger wird – und welches Objekt müssten Sie konstruieren, damit aus der Liste eine Eigenschaft wird?

Querverweise im Vault

• Das Versprechen, das keiner halten kann: Zwei-Phasen-Commit, Sagas und das Ende der verteilten Transaktion – die Atomizität als Gegenstück zur Isolation: dort geht es um das A in ACID über Systemgrenzen hinweg, hier um das I innerhalb eines Systems.
• Einigkeit ohne Abstimmung: CRDTs und die Kunst der konfliktfreien Replikation – die radikale Gegenantwort auf Teil 9: Wenn Koordination unvereinbar mit Verfügbarkeit ist, entwerfe Datentypen, die keine brauchen.
• Die Ordnung ohne Uhr: Lamport-Zeitstempel, Vektoruhren und die Kausalität verteilter Systeme – die Vorgeschichte der Abhängigkeitskanten: happened-before ist genau das Werkzeug, mit dem Adyas DSG operiert.
• Uhren, die ihre eigene Unsicherheit kennen: Google Spanner, TrueTime und die Beherrschung der Zeit in der Cloud – wie man Start- und Commit-Timestamps global vergibt, wenn man bereit ist, in Hardware zu investieren.
• Wie Maschinen sich einig werden: Verteilter Konsens von FLP über Paxos zu Raft – was Koordination kostet, wenn man sie nicht vermeiden kann.
• Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen – ein Entwurf, der die Invariantenprüfung in den Schreibpfad eines einzigen Streams verlegt und damit Write Skew strukturell ausschließt.
• Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank – die Speicherseite der Mehrversionen-Idee: alte Versionen liegenlassen statt überschreiben.
• Der lange Schwanz der Latenz: Tail Latency und warum Mittelwerte in der Cloud lügen – warum Abbruch-und-Wiederholung sich im Mittelwert versteckt und im 99. Perzentil zeigt.

Quellen und zum Weiterlesen

• Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, Patrick O'Neil – A Critique of ANSI SQL Isolation Levels, SIGMOD '95, San Jose, CA, 1995: https://www.cs.umb.edu/~poneil/iso.pdf
• Atul Adya, Barbara Liskov, Patrick O'Neil – Generalized Isolation Level Definitions, Proceedings of the IEEE International Conference on Data Engineering (ICDE), San Diego, CA, März 2000: https://pmg.csail.mit.edu/papers/icde00.pdf
• Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil, Dennis Shasha – Making Snapshot Isolation Serializable, ACM Transactions on Database Systems, Vol. 30, No. 2, Juni 2005, S. 492–528: https://dsf.berkeley.edu/cs286/papers/ssi-tods2005.pdf
• Michael J. Cahill, Uwe Röhm, Alan D. Fekete – Serializable Isolation for Snapshot Databases, SIGMOD '08, Vancouver, BC, Juni 2008: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F13/handouts/papers/p729-cahill.pdf
• Dan R. K. Ports, Kevin Grittner – Serializable Snapshot Isolation in PostgreSQL, Proceedings of the VLDB Endowment, Vol. 5, No. 12, 2012 (arXiv:1208.4179): https://arxiv.org/abs/1208.4179
• Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica – Highly Available Transactions: Virtues and Limitations, Proceedings of the VLDB Endowment, Vol. 7, No. 3, S. 181–192: https://www.vldb.org/pvldb/vol7/p181-bailis.pdf
• PostgreSQL Global Development Group – PostgreSQL Documentation, Chapter 13.2: Transaction Isolation: https://www.postgresql.org/docs/current/transaction-iso.html
• Microsoft – Snapshot isolation in SQL Server: https://learn.microsoft.com/sql/connect/ado-net/sql/snapshot-isolation-sql-server
• Microsoft – Transaction locking and row versioning guide: https://learn.microsoft.com/sql/relational-databases/sql-server-transaction-locking-and-row-versioning-guide

Erstellt im Rahmen des täglichen Lern-Workflows. Interessensgebiet: Software-Architekturen. Geschätzte Lesedauer: ~30 Minuten.

← All articles