Auf der Suche nach einem schnelleren SQLite

• Wenn in serverlosen und Edge-Umgebungen mehrere SQLite-Instanzen parallel laufen, erhöht synchrones I/O-Warten die Tail Latency; Forschende aus Helsinki und Cambridge haben untersucht, wie sich dies durch asynchrones I/O und Storage-Disaggregation verringern lässt
• Linux io_uring ermöglicht es Anwendungen über Submission- und Completion-Queues, während I/O-Anfragen weiter andere Aufgaben auszuführen, und bildet damit eine Grundlage, um Thread-Blocking zu reduzieren
• Wenn SQLite während der Ausführung von sqlite3_step() benötigte B-Tree-Seiten nicht im Cache findet, liest es die Daten per synchronem I/O wie POSIX read() von der Festplatte, wodurch der Thread bis zum Abschluss des I/O anhält
• Die Forschenden haben nicht nur POSIX-Aufrufe ersetzt, sondern im Rust-basierten Rewrite-Projekt Limbo VM und BTree an ein asynchrones Ausführungsmodell angepasst
• In Benchmarks sank die p999-Tail-Latenz um bis zu 100-fach, während p90 und p99 nahezu identisch mit SQLite waren; die Bewertung mit mehreren Readern/Writern bleibt eine Aufgabe für die Zukunft

---

Forschung zur Beschleunigung von SQLite

• Forschende der University of Helsinki und aus Cambridge behandeln in „Serverless Runtime / Database Co-Design With Asynchronous I/O“, wie sich asynchrones I/O und Storage-Disaggregation auf SQLite anwenden lassen
• Dieses Paper wurde zur Grundlage von Limbo, einem Rust-basierten Rewrite-Projekt von SQLite
• Da es sich um ein Workshop-Paper handelt, ist es kurz; der Fokus liegt auf Serverless und Edge Computing
• Der Kernpunkt: Auch wenn SQLite selbst bereits schnell ist, lässt sich die Tail Latency in Multi-Tenant-Umgebungen durch eine Änderung des Ausführungsmodells weiter senken

Wie io_uring I/O-Wartezeiten reduziert

• io_uring im Linux-Kernel stellt eine Schnittstelle für asynchrones I/O bereit
• Der Name stammt von den Ringpuffern, die von User Space und Kernel Space gemeinsam genutzt werden; dadurch sinkt der Overhead durch Pufferkopien zwischen beiden Bereichen
• Eine Anwendung kann nach dem Einreichen einer I/O-Anfrage parallel andere Arbeit erledigen, bis das Betriebssystem den Abschluss meldet
• Der Ablauf ist wie folgt
  • Mit dem Systemaufruf io_uring_setup() werden zwei Speicherbereiche eingerichtet: Submission Queue und Completion Queue
  • Die Anwendung legt I/O-Anfragen in die Submission Queue und signalisiert dem Betriebssystem mit io_uring_enter(), die Verarbeitung zu starten
  • Anders als read() und write() blockiert dies den Thread nicht, sondern gibt die Kontrolle an den User Space zurück
  • Die Anwendung erledigt andere Aufgaben und pollt regelmäßig die Completion Queue, um den Abschluss des I/O zu prüfen

Der synchrone I/O-Flaschenhals bei der SQLite-Query-Ausführung

• Eine SQLite-Anwendung öffnet mit sqlite3_open() eine Datenbankdatei; dabei werden Low-Level-OS-I/O-Aufrufe wie POSIX open ausgeführt
• sqlite3_prepare() wandelt SQL-Anweisungen wie SELECT und INSERT in eine Sequenz von Bytecode-Instruktionen um
• sqlite3_step() führt die Bytecode-Instruktionen aus, bis eine von der Query zu lesende Zeile erzeugt wurde oder die Ausführung beendet ist
  • Wenn eine lesbare Zeile vorhanden ist, wird SQLITE_ROW zurückgegeben
  • Wenn die Anweisung abgeschlossen ist, wird SQLITE_DONE zurückgegeben
• Während der Ausführung wird der Backend-Pager aufgerufen und der B-Tree durchlaufen, der Tabellen und Zeilen repräsentiert
• Wenn eine benötigte B-Tree-Seite nicht im SQLite-Seitencache liegt, kommt es zu einem Festplattenzugriff
  • SQLite liest den Seiteninhalt per synchronem I/O wie POSIX read von der Festplatte in den Speicher
  • Währenddessen blockiert sqlite3_step() den Kernel-Thread
  • Um während der I/O-Wartezeit parallel arbeiten zu können, muss die Anwendung mehr Threads verwenden

Warum SQL in Serverless- und Edge-Umgebungen eingebettet werden soll

