2024-10-30

Für Analytik optimierte nebenläufige Transaktionen

Mark Raasveldt, Hannes Mühleisen

Das ist der zweite Beitrag zu DuckDBs ACID-Unterstützung. Wenn Sie den ersten noch nicht gelesen haben, Daten mit Vertrauen und ACID ändern, beginnen Sie am besten dort.

Im vorherigen Beitrag haben wir erläutert, warum Änderungen an Daten deutlich vernünftiger sind, wenn die formalen „ACID“-Transaktionseigenschaften gelten. Ein Datensystem sollte nicht erlauben, „die Hälfte“ einer CSV-Datei in eine Tabelle zu importieren, nur weil in Zeile 431.741 ein unerwarteter String steht.

Die ACID-Eigenschaften von Transaktionen unter Nebenläufigkeit zu sichern, ist sehr anspruchsvoll und eines der „Heiligen Grale“ der Datenbanken. DuckDB implementiert fortgeschrittene Verfahren für Concurrency Control und Logging. In diesem Beitrag beschreiben wir DuckDBs Multi-Version-Concurrency-(MVCC-) und Write-Ahead-Logging-(WAL-)Schemata, die speziell dafür entworfen sind, transaktionale Garantien für analytische Anwendungsfälle unter nebenläufiger Last effizient zu sichern.

Concurrency Control

Pessimistische Concurrency Control. Klassische Datenbanksysteme steuern Nebenläufigkeit über Locks. Eine Transaktion holt Locks, damit (a) keine andere Transaktion ihre uncommitted Änderungen sieht und (b) sie keine uncommitted Änderungen anderer Transaktionen sieht. Locks braucht man beim Lesen (Shared Locks) und beim Schreiben (Exclusive Locks). Versucht eine andere Transaktion Daten zu lesen, die eine andere Transaktion geschrieben hat, muss sie warten, bis die andere Transaktion fertig ist und ihren Exclusive Lock freigibt. Diese Art der Concurrency Control heißt pessimistisch, weil Locks immer geholt werden, auch wenn es keine Konflikte zwischen Transaktionen gibt.

Diese Strategie funktioniert gut für transaktionale Workloads. Die bestehen aus kleinen Transaktionen, die wenige Zeilen lesen oder ändern. Eine typische Transaktion lockt nur wenige Zeilen und hält die Locks nur kurz. Für analytische Workloads funktioniert das schlecht. Die bestehen aus großen Transaktionen, die große Teile der Tabelle lesen oder ändern. Eine analytische Transaktion in einem System mit pessimistischer Concurrency Control lockt daher viele Zeilen und hält die Locks lange – andere Transaktionen können nicht laufen.

Optimistische Concurrency Control. DuckDB steuert Nebenläufigkeitskonflikte anders. Transaktionen halten keine Locks – sie können immer jede Zeile in jeder Tabelle lesen und schreiben. Tritt ein Konflikt auf und mehrere Transaktionen schreiben gleichzeitig in dieselbe Zeile, wird eine der konfliktierenden Transaktionen abgebrochen. Die abgebrochene Transaktion kann bei Bedarf wiederholt werden. Diese Art der Concurrency Control heißt optimistisch.

Gibt es nie Nebenläufigkeitskonflikte, ist diese Strategie sehr effizient, weil wir Transaktionen nicht unnötig durch pessimistisches Locking verlangsamt haben. Das passt gut zu analytischen Workloads: Read-only-Transaktionen können einander nie konfliktieren, und mehrere Writer, die dieselben Zeilen ändern, sind in diesen Workloads selten.

Multi-Version Concurrency Control

