2021-10-29

DuckDB-Wasm: Effizientes analytisches SQL im Browser

André Kohn, Dominik Moritz

DuckDB-Wasm ist schnell! Wenn Sie wegen der Leistungszahlen hier sind, schauen Sie sich unsere Benchmarks unter shell.duckdb.org/versus an.

Effiziente Analytik im Browser

Der Webbrowser hat sich zu einer universellen Rechenplattform entwickelt, die sogar in Ihrem Auto läuft. Sein Aufstieg wurde von steigenden Anforderungen an die Browser-Programmiersprache JavaScript begleitet. JavaScript wurde vor allem darauf entworfen, sehr flexibel zu sein, was auf Kosten einer geringeren Verarbeitungseffizienz gegenüber nativen Sprachen wie C++ geht. Das wird besonders deutlich, wenn man die Ausführungszeiten komplexerer Datenanalyseaufgaben betrachtet, die oft um Größenordnungen hinter der nativen Ausführung zurückbleiben. In der Vergangenheit wurden solche Analyseaufgaben daher auf Server geschoben, die jede clientseitige Verarbeitung an zusätzliche Roundtrips über das Internet binden und ihre eigenen Skalierungsprobleme mitbringen.

Die Verarbeitungskapazitäten von Browsern wurden vor 4 Jahren mit der Einführung von WebAssembly enorm gesteigert:

WebAssembly (abbreviated Wasm) is a binary instruction format for a stack-based virtual machine. Wasm is designed as a portable compilation target for programming languages, enabling deployment on the web for client and server applications.

The Wasm stack machine is designed to be encoded in a size- and load-time efficient binary format. WebAssembly aims to execute at native speed by taking advantage of common hardware capabilities available on a wide range of platforms.

