2024-09-25

Daten mit Zuversicht und ACID ändern

Hannes Mühleisen, Mark Raasveldt

Das große Zitat „Alles ändert sich und nichts bleibt gleich“ von Heraklit, laut Sokrates, laut Platon ist nicht sehr kontrovers: Veränderung ist so alt wie das Universum. Irgendwie betrachten wir Veränderung beim Umgang mit Daten aber oft nur als Nachgedanken.

Statische Datensätze sind Momentaufnahmen dessen, wie die Welt in einem Augenblick aussah. Sehr schnell bewegt sich die Welt aber weiter, und der Datensatz muss nachziehen, um nützlich zu bleiben. In der Welt der Tabellen können neue Zeilen hinzugefügt werden, alte Zeilen können gelöscht werden, und manchmal müssen Zeilen geändert werden, um eine neue Situation abzubilden. Oft sind Änderungen miteinander verbunden. Eine Zeile in einer Tabelle, die Bestellungen auf Kunden abbildet, ist ohne den entsprechenden Eintrag in der Tabelle orders nicht sehr nützlich. Die meisten, wenn nicht alle Datensätze werden irgendwann geändert. Als Datenmanagementsystem ist das Verwalten von Änderung also nicht optional. Änderung richtig zu verwalten ist aber schwierig.

ACID-Garantien

Frühe Datenmanagementsystem-Forscher haben ein Konzept namens „Transaktionen“ erfunden, dessen Begriffe zuerst formalisiert in den 1980ern wurden. Im Kern beschreiben Transaktionalität und die bekannten ACID-Prinzipien eine Menge von Garantien, die ein Datenmanagementsystem liefern muss, um als sicher zu gelten. ACID ist ein Akronym für Atomicity, Consistency, Isolation und Durability (Atomarität, Konsistenz, Isolation und Dauerhaftigkeit).

Die ACID-Prinzipien sind keine theoretische Übung. Ähnlich wie die Regeln für Flugzeuge oder Züge sind sie „in Blut geschrieben“ – hart erkämpfte Lektionen aus Jahrzehnten Datenmanagementpraxis. Es ist sehr schwer für eine Anwendung, korrekt zu argumentieren, wenn sie mit Nicht-ACID-Systemen umgeht. Das Endergebnis solcher Probleme ist oft korrupte Daten oder Daten, die die Realität nicht mehr genau abbilden. Zum Beispiel können Zeilen verdoppelt oder fehlend sein.

DuckDB liefert volle ACID-Garantien standardmäßig ohne zusätzliche Konfiguration. In diesem Blogpost beschreiben wir im Detail, was das bedeutet, zusammen mit konkreten Beispielen, und zeigen, wie Sie diese Funktionalität nutzen können.

Atomarität

Atomarität bedeutet, dass entweder alle Änderungen in einer Menge von Updates passieren oder keine von ihnen. Betrachten Sie das Beispiel unten, in dem wir zwei Zeilen in zwei getrennte Tabellen einfügen. Die Inserts selbst sind getrennte Anweisungen, können aber atomar gemacht werden, indem man sie in eine Transaktion packt:

CREATE TABLE customer (id INTEGER, name VARCHAR);
CREATE TABLE orders (customer_id INTEGER, item VARCHAR);

BEGIN TRANSACTION;
INSERT INTO customer VALUES (42, 'DuckLabs');
INSERT INTO orders VALUES (42, 'stale bread');
COMMIT;

SELECT * FROM orders;

┌─────────────┬─────────────┐
│ customer_id │    item     │
│    int32    │   varchar   │
├─────────────┼─────────────┤
│          42 │ stale bread │
└─────────────┴─────────────┘

Indem wir die Änderungen in eine Transaktion packen, können wir sicher sein, dass entweder beide Zeilen geschrieben werden oder keine von ihnen. Die Anweisung BEGIN TRANSACTION bedeutet, dass alle folgenden Anweisungen zu dieser Transaktion gehören. Das COMMIT bedeutet das Ende der Transaktion – und persistiert die Änderungen auf die Platte.

Es ist auch möglich, eine Menge von Änderungen rückgängig zu machen, indem man am Ende einer Transaktion ein ROLLBACK ausführt. Das stellt sicher, dass keine der in der Transaktion gemachten Änderungen persistiert wird.

