Rendre l'index durable
Un index qui vit dans la RAM disparaît au redémarrage. Comment l'écrire sur disque une fois pour toutes, sans jamais le corrompre, même si le courant saute en pleine insertion ?
Au chapitre précédent, on a gagné le droit de faire confiance à un index : l’oracle différentiel certifie qu’il retrouve vraiment les voisins qu’il prétend rendre. Mais cet index, soigneusement construit et vérifié, vit dans la RAM. Et la RAM s’efface au moindre redémarrage. Rebâtir un index de plusieurs millions de vecteurs prend des heures de calcul. La question de ce chapitre est donc terre à terre, et pourtant elle décide de la survie du moteur : comment écris-tu cet index sur disque une fois pour toutes, le relis intact, et survis à une coupure de courant survenue en pleine écriture ?
C’est un changement de monde. Jusqu’ici on raisonnait en géométrie, en distances, en rappel. Maintenant on raisonne en octets, en pannes, en garanties. Et on va découvrir une menace sournoise, cousine directe de celle du chapitre 5 : un index sauvegardé peut se relire sans la moindre erreur apparente, et mentir quand même sur son contenu.
Un index qui ne survit pas au redémarrage
Un index en mémoire est volatil par nature. Coupe l’alimentation, tue le processus, redémarre la machine : tout est perdu. Pour qu’un état survive, il faut le rendre durable Durabilité Garantie qu'une donnée, une fois confirmée comme écrite, survit aux redémarrages et aux pannes. C'est le D de l'acronyme ACID. Pour un index en mémoire, la durabilité n'est pas acquise : il faut explicitement écrire l'état sur un support persistant et forcer son passage sur le disque physique. Une écriture qui n'a pas été rendue durable peut disparaître au prochain incident, comme si elle n'avait jamais eu lieu. , c’est-à-dire l’écrire sur un support qui garde sa valeur sans courant (un disque, un SSD) et s’assurer que l’écriture a vraiment atteint ce support.
On pourrait croire que c’est trivial : il suffit d’ouvrir un fichier et d’y déverser l’index. C’est exactement là que se cache le piège. Écrire des données prend du temps, et pendant ce temps, n’importe quoi peut arriver. La machine peut tomber au milieu de l’opération. Et une écriture interrompue ne laisse pas un fichier vide bien propre : elle laisse un fichier à moitié écrit.
Le vrai danger : l’écriture partielle
Imagine que ton index occupe dix blocs sur le disque. Tu lances la sauvegarde, qui réécrit ces dix blocs un par un. La machine s’éteint après le sixième. Sur le disque, tu as maintenant six blocs neufs et quatre blocs anciens, soudés dans le même fichier. C’est une écriture partielle Écriture partielle Écriture interrompue en plein vol (coupure de courant, plantage, processus tué) qui laisse un fichier à moitié ancien, à moitié neuf. Le danger n'est pas la perte : c'est la corruption silencieuse, car le fichier mélangé s'ouvre souvent sans erreur et se parse en partie, mentant sur son contenu. En anglais : torn write. C'est la menace centrale que toute stratégie de persistance sérieuse doit neutraliser. , et c’est le cauchemar de toute persistance.
Le piège n’est pas la perte de données. La perte, on sait la gérer : il suffit de tout reconstruire. Le piège, c’est la corruption silencieuse. Ce fichier hybride s’ouvre sans erreur. Son en-tête est cohérent, ses premiers enregistrements se lisent parfaitement. Il a l’air valide. Mais ses pointeurs internes traversent la frontière entre l’ancien et le neuf, et l’index qu’on relit est un monstre incohérent qui renverra des voisins absurdes sans jamais lever d’exception.
Tu reconnais le motif. Au chapitre 5, un index pouvait passer tous ses tests locaux tout en s’effondrant en qualité. Ici, un fichier peut passer tous ses contrôles d’ouverture tout en étant structurellement pourri. La même leçon, transposée : ce qui a l’air correct en surface peut être faux en profondeur.
Quatre stratégies pour écrire sans se déchirer
Face à l’écriture partielle, l’ingénierie a inventé plusieurs parades. En voici quatre, plus la naïve qui sert de contre-exemple. Chacune fait un compromis différent entre sûreté, coût d’écriture, vitesse de relecture et fraîcheur des données.
L’écrasement en place est la stratégie naïve : on réécrit le fichier final directement. Rapide et simple, mais c’est précisément celle qui se déchire. Les quatre autres la corrigent, chacune à sa façon.
L’ écriture atomique Écriture atomique Écriture qui se produit entièrement ou pas du tout : aucun état intermédiaire n'est jamais observable, même en cas de panne au pire moment. C'est le A de ACID (atomicité). Une écriture atomique transforme la question « le fichier est-il à moitié écrit ? » en une impossibilité : à la relecture, on retrouve soit l'ancien état complet, soit le nouveau complet, jamais un mélange. par échange de nom écrit le nouvel index dans un fichier temporaire, à côté, sans toucher à l’original ; une fois le temporaire complet et forcé sur disque, un renommage le publie d’un coup. L’instantané fait pareil avec une photo complète et périodique de l’état. Le journal append-only ne réécrit jamais rien : il ajoute chaque changement à la fin d’un fichier, si bien qu’une panne ne peut abîmer que le dernier enregistrement, qu’on tronque à la relecture. Le fichier mappé en mémoire laisse le système d’exploitation gérer le va-et-vient entre mémoire et disque, élégant mais dont la durabilité dépend du moment où le système décide d’écrire ses pages.
La clé : l’atomicité par échange de nom
De ces quatre parades, une mérite qu’on s’y arrête, car c’est la plus universelle et la plus enseignante : l’échange de nom atomique. Son idée tient en trois temps.
D’abord, on écrit la totalité du nouvel index dans un fichier temporaire, distinct du fichier officiel. Pendant tout ce temps, le fichier officiel reste l’ancien index, complet et intact : si la machine tombe ici, on perd juste le temporaire à moitié écrit, sans conséquence. Ensuite, on appelle fsync fsync Appel système qui force le passage des données d'un fichier depuis les caches volatils (mémoire de l'application, cache du système d'exploitation) jusqu'au support physique durable. Tant que fsync n'a pas rendu la main, une écriture peut n'exister que dans un cache que la panne effacera. C'est la barrière qui transforme une écriture apparente en écriture durable, et l'étape qu'on oublie le plus souvent dans le motif d'échange de nom atomique. sur le temporaire pour garantir qu’il est vraiment sur le disque, et pas seulement dans un cache que la panne effacerait. Enfin, on renomme le temporaire par-dessus l’officiel.
Ce dernier geste est le secret. Au niveau du système de fichiers, le renommage est atomique : il n’existe aucun instant où le nom de l’index pointe sur un fichier à moitié remplacé. À tout moment, il désigne soit l’ancien fichier entier, soit le nouveau entier. Le « à moitié » est rendu impossible par construction.
C’est ce que font, sous le capot, les éditeurs de texte qui ne corrompent jamais ton fichier, les bases de données embarquées, et la plupart des outils sérieux. La même technique transforme une écriture dangereuse en une transition tout-ou-rien.
Relire et exiger l’identique : l’oracle de round-trip
Supposons l’index correctement écrit, sans aucun crash. Es-tu tranquille ? Pas encore. Il reste une seconde façon de mentir, et elle n’a rien à voir avec les pannes : la sérialisation elle-même peut trahir.
Sérialiser, c’est transformer une structure en mémoire en une suite d’octets pour le disque. Désérialiser, c’est l’inverse. On aimerait que ces deux opérations soient exactement réciproques : relire ce qu’on vient d’écrire doit redonner l’état de départ, à l’octet près. Mais c’est facile à casser. Un vecteur de flottants écrit avec trop peu de précision revient arrondi, donc différent. Un ensemble de voisins écrit dans un ordre instable revient dans un ordre changé, donc des octets différents d’une écriture à l’autre.
D’où le test de round-trip Test de round-trip Test qui sérialise une structure, la relit depuis sa forme persistée, et exige que le résultat soit identique à l'original. C'est l'oracle différentiel du chapitre 5 transposé à la persistance : la référence est l'état en mémoire, la version testée est ce qu'on relit du disque. Un contrôle logique (mêmes éléments) peut rester vert pendant qu'une comparaison octet pour octet attrape une corruption silencieuse, comme un arrondi de flottants ou un ordre d'écriture instable. : on sérialise l’état, on le relit, et on exige que le résultat soit identique à l’original. C’est, mot pour mot, l’oracle différentiel du chapitre 5, transposé à la persistance. La référence n’est plus l’index exact lent, c’est l’état en mémoire. La version testée n’est plus l’index approché, c’est ce qu’on relit du disque.
Et le piège du chapitre 5 revient lui aussi. Un contrôle logique, qui vérifie qu’on a bien les mêmes nœuds et les mêmes ensembles de voisins, reste vert même quand l’ordre des voisins a changé : logiquement, c’est pareil. Seule une comparaison octet pour octet contre une référence canonique attrape cette instabilité. Le contrôle logique est aveugle là où l’oracle strict voit. Propriété locale contre vérité globale, encore une fois.
À toi de planter la machine
Le composant ci-dessous réunit les deux dangers du chapitre. En haut, choisis une stratégie de persistance et glisse l’instant du crash le long du plan d’écriture : observe ce que la relecture récupère selon où tombe la machine. En bas, l’oracle de round-trip : active les bugs de sérialisation et regarde le contrôle logique rester vert pendant que la comparaison octet pour octet vire au rouge.
Stratégie de persistance
Planter la machine
Glisse pour couper le courant après N opérations exécutées.
Plan d'écriture
- écrire le bloc 0 dans l'indexnon atteinte
- écrire le bloc 1 dans l'indexnon atteinte
- écrire le bloc 2 dans l'indexnon atteinte
- écrire le bloc 3 dans l'indexnon atteinte
- écrire le bloc 4 dans l'indexnon atteinte
- écrire le bloc 5 dans l'indexnon atteinte
- écrire le bloc 6 dans l'indexnon atteinte
- fsync : forcer l'index sur le disquenon atteinte
Après redémarrage
Ancien index intact : écriture perdue, mais cohérent
Index relu : 4 nœuds
Oracle de round-trip
Sérialiser, relire, comparer à l'état en mémoire.
- Contrôle logique (mêmes ensembles)vert
- Oracle octet pour octetvert
Le contrôle logique reste vert là où l'oracle octet pour octet voit la corruption.
Trois questions à te poser en jouant :
- Choisis l’écrasement en place et place le crash au milieu. Quel verdict ? Recommence avec l’échange de nom atomique au même endroit. Pourquoi l’un se déchire-t-il et pas l’autre ?
- Avec le journal append-only, déplace le crash enregistrement par enregistrement. Vois-tu jamais « corrompu » apparaître ? Que récupère-t-on à la place ?
- Dans l’oracle, active l’ordre de voisins instable seul. Le contrôle logique vire-t-il au rouge ? Et l’oracle octet pour octet ? Lequel des deux aurait laissé passer le bug en production ?
Exercices
En une phrase
Un index en mémoire ne devient durable qu’écrit sur disque, et l’écrire naïvement par-dessus l’ancien fichier l’expose à l’écriture partielle, une corruption silencieuse qu’on neutralise par l’atomicité (écrire à côté puis renommer d’un coup, ou n’ajouter qu’en fin de journal) ; et comme au chapitre 5, seul un oracle de round-trip octet pour octet, et non un simple contrôle logique, garantit que ce qu’on relit est exactement ce qu’on avait en mémoire.
1. Pourquoi une écriture partielle est-elle plus dangereuse qu'une simple perte de données ?
2. En quoi l'échange de nom atomique évite-t-il l'écriture partielle ?
3. Un bug écrit les voisins dans un ordre instable. Quel contrôle l'attrape ?
Vers le chapitre 7
L’index est maintenant durable et vérifié : il survit aux redémarrages et on sait prouver qu’on le relit fidèlement. Mais il lui manque encore quelque chose. Toute la recherche qu’on a bâtie repose sur le SENS, capté par les vecteurs. Or il y a des requêtes où le sens ne suffit pas : un numéro de référence exact, un nom propre rare, un mot-clé qui doit apparaître tel quel. La recherche vectorielle, brillante sur les paraphrases, peut passer à côté d’une correspondance littérale évidente. Le chapitre 7 marie donc nos vecteurs au monde lexical, celui des mots exacts à la BM25, pour bâtir une recherche hybride qui cherche à la fois par le sens et par la lettre.
Sources
- Haerder, T. & Reuter, A. (1983). « Principles of Transaction-Oriented Database Recovery. » ACM Computing Surveys 15(4), 287-317. DOI 10.1145/289.291
- Pillai, T. S., Chidambaram, V., Alagappan, R., Al-Kiswany, S., Arpaci-Dusseau, A. C. & Arpaci-Dusseau, R. H. (2014). « All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications. » OSDI. USENIX
- O’Neil, P., Cheng, E., Gawlick, D. & O’Neil, E. (1996). « The Log-Structured Merge-Tree (LSM-Tree). » Acta Informatica 33(4), 351-385. DOI 10.1007/s002360050048
Pour aller plus loin
- Documentation de redb, magasin clé-valeur transactionnel embarqué en Rust : redb.org