1. Introduction : le champ de mines caché derrière l’ajout d’un seul bloc de 4 Ko

Lorsque vous appuyez sur Ctrl+S dans un éditeur de texte ou validez un virement bancaire, votre application émet un appel système write(). Du point de vue du développeur, la sauvegarde semble être une opération unique, instantanée et indivisible.

Mais sous le capot du noyau du système d’exploitation, du système de fichiers, du moteur de base de données et du contrôleur SSD se cache l’un des problèmes les plus redoutables de l’informatique : le problème de la cohérence après crash (Crash Consistency Problem).

Prenons l’opération la plus élémentaire possible dans un système de fichiers UNIX classique (tel que UFS ou ext2) : ajouter un nouveau bloc de données de $4\,\text{Ko}$ ($D_{\text{new}}$) à la fin d’un fichier existant. Même cette opération triviale nécessite la mise à jour d’au moins trois structures physiquement séparées sur le disque :

1. La table de bits des données (Data Bitmap $B$) : basculer le bit du bloc physique $k$ de $0$ (libre) à $1$ (alloué).
2. L’inode ($I$) : mettre à jour les métadonnées du fichier (taille size, horodatage mtime et pointeur vers l’adresse physique du bloc $k$).
3. Le bloc de données ($D_{\text{new}}$) : écrire les $4\,\text{Ko}$ effectifs de l’utilisateur dans le secteur physique $k$.

Or, la mémoire vive (DRAM) est rapide mais volatile, tandis que les disques et SSD NAND sont non volatils mais incapables de mettre à jour simultanément trois blocs distants $(B, I, D_{\text{new}})$ en une seule opération physique atomique. Si une coupure de courant survient au milieu de ces trois écritures ($2^3 - 2 = 6$ états d’écriture partielle), le système de fichiers se réveille dans un état d’incohérence critique :

2. Pourquoi les écritures n’arrivent pas sur le disque dans l’ordre du programme

Dans une architecture moderne, l’ordre chronologique des appels write() ne correspond presque jamais à l’ordre d’écriture physique sur le support non volatil en raison de quatre couches de mise en mémoire tampon et de réordonnancement (Reordering) :

  flowchart TD
    APP["1. Espace utilisateur<br/>Tampons d'exécution (stdio fwrite) / Buffer Pool SGBD"]
    PC["2. Cache de pages du noyau OS (Dirty DRAM Pages)<br/>Write-Back Caching : fusionne et retarde les écritures pendant plusieurs secondes"]
    SCHED["3. Couche bloc OS & Ordonnanceur d'E/S (mq-deadline / BFQ)<br/>Trie les requêtes par adresse LBA pour minimiser les déplacements"]
    DEV["4. Cache DRAM volatile embarqué du disque & Files NCQ/NVMe<br/>Le contrôleur FTL du SSD réordonne les écritures sur les canaux NAND"]
    MEDIA[("5. Support physique non volatil<br/>Cellules Flash NAND / Plateaux magnétiques (Seul niveau résistant aux coupures !)")]

    APP -->|"Appel système write()"| PC
    PC -->|"Flush arrière-plan / fsync()"| SCHED
    SCHED -->|"Commandes NVMe / SATA"| DEV
    DEV -->|"Barrière FLUSH CACHE / FUA"| MEDIA

Pour garantir l’ordre et la persistance, le système doit émettre des barrières matérielles explicites (NVMe Flush, SATA FLUSH CACHE EXT ou bit FUA: Force Unit Access) forçant le disque à vider son propre tampon DRAM volatile vers les cellules NAND.

3. Génération 1 : Mises à jour sur place, fsck et Soft Updates

1. fsck (File System Consistency Check) et le mur de passage à l’échelle : Les premiers systèmes UNIX (FFS, ext2) réparaient les incohérences après un crash en parcourant l’intégralité des inodes, bitmaps et répertoires avant le montage (fsck). Comme sa complexité dépend de la capacité totale du disque $O(N_{\text{disk}})$, vérifier un volume moderne de plusieurs téraoctets prend des heures ou des jours, même si un seul bloc de $4\,\text{Ko}$ était en cours d’écriture !
2. Soft Updates (Ganger & McKusick 1994) : Adopté par FreeBSD UFS, ce mécanisme évitait la journalisation en suivant finement les dépendances entre pointeurs en mémoire et en brisant les dépendances cycliques par des opérations temporaires de roll-back et roll-forward en RAM avant l’écriture disque.

4. Le pilier du stockage moderne : Write-Ahead Logging (WAL) et Journalisation

Pour réduire le temps de récupération de $O(N_{\text{disk}})$ au seul volume des transactions actives au moment du crash $O(N_{\text{active}})$ (quelques millisecondes !), les systèmes de fichiers (ext3/ext4, XFS, NTFS) et les bases de données utilisent la journalisation (Write-Ahead Logging, WAL / Journaling) :