(ref: https://webassembly.org/)

Vier Jahre später ist die WebAssembly-Revolution in vollem Gange, erste Implementierungen werden in vier großen Browsern ausgeliefert. Sie hat uns bereits Game-Engines, ganze IDEs und sogar eine Browser-Version von Photoshop gebracht. Heute reißen wir uns ein mit einem ersten Release der npm-Bibliothek @duckdb/duckdb-wasm.

Als In-Process-analytische Datenbank hat DuckDB die seltene Gelegenheit, OLAP-Workloads im Browser deutlich zu beschleunigen. Wir glauben, dass es Bedarf an einer umfassenden, in sich geschlossenen Datenanalysebibliothek gibt. DuckDB-Wasm lagert Ihre Abfragen automatisch auf eigene Worker-Threads aus und liest Parquet-, CSV- und JSON-Dateien entweder vom lokalen Dateisystem oder von HTTP-Servern, angetrieben durch schlichten SQL-Input. In diesem Blogbeitrag wollen wir die Bibliothek vorstellen und Herausforderungen auf unserem Weg zu einer browsernativen OLAP-Datenbank zeigen.

DuckDB-Wasm ist noch nicht stabil. Sie werden raue Kanten und Bugs in diesem Release finden. Bitte teilen Sie Ihre Gedanken mit uns auf GitHub.

Wie kommen Daten hinein?

Tauchen wir in Beispiele ein. DuckDB-Wasm bietet verschiedene Wege, Ihre Daten zu laden. Erstens: Rohe SQL-Value-Klauseln wie INSERT INTO sometable VALUES (1, 'foo'), (2, 'bar') sind leicht zu formulieren und hängen nur von schlichtem SQL-Text ab. Alternativ ziehen SQL-Statements wie CREATE TABLE foo AS SELECT * FROM 'somefile.parquet' unser integriertes Web-Dateisystem zu Rate, um somefile.parquet lokal, remote oder aus einem Buffer aufzulösen. Die Methoden insertCSVFromPath und insertJSONFromPath bieten außerdem bequeme Wege, CSV- und JSON-Dateien mit zusätzlichen typisierten Einstellungen wie Spaltentypen zu importieren. Und schließlich kopiert die Methode insertArrowFromIPCStream (optional über insertArrowTable, insertArrowBatches oder insertArrowVectors) rohe IPC-Stream-Bytes direkt in einen WebAssembly-Stream-Decoder.

Das folgende Beispiel zeigt verschiedene Optionen, wie Daten in DuckDB-Wasm importiert werden können:

// Data can be inserted from an existing arrow.Table
await c.insertArrowTable(existingTable, { name: "arrow_table" });
// ..., from Arrow vectors
await c.insertArrowVectors({
    col1: arrow.Int32Vector.from([1, 2]),
    col2: arrow.Utf8Vector.from(["foo", "bar"]),
}, {
    name: "arrow_vectors"
});
// ..., from a raw Arrow IPC stream
const c = await db.connect();
const streamResponse = await fetch(`someapi`);
const streamReader = streamResponse.body.getReader();
const streamInserts = [];
while (true) {
    const { value, done } = await streamReader.read();
    if (done) break;
    streamInserts.push(c.insertArrowFromIPCStream(value, { name: "streamed" }));
}
await Promise.all(streamInserts);

// ..., from CSV files
// (interchangeable: registerFile{Text,Buffer,URL,Handle})
await db.registerFileText(`data.csv`, "1|foo\n2|bar\n");
// ... with typed insert options
await db.importCSVFromPath('data.csv', {
    schema: 'main',
    name: 'foo',
    detect: false,
    header: false,
    delimiter: '|',
    columns: {
        col1: new arrow.Int32(),
        col2: new arrow.Utf8(),
    }
});

// ..., from JSON documents in row-major format
await db.registerFileText("rows.json", `[
    { "col1": 1, "col2": "foo" },
    { "col1": 2, "col2": "bar" },
]`);
// ... or column-major format
await db.registerFileText("columns.json", `{
    "col1": [1, 2],
    "col2": ["foo", "bar"]
}`);
// ... with typed insert options
await db.importJSONFromPath('rows.json', { name: 'rows' });
await db.importJSONFromPath('columns.json', { name: 'columns' });

// ..., from Parquet files
const pickedFile: File = letUserPickFile();
await db.registerFileHandle("local.parquet", pickedFile);
await db.registerFileURL("remote.parquet", "https://origin/remote.parquet");

// ..., by specifying URLs in the SQL text
await c.query(`
    CREATE TABLE direct AS
        SELECT * FROM 'https://origin/remote.parquet'
`);
// ..., or by executing raw insert statements
await c.query(`INSERT INTO existing_table
    VALUES (1, "foo"), (2, "bar")`);

Wie kommen Daten heraus?

Jetzt, da wir die Daten geladen haben, kann DuckDB-Wasm Abfragen auf zwei verschiedenen Wegen ausführen, die sich in der Ergebnis-Materialisierung unterscheiden. Erstens führt die Methode query eine Abfrage bis zum Ende aus und gibt die Ergebnisse als einzelne arrow.Table zurück. Zweitens holt die Methode send Abfrageergebnisse lazy über einen arrow.RecordBatchStreamReader. Beide Methoden sind generisch und erlauben typisierte Ergebnisse in TypeScript:

// Either materialize the query result
await conn.query<{ v: arrow.Int32 }>(`
    SELECT * FROM generate_series(1, 100) t(v)
`);
// ..., or fetch the result chunks lazily
for await (const batch of await conn.send<{ v: arrow.Int32 }>(`
    SELECT * FROM generate_series(1, 100) t(v)
`)) {
    // ...
}

Alternativ können Sie Statements für parametrisierte Abfragen vorbereiten mit:

// Prepare query
const stmt = await conn.prepare<{ v: arrow.Int32 }>(
    `SELECT (v + ?) AS v FROM generate_series(0, 10000) t(v);`
);
// ... and run the query with materialized results
await stmt.query(234);
// ... or result chunks
for await (const batch of await stmt.send(234)) {
    // ...
}

Sieht nach Arrow aus

DuckDB-Wasm nutzt Arrow als Datenprotokoll für den Datenimport und alle Abfrageergebnisse. Arrow ist ein datenbankfreundliches Spaltenformat, das in Chunks von Spaltenvektoren organisiert ist, Record Batches genannt, und Zero-Copy-Reads mit nur geringem Overhead unterstützt. Die npm-Bibliothek apache-arrow setzt das Arrow-Format im Browser um und wird bereits von anderen Datenverarbeitungs-Frameworks genutzt, etwa Arquero. Arrow erspart uns daher nicht nur die Umsetzung der SQL-Typ-Logik in JavaScript, es macht uns auch kompatibel zu bestehenden Werkzeugen.

Warum nicht schlichte JavaScript-Objekte?

WebAssembly ist isoliert und speichersicher. Diese Isolation gehört zu seiner DNA und treibt grundlegende Designentscheidungen in DuckDB-Wasm. WebAssembly führt zum Beispiel eine Barriere zum traditionellen JavaScript-Heap ein. Diese Barriere zu überqueren ist schwierig, weil JavaScript mit nativen Funktionsaufrufen, Speicherbesitz und Serialisierungsleistung umgehen muss. Sprachen wie C++ machen das schlimmer, weil sie auf Smart Pointer setzen, die über das FFI nicht verfügbar sind. Sie lassen uns die Wahl, Speicherbesitz entweder an statische Singletons innerhalb der WebAssembly-Instanz zu übergeben oder den Speicher über C-artige APIs in JavaScript zu verwalten, einer Sprache, die zu dynamisch für solide Umsetzungen des RAII-Idioms ist. Die Speicherisolation zwingt uns, Daten zu serialisieren, bevor wir sie an die WebAssembly-Instanz übergeben können. Browser können JavaScript-Objekte nativ mit den Funktionen JSON.stringify und JSON.parse nach und von JSON serialisieren, das ist aber langsamer als zum Beispiel das Kopieren roher nativer Arrays.

Web-Dateisystem

DuckDB-Wasm integriert ein eigenes Dateisystem für WebAssembly. DuckDB selbst baut auf einem virtuellen Dateisystem auf, das höhere Aufgaben wie das Lesen einer Parquet-Datei von niedrigschwelligen Dateisystem-APIs entkoppelt, die betriebssystemspezifisch sind. Diese Abstraktion nutzen wir in DuckDB-Wasm, um Dateisystem-Implementierungen an die verschiedenen WebAssembly-Umgebungen anzupassen.

Die folgende Abbildung zeigt unser aktuelles Web-Dateisystem in Aktion. Das Sequenzdiagramm zeigt einen Nutzer, der eine SQL-Abfrage ausführt, die eine einzelne Parquet-Datei scannt. Die Abfrage wird zuerst über eine JavaScript-API an einen eigenen Web Worker ausgelagert. Dort wird sie an das WebAssembly-Modul übergeben, das die Abfrage verarbeitet, bis die Ausführung die Tabellenfunktion parquet_scan trifft. Diese Tabellenfunktion liest die Datei dann über ein gepuffertes Dateisystem, das wiederum Paged Reads auf dem Web-Dateisystem auslöst. Dieses Web-Dateisystem nutzt dann eine umgebungsspezifische Runtime, um die Datei von mehreren möglichen Orten zu lesen.

Je nach Kontext kann die Parquet-Datei entweder auf dem lokalen Gerät, auf einem Remote-Server oder in einem Buffer liegen, den der Nutzer vorab registriert hat. Wir behandeln alle drei Fälle bewusst gleich, um das Holen und Verarbeiten externer Daten zu vereinheitlichen. Das vereinfacht nicht nur die Analyse, es ermöglicht auch fortgeschrittenere Features wie das teilweise Konsumieren strukturierter Dateiformate. Parquet-Dateien bestehen zum Beispiel aus mehreren Row Groups, die Daten spaltenweise speichern. Dadurch müssen wir für eine Abfrage möglicherweise nicht die gesamte Datei herunterladen, sondern nur benötigte Bytes.

Eine Abfrage wie SELECT count(*) FROM parquet_scan(...) kann zum Beispiel allein auf den Dateimetadaten ausgewertet werden und ist in Millisekunden fertig, selbst bei Remote-Dateien, die mehrere Terabyte groß sind. Ein weiteres allgemeineres Beispiel sind Paging-Scans mit Qualifiern LIMIT und OFFSET wie SELECT * FROM parquet_scan(...) LIMIT 20 OFFSET 40 oder Abfragen mit selektiven Filterprädikaten, bei denen ganze Row Groups anhand von Metadatenstatistiken übersprungen werden können. Diese teilweisen Dateileses sind keine bahnbrechende Neuheit und könnten heute in JavaScript umgesetzt werden, mit DuckDB-Wasm werden diese Optimierungen jetzt aber von der Semantik von SQL-Abfragen angetrieben statt von feinabgestimmter Anwendungslogik.

Hinweis: Der gemeinsame Nenner unter den verfügbaren File-APIs ist leider nicht groß. Das begrenzt die Features, die wir im Browser bereitstellen können. Lokale Persistenz von DuckDB-Datenbanken wäre zum Beispiel ein Feature mit erheblicher Wirkung, erfordert aber einen Weg, synchron in nutzerbereitgestellte Dateien oder IndexedDB zu lesen und zu schreiben. Wir könnten diese Einschränkungen in Zukunft umgehen, das ist aber Gegenstand laufender Forschung.

Fortgeschrittene Features

WebAssembly 1.0 ist in allen großen Browsern gelandet. Die WebAssembly Community Group hat das Design dieser ersten Version im November 2017 festgeschrieben, die jetzt als WebAssembly MVP bezeichnet wird. Seitdem läuft die Entwicklung weiter, mit acht zusätzlichen Features, die zum Standard hinzugekommen sind, und mindestens fünf Vorschlägen, die derzeit in Arbeit sind.

Das rasche Tempo dieser Entwicklung bringt Herausforderungen und Chancen für Bibliotheksautoren. Einerseits finden die verschiedenen Features unterschiedlich schnell ihren Weg in die Browser, was zu einem zersplitterten Raum von Post-MVP-Funktionalität führt. Andererseits können Features flache Leistungsverbesserungen bringen und sind daher unverzichtbar, wenn maximale Leistung angestrebt wird.

Das vielversprechendste Feature für DuckDB-Wasm ist Exception Handling, das in Chrome 95 bereits standardmäßig aktiviert ist. DuckDB und DuckDB-Wasm sind in C++ geschrieben und nutzen Exceptions für fehlerhafte Situationen. DuckDB nutzt Exceptions nicht für den allgemeinen Kontrollfluss, sondern um Fehler automatisch nach oben zum Top-Level-Plan-Driver zu propagieren. In nativen Umgebungen sind diese Exceptions als „Zero-Cost Exceptions“ umgesetzt, weil sie keinen Overhead verursachen, bis sie geworfen werden. Mit dem WebAssembly-MVP ist das jedoch nicht mehr möglich, weil die Compiler-Toolchain Emscripten Exceptions über JavaScript emulieren muss. Ohne WebAssembly-Exceptions ruft DuckDB-Wasm werfende Funktionen über einen JavaScript-Hook auf, der über JavaScript-aborts emulierte Exceptions fangen kann. Ein Beispiel für diese Hook-Aufrufe ist in der folgenden Abbildung gezeigt. Beide Stack Traces stammen von einem einzelnen Paged Read einer Parquet-Datei in DuckDB-Wasm. Die linke Seite zeigt einen Stack Trace mit dem WebAssembly-MVP und erfordert mehrere Aufrufe über die Funktionen wasm-to-js-i*. Der rechte Stack Trace nutzt WebAssembly-Exceptions ohne jegliche Hook-Aufrufe.

Dieser zersplitterte Feature-Raum ist eine vorübergehende Herausforderung, die gelöst sein wird, sobald wirkungsvolle Features wie Exception Handling, SIMD und Bulk-Memory-Operationen überall verfügbar sind. In der Zwischenzeit liefern wir mehrere WebAssembly-Module aus, die für verschiedene Feature-Sets kompiliert sind, und wählen adaptiv das beste Bundle für Sie anhand dynamischer Browser-Checks.

Das folgende Beispiel zeigt, wie die asynchrone Version von DuckDB-Wasm mit manuellen oder JsDelivr-Bundles instanziiert werden kann:

// Import the ESM bundle (supports tree-shaking)
import * as duckdb from '@duckdb/duckdb-wasm/dist/duckdb-esm.js';

// Either bundle them manually, for example as Webpack assets
import duckdb_wasm from '@duckdb/duckdb-wasm/dist/duckdb.wasm';
import duckdb_wasm_next from '@duckdb/duckdb-wasm/dist/duckdb-next.wasm';
import duckdb_wasm_next_coi from '@duckdb/duckdb-wasm/dist/duckdb-next-coi.wasm';
const WEBPACK_BUNDLES: duckdb.DuckDBBundles = {
    asyncDefault: {
        mainModule: duckdb_wasm,
        mainWorker: new URL('@duckdb/duckdb-wasm/dist/duckdb-browser-async.worker.js', import.meta.url).toString(),
    },
    asyncNext: {
        mainModule: duckdb_wasm_next,
        mainWorker: new URL('@duckdb/duckdb-wasm/dist/duckdb-browser-async-next.worker.js', import.meta.url).toString(),
    },
    asyncNextCOI: {
        mainModule: duckdb_wasm_next_coi,
        mainWorker: new URL(
            '@duckdb/duckdb-wasm/dist/duckdb-browser-async-next-coi.worker.js',
            import.meta.url,
        ).toString(),
        pthreadWorker: new URL(
            '@duckdb/duckdb-wasm/dist/duckdb-browser-async-next-coi.pthread.worker.js',
            import.meta.url,
        ).toString(),
    },
};
// ..., or load the bundles from jsdelivr
const JSDELIVR_BUNDLES = duckdb.getJsDelivrBundles();

// Select a bundle based on browser checks
const bundle = await duckdb.selectBundle(JSDELIVR_BUNDLES);
// Instantiate the asynchronous version of DuckDB-Wasm
const worker = new Worker(bundle.mainWorker!);
const logger = new duckdb.ConsoleLogger();
const db = new duckdb.AsyncDuckDB(logger, worker);
await db.instantiate(bundle.mainModule, bundle.pthreadWorker);

Sie können die Features und das gewählte Bundle in Ihrem Browser auch mit dem Web-Shell-Befehl .features testen.

Multithreading

2018 schickten die Schwachstellen Spectre und Meltdown lähmende Schockwellen durch das Internet. Heute stehen wir vor den Nachwirkungen dieser Ereignisse, insbesondere in Software, die beliebigen Nutzercode ausführt – etwa Webbrowser. Kurz nach den Veröffentlichungen schränkten alle großen Browser-Anbieter die Nutzung von SharedArrayBuffers ein, um gefährliche Timing-Angriffe zu verhindern. SharedArrayBuffers sind Rohbuffer, die unter Web Workern für globalen Zustand geteilt werden können, und eine Alternative zur browserspezifischen Message Passing. Diese Einschränkungen hatten nachteilige Auswirkungen auf WebAssembly-Module, weil SharedArrayBuffers für die Umsetzung von POSIX-Threads in WebAssembly nötig sind.

Ohne SharedArrayBuffers können WebAssembly-Module in einem eigenen Web Worker laufen, um die Haupt-Event-Loop nicht zu blockieren, können aber keine zusätzlichen Worker für parallele Berechnungen innerhalb derselben Instanz spawnen. Standardmäßig können wir die parallele Query-Ausführung von DuckDB im Web daher nicht entfesseln. Browser-Anbieter haben jedoch kürzlich begonnen, SharedArrayBuffers für Websites wieder zu aktivieren, die cross-origin-isolated sind. Eine Website ist cross-origin-isolated, wenn sie das Hauptdokument mit den folgenden HTTP-Headern ausliefert:

Cross-Origin-Embedder-Policy: require-corp
Cross-Origin-Opener-Policy: same-origin

Diese Header weisen Browser an, A) das Top-Level-Dokument von anderen Top-Level-Dokumenten außerhalb seiner eigenen Origin zu isolieren und B) das Dokument daran zu hindern, beliebige Cross-Origin-Requests zu stellen, es sei denn, die angeforderte Ressource stimmt ausdrücklich zu. Beide Einschränkungen haben weitreichende Implikationen für eine Website, weil viele Drittanbieter-Datenquellen die Header heute noch nicht bereitstellen und die Top-Level-Isolation derzeit die Kommunikation mit zum Beispiel OAuth-Pop-ups behindert (es gibt Pläne, das aufzuheben).