In einem optimistischen Concurrency-Control-Modell können mehrere Transaktionen dieselben Tabellen gleichzeitig lesen und ändern. Damit ACID-Isolation gilt, dürfen sie einander halbfertige Änderungen nicht sehen. Eine bekannte Technik dafür ist Multi-Version Concurrency Control (MVCC). MVCC hält mehrere Versionen geänderter Zeilen. Ändert eine Transaktion eine Zeile, können wir eine Kopie anlegen und diese ändern. Andere Transaktionen lesen weiter die Originalversion. So sieht jede Transaktion ihren eigenen, konsistenten Datenbankzustand. Oft ist das die „Version“, die beim Start der Transaktion existierte. MVCC ist in Datenbanksystemen weit verbreitet; auch PostgreSQL nutzt MVCC.

DuckDB implementiert MVCC mit einer Technik, die vom Paper „Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems“ des einen und einzigen Thomas Neumann inspiriert ist. Diese MVCC-Implementierung hält für jede Zeile einer Tabelle eine Liste früherer Versionen. Transaktionen aktualisieren die Tabellendaten in-place, speichern die vorherige Version der geänderten Zeile aber in den Undo-Buffern. Unten ein illustriertes Beispiel.

-- add 5 to Sally's balance
UPDATE Accounts SET Balance = Balance + 5 WHERE Name = 'Sally';

Beim Lesen einer Zeile prüft eine Transaktion zuerst, ob es Versionsinformationen für diese Zeile gibt. Wenn nicht – der häufige Fall –, kann sie die Originaldaten lesen. Gibt es Versionsinformationen, muss die Transaktion die Transaktionsnummer zum Startzeitpunkt mit denen in den Undo-Buffern vergleichen und die richtige Version lesen.

Effizientes MVCC für Analytik

Der obige Ansatz funktioniert gut für transaktionale Workloads, in denen einzelne Zeilen häufig geändert werden. Für analytische Anwendungsfälle sehen wir ein ganz anderes Nutzungsmuster: Änderungen sind viel „massiger“ und betreffen oft nur eine Teilmenge der Spalten. Zum Beispiel löschen wir meist nicht einzelne Zeilen, sondern alle Zeilen, die einem Muster entsprechen, z. B.:

DELETE FROM orders WHERE order_time < DATE '2010-01-01';

Häufig sind auch Bulk-Updates von Spalten, z. B. um den ewigen Ärger zu beheben, dass Leute unsinnige In-Domain-Werte für NULL verwenden:

UPDATE people SET age = NULL WHERE age = -99;

Hat jede Zeile Versionsinformationen, erzeugen solche Bulk-Änderungen eine enorme Menge Einträge in den Undo-Buffern, die viel Speicher brauchen und ineffizient zu verarbeiten und zu lesen sind.

Es gibt noch eine Komplikation: Der Originalansatz setzt auf In-Place-Updates. Die können wir auf unkomprimierten Daten effizient ausführen, nicht aber, wenn Daten komprimiert sind. Da DuckDB Daten komprimiert hält, sowohl auf der Platte als auch im Speicher, sind In-Place-Updates nicht möglich.

Deshalb speichert DuckDB Bulk-Versionsinformationen pro Spalte. Für jeden Batch von 2048 Zeilen wird ein einziger Versionsinformationseintrag gehalten. Die Versionsinformation speichert die Änderungen an den Daten, nicht die alten Daten, weil wir die Originaldaten nicht in-place ändern können. Änderungen werden beim Checkpoint auf die Platte geschrieben. Unten ein illustriertes Beispiel.

-- add 20% interest to all accounts
UPDATE Accounts SET Balance = Balance + Balance / 5;

Ein schöner Aspekt dieses Undo-Buffer-Schemas: Es ist weitgehend performance-transparent. Ohne Änderungen entstehen keine Extra-Rechenkosten für Transaktionsunterstützung. Soweit uns bekannt, ist DuckDB das einzige transaktionale Datenmanagementsystem, das für Bulk-Änderungen an Daten optimiert ist, wie sie in analytischen Anwendungsfällen üblich sind. Aber selbst mit vorhandenen Änderungen ist unser Transaktionsschema sehr schnell für die Transaktionen, die wir in der Analytik erwarten.

Benchmarks