BEGIN TRANSACTION;
INSERT INTO orders VALUES (42, 'iceberg lettuce');
INSERT INTO orders VALUES (42, 'dried worms');
ROLLBACK;
SELECT * FROM orders;

┌─────────────┬─────────────┐
│ customer_id │    item     │
│    int32    │   varchar   │
├─────────────┼─────────────┤
│          42 │ stale bread │
└─────────────┴─────────────┘

Wie wir sehen, wurden die zwei neuen Zeilen nicht dauerhaft eingefügt.

Atomarität ist großartig, weil sie der Anwendung erlaubt, die Datenbank von einem konsistenten Zustand in einen anderen konsistenten Zustand zu bringen, ohne sich je um sichtbare Zwischenzustände für eine Anwendung sorgen zu müssen.

Wir sollten anmerken, dass Abfragen standardmäßig im sogenannten „Auto-Commit“-Modus laufen, in dem jede Abfrage automatisch in ihrer eigenen Transaktion ausgeführt wird. Selbst für diese Einzelsatz-Abfragen sind Transaktionen aber sehr nützlich. Zum Beispiel: Beim Bulk-Laden von Daten in eine Tabelle mit einem INSERT- oder COPY-Befehl werden entweder alle Daten geladen oder keine der Daten. Das System lädt eine CSV-Datei nicht teilweise in eine Tabelle.

Wir sollten auch anmerken, dass in DuckDB Schemaänderungen ebenfalls transaktional sind. Das bedeutet, dass Sie Tabellen anlegen oder löschen sowie das Schema einer Tabelle ändern können – alles im Schutz einer Transaktion. Es bedeutet auch, dass Sie jede dieser Operationen durch ein ROLLBACK rückgängig machen können.

Konsistenz

Konsistenz bedeutet, dass alle in der Datenbank definierten Constraints immer gelten müssen, sowohl vor als auch nach einer Transaktion. Die Constraints können nie verletzt werden. Beispiele für Constraints sind PRIMARY KEY- oder FOREIGN KEY-Constraints.

CREATE TABLE customer (id INTEGER, name VARCHAR, PRIMARY KEY (id));

INSERT INTO customer VALUES (42, 'DuckLabs');
INSERT INTO customer VALUES (42, 'Wilbur the Duck');

Im Beispiel oben verlangt die Tabelle customer, dass die Spalte id für alle Einträge eindeutig ist, sonst würden mehrere Kunden denselben Bestellungen zugeordnet. Wir können diesen Constraint durchsetzen, indem wir einen sogenannten PRIMARY KEY auf dieser Spalte definieren. Wenn wir zwei Einträge mit derselben ID einfügen, schlägt die Konsistenzprüfung fehl, und wir bekommen eine Fehlermeldung:

Constraint Error: Duplicate key "id: 42" violates primary key
constraint. (...)

Solche Constraints zu haben ist ein großartiger Weg, sicherzustellen, dass Daten konsistent bleiben, auch nachdem viele Updates stattgefunden haben.

Isolation

Isolation bedeutet, dass nebenläufige Transaktionen voneinander isoliert sind. Eine Datenbank kann viele Clients haben, die gleichzeitig mit ihr interagieren, wodurch viele Transaktionen auf einmal passieren. Ein einfacher Weg, diese Transaktionen zu isolieren, ist, sie nacheinander auszuführen. Das wäre aber untragbar langsam. Tausende Anfragen müssten auf eine besonders langsame warten.

Um dieses Problem zu vermeiden, werden Transaktionen typischerweise verschränkt ausgeführt. Da diese Transaktionen aber Daten ändern, muss man sicherstellen, dass jede Transaktion logisch isoliert ist – sie sieht immer nur einen konsistenten Zustand der Datenbank und kann – zum Beispiel – nie Daten aus einer Transaktion lesen, die noch nicht committed hat.

DuckDB hat keine Connections im üblichen Sinn – es ist keine Client/Server-Datenbank, die es getrennten Anwendungen erlaubt, sich zu verbinden. DuckDB hat aber volle Multi-Client-Unterstützung innerhalb einer einzelnen Anwendung. Der Nutzer kann mehrere Clients anlegen, die alle mit derselben DuckDB-Instanz verbunden sind. Die Transaktionen können nebenläufig laufen und sind mit Snapshot Isolation isoliert.