Wir gehen daher davon aus, dass DuckDB-Wasm die Mehrheit der Nutzer auf nicht-isolierten Websites finden wird. Wir experimentieren jedoch mit eigenen Bundles für isolierte Sites mit dem Suffix -next-coi und werden den künftigen Bedarf unserer Nutzer genau beobachten.

Web Shell

Wir hosten außerdem eine Web Shell, angetrieben von DuckDB-Wasm, neben dem Bibliotheks-Release unter shell.duckdb.org. Nutzen Sie die folgenden Shell-Befehle, um Remote-TPC-H-Dateien bei Scale Factor 0.01 abzufragen. Wenn Sie Ihre eigenen abfragen, setzen Sie CORS-Header richtig, weil Ihr Browser diese Requests sonst blockiert. Sie können alternativ den Befehl .files nutzen, um Dateien vom lokalen Dateisystem zu registrieren.

.timer on

SELECT count(*)
FROM 'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/lineitem.parquet';

SELECT count(*)
FROM 'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/customer.parquet';

SELECT avg(c_acctbal)
FROM 'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/customer.parquet';

SELECT *
FROM 'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/orders.parquet'
LIMIT 10;

SELECT n_name, avg(c_acctbal)
FROM
    'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/customer.parquet',
    'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/nation.parquet'