• Wenn Serverless Computing am Edge ausgeführt wird und sich die Datenbank in einer Cloud-Umgebung befindet, entstehen Netzwerk-Roundtrip-Kosten zwischen Serverless-Funktion und Cloud
• Eine Möglichkeit ist, Daten am Edge mitzuplatzieren; als besserer Ansatz wird jedoch genannt, die Datenbank direkt in die Edge-Runtime einzubetten
• Cloudflare Workers erreichen bereits eine solche Form, stellen jedoch ein KV-Interface bereit
• KV passt nicht zu allen Problembereichen
  • Werden tabellarische Daten auf ein KV-Modell abgebildet, verschlechtert sich die Developer Experience
  • Außerdem entstehen Kosten für Serialisierung und Deserialisierung
• SQL kann besser geeignet sein, und SQLite kann als Embedded Database direkt in eine Serverless-Runtime integriert werden

Warum sich SQLite nicht einfach auf io_uring umstellen lässt

• SQLite verwendet synchrones I/O auf Basis der traditionellen POSIX-Aufrufe read() und write()
• Für kleine Anwendungen ist das nicht unbedingt ein großes Problem, kann aber zum Flaschenhals werden, wenn auf einem Server Hunderte SQLite-Datenbanken laufen
• In Umgebungen, in denen die Auslastung der Serverressourcen maximiert werden muss, wirkt synchrones I/O als Einschränkung
• SQLite hat Probleme mit Nebenläufigkeit und Multi-Tenancy
  • Da I/O synchron ist und blockiert, konkurrieren Anwendungen auf derselben Maschine um Ressourcen
  • Dadurch steigt die Latenz
• POSIX-I/O-Aufrufe lassen sich nicht einfach durch io_uring ersetzen
  • Anwendungen, die blockierendes I/O verwenden, müssen für das asynchrone I/O-Modell von io_uring neu entworfen werden
  • Die SQLite-Bibliothek muss in der Lage sein, während laufendem I/O die Kontrolle an die Anwendung zurückzugeben
• Statt nur einzelne Aufrufe in SQLite zu ändern, wählten die Forschenden den Ansatz, SQLite in Rust neu zu schreiben und io_uring zu verwenden

Limbos asynchrones Ausführungsmodell

• Limbo ist ein Projekt, das SQLite in Rust neu schreibt und die Komponenten VM und BTree so verändert, dass sie asynchrones I/O unterstützen
• Synchrone Bytecode-Instruktionen werden durch asynchrone Gegenstücke ersetzt
• Beispielsweise bewegt die Instruktion Next den Cursor weiter und holt bei Bedarf die nächste Seite
  • In der bisherigen synchronen Version wird bei auftretendem Festplatten-I/O blockiert, bis die Seite gelesen und an den Aufrufer zurückgegeben wurde
  • In der asynchronen Version kehrt NextAsync sofort zurück, nachdem es eingereicht wurde
  • Der Aufrufer kann anschließend blockieren oder andere Arbeit ausführen
• Asynchrones I/O beseitigt Blocking und verbessert die Nebenläufigkeit
• Um die Ressourcenauslastung weiter zu erhöhen, wird außerdem Storage-Disaggregation vorgeschlagen, also die Trennung von Query Engine und Storage Engine
• Als zugehörige Erklärung wird Disaggregated Storage - a brief introduction verlinkt

Benchmark-Ergebnisse und offene Fragen

• Der Benchmark simuliert eine Multi-Tenant-Serverless-Runtime
• Jeder Tenant besitzt dabei seine eigene eingebettete Datenbank
• Die Anzahl der Tenants wird in Zehnerschritten von 1 bis 100 variiert
• SQLite verwendet für jeden Tenant einen eigenen Thread; gemessen wird, indem in jedem Thread Queries ausgeführt werden
• Die ausgeführte Query lautet SELECT * FROM users LIMIT 100 und wird 1000-mal wiederholt
• Limbo führt dasselbe Experiment durch, verwendet dabei jedoch Rust-Coroutinen
• Im Ergebnis sinkt die Tail Latency bei p999 um bis zu 100-fach
• Die SQLite-Query-Latenz verschlechterte sich mit zunehmender Thread-Zahl nicht graduell
• Die Arbeit ist noch im Gange, und im Paper bleiben einige offene Fragen
  • Future Work behandelt weitere Benchmarks mit mehreren Readern und Writern
  • Der Vorteil zeigt sich erst ab p999 deutlich
  • Die Performance bei p90 und p99 ist nahezu identisch mit SQLite
• Der Limbo-Code ist als Open Source verfügbar
• Limbo ist inzwischen ein offizielles Turso-Projekt; auch ein Einführungsbeitrag wurde veröffentlicht