SQLite

Analyse d'un chef-d'œuvre de l'ingénierie logicielle

ELLE EST PARTOUT

Et pourtant, on ne la voit jamais

LA BDD LA PLUS DÉPLOYÉE AU MONDE

Elle est dans votre poche, votre voiture, votre avion, ...

sqlite-everywhere.jpg

Tous les smartphones, tous les navigateurs
Android, iOS, macOS, Windows 10 et 11 ; Firefox, Chrome, Safari

Des applications par millions
Skype, iTunes, Dropbox, TurboTax, QuickBooks, PHP, Python

Téléviseurs, box, voitures, avions
La plupart des systèmes multimédia embarqués ; testée selon les exigences de la norme DO-178B

Plus de mille milliards de bases actives
Ce n'est pas PostgreSQL, ce n'est pas MySQL, c'est encore moins Oracle

MAINTENANT IMAGINEZ ...

 

Qu'une base de données relationnelle tienne dans un fichier
et utilise juste 7 fonctions de la libc

Qu'elle embarque une machine virtuelle complète,
avec 191 instructions pour exécuter vos requêtes SQL

Qu'elle compte 590 fois plus de code de test
que de code fonctionnel

Qu'elle vous garantit de pouvoir relire vos données
jusqu'en 2050

···

Entrons dans le terrier !
Et suivons le lapin blanc

UNE PARENTHÈSE HISTORIQUE

Un homme, un destroyer et un fichier

RICHARD HIPP

L'auteur, et toujours le développeur principal

richard-hipp.jpg

Dwayne Richard Hipp, 1961, Caroline du Nord
Doctorat à Duke en 1992, thèse en compréhension du langage naturel, pas en bases de données

Hwaci, sa société de conseil
Hipp, Wyrick & Company : la société montée après sa thèse, rebaptisée en 1994

Il écrit lui-même tous ses outils
Lemon le générateur d'analyseurs, Fossil le gestionnaire de sources, Pikchr les diagrammes, althttpd le serveur de sqlite.org

Vingt-six ans sur le même logiciel
Premier commit le 29 mai 2000 ; il en vit depuis, en vendant du support aux industriels

UN DESTROYER ET UNE BASE QUI TOMBE

C'était en l'an 2000, au printemps ...

ddg-79-oscar-austin.jpg

Richard Hipp, General Dynamics, US Navy
Sous-traitant à Bath Iron Works sur le destroyer DDG-79 USS Oscar Austin

Un logiciel de contrôle des avaries
Localiser les vannes à fermer quand une canalisation rompt

HP-UX et une base Informix
« Sometimes the server would go down, and then our application wouldn't run »

Et si la base n'était qu'un fichier ?
Rien à démarrer, rien à administrer : ouvrir et lire

Née comme une extension Tcl
Hipp est un habitué de Tcl ; l'interface Tcl est toujours dans les sources

SQLITE, KÉZAKO

Ce qu'elle est et ce qu'elle n'est pas

keep-it-simple-but-make-it-amazing.gif

C'est avant tout une bibliothèque
Et non un serveur et un service

La base est un fichier unique
Se connecter, c'est ouvrir le fichier ; pas de processus serveur, pas de socket, pas de réseau

Aucune dépendance externe
Tokenizer, parser, machine virtuelle, B-tree, pager, journalisation : tout est embarqué

S'appuie uniquement sur 7 fonctions de la libc
memcmp, memcpy, memmove, memset, strcmp, strlen, strncmp ; malloc, realloc et free sont optionnels

Pas de GRANT, pas de rôles
Les seuls droits sont les permissions du fichier ; un seul écrivain à la fois

Accès réseau ou écritures concurrentes ?
Alors prenez du client-serveur. Pour tout le reste utilisez SQLite

SQLITE, TROIS VERSIONS

Et un format pour les gouverner tous

mindblowing.jpg

Version 1.0, le 17 août 2000
Stockage délégué à GDBM, le gestionnaire de bases GNU

Version 2.0, le 28 septembre 2001
B-tree maison à la place de GDBM, arrivée des transactions

Version 3.0, le 18 juin 2004
Nouveau format de fichier, typage manifeste, UTF-16, BLOB ; financé en partie par AOL

Toujours au format 3 aujourd'hui
Version 3.54.1 le 16 octobre 2026 : un fichier créé en 2004 s'ouvre tel quel