Wie mehrere Connections angelegt werden, unterscheidet sich pro Client. Unten ein Beispiel, in dem wir die Transaktionalität des Systems mit dem Python-Client zeigen.

import duckdb

con1 = duckdb.connect(":memory:mydb")
con1.sql("CREATE TABLE customer (id INTEGER, name VARCHAR)")

con1.sql("INSERT INTO customer VALUES (42, 'DuckLabs')")

con1.begin()
con1.sql("INSERT INTO customer VALUES (43, 'Wilbur the Duck')")
# no commit!

# start a new connection
con2 = duckdb.connect(":memory:mydb")
con2.sql("SELECT name FROM customer").show()

# ┌─────────────┐
# │    name     │
# │   varchar   │
# ├─────────────┤
# │ DuckLabs │
# └─────────────┘

# commit from the first connection
con1.commit()

# now the changes are visible
con2.sql("SELECT name FROM customer").show()

# ┌─────────────────┐
# │      name       │
# │     varchar     │
# ├─────────────────┤
# │ DuckLabs     │
# │ Wilbur the Duck │
# └─────────────────┘

Wie Sie sehen, haben wir zwei Connections zur selben Datenbank, und die erste Connection fügt den Kunden Wilbur the Duck ein, committed die Änderung aber noch nicht. In der Zwischenzeit liest die zweite Connection aus der Kundentabelle. Das Ergebnis zeigt den neuen Eintrag noch nicht, weil die zwei Transaktionen voneinander bezüglich uncommitted Änderungen isoliert sind. Nachdem die erste Connection committed, kann die zweite Connection ihre Änderungen lesen.

Dauerhaftigkeit

Schließlich ist Dauerhaftigkeit das Verhalten eines Systems bei Ausfall. Das ist wichtig, weil ein Prozess abstürzen oder die Stromversorgung eines Computers verloren gehen kann. Ein Datenbanksystem muss jetzt sicherstellen, dass alle committed Transaktionen dauerhaft sind, das heißt ihre Effekte nach dem Neustart der Datenbank sichtbar sind. Transaktionen, die noch nicht abgeschlossen sind, dürfen keine sichtbaren Spuren hinterlassen. Datenbanken garantieren diese Eigenschaft typischerweise, indem sie die verschiedenen Caches genau im Blick behalten, zum Beispiel durch fsync, um Änderungen auf die Platte zu zwingen, wenn Transaktionen abschließen. Das Überspringen von fsync ist eine häufige „Optimierung“, die die Dauerhaftigkeit gefährdet.

Hier ein Beispiel, wieder mit Python:

import duckdb
import os
import signal

con = duckdb.connect("mydb.duckdb")
con.sql("CREATE TABLE customer (id INTEGER, name VARCHAR)")
con.sql("INSERT INTO customer VALUES (42, 'DuckLabs')")

# begin a transaction
con.begin()
con.sql("INSERT INTO customer VALUES (43, 'Wilbur the Duck')")
# no commit!

os.kill(os.getpid(), signal.SIGKILL)

Nach dem Neustart können wir die Tabelle customer prüfen:

import duckdb

con = duckdb.connect("mydb.duckdb")
con.sql("SELECT name FROM customer").show()

┌─────────────┐
│    name     │
│   varchar   │
├─────────────┤
│ DuckLabs │
└─────────────┘

In diesem Beispiel legen wir zuerst die Kundentabelle in der Datenbankdatei mydb.duckdb an. Dann fügen wir eine einzelne Zeile mit DuckLabs als erste Transaktion ein. Dann beginnen wir, committen aber nicht eine zweite Transaktion, die den Eintrag Wilbur the Duck hinzufügt. Wenn wir dann den Prozess und damit die Datenbank killen, sehen wir, dass beim Neustart nur der Eintrag DuckLabs überlebt hat. Das liegt daran, dass die zweite Transaktion nicht committed war und deshalb nicht der Dauerhaftigkeit unterlag. Natürlich wird das komplizierter, wenn unsaubere Exits wie Betriebssystemabstürze berücksichtigt werden müssen. DuckDB garantiert Dauerhaftigkeit auch in diesen Umständen, mehr dazu unten.