Hier ein kleines Experiment, das DuckDB 1.1.0, HyPer 9.1.0, SQLite 3.43.2 und PostgreSQL 14.13 auf einem aktuellen MacBook Pro vergleicht und einige Effekte eines OLAP-optimierten Transaktionsschemas zeigt. HyPer implementiert das MVCC-Schema aus dem oben genannten Neumann-Paper. SQLite implementiert MVCC eigentlich nicht; es dient vor allem als Vergleichspunkt.

Wir erzeugen zwei Tabellen mit entweder 1 oder 100 Spalten, jeweils mit 10 Millionen Zeilen, die die Integer-Werte 1–100 wiederholen.

CREATE TABLE mvcc_test_1 (i INTEGER);
INSERT INTO mvcc_test_1
    SELECT s1
    FROM
        generate_series(1, 100) s1(s1),
        generate_series(1, 100_000) s2(s2);

CREATE TABLE mvcc_test_100 (i INTEGER,
    j1 INTEGER, j2 INTEGER, ..., j99 INTEGER);
INSERT INTO mvcc_test_100
    SELECT s1, s1, s1, ..., s1
    FROM
        generate_series(1, 100) s1(s1),
        generate_series(1, 100_000) s2(s2);

Dann führen wir drei Transaktionen auf beiden Tabellen aus, die eine einzelne Spalte inkrementieren, mit steigender Zahl betroffener Zeilen: 1 %, 10 % und 100 %:

UPDATE mvcc_test_... SET i = i + 1 WHERE i <= 1;
UPDATE mvcc_test_... SET i = i + 1 WHERE i <= 10;
UPDATE mvcc_test_... SET i = i + 1 WHERE i <= 100;

Im Ein-Spalten-Fall sollte es keine großen Unterschiede zwischen zeilen- und spaltenorientiertem Concurrency-Control-Schema geben, und die Ergebnisse zeigen das:

Mehr geänderte Zeilen brauchten mehr Zeit. Die Zeilen sind klein, jede enthält nur einen Wert. DuckDB und HyPer mit ihrem moderneren Undo-Buffer-MVCC sind generell deutlich schneller als PostgreSQL. SQLite schlägt sich gut, hat aber natürlich kein MVCC. Die Zeiten steigen grob um den Faktor 10, wenn sich die Zahl geänderter Zeilen verzehnfacht. Soweit so gut.

Im 100-Spalten-Fall sehen die Ergebnisse ganz anders aus:

Erinnerung: Hier ändern wir eine einzelne Spalte von 100, ein häufiger Fall beim Aufbereiten analytischer Datensätze. Weil DuckDBs MVCC-Schema dafür entworfen ist, zeigt es genau dieselbe Laufzeit wie im Ein-Spalten-Experiment oben. In SQLite wirkt sich die größere Zeilengröße klar auf die Update-Zeit aus, obwohl es kein MVCC gibt. HyPer und PostgreSQL zeigen ebenfalls viel größere, bis zu 100-fache (!) Verlangsamungen, wenn die Zahl geänderter Zeilen steigt.

Das führt uns sauber zum Checkpointing.

Write-Ahead Logging und Checkpointing

Daten, die nicht auf die Platte geschrieben wurden, sondern noch in CPU-Caches oder im Hauptspeicher liegen, gehen verloren, wenn das Betriebssystem abstürzt oder der Strom ausfällt. Um Dauerhaftigkeit von Änderungen trotz solcher Ereignisse zu garantieren, muss DuckDB sicherstellen, dass committed Änderungen in persistenten Speicher geschrieben werden. Änderungen in einer Transaktion können aber über potenziell große Tabellen verstreut sein, und sie vollständig auf die Platte zu schreiben, kann langsam sein – besonders, wenn das vor jedem Commit passieren muss. Außerdem wissen wir noch nicht, ob wir eine Änderung wirklich persistieren wollen; beim Commit selbst kann noch ein Fehler auftreten.