Rétrocompatibilité promise jusqu'en 2050
Des bugs de format sont conservés exprès : les corriger casserait des fichiers existants

Un fichier identique bit à bit partout
32 et 64 bits, big et little endian ; format retenu par la Library of Congress pour la préservation numérique

DOMAINE PUBLIC

Ni licence, ni pull request

public-domain.gif

Code et documentation dédiés au domaine public
Copier, modifier, vendre, embarquer, sans condition ; ce n'est donc pas une licence approuvée par l'OSI

Des juridictions ne le reconnaissent pas
Hwaci leur vend une « Warranty of Title » ; c'est pour ça qu'elle est partout

Fossil plutôt que GitHub
Un gestionnaire de sources maison, écrit en C, qui stocke tout dans une base SQLite

Contributions extérieures refusées
Accepter un patch, c'est accepter un droit d'auteur : adieu le domaine public

Les rapports de bugs, eux, sont bienvenus
Forum public, contributions anonymes autorisées ; une poignée de développeurs tient la roadmap

ARCHITECTURE

Suivons le lapin blanc

POURQUOI EN C ?

Et pourquoi pas en Rust

why-c.jpg

« C is old and boring »
Un langage connu, stable, compris de tous

« Portable assembly language »
Au plus près du matériel, portable partout

Appelable de partout
Wrappers Rust, Go, Python, Java, C#, PHP, Perl, JavaScript ...

Dépendances minimales
Pas de runtime de plusieurs mégaoctets

Réécrire SQLite en Rust ou en Go ?
Excellent exercice éducatif ; personne n'atteindra cette fiabilité de sitôt

L'AMALGAMATION

Un projet, deux fichiers

fusion.jpg

Plus de 100 fichiers sources concaténés
sqlite3.c : 271 131 lignes et 9,6 Mo ; sqlite3.h : 14 447 lignes (3.54.1)

La forme de distribution recommandée
sqlite-amalgamation.zip fait 2,8 Mo ; les sources complètes 13,9 Mo, tests compris

5 à 10 % plus rapide
Le compilateur inline et optimise entre modules

Des centaines d'options de compilation
SQLITE_OMIT_JSON, SQLITE_OMIT_TRIGGER, SQLITE_ENABLE_FTS5, SQLITE_ENABLE_RTREE ...

Deux fichiers à déposer dans votre projet
Et ça compile partout où il y a un compilateur C

VUE D'ENSEMBLE

Quatre sous-systèmes et onze briques

sqlite-architecture.png

Une seule frontière publique
sqlite3.h : sqlite3_open, sqlite3_prepare_v2, sqlite3_step, sqlite3_finalize

Le front-end compile
Tokenizer (tokenize.c), parser (parse.y), générateur de code (build.c, select.c, where.c)

Le back-end exécute
Machine virtuelle (vdbe.c), B-tree (btree.c), pager (pager.c, wal.c), VFS (os_unix.c, os_win.c)

Deux services transverses
Utilitaires (util.c, printf.c, hash.c, utf.c) et code de test (test*.c, exclu des builds)

TOKENIZER ET PARSER

Du texte SQL à l'arbre syntaxique

LE SQL DE SQLITE

Du SQL-92 avec quelques limites

car-sql.jpg

SQL-92 presque complet
Jointures, sous-requêtes, triggers FOR EACH ROW, vues (en lecture seule)

Et du SQL moderne
CTE, fonctions de fenêtre, UPSERT, RETURNING, RIGHT et FULL JOIN depuis 3.39 (2022)

GRANT et REVOKE n'existent pas
Sans utilisateurs, ils n'auraient aucun sens : ce serait une erreur de syntaxe

ALTER TABLE limité
RENAME, ADD COLUMN, RENAME COLUMN, DROP COLUMN, rien d'autre

Clés étrangères désactivées par défaut
Supportées depuis 3.6.19 (2009), PRAGMA foreign_keys = ON ; c'est pour la compatibilité

DU TEXTE AU BYTECODE

Qui appelle qui

tokenizer-parser.png

 

LE TOKENIZER

899 lignes écrites à la main

preskovic.gif

Pas de lex, pas de flex
Un découpage manuel, UTF-8, sans dépendance ni outil externe