Warum ACID in OLAP?

Es gibt zwei Hauptklassen von Datenmanagementsystemen, transaktionale Systeme (OLTP) und analytische Systeme (OLAP). Wie der Name andeutet, sind transaktionale Systeme deutlich stärker damit beschäftigt, die ACID-Eigenschaften zu garantieren als analytische. Systeme wie das ehrwürdige PostgreSQL sind zu Recht stolz darauf, standardmäßig das „Richtige“ bezüglich transaktionaler Garantien zu tun. Selbst NoSQL-transaktionale Systeme wie MongoDB, die sich früh vom Garantieren der ACID-Prinzipien „für die Performance“ verabschiedet hatten, mussten schließlich „zurückrollen“ und ACID-Garantien anbieten, mit ein oder zwei Hürden unterwegs.

Analytische Systeme wie DuckDB haben – im Prinzip – weniger Imperativ, starke transaktionale Garantien zu liefern. Sie sind oft nicht das sogenannte „System of Record“, also das Datenmanagementsystem, das als Wahrheitsquelle gilt. Tatsächlich bietet DuckDB verschiedene Connectors, um Daten aus Systems of Record zu laden, wie den PostgreSQL-Scanner. Würde eine OLAP-Datenbank korrupt, ist es oft möglich, sich von dieser Wahrheitsquelle zu erholen. Dafür müssen Nutzer natürlich zuerst merken, dass etwas schiefgelaufen ist, was nicht immer einfach zu erkennen ist. Ein häufiger Fehler ist zum Beispiel, Daten aus derselben CSV-Datei zweimal in eine Datenbank zu ingestieren, weil der erste Versuch irgendwann schiefging. Das kann zu doppelten Zeilen führen, die falsche Aggregatergebnisse verursachen. ACID verhindert diese Art von Problemen. ACID-Eigenschaften ermöglichen nützliche Funktionalität in OLAP-Systemen. Zum Beispiel:

Nebenläufige Ingestion und Reporting. Da Veränderung kontinuierlich ist, haben wir oft Dateningestionsströme, die neue Daten zu einem Datenbanksystem hinzufügen. In analytischen Systemen ist es üblich, eine einzelne Connection zu haben, die neue Daten an eine Datenbank anhängt, während andere Connections aus der Datenbank lesen, um z. B. Graphen und Reports zu erzeugen. Sind diese Connections isoliert, werden die erzeugten Graphen und Aggregate immer über einen vollständigen und konsistenten Snapshot der Datenbank ausgeführt, sodass die erzeugten Graphen und Aggregate korrekt sind.

Falsche Transformationen zurückrollen. Beim Analysieren von Daten ist ein übliches Muster, Daten aus in Flat Files gespeicherten Datensätzen zu laden und dann eine Reihe von Transformationen auf diesen Daten durchzuführen. Zum Beispiel könnten wir einen Datensatz aus einer CSV-Datei laden, dann NULL-Werte bereinigen und unvollständige Zeilen löschen. Machen wir eine falsche Transformation, ist es möglich, dass wir versehentlich zu viele Zeilen löschen.

Das ist nicht das Ende der Welt, weil wir uns erholen können, indem wir die ursprünglichen CSV-Dateien erneut lesen. Wir können uns aber viel Zeit sparen, indem wir die Transformationen in eine Transaktion packen und zurückrollen, wenn etwas schiefgeht. Zum Beispiel:

CREATE TABLE people AS SELECT * FROM 'people.csv';

BEGIN TRANSACTION;
UPDATE people SET age = NULL WHERE age = -99;
-- oops, we deleted all rows!
DELETE FROM people WHERE name <> 'non-existent name';
-- we can recover our original table by rolling back the delete
ROLLBACK;

SQL-Assertions. Tritt in einer Transaktion ein (Nicht-Syntax-)Fehler auf, wird die Transaktion automatisch abgebrochen, und die Änderungen können nicht committed werden. Wir können diese Eigenschaft von Transaktionen nutzen, um Assertions zu unseren Transaktionen hinzuzufügen. Wird eine dieser Assertions ausgelöst, wird ein Fehler geworfen, und die Transaktion kann nicht committed werden. Wir können die Funktion error nutzen, um unser eigenes assert-Makro zu definieren:

CREATE MACRO assert(condition, message) AS
    CASE WHEN NOT condition THEN error(message) END;

Dann können wir dieses assert-Makro nutzen, um zu asserten, dass die Tabelle people nicht leer ist:

CREATE TABLE people AS SELECT * FROM 'people.csv';

BEGIN TRANSACTION;
UPDATE people SET age = NULL WHERE age = -99;
-- oops, we deleted all rows!
DELETE FROM people WHERE name <> 'non-existent name';
SELECT assert(
           (SELECT count(*) FROM people) > 0,
           'People should not be empty'
       );
COMMIT;

Wenn die Assertion auslöst, wird die Transaktion automatisch abgebrochen, und die Änderungen werden zurückgerollt.

Vollständige TPC-H-Benchmark-Implementierung

Das Transaction Processing Performance Council (TPC) ist ein Branchenverband von Datenmanagementsystemen und Hardwareanbietern. TPC veröffentlicht Datenbank-Benchmark-Spezifikationen und überwacht die Prüfung von Benchmark-Ergebnissen, die es dann auf seiner Website veröffentlicht. Es gibt verschiedene Benchmarks für unterschiedliche Einsatzfälle. Der TPC-H Decision Support Benchmark zielt speziell auf analytische Query-Verarbeitung auf großen Datenmengen. Seine berühmten 22 SQL-Abfragen und Datengenerator-Details wurden sowohl von Datenbankanbietern als auch Akademikern ad nauseam gründlich analysiert.

Weniger bekannt ist, dass der offizielle TPC-H-Benchmark Datenänderungs-Transaktionen enthält, die ACID-Compliance verlangen, was angesichts des Namens der Organisation nicht allzu überraschend ist. Bei einmaligen Performance-Shoot-outs werden die Updates typischerweise ignoriert und nur die Laufzeiten der 22 Abfragen auf einem statischen Datensatz berichtet. Solche Ergebnisse sind rein informativ und können vom TPC nicht geprüft oder formal veröffentlicht werden. Aber wie wir oben argumentiert haben, ist Veränderung unvermeidlich, also führen wir die TPC-H-Experimente mit Updates mit DuckDB durch.

TPC-H erzeugt Daten für ein fiktives Unternehmen, das Dinge verkauft. Die größten Tabellen sind orders und lineitem, die Elemente jeder Bestellung enthält. Der Benchmark kann Daten unterschiedlicher Größen erzeugen, die Größe wird durch einen sogenannten „Scale Factor“ (SF) gesteuert. Die Spezifikation definiert zwei „Refresh Functions“, die die Datenbank ändern. Die erste Refresh Function fügt SF * 1500 neue Zeilen in die Tabelle orders ein und zufällig zwischen 1 und 7 neue Einträge für jede Bestellung in die Tabelle lineitem. Die zweite Refresh Function löscht SF * 1500 Einträge aus der Tabelle orders zusammen mit den zugehörigen lineitem-Einträgen. Der Benchmark-Datengenerator dbgen kann eine beliebige Menge von Refresh-Function-CSV-Dateien mit neuen Einträgen für orders und lineitem zusammen mit zu löschenden Zeilen erzeugen.

Metriken

Die Hauptbenchmark-Metrik von TPC-H wird aus einem „Power“- und einem „Throughput“-Testergebnis kombiniert.

Der Power-Test führt die erste Refresh Function aus und nimmt die Zeit, führt dann die 22 Abfragen aus, führt dann die zweite Refresh Function aus und berechnet das geometrische Mittel aller Zeiten. Mit einem Scale Factor von 100 und DuckDB 1.1.1 auf einem MacBook Pro mit einer M3-Max-CPU und 64 GB RAM bekommen wir einen Power@Size-Wert von 650 536.

Der Throughput-Test führt eine Zahl nebenläufiger Query-„Streams“ aus, die die 22 Benchmark-Abfragen in gemischter Reihenfolge parallel ausführen. Zusätzlich führt ein einzelner Refresh-Stream beide Refresh Functions mehrmals aus. Die Zahl der Query-Streams und Refresh-Sets wird aus dem Scale Factor abgeleitet. Für SF100 gibt es 5 Query-Streams und 10 Refresh-Sets. Für unser Experiment bekommen wir einen Throughput@Size von 452 571. Ergebnisse sind schwer zu vergleichen, aber das Ergebnis sieht nicht schlecht aus im Vergleich zur offiziellen Ergebnisliste.