1. Journal Write : avant de toucher aux emplacements définitifs (Home Locations), le système ajoute séquentiellement dans le Journal un bloc descripteur de début TxB (avec l’identifiant TID) suivi des blocs modifiés $(I, B, D_{\text{new}})$.
2. Journal Commit (Point de validation atomique) : après une barrière matérielle de vidage cache, le système écrit un unique bloc de fin TxE (Transaction End). L’écriture de cet unique secteur TxE bascule atomiquement toute la transaction dans l’état validé !
3. Checkpoint : une fois TxE sur disque, les blocs $(I, B, D_{\text{new}})$ sont copiés de manière asynchrone vers leurs emplacements définitifs.

  flowchart LR
    subgraph Journal ["Journal circulaire sur disque (Ajout séquentiel)"]
        TXB["1. TxB (TID=42)<br/>Descripteur"] --> JB["2. Bitmap B journalisé"]
        JB --> JI["3. Inode I journalisé"]
        JI --> JD["4. Données D_new journalisées"]
        JD ==>|"★Barrière matérielle FLUSH"| TXE["5. TxE (TID=42)<br/>Bloc Commit atomique"]
    end

    subgraph Home ["Emplacements définitifs (Home Locations)"]
        HB["Bitmap définitif"]
        HI["Table d'inodes définitive"]
        HD["Bloc de données définitif"]
    end

    TXE ==>|"6. Checkpoint (Écriture asynchrone)"| HB
    TXE ==>|"6. Checkpoint"| HI
    TXE ==>|"6. Checkpoint"| HD

• Coupure AVANT TxE : les emplacements définitifs sont intacts ; au redémarrage, la transaction incomplète est simplement ignorée.
• Coupure APRÈS TxE : au redémarrage, le gestionnaire de reprise rejoue (Redo replay, opération idempotente) les blocs du journal vers leurs emplacements définitifs en quelques millisecondes. ext4 optimise encore ce processus grâce aux sommes de contrôle du journal (CRC32C) intégrées dans TxE.

Pour éviter de doubler le volume d’écriture ($2\times$ Write Amplification), le mode par défaut data=ordered d’ext4 ne journalise que les métadonnées $(I, B)$, mais impose que le bloc de données $D_{\text{new}}$ soit intégralement écrit à son emplacement définitif AVANT que le bloc de validation TxE des métadonnées ne soit écrit dans le journal. Dans les SGBD relationnels, l’algorithme ARIES (Mohan et al., 1992) gère la politique Steal / No-Force via les numéros pageLSN et trois phases : Analysis, Redo (Repeating History) et Undo (avec Compensation Log Records, CLRs).

5. Génération 3 : Copy-on-Write (CoW) et arbres de Merkle (ZFS / Btrfs)

Les systèmes de fichiers de nouvelle génération (ZFS, Btrfs, APFS) interdisent toute réécriture sur place (In-Place Overwrite) grâce au Copy-on-Write (CoW / Shadow Paging) :

1. Tout bloc de données modifié $D_{2,\text{new}}$ et son inode parent $I_{v2}$ sont écrits dans de nouveaux blocs libres, laissant les anciens blocs $D_{2,\text{old}}$ totalement intacts.
2. Une fois toute la nouvelle branche persistée sur disque, une seule écriture atomique met à jour le bloc racine (Uberblock dans ZFS) de $U_1$ vers $U_2$.
3. Avantages : récupération instantanée en $0$ seconde sans rejeu de journal, instantanés (Snapshots) en $O(1)$ sans copie, et auto-guérison (Self-Healing) contre la corruption silencieuse (Bit Rot) grâce aux arbres de Merkle intégrant des empreintes cryptographiques de 256 bits dans chaque pointeur parent.

6. Les pièges de fsync() pour les développeurs et les tests par injection de fautes

Même sur un système journalisé ou CoW, remplacer un fichier par rename("config.json.tmp", "config.json") sans appeler fsync() au préalable produit des fichiers vides de $0$ octet après une coupure de courant sous Delayed Allocation (ext4), car le renommage des métadonnées est validé avant l’écriture des pages de données !

Le protocole complet en 6 étapes pour une sauvegarde atomique résistante aux crashs est : (1) write() dans le fichier temporaire $\to$ (2) fsync(fd) sur le fichier temporaire $\to$ (3) close(fd) $\to$ (4) rename() atomique $\to$ (5) ouverture du répertoire parent et fsync(dir_fd) pour persister l’entrée de répertoire $\to$ (6) close(dir_fd).

Comme l’a révélé le scandale PostgreSQL fsyncgate en 2018 (où le noyau Linux marquait une page sale comme Clean après une erreur d’E/S EIO lors d’un fsync(), corrigé depuis par errseq_t), la validation des systèmes de stockage modernes repose désormais sur des outils d’injection systématique de fautes tels qu’ALICE et CrashMonkey, qui explorent toutes les permutations de réordonnancement matériel face aux coupures de courant.