Der klassische Ansatz transaktionaler Datenmanagementsysteme, das Schreiben in persistenten Speicher mit dem Wunsch nach akzeptabler Dauer zu verbinden, ist das Write-Ahead Log (WAL). Das WAL ist eine Logdatei aller Änderungen an der Datenbank. Bei jedem Transaktions-Commit werden die Änderungen ins WAL geschrieben. Beim Neustart werden die Datenbankdateien von der Platte geladen, die Änderungen im WAL (falls vorhanden) erneut angewendet, und es geht weiter. Nach einer gewissen Menge Änderungen müssen die WAL-Änderungen physisch auf die Tabelle angewendet werden – „Checkpointing“. Danach können die WAL-Einträge verworfen werden – „Truncating“. Dieses Schema stellt sicher, dass Änderungen auch dann überdauern, wenn direkt nach einem Commit ein Absturz oder Stromausfall eintritt.

DuckDB implementiert Write-Ahead Logging; vielleicht haben Sie hier und da eine .wal-Datei gesehen. Checkpointing passiert normalerweise automatisch, sobald die WAL-Datei ein Limit erreicht – standardmäßig 16 MB, anpassbar mit der Einstellung checkpoint_threshold. Checkpoints passieren auch automatisch beim Herunterfahren der Datenbank. Checkpoints können auch explizit ausgelöst werden mit den Befehlen CHECKPOINT und FORCE CHECKPOINT. Der Unterschied: Letzterer bricht aktive Transaktionen ab (Rollback), damit der Checkpoint sofort passiert, ersterer wartet.

DuckDB ruft explizit den Systemaufruf fsync() auf, damit WAL-Einträge zwingend in persistenten Speicher geschrieben werden und die vielen Caches auf dem Weg ignoriert werden. Das ist nötig, weil auch diese Caches bei Stromausfall verloren gehen können; es nützt nichts, Logeinträge ins WAL zu schreiben, wenn sie am Ende nicht wirklich auf dem Speicher landen, weil Betriebssystem oder Platte aus Performancegründen lieber gewartet haben. fsync() braucht aber Zeit, und obwohl es allgemein als schlechte Praxis gilt, gibt es Systeme, die das gar nicht oder nicht standardmäßig tun, um mit mehr Transaktionen pro Sekunde zu prahlen.

In DuckDB sind sogar Bulk-Loads wie das Laden großer Dateien in Tabellen (z. B. mit der COPY-Anweisung) voll transaktional. Sie können also so etwas tun:

BEGIN TRANSACTION;
CREATE TABLE people (age INTEGER, ...);
COPY people FROM 'many_people.csv';
UPDATE people SET age = NULL WHERE age = -99;
SELECT
    CASE
        WHEN (SELECT count(*) FROM people) = 1_000_000 THEN true
        ELSE error('expected 1m rows')
    END;
COMMIT;

Diese Transaktion erzeugt eine Tabelle, kopiert eine große CSV-Datei hinein und aktualisiert die Tabelle, um einen Magiewert zu ersetzen. Zum Schluss wird geprüft, ob die erwartete Zeilenzahl in der Tabelle steht. All das ist in einer Transaktion gebunden. Geht irgendwo etwas schief oder schlägt die Prüfung fehl, wird die Transaktion abgebrochen und es gibt null Änderungen an der Datenbank – die Tabelle existiert nicht einmal. Das ist großartig, weil es Alles-oder-nichts-Semantik für komplexe Ladeaufgaben ermöglicht, auch in viele Tabellen.