Une table de classes de caractères
Un switch sur aiClass[c] devient une table de saut, pas une recherche binaire

Les mots-clés par table de hachage générée
tool/mkkeywordhash.c produit keywordhash.h : 147 mots-clés, code compact pour l'embarqué

C'est le tokenizer qui appelle le parser
sqlite3RunParser : l'inverse de yacc, réentrant et thread-safe

DÉCOUPER UN TOKEN

Une table, un switch, un hachage

tokenizer.png

 

LEMON, LE YACC FAIT MAISON

Un générateur de parseurs en 6074 lignes de code

yacc.jpg

Écrit par Richard Hipp pendant sa thèse
Entre 1987 et 1992, à Duke ; perdu, puis réécrit pour SQLite

LALR(1), comme yacc et Bison
Même famille d'analyseurs, mais des choix inverses

Le tokenizer appelle le parser
Un « push parser » : pas de variables globales, réentrant, thread-safe

Des destructeurs de non-terminaux
La mémoire est libérée même quand l'analyse échoue en cours de route

Des noms symboliques
expr(A) ::= expr(B) PLUS expr(C). plutôt que $1, $2, $3

Fourni avec SQLite
tool/{lemon,lempar}.c, réutilisable dans vos propres projets

PARSE.Y ET LEMPAR.C

La grammaire du SQL de SQLite


                                cmd ::= BEGIN transtype(Y) trans_opt.  {sqlite3BeginTransaction(pParse, Y);}
                                trans_opt ::= .
                                trans_opt ::= TRANSACTION.
                                trans_opt ::= TRANSACTION nm.
                                %type transtype {int}
                                transtype(A) ::= .             {A = TK_DEFERRED;}
                                transtype(A) ::= DEFERRED(X).  {A = @X; /*A-overwrites-X*/}
                                transtype(A) ::= IMMEDIATE(X). {A = @X; /*A-overwrites-X*/}
                                transtype(A) ::= EXCLUSIVE(X). {A = @X; /*A-overwrites-X*/}
                                cmd ::= COMMIT|END(X) trans_opt.   {sqlite3EndTransaction(pParse,@X);}
                                cmd ::= ROLLBACK(X) trans_opt.     {sqlite3EndTransaction(pParse,@X);}
                                savepoint_opt ::= SAVEPOINT.
                                savepoint_opt ::= .
                                cmd ::= SAVEPOINT nm(X). {
                                  sqlite3Savepoint(pParse, SAVEPOINT_BEGIN, &X);
                                }
                                cmd ::= RELEASE savepoint_opt nm(X). {
                                  sqlite3Savepoint(pParse, SAVEPOINT_RELEASE, &X);
                                }
                                ...
                            

PARSE.Y, LEMPAR.C ET PARSE.C

Les trois fichiers

parser.png

 

LE VDBE

Le Virtual DataBase Engine, la VM de SQLite

BYTECODE PLUTÔT QU'ARBRE

Le choix qui distingue SQLite

drake-bytecode-ast.jpg

PostgreSQL et MySQL interprètent un arbre d'objets
L'arbre syntaxique est visité à l'exécution

SQLite compile en bytecode
Un programme plat : une instruction par ligne, un opcode et cinq opérandes

Plus lisible
EXPLAIN affiche le programme tel qu'il sera exécuté

Plus débogable
Front-end et back-end séparés ; PRAGMA vdbe_trace = ON trace l'exécution

Exécutable pas à pas
sqlite3_step rend la main à chaque ligne de résultat : indispensable pour une bibliothèque

UNE MACHINE À REGISTRES

191 opcodes, pas un de plus

perfectly-balanced.jpg

Des registres typés dynamiquement
NULL, entier 64 bits, double, texte, BLOB, RowSet, Frame, ou indéfini

191 opcodes en 3.54.1
Une centaine au début de SQLite 3, 189 début 2025

Générés depuis les commentaires de vdbe.c
Un script lit les lignes « Opcode: » et produit opcodes.h, opcodes.c et la documentation

Une VM assez évoluée
Init, Transaction, OpenRead, Rewind, Column, ResultRow, Next, Halt, Savepoint, Vacuum, Checkpoint ...

Un giant switch
sqlite3VdbeExec dans vdbe.c, 9573 lignes

EXPLAIN