WHERE c_nationkey = n_nationkey
GROUP BY n_name;

SELECT *
FROM
    'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/region.parquet',
    'https://blobs.duckdb.org/data/tpch-sf0.01-parquet/nation.parquet'
WHERE r_regionkey = n_regionkey;

Evaluation

Die folgende Tabelle gibt einen Vorgeschmack auf die Ausführungszeiten einiger TPC-H-Abfragen bei Scale Factor 0.5 mit den Bibliotheken DuckDB-Wasm, sql.js, Arquero und Lovefield. Eine ausführlichere Diskussion mit allen TPC-H-Abfragen, zusätzlichen Scale Factors und Mikrobenchmarks finden Sie auf der Seite „DuckDB-Wasm versus X“.

Zukünftige Forschung

Wir glauben, dass WebAssembly bisher schlummerndes Potenzial für geteilte Query-Verarbeitung zwischen Clients und Servern freilegt. Berechnung näher an den Client zu schieben kann teure Roundtrips zum Server eliminieren und so Interaktivität und Skalierbarkeit von In-Browser-Analytik steigern. Wir glauben weiter, dass das Release von DuckDB-Wasm der erste Schritt zu einer universelleren Datenebene sein könnte, die mehrere Schichten überspannt, einschließlich traditioneller Datenbankserver, Clients, CDN-Worker und Computational Storage. Als In-Process-analytische Datenbank könnte DuckDB der ideale Treiber für verteilte Query-Pläne sein, die Skalierbarkeit und Interaktivität von SQL-Datenbanken zu geringen Kosten steigern.