ACID-Tests

Abschnitt 3 der TPC-H-Benchmark-Spezifikation diskutiert die ACID-Eigenschaften im Detail. Die Spezifikation definiert eine Menge von Tests, um die ACID-Garantien eines Datenmanagementsystems zu stressen. Die Spec merkt gebührend an, dass kein Test beweisen kann, dass die ACID-Eigenschaften vollständig unterstützt werden; sie zu bestehen ist eine „notwendige, aber nicht hinreichende Bedingung“ der Compliance. Unten geben wir einen Überblick, was getestet wird.

Die Tests spezifizieren eine „ACID Transaction“, die die Tabellen lineitem und orders so ändert, dass eine Invariante gilt: Die Tabelle orders enthält eine Gesamtsumme aller Preise aller Lineitems, die zu dieser Bestellung gehören. Die Transaktion wählt eine zufällige Bestellung und ändert das letzte Lineitem auf einen neuen Preis. Dann berechnet sie den Gesamtpreis der Bestellung neu und aktualisiert die Tabelle orders damit. Schließlich fügt die Transaktion Informationen darüber, welche Zeile wann aktualisiert wurde und welches Preisdelta genutzt wurde, in eine Tabelle history ein.

Um Atomarität zu testen, wird die ACID-Transaktion für eine zufällige Bestellung ausgeführt und dann committed. Es wird geprüft, dass die Datenbank entsprechend mit den angegebenen Werten geändert wurde. Der Test wird wiederholt, diesmal wird die Transaktion aber abgebrochen. Es wird geprüft, dass die Datenbank nicht geändert wurde.

Für Konsistenz führen eine Zahl von Threads die ACID-Transaktion parallel 100-mal auf zufälligen Bestellungen aus. Vor und nach dem Test wird eine Konsistenzbedingung geprüft, die im Wesentlichen sicherstellt, dass die Summe aller Lineitem-Preise für eine Bestellung mit der Summe in der Bestellung konsistent ist.

Um Isolation zu testen, führt ein Thread die Transaktion aus, committed oder rollbackt aber noch nicht. Eine andere Connection stellt sicher, dass die Änderungen für sie nicht sichtbar sind. Eine weitere Testreihe hat zwei Threads, die Transaktionen auf derselben Bestellung ausführen, und stellt sicher, dass eine von ihnen vom System wegen des Konflikts abgebrochen wird.

Schließlich, um Dauerhaftigkeit zu testen, führen eine Zahl von Threads die ACID-Transaktion aus und loggen die Ergebnisse. Sie dürfen mindestens 100 Transaktionen jeweils abschließen. Dann wird ein Ausfall verursacht; in unserem Fall haben wir einfach den Prozess gekillt (mit SIGKILL). Dann darf das Datenbanksystem die committed Änderungen aus dem Write-Ahead Log (WAL) wiederherstellen. Das Log wird geprüft, um sicherzustellen, dass es keine Log-Einträge gibt, die nicht in der Tabelle history reflektiert sind, und keine History-Einträge, die keine Log-Einträge haben, minus sehr wenige, die inflight verloren gegangen sein könnten (d. h. von der Datenbank persistiert, aber noch nicht vom Benchmark-Treiber geloggt). Schließlich wird die Konsistenz erneut geprüft.

Wir freuen uns zu berichten, dass DuckDB alle Tests bestanden hat.

Unsere Skripte zum Ausführen des Benchmarks sind auf GitHub verfügbar. Wir planen, in Zukunft ein formales Audit unserer Ergebnisse durchzuführen. Wir werden diesen Beitrag aktualisieren, wenn das passiert.

Fazit

Veränderung in Datensätzen ist unvermeidlich, und Datenmanagementsysteme müssen Veränderung sicher verwalten können. DuckDB unterstützt starke ACID-Garantien, die sichere und nebenläufige Datenänderung erlauben. Wir haben umfangreiche Experimente mit den transaktionalen Validierungstests von TPC-H durchgeführt und festgestellt, dass sie bestehen.