À la recherche d’un SQLite plus rapide

• Dans les environnements serverless et edge, l’exécution simultanée de plusieurs instances SQLite amplifie la latence de queue à cause de l’attente d’E/S synchrones ; des chercheurs d’Helsinki et de Cambridge ont expérimenté une approche visant à la réduire grâce aux E/S asynchrones et à la désagrégation du stockage
• Sous Linux, io_uring permet à une application de continuer d’autres traitements pendant des requêtes d’E/S via une file de soumission et une file de complétion, ce qui constitue une base pour réduire le blocage des threads
• Dans SQLite, si une page de B-Tree nécessaire pendant l’exécution de sqlite3_step() n’est pas dans le cache, le disque est lu via des E/S synchrones comme read() POSIX, ce qui bloque le thread jusqu’à la fin de l’E/S
• Les chercheurs ne se sont pas contentés de remplacer les appels POSIX : dans Limbo, un projet de réécriture en Rust, ils ont adapté la VM et le BTree à un modèle d’exécution asynchrone
• Dans les benchmarks, la latence de queue p999 a été réduite jusqu’à 100 fois, mais p90 et p99 restent presque identiques à SQLite, et l’évaluation avec plusieurs readers/writers demeure un travail futur

---

Des recherches pour rendre SQLite plus rapide

• Des chercheurs de l’University of Helsinki et de Cambridge expliquent dans « Serverless Runtime / Database Co-Design With Asynchronous I/O » comment appliquer les E/S asynchrones et la désagrégation du stockage à SQLite
• Cet article a servi de base à Limbo, un projet de réécriture de SQLite en Rust
• Comme il s’agit d’un papier d’atelier, il est court et se concentre sur le serverless et l’edge computing
• L’idée centrale est que, même si SQLite est déjà rapide en soi, la latence de queue dans les environnements multi-tenant peut encore être réduite en changeant le modèle d’exécution

L’attente d’E/S réduite par io_uring

• io_uring, dans le noyau Linux, fournit une interface d’E/S asynchrones
• Son nom vient du ring buffer partagé entre l’espace utilisateur et l’espace noyau, qui réduit le surcoût lié à la copie de tampons entre les deux espaces
• Après avoir soumis une requête d’E/S, l’application peut poursuivre d’autres tâches jusqu’à ce que l’OS signale sa complétion
• Le déroulé est le suivant
  • L’appel système io_uring_setup() configure deux zones mémoire : une file de soumission et une file de complétion
  • L’application place une requête d’E/S dans la file de soumission, puis indique à l’OS de démarrer le traitement avec io_uring_enter()
  • Au lieu de bloquer le thread comme read() et write(), le contrôle revient à l’espace utilisateur
  • L’application effectue d’autres tâches, puis interroge périodiquement la file de complétion pour vérifier la fin de l’E/S

Le goulot d’étranglement des E/S synchrones dans l’exécution des requêtes SQLite

• Une application SQLite ouvre un fichier de base de données avec sqlite3_open(), ce qui déclenche des E/S bas niveau de l’OS comme open POSIX
• sqlite3_prepare() transforme une instruction SQL comme SELECT ou INSERT en une séquence d’instructions bytecode
• sqlite3_step() exécute les instructions bytecode jusqu’à produire une ligne à lire ou jusqu’à la fin de l’exécution
  • S’il y a une ligne à lire, elle renvoie SQLITE_ROW
  • Lorsque l’instruction est terminée, elle renvoie SQLITE_DONE
• Pendant l’exécution, le pager backend est appelé et parcourt le B-Tree qui représente les tables et les lignes
• Si la page de B-Tree nécessaire n’est pas dans le cache de pages de SQLite, un accès disque a lieu
  • SQLite lit le contenu de la page depuis le disque vers la mémoire via des E/S synchrones comme read POSIX
  • Pendant ce temps, sqlite3_step() bloque le thread noyau
  • Pour effectuer des tâches concurrentes pendant l’attente d’E/S, l’application doit utiliser davantage de threads

Pourquoi embarquer SQL dans le serverless et l’edge

• Lorsque le serverless computing s’exécute en edge et que la base de données se trouve dans un environnement cloud, il existe un coût d’aller-retour réseau entre la fonction serverless et le cloud
• Une option consiste à colocaliser les données en edge, mais une meilleure approche proposée consiste à embarquer la base de données dans le runtime edge
• Cloudflare Workers atteint déjà ce type de modèle, mais expose une interface KV
• Le KV ne convient pas bien à tous les domaines de problèmes
  • Mapper des données tabulaires vers un modèle KV dégrade l’expérience développeur
  • Il entraîne aussi des coûts de sérialisation et de désérialisation
• SQL peut être plus approprié, et SQLite, en tant que base de données embarquée, peut être inclus directement dans un runtime serverless

Pourquoi il est difficile de remplacer simplement SQLite par io_uring

• SQLite utilise des E/S synchrones fondées sur les appels POSIX traditionnels read() et write()
• Même si ce n’est pas un gros problème pour de petites applications, cela peut devenir un goulot d’étranglement lorsque des centaines de bases SQLite s’exécutent sur un même serveur
• Dans des environnements où il faut maximiser l’utilisation des ressources serveur, les E/S synchrones deviennent une contrainte
• SQLite présente des problèmes de concurrence et de multi-tenancy
  • Comme les E/S sont synchrones et bloquantes, les applications sur la même machine se disputent les ressources
  • Résultat : la latence augmente
• Il est difficile de remplacer simplement les appels d’E/S POSIX par io_uring
  • Les applications utilisant des E/S bloquantes doivent être repensées pour s’adapter au modèle d’E/S asynchrones d’io_uring
  • La bibliothèque SQLite doit pouvoir rendre le contrôle à l’application pendant qu’une E/S est en cours
• Les chercheurs ont choisi de ne pas remplacer seulement quelques appels de SQLite, mais de réécrire SQLite en Rust et d’utiliser io_uring

Le modèle d’exécution asynchrone de Limbo

• Limbo est un projet de réécriture de SQLite en Rust ; ses composants VM et BTree ont été modifiés pour prendre en charge les E/S asynchrones
• Les instructions bytecode synchrones sont remplacées par des équivalents asynchrones
• Par exemple, l’instruction Next avance le curseur et récupère la page suivante si nécessaire
  • Dans la version synchrone existante, lorsqu’une E/S disque survient, l’exécution se bloque jusqu’à ce que la page soit lue et renvoyée à l’appelant
  • Dans la version asynchrone, NextAsync revient immédiatement après sa soumission
  • L’appelant peut ensuite bloquer ou effectuer d’autres tâches
• Les E/S asynchrones éliminent le blocage et améliorent la concurrence
• Pour augmenter encore l’utilisation des ressources, l’article propose aussi une désagrégation du stockage, qui sépare le moteur de requêtes du moteur de stockage
• Une explication connexe, Disaggregated Storage - a brief introduction, est également liée

Résultats des benchmarks et questions restantes

• Les benchmarks simulent un runtime serverless multi-tenant
• Chaque tenant dispose de sa propre base de données embarquée
• Le nombre de tenants varie de 1 à 100, par paliers de 10
• SQLite utilise un thread séparé par tenant, et les mesures sont effectuées en exécutant des requêtes dans chaque thread
• La requête exécutée est SELECT * FROM users LIMIT 100, répétée 1000 fois
• Limbo exécute la même expérience, mais avec des coroutines Rust
• Résultat : la latence de queue en p999 diminue jusqu’à 100 fois
• La latence des requêtes SQLite ne s’est pas dégradée progressivement avec l’augmentation du nombre de threads
• Le travail est encore en cours, et l’article laisse plusieurs questions ouvertes
  • La section Future Work couvre des benchmarks supplémentaires avec plusieurs readers et writers
  • Le bénéfice n’apparaît nettement qu’au-delà de p999
  • Les performances en p90 et p99 sont presque identiques à celles de SQLite
• Le code de Limbo est disponible en open source
• Limbo est désormais un projet officiel de Turso, et un article de présentation a également été publié