Große Änderungen zu loggen ist aber ein Problem. Stellen Sie sich vor, many_people.csv ist groß, sagen wir zehn Gigabyte. Wie besprochen werden alle Änderungen ins WAL geschrieben und irgendwann checkpointed. Die Änderungen in der Datei sind groß genug, um sofort einen Checkpoint auszulösen. Also schreiben wir erst zehn Gigabyte ins WAL, lesen sie wieder und schreiben sie dann in die Datenbankdatei. Statt zehn lesen und zehn schreiben haben wir zwanzig gelesen und zwanzig geschrieben. Das ist nicht ideal. Statt Transaktionen für Bulk-Loads zu umgehen, schreibt DuckDB große Änderungen optimistisch direkt in neue Blöcke der Datenbankdatei und legt nur eine Referenz ins WAL. Beim Commit werden diese neuen Blöcke zur Tabelle hinzugefügt. Beim Rollback werden die Blöcke als freier Speicher markiert. Das kann die Datenbankdatei sinnlos wachsen lassen, wenn Transaktionen abgebrochen werden; der häufige Fall profitiert aber stark. Wieder erleben Nutzer nahezu kostenlose Transaktionalität.

Weitere Experimente

Concurrency Control und Write-Ahead Logging bei Fehlern korrekt zu machen, ist sehr anspruchsvoll. Software Engineers neigen zum „Happy Path“, auf dem alles wie geplant läuft. Der bekannte TPC-H-Benchmark enthält tatsächlich Tests, die Concurrency- und Logging-Schemata belasten (Abschnitt 3.5.4, „Durability Tests“). Unser vorheriger Blogbeitrag hat diesen Test ebenfalls implementiert, und DuckDB hat bestanden.

Zusätzlich haben wir unseren eigenen, noch anspruchsvolleren Dauerhaftigkeitstest definiert: Wir führen die TPC-H-Refresh-Sets nacheinander in einem Unterprozess aus. Der Unterprozess meldet das zuletzt committed Refresh. Während sie laufen, wird der Unterprozess nach einem zufälligen (kurzen) Zeitintervall beendet (SIGKILL). Dann wird DuckDB neu gestartet, erholt sich wahrscheinlich vom WAL und setzt die Refresh-Sets fort. Wegen des zufälligen Intervalls wird DuckDB wahrscheinlich auch während der WAL-Wiederherstellung beendet. Das darf den Inhalt der Datenbank natürlich nicht beeinflussen. Schließlich haben wir das korrekte Ergebnis nach 4000 Refresh-Sets mit DuckDB vorausberechnet und prüfen am Ende, ob es Unterschiede gibt. Glücklicherweise gab es keine.

Um die Implementierung weiter zu belasten, haben wir das Experiment auf einem speziellen Dateisystem wiederholt, LazyFS. Dieses FUSE-Dateisystem ist speziell dafür entworfen, Bugs in Datenbanksystemen aufzudecken, indem es unter anderem Änderungen nicht korrekt mit fsync() auf die Platte flush’t. In unserer LazyFS-Konfiguration wird jede in eine Datei geschriebene Änderung verworfen, sofern sie nicht sync-ed ist – was auch beim Schließen einer Datei passiert. In unserem Experiment, in dem wir die Datenbank beenden, gingen also alle nicht-sync-ed WAL-Einträge verloren. Wir haben die oben beschriebenen Dauerhaftigkeitstests auf LazyFS wiederholt und freuen uns, berichten zu können, dass keine Probleme gefunden wurden.

Fazit

In diesem Beitrag haben wir DuckDBs Ansätze zu Concurrency Control und Write-Ahead Logging beschrieben. Natürlich arbeiten wir ständig daran, sie zu verbessern. Ein unangenehmer Fehlermodus in realen Systemen sind partielle („torn“) Writes in Dateien, bei denen nur Teile von Schreibanfragen in der Datei ankommen. Glücklicherweise lässt sich LazyFS noch feindseliger konfigurieren, zum Beispiel indem Read- und Write-Systemaufrufe komplett fehlschlagen, partielle oder falsche Daten zurückgeben oder Daten nur teilweise auf die Platte schreiben. Wir wollen die Experimente ausweiten, damit DuckDBs Transaktionsbehandlung so kugelsicher wie möglich ist.

Und wer weiß – vielleicht trauen wir uns irgendwann, den berühmten Kyle von Jepsen auf DuckDB loszulassen.