Lire le programme d'une requête


                                CREATE TABLE users(id INTEGER PRIMARY KEY, name TEXT, age INTEGER);
                                INSERT INTO users(name, age) VALUES ('Alice', 42), ('Bob', 17), ('Carol', 33);
                                EXPLAIN SELECT name FROM users WHERE age > 18;
                            

                                addr  opcode         p1    p2    p3    p4             p5  comment
                                ----  -------------  ----  ----  ----  -------------  --  -------------
                                0     Init           0     9     0                    0
                                1     OpenRead       0     2     0     3              0
                                2     Rewind         0     8     0                    0
                                3       Column         0     2     1                    0
                                4       Le             2     7     1     BINARY-8       84
                                5       Column         0     1     3                    0
                                6       ResultRow      3     1     0                    0
                                7     Next           0     3     0                    1
                                8     Halt           0     0     0                    0
                                9     Transaction    0     0     1     0              1
                                10    Integer        18    2     0                    0
                                11    Goto           0     1     0                    0
                            

PREPARED STATEMENTS

Compiler une fois, exécuter mille fois

sqlite3_prepare_v2 compile
Le texte SQL devient un programme VDBE : un sqlite3_stmt

sqlite3_bind_* remplit les registres
Les paramètres sont des registres, pas du texte : adieu les injections SQL

sqlite3_step exécute
Jusqu'au prochain ResultRow, puis rend la main avec SQLITE_ROW

sqlite3_reset rejoue
Sans recompiler, avec de nouveaux paramètres

sqlite3_finalize libère
Registres vidés, curseurs fermés

LES TRICKS DU BYTECODE

Ce qu'on trouve en lisant vdbe.c

Des coroutines
InitCoroutine, Yield, EndCoroutine : une sous-requête produit ses lignes à la demande, sans table temporaire

Des sous-programmes
Gosub, Return, Program : triggers et clés étrangères

Une exécution unique
Once : les initialisations ne sont faites qu'au premier passage

Des filtres de Bloom
Filter et FilterAdd depuis 3.38 (2022) : éviter des recherches inutiles dans les jointures

Un prologue en fin de programme
Init saute à la fin, Transaction ouvre, Goto revient : le corps de boucle reste compact

LE QUERY PLANNER

Choisir le bon chemin avant de compiler


                                sqlite> EXPLAIN QUERY PLAN SELECT name FROM users WHERE age > 18;
                                `--SCAN users
                                sqlite> CREATE INDEX users_age ON users(age);
                                sqlite> EXPLAIN QUERY PLAN SELECT name FROM users WHERE age > 18;
                                `--SEARCH users USING INDEX users_age (age>?)
                                sqlite> EXPLAIN QUERY PLAN SELECT age FROM users WHERE age > 18 ORDER BY name;
                                |--SEARCH users USING INDEX users_age (age>?)
                                `--USE TEMP B-TREE FOR ORDER BY
                            

SCAN ou SEARCH
Parcours complet ou recherche par index ; COVERING INDEX quand l'index suffit
ANALYZE et sqlite_stat1 : des statistiques pour distinguer un bon index d'un mauvais ; PRAGMA optimize avant de fermer

Next Generation Query Planner (SQLite 3.8.0, août 2013)
N plus proches voisins au lieu du glouton : sur TPC-H Q8, un plan 750 fois plus rapide

Les optimisations classiques
Index automatiques, covering index, skip-scan, push-down, aplatissement des sous-requêtes

UN PROGRAMME PLUS GROS

Les coroutines, pour de vrai


                                    SELECT u.name
                                    FROM (SELECT name, age FROM users LIMIT 3) u
                                    WHERE u.age > 20;
                                

                                    QUERY PLAN
                                    |--CO-ROUTINE u
                                    |  `--SCAN users
                                    `--SCAN u
                                

                                addr  opcode         p1    p2    p3    p4             p5  comment
                                ----  -------------  ----  ----  ----  -------------  --  -------------
                                0     Init           0     19    0                    0
                                1     InitCoroutine  1     11    2                    0
                                2     Integer        3     2     0                    0
                                3     OpenRead       1     2     0     3              0
                                4     Rewind         1     10    0                    0
                                5       Column         1     1     3                    0
                                6       Column         1     2     4                    0
                                7       Yield          1     0     0                    0
                                8       DecrJumpZero   2     10    0                    0
                                9     Next           1     5     0                    1
                                10    EndCoroutine   1     0     0                    0
                                11    InitCoroutine  1     0     2                    0
                                12      Yield          1     18    0                    0
                                13      Copy           4     5     0                    2
                                ...
                            

B-TREE ET FORMAT DE FICHIER

Un seul fichier, des pages, deux sortes d'arbres

KNUTH ET L'EXERCICE DE FIN DE CHAPITRE

Comment on écrit un B-tree en 2001

donald-knuth.jpg

Nobody ever taught me about a B-tree ... I flipped to the chapter on searching and looked up B-trees. He does not provide an algorithm for deleting from the B-tree. That's an exercise at the end of the chapter, so before I wrote my own B-tree I had to solve the exercise

D. Richard Hipp, podcast Corecursive, épisode 66

UN FICHIER, DES PAGES

« SQLite format 3 »


                                00000000  53 51 4c 69 74 65 20 66  6f 72 6d 61 74 20 33 00  |SQLite format 3.|
                                00000010  10 00 01 01 00 40 20 20  00 00 00 06 00 00 00 05  |.....@  ........|
                                00000020  00 00 00 00 00 00 00 00  00 00 00 04 00 00 00 04  |................|
                            

100 octets d'en-tête
La chaîne « SQLite format 3\0 », la taille de page (0x1000 = 4096), les versions de format ...

Des pages de 512 à 65 536 octets
4096 par défaut, toujours une puissance de deux, fixée à la création

Six familles de pages
B-tree (table ou index, interne ou feuille), freelist, overflow, pointer map, lock-byte

Identique sur toutes les plateformes
Big ou little endian, 32 ou 64 bits : le fichier se copie tel quel

281 téraoctets au maximum
4 294 967 294 pages de 65 536 octets ; et 2000 colonnes par table, 1 Go par valeur, 1 Go par requête

DEUX SORTES DE B-TREE

Tables et index ne sont pas rangés pareil

Table b-tree
Clé = rowid entier 64 bits, toutes les données dans les feuilles : un B+tree

Index b-tree
Clés arbitraires, aucune donnée : la clé contient les colonnes indexées et le rowid

Un arbre par table, un par index
Tous dans le même fichier, repérés par leur page racine

INTEGER PRIMARY KEY
Un alias du rowid : pas d'index supplémentaire, la table est déjà triée dessus

WITHOUT ROWID, 3.8.2 (2013)
La table vit dans un index b-tree : jusqu'à moitié moins d'espace, deux fois plus rapide

PAGE 1 : LE SCHÉMA EST DU SQL

La table sqlite_schema


                                sqlite> SELECT type, name, rootpage, sql FROM sqlite_schema;
                                type     name     rootpage                                 sql
                                -----  ---------  --------  ------------------------------------------------------------------
                                table  users             2  CREATE TABLE users(id INTEGER PRIMARY KEY, name TEXT, age INTEGER)
                                index  users_age         3  CREATE INDEX users_age ON users(age)
                            

La page 1 est la racine de sqlite_schema
Une table comme les autres : type, name, tbl_name, rootpage, sql

Le schéma est stocké en texte
Les ordres CREATE tels que vous les avez écrits, reparsés à chaque ouverture

rootpage pointe vers l'arbre
Chaque table et chaque index a sa page racine

Voilà pourquoi ALTER TABLE est limité
Modifier le schéma, c'est réécrire du texte SQL et le reparser

ENREGISTREMENTS : VARINT ET SERIAL TYPES

Stocker au plus compact

Le varint
Entier de 1 à 9 octets, bit de poids fort = « il y a une suite » ; utilisé partout dans le format

Un enregistrement = en-tête + corps
L'en-tête liste un serial type par colonne, le corps enchaîne les valeurs

Les entiers prennent la place qu'il faut
0, 1, 2, 3, 4, 6 ou 8 octets selon la valeur

Les constantes 0 et 1 tiennent en zéro octet
Serial types 8 et 9 : le type dit tout, pas besoin de valeur

Texte et BLOB
La longueur est codée dans le serial type : (N - 13) / 2 pour le texte, (N - 12) / 2 pour le BLOB

DÉBORDEMENT ET RECYCLAGE

Quand une valeur ne tient pas dans sa page


                                    sqlite> SELECT name, pageno, pagetype, payload, unused
                                       ...>   FROM dbstat('main') WHERE name = 'docs' LIMIT 4;
                                    name  pageno  pagetype  payload  unused
                                    ----  ------  --------  -------  ------
                                    docs       2  internal        0    3741
                                    docs       7  leaf         3821     258
                                    docs       3  overflow     4092       0
                                    docs       4  overflow     4092       0
                                

                                    sqlite> DELETE FROM docs WHERE id > 10;
                                    page_count   = 152
                                    freelist_cnt = 120
                                    sqlite> VACUUM;
                                    apres VACUUM = 32 pages, 0 libres
                                

Les pages de débordement
Une valeur trop grosse déborde sur une chaîne de pages, la cellule ne garde que le début et un pointeur

La freelist
Les pages libérées ne sont pas rendues au disque, elles sont chaînées et réutilisées

Le fichier ne rétrécit pas tout seul
120 pages libres sur 152 après un DELETE ; VACUUM réécrit la base et rend l'espace

PLUS RAPIDE QUE LE SYSTÈME DE FICHIERS

SQLite comme format de fichier applicatif

35 % plus rapide que fread et fwrite
Blobs de 10 Ko, 100 000 fichiers, sur Linux, macOS et Android ; jusqu'à 5 fois sur Windows 10

Moins d'appels système
Un seul open, des lectures groupées par page, un cache de pages

Un zip à 1 % près
Une archive SQLite compressée pèse autant qu'un zip, mais se met à jour sans tout réécrire

Un format de fichier applicatif
Documents monofichiers, transactions, requêtes, portabilité, accès concurrent

« Small. Fast. Reliable. Choose any three. »
Le slogan de la page d'accueil

UN MOTEUR NON TYPÉ

Le typage dynamique dans une base relationnelle

CLASSES DE STOCKAGE ET AFFINITÉS

Le type appartient à la valeur, pas à la colonne

Cinq classes de stockage
NULL, INTEGER, REAL, TEXT, BLOB : c'est la valeur qui porte son type

Cinq affinités de colonne
TEXT, NUMERIC, INTEGER, REAL, BLOB : une préférence, pas une contrainte

Des règles de nommage
Le type déclaré contient INT ? INTEGER. CHAR, CLOB ou TEXT ? TEXT. BLOB ou rien ? BLOB. REAL, FLOA ou DOUB ? REAL. Sinon NUMERIC

Comme Python ou JavaScript
Un typage dynamique là où les autres SGBD relationnels sont stricts

UNE CHAÎNE DANS UN ENTIER

Ça passe, et c'est voulu


                                    CREATE TABLE t(a INTEGER);
                                    INSERT INTO t VALUES ('hello'), (42), ('42'), (3.0);
                                    SELECT a, typeof(a) FROM t;
                                

                                      a    typeof(a)
                                    -----  ---------
                                    hello  text
                                       42  integer
                                       42  integer
                                        3  integer
                                

Aucune erreur
'hello' est stocké tel quel, '42' devient l'entier 42, 3.0 devient l'entier 3

La vérification revient à l'application
SQLite fait confiance à celui qui écrit

L'avantage : le stockage le plus compact
Chaque valeur est encodée selon ce qu'elle est, pas selon la colonne

STRICT tables, 3.37.0 (2021)
INT, INTEGER, REAL, TEXT, BLOB, ANY ; sinon erreur SQLITE_CONSTRAINT_DATATYPE

TRANSACTIONS

ACID avec un fichier et deux fsync

CINQ ÉTATS DE VERROU

Un seul écrivain à la fois

UNLOCKED
Personne ne lit ni n'écrit

SHARED
Lecture : autant de lecteurs qu'on veut, simultanément

RESERVED
Un processus prévoit d'écrire, un seul à la fois ; les lecteurs continuent

PENDING
Plus de nouveaux lecteurs : l'écrivain attend que les verrous SHARED se libèrent

EXCLUSIVE
Écriture : un seul verrou, aucun autre ne coexiste

Posés par le VFS
Verrous POSIX, verrous Windows ou fichiers dot-lock selon la plateforme

LE COMMIT ATOMIQUE

Le journal de rollback

Verrou SHARED puis RESERVED
Lire les pages nécessaires depuis le fichier

Créer le journal de rollback
Copie des pages d'origine dans le fichier -journal, puis modifications en mémoire

fsync du journal
Premier fsync : le contenu, puis l'en-tête avec le nombre de pages

Verrou EXCLUSIVE, écriture des pages
Les pages modifiées sont écrites dans le fichier de base

fsync de la base
Deuxième fsync

Supprimer le journal
C'est le point de commit : la suppression d'un fichier est atomique du point de vue du processus

Panne au milieu ?
Le « hot journal » est rejoué au prochain accès : la base revient à l'état d'avant

WAL

Write-Ahead Logging, depuis 3.7.0 (juillet 2010)

L'inverse du journal
On ajoute les pages modifiées au fichier -wal, la base reste intacte

Commit = un enregistrement dans le WAL
Écriture séquentielle, moins de fsync

Lecteurs et écrivain ne se bloquent plus
Chacun lit un instantané cohérent

Le wal-index
Fichier -shm en mémoire partagée : où trouver la dernière version de chaque page

Checkpoint
Recopie du WAL dans la base, automatique tous les 1000 pages (4 Mo)

Les limites
Tous les processus sur la même machine, pas de réseau ; PRAGMA journal_mode = WAL

VFS

Virtual File System, la couche de portabilité

Tout passage par l'OS traverse le VFS
Ouvrir, lire, écrire, verrouiller, fsync, l'heure, l'aléa

Trois objets
sqlite3_vfs, sqlite3_file, sqlite3_io_methods

Des VFS de série
unix, unix-excl, unix-none, unix-dotfile, win32, win32-longpath ...

Des shims empilables
vfstrace journalise les appels, test_vfs simule des pannes, quota, chiffrement

Le vôtre
sqlite3_vfs_register, ou dans l'URI : file:demo.db?vfs=unix-none

C'est ce qui fait tourner SQLite partout
os_unix.c et os_win.c de série, des VFS maison sur les systèmes exotiques

SAVEPOINTS ET TRANSACTIONS IMBRIQUÉES

Annuler une partie seulement


                                    BEGIN;
                                      UPDATE compte SET solde = solde - 30;
                                      SAVEPOINT virement;
                                        UPDATE compte SET solde = solde - 50;
                                      ROLLBACK TO virement;
                                      RELEASE virement;
                                    COMMIT;
                                

                                    solde au depart   : 100
                                    apres -30         : 70
                                    dans le savepoint : 20
                                    apres ROLLBACK TO : 70
                                    apres COMMIT      : 70
                                

Des points de reprise nommés
SAVEPOINT, ROLLBACK TO pour revenir en arrière, RELEASE pour valider

Imbriquables
Un savepoint hors transaction en ouvre une ; les savepoints s'empilent

L'opcode Savepoint
Celui aperçu dans la liste des 191 instructions du VDBE

Le journal de statement
SQLite pose un savepoint implicite autour de chaque instruction, pour pouvoir l'annuler seule en cas d'erreur

EXTENSIONS

Le mécanisme des tables virtuelles

TABLES VIRTUELLES

Du SQL sur n'importe quoi

Une table qui n'est pas dans le fichier
Chaque requête appelle vos callbacks : la structure sqlite3_module

Le planner négocie avec vous
xBestIndex reçoit les contraintes et annonce un coût ; xFilter, xNext, xColumn font le reste

Livrées avec SQLite
FTS5 (recherche plein texte), R-Tree (index spatial), json_each, dbstat, csv, generate_series

Des fonctions à valeur de table
Colonnes HIDDEN : SELECT value FROM generate_series(5, 50)

LES TESTS

Probablement le projet le plus testé au monde

PLUS DE TESTS QUE DE CODE

590 fois plus

testing.jpg

155 800 lignes de bibliothèque
Sans blancs ni commentaires (3.42.0, 2023)

92 millions de lignes de tests
92 053 KSLOC

Le ratio
Pour chaque ligne de code, 590 lignes de test

7519 assert() dans l'amalgamation 3.54.1
Actifs dans les builds de test, compilés hors production

TROIS HARNAIS ET DU FUZZING

Tester de quatre façons différentes

test-harness.jpg

TCL Tests
51 445 cas de test, des millions à l'exécution ; le harnais historique, open source

TH3 (Test Harness 3)
50 362 cas, 2,4 millions à l'exécution ; propriétaire, sous licence

SQL Logic Test
7,2 millions de requêtes comparées à PostgreSQL, MySQL, SQL Server et Oracle

dbsqlfuzz
Un milliard de mutations par jour, plus AFL et OSS-Fuzz de Google

100 % DE COVERAGE

L'exigence de l'avionique

avionic-harness.jpg

100 % de couverture de branches
Dans la configuration déployée, pas dans une configuration de test

100 % MC/DC
Modified Condition/Decision Coverage, atteint le 25 juillet 2009 après dix mois d'effort

À la demande d'avionneurs
TH3 a été conçu pour les exigences de la norme DO-178B

Mesuré avec gcov
Et des macros testcase(), ALWAYS(), NEVER() pour documenter les branches

TH3 tourne sur l'embarqué
Cross-compilé, transféré sur la cible, exécuté sans OS complet

COMMENT CORROMPRE UNE BASE SQLITE

La page howtocorrupt.html, petite leçon d'humilité

Écraser le fichier
Un autre thread ou processus qui écrit dedans, ou qui ferme le mauvais descripteur

Des verrous qui mentent
NFS et les systèmes de fichiers réseau

Des fsync qui mentent
Disques et OS qui répondent avant d'avoir écrit

Le matériel
Disques et mémoires flash défaillants

Votre application
Corruption mémoire, ou PRAGMA synchronous = OFF et journal_mode = OFF

Et en dernier, SQLite
Des bugs existent, rares et obscurs

CASSER POUR DURCIR

Les tests qu'on n'écrit jamais

musk-cybertruck.jpg

Manque de mémoire
malloc échoue à chaque point possible : pas de corruption, pas de fuite

Erreurs d'entrée-sortie
Disque plein, écriture échouée : injectées par un VFS de test

Crash et coupure de courant
Simulés au milieu des commits : la base doit se rétablir

Fichiers malformés
Bases corrompues volontairement, puis fuzzées

Valeurs limites
Chaque limite de limits.html est testée aux bornes

Et le reste
Valgrind, mutation testing, une checklist de 200 points avant chaque release

Chaque branche est testée
Même celle qui n'arrive jamais

POUR CONCLURE

270k lignes et des enseignements

UN PETIT CHEF-D'ŒUVRE

Et ce n'est pas un jouet

will-smith-just-because.jpg

Sobriété
Zéro dépendance, un fichier, une machine virtuelle de 191 opcodes

Rigueur
590 fois plus de tests que de code, 100 % MC/DC

Vision
Un format stable depuis 2004, promis jusqu'en 2050

Maîtrise
Une poignée de développeurs, une porte fermée, une roadmap tenue

Documentation
Chaque choix est expliqué sur sqlite.org, avec ses raisons

QUELQUES LEÇONS

Ce qu'on peut en tirer

le-pari-bien.jpg

Embrasser la simplicité
La complexité est un coût, pas une fierté

Tester ce qu'on livre
Dans la configuration livrée, jusqu'au else qui n'arrive jamais

La compatibilité est une feature
Un format et une API stables valent plus qu'une nouveauté

Savoir dire non
Pas de client-serveur, pas de PR, pas de réécriture : la maîtrise a un prix, et il est assumé

« Old and boring » n'est pas une insulte
Le C, Tcl, Fossil : des outils qu'on connaît et qu'on maîtrise

POUR ALLER PLUS LOIN

Tout est sur sqlite.org

sqlite-org-docs.png

La documentation
arch, fileformat2, whybytecode, atomiccommit, wal, testing, howtocorrupt : une mine d'informations

Le code source
sqlite.org/src, ou l'amalgamation : un C exemplaire, cohérent d'un bout à l'autre

Corecursive, épisode 66
Deux heures avec Richard Hipp

Ma vidéo
« SQLite, la base de données la plus folle ! », lien dans les références

A PROPOS DE MOI

Un peu de personal branding

OLIVIER PONCET

Retrouvez-moi sur les réseaux

ponceto.png
@ponceto91 emaxilde.net
@ponceto91 github.com/ponceto/
@ponceto91 gitlab.com/ponceto/
@ponceto91 bitbucket.org/ponceto/

qrcode.png

MERCI

Des questions ?