Bases de données, journaux et état

Qu'est-ce qui est vrai : le relevé ou le solde ?

Kofi ouvre l'historique de son compte de monnaie mobile : une liste d'opérations datées, et tout en haut un solde de 90 francs. Les deux informations sont exactes, mais elles ne sont pas de même nature. Le solde se déduit de la liste ; la liste ne se déduit pas du solde. Si on ne conservait que « 90 », on ne pourrait ni expliquer pourquoi, ni détecter une erreur, ni retrouver ce qui s'est passé hier. Cette asymétrie est l'idée de tout l'atelier.

Les mots

• Un événement est un fait qui s'est produit : « crédit de 100 pour Awa », « transfert de 30 d'Awa vers Kofi ». Il a un numéro d'ordre.
• Le journal (log) est la suite ordonnée des événements. Il est append-only : on ajoute à la fin, on ne modifie ni ne supprime les entrées passées.
• L'état est le résumé à un instant donné : les soldes, le contenu des comptes. Il est dérivé du journal.
• La projection (ou rejeu) est le calcul qui passe du journal à l'état : on part d'un état vide et on applique chaque événement dans l'ordre. En formule : état après l'événement k = règle(état après k - 1, événement k).

Un exemple suivi

Deux comptes démarrent à 0 (Awa, Kofi). Voici six événements, avec la règle « un débit ou un transfert qui rendrait un solde négatif est rejeté : sans effet, mais il reste dans le journal ».

L'état final est Awa = 50, Kofi = 90. Vérification de cohérence : crédits acceptés 100 + 50 + 10 = 160, débits acceptés 20, 160 - 20 = 140 = 50 + 90. Le transfert ne crée ni ne détruit de l'argent : il le déplace.

Pourquoi garder les deux ?

On peut donc jeter l'état et le recalculer, mais pas l'inverse. C'est la raison pour laquelle les systèmes qui doivent rendre des comptes (banques, registres, blockchains) traitent le journal comme la source de vérité et l'état comme un confort de lecture.

L'approche opposée, qui écrase la valeur en place (« mettre le solde à 90 »), ne conserve aucune trace : une erreur ou une fraude ne laisse rien à examiner.

Ce que cela ne garantit pas

• Un journal append-only n'est « en ajout seulement » que si le logiciel et les droits d'accès l'imposent. Quelqu'un qui peut écrire dans le fichier peut modifier le passé ; nous le verrons dans l'exercice de sécurité.
• Le journal peut contenir des événements faux (un crédit qui n'aurait pas dû avoir lieu). Rejouer reconstruit fidèlement ce qui y est écrit, pas ce qui est vrai dans le monde.
• Si un bogue fait diverger l'état du journal, c'est le journal qui fait foi : on rejoue.

À retenir

Journal = faits ordonnés, ajoutés à la fin. État = résumé dérivé, reconstructible. Un événement rejeté reste au journal. La fiabilité du journal repose sur ce qui l'empêche d'être modifié, pas sur le mot « append-only ».

Deux ordinateurs, un même journal, deux soldes différents ?

Awa et un auditeur reçoivent chacun une copie du même journal. Si leurs soldes finaux diffèrent, l'un des deux a fait une erreur — ou les règles n'étaient pas les mêmes. Pour que le rejeu serve de vérification, il faut qu'il soit déterministe : mêmes entrées, même sortie, partout et toujours. C'est ce qui permet à n'importe qui de recalculer l'état et d'obtenir le même résultat que tout le monde.

La règle d'application

Voici le cœur d'un rejeu, en Python :

def apply(state, event):
    kind, amount = event[0], event[-1]
    if amount <= 0:
        return False          # montants : entiers strictement positifs seulement
    if kind == "CREDIT":
        _, who, amount = event
        state[who] = state.get(who, 0) + amount
        return True
    if kind == "DEBIT":
        _, who, amount = event
        if state.get(who, 0) < amount:
            return False      # rejeté : aucun effet, reste au journal
        state[who] = state[who] - amount
        return True
    if kind == "TRANSFER":
        _, src, dst, amount = event
        if state.get(src, 0) < amount:
            return False
        state[src] = state[src] - amount
        state[dst] = state.get(dst, 0) + amount
        return True
    return False              # type inconnu : rejeté

def replay(log):
    state, rejected = {}, 0
    for event in log:
        if not apply(state, event):
            rejected += 1
    return state, rejected

Remarquez trois choses. La fonction ne regarde rien d'autre que l'état et l'événement. Le résultat « rejeté » n'est pas une exception : c'est une conséquence normale des règles, qui doit être la même à chaque rejeu. Et les montants sont des entiers strictement positifs (un montant nul, négatif ou un type d'événement inconnu est rejeté, sinon un CREDIT négatif ferait baisser un solde sous zéro) : le franc CFA n'a pas de sous-unité d'usage courant, donc 5 000 francs s'écrivent 5000 ; pour une monnaie à centimes, on stocke de même un entier de la plus petite unité. Avec des nombres à virgule, 0.1 + 0.2 vaut 0.30000000000000004 en Python : de petites erreurs d'arrondi s'accumulent et peuvent dépendre de l'ordre des opérations.

L'ordre fait partie des données

Prenons deux événements : A = DEBIT Awa 30 et B = CREDIT Awa 50, Awa démarrant à 0.

Les mêmes deux événements donnent des états différents selon l'ordre. Un journal est donc une suite numérotée, pas un ensemble : l'ordre est une donnée, au même titre que les montants. (Le consensus, que vous étudierez plus tard, est précisément la façon dont plusieurs machines s'accordent sur CET ordre.)

Ce qui rend un rejeu non déterministe

• Lire l'heure ou un nombre aléatoire dans la règle d'application ;
• utiliser des nombres à virgule ;
• dépendre de l'ordre d'itération d'une structure non ordonnée ;
• appliquer une version différente des règles à une partie du journal : les règles font partie de l'identité de l'état. Si l'on change la règle de rejet, un ancien journal ne donne plus les mêmes soldes.

Vérifier un état

Un état reconstruit se vérifie de deux façons. D'abord, en le recalculant depuis le journal et en comparant. Ensuite, par des invariants : des propriétés qui doivent toujours tenir. Ici, la somme des soldes est égale aux crédits acceptés moins les débits acceptés (un transfert ne la change pas), et aucun solde n'est négatif. Si un invariant est violé après un rejeu, il y a un bogue dans les règles ou une anomalie dans le journal.

Instantanés : éviter de tout rejouer

Rejouer un million d'événements pour lire un solde est lent. Un instantané (snapshot) est une copie de l'état après l'événement k. Pour obtenir l'état actuel, on repart de l'instantané et on ne rejoue que les événements k + 1, k + 2, … Avec un instantané après 900 000 événements dans un journal de 1 000 000, on rejoue 100 000 événements. L'instantané est un cache : il doit toujours pouvoir être comparé au rejeu complet (c'est l'objet du laboratoire autonome).

Ce que cela ne garantit pas

Rejouer prouve que l'état est cohérent avec le journal, pas que le journal est exact. Si un événement a été falsifié avant le rejeu, le rejeu reconstruit fidèlement le mensonge. Savoir que le journal n'a pas été modifié demande un mécanisme de plus (exercice de sécurité).

À retenir

Un rejeu est une fonction de (état, événement) vers un nouvel état, sans hasard ni horloge ; l'ordre des événements fait partie des données ; on compte en entiers ; on vérifie par recalcul et par invariants ; un instantané évite de tout rejouer.

Pourquoi pas simplement un fichier ?

On pourrait écrire le journal dans un fichier texte. Mais dès que plusieurs programmes lisent et écrivent, qu'il faut chercher vite et qu'une panne ne doit rien abîmer, on réinvente à la main ce que fournit une base de données : un stockage organisé, un langage de requêtes, des index et des garanties en cas de panne. SQLite est une base complète contenue dans un seul fichier, sans serveur à installer ; Python la pilote avec son module sqlite3.

Tables, lignes, requêtes

Une table est un tableau : chaque ligne est un enregistrement, chaque colonne un champ. Le langage SQL décrit ce qu'on veut sans dire comment le calculer.

CREATE TABLE events (
  id           INTEGER PRIMARY KEY AUTOINCREMENT,
  kind         TEXT    NOT NULL CHECK (kind IN ('CREDIT', 'DEBIT', 'TRANSFER')),
  account      TEXT    NOT NULL,   -- compte crédité (CREDIT), débité (DEBIT, TRANSFER)
  counterparty TEXT,               -- bénéficiaire, seulement pour TRANSFER
  amount       INTEGER NOT NULL CHECK (amount > 0)
);

INSERT INTO events (kind, account, amount) VALUES
  ('CREDIT', 'awa',  100),
  ('CREDIT', 'kofi',  50),
  ('DEBIT',  'awa',   30);

SELECT account,
       SUM(CASE kind WHEN 'CREDIT' THEN amount ELSE -amount END) AS balance
FROM events
WHERE kind IN ('CREDIT', 'DEBIT')
GROUP BY account;

Résultat de la dernière requête : awa | 70 et kofi | 50. C'est exactement la projection de la leçon 2, exprimée en SQL : le journal est la table events, le solde est un calcul sur elle. Les contraintes CHECK refusent d'office un type inconnu ou un montant nul ou négatif ; PRIMARY KEY AUTOINCREMENT donne à chaque ligne un numéro d'ordre croissant. Comme dans la leçon 1, un transfert est un événement (TRANSFER, avec le bénéficiaire dans counterparty) ; cette requête ne le compte pas (il faudrait débiter account et créditer counterparty), c'est pourquoi l'état est aussi gardé dans une table à part, plus bas.

Les index : réutiliser l'atelier 102

Chercher les événements d'un compte avec WHERE account = 'awa' sans index oblige à parcourir toute la table : O(n). Un index est une structure supplémentaire, maintenue par la base, qui retrouve les lignes en O(log n) : en SQLite, les tables et les index sont rangés dans des arbres B, les arbres équilibrés à nombreux enfants évoqués à l'atelier 102.

CREATE INDEX idx_events_account ON events (account);

Le prix : chaque insertion doit aussi mettre à jour l'index, et il occupe de la place. On indexe ce qu'on cherche souvent.

Garder l'état à côté du journal

On peut conserver, dans une seconde table, un état déjà calculé :

CREATE TABLE balances (
  account TEXT PRIMARY KEY,
  amount  INTEGER NOT NULL CHECK (amount >= 0)
);

La contrainte CHECK (amount >= 0) fait refuser par la base toute opération qui rendrait un solde négatif : le UPDATE fautif échoue, donc (leçon 4) toute la transaction est annulée. C'est un second garde-fou pour la règle de rejet. Lire un solde devient un accès par clé, O(log n) (ou O(1) en mémoire dans un dictionnaire).

Un journal qui refuse les modifications

On peut demander à SQLite d'interdire la modification et la suppression des lignes de events :

CREATE TRIGGER events_no_update BEFORE UPDATE ON events
BEGIN
  SELECT RAISE(ABORT, 'events is append-only');
END;

(Un déclencheur analogue BEFORE DELETE ferme l'autre porte.) C'est utile contre les erreurs et les bogues. Mais quelqu'un qui contrôle le fichier ou les droits d'administration peut supprimer le déclencheur ou réécrire le fichier : ce n'est pas une garantie cryptographique.

Ce que cela ne garantit pas

• Une base de données n'est pas « vraie » : elle conserve ce qu'on lui a donné, y compris des erreurs.
• Un index accélère certaines recherches et ralentit les écritures ; sans mesure (atelier 102), on ne sait pas s'il vaut son coût.
• SQL n'est pas magique : la requête de solde ci-dessus n'applique aucune règle métier.

À retenir

Table = journal ; requête = projection ; index = arbre qui accélère la recherche ; contraintes et déclencheurs = garde-fous, pas preuves. Les règles du registre se vérifient à l'ajout ou au rejeu.

Le transfert qui disparaît

Awa envoie 5 000 francs à Kofi. Dans notre registre, c'est un événement (TRANSFER), mais il demande trois écritures dans la base : ajouter l'événement au journal, retirer 5 000 du solde d'Awa, ajouter 5 000 au solde de Kofi. Le programme écrit les deux premières… et la batterie lâche. Au redémarrage, Awa a perdu 5 000 francs que Kofi n'a jamais reçus : l'argent a été détruit. (Dans l'autre sens, avec le crédit de Kofi écrit sans le débit d'Awa, il aurait été créé.) Le problème n'est pas une erreur de calcul, c'est que des écritures qui devaient aller ensemble ont été séparées.

Atomicité : tout ou rien

Une transaction regroupe plusieurs opérations en une seule unité atomique : toutes sont appliquées, ou aucune. Il n'existe pas de résultat intermédiaire visible après une panne.

BEGIN;
INSERT INTO events (kind, account, counterparty, amount) VALUES ('TRANSFER', 'awa', 'kofi', 5000);
UPDATE balances SET amount = amount - 5000 WHERE account = 'awa';
UPDATE balances SET amount = amount + 5000 WHERE account = 'kofi';
COMMIT;

Tant que COMMIT n'a pas réussi, rien n'est définitivement écrit ; en cas d'erreur, ROLLBACK (ou la panne elle-même) annule tout. Si Awa n'avait que 3 000 francs, la contrainte CHECK (amount >= 0) de la table balances ferait échouer le premier UPDATE : la transaction entière serait annulée, et le transfert refusé ne serait écrit nulle part, ni dans events ni dans balances.

La règle se vérifie dans la transaction

La règle « pas de solde négatif » doit être vérifiée au moment de l'ajout, dans la même transaction que les écritures. Sinon, deux demandes simultanées peuvent lire le même solde avant que l'une des deux n'écrive, et dépenser deux fois la même somme. Voici le code complet en Python :

import sqlite3
# isolation_level=None : nous écrivons nous-mêmes BEGIN / COMMIT / ROLLBACK
conn = sqlite3.connect("ledger.db", isolation_level=None)

def transfer(conn, src, dst, amount):
    if amount <= 0:
        raise ValueError("montant invalide")
    conn.execute("BEGIN IMMEDIATE")   # verrou d'écriture pris AVANT de lire le solde
    try:
        row = conn.execute("SELECT amount FROM balances WHERE account = ?", (src,)).fetchone()
        if row is None or row[0] < amount:
            conn.execute("ROLLBACK")
            return False              # refusé : rien n'est écrit
        conn.execute("INSERT INTO events (kind, account, counterparty, amount) "
                     "VALUES ('TRANSFER', ?, ?, ?)", (src, dst, amount))
        conn.execute("UPDATE balances SET amount = amount - ? WHERE account = ?", (amount, src))
        cur = conn.execute("UPDATE balances SET amount = amount + ? WHERE account = ?", (amount, dst))
        if cur.rowcount != 1:
            raise ValueError("compte destinataire inconnu")   # sinon l'argent disparaîtrait
        conn.execute("COMMIT")
        return True
    except Exception:
        conn.execute("ROLLBACK")      # annule les trois écritures
        raise

BEGIN IMMEDIATE prend le verrou d'écriture de SQLite avant la lecture du solde : un second transfert simultané attend, ou échoue avec une erreur de base verrouillée, au lieu de lire le même solde en même temps. Cette question d'isolation est l'une des lettres d'ACID, citée plus bas pour mémoire.

Python offre aussi un raccourci : avec le mode par défaut du module sqlite3 (connexion ouverte sans isolation_level=None), un bloc with conn: valide la transaction si le bloc se termine bien et l'annule si une exception en sort (il ne ferme pas la connexion).

conn = sqlite3.connect("ledger.db")
with conn:    # valide si le bloc se termine bien, annule si une exception en sort
    conn.execute("INSERT INTO events (kind, account, counterparty, amount) VALUES ('TRANSFER', 'awa', 'kofi', 5000)")
    conn.execute("UPDATE balances SET amount = amount - 5000 WHERE account = 'awa'")
    conn.execute("UPDATE balances SET amount = amount + 5000 WHERE account = 'kofi'")

Ce raccourci ne vérifie pas le solde : la règle de rejet reste à écrire dans le bloc.

Durabilité : ce qui est validé survit

Une fois que COMMIT a répondu « réussi », les données survivent à une coupure de courant ou à un plantage du programme. Concrètement, avec les réglages par défaut, SQLite consigne d'abord dans un fichier de reprise de quoi défaire la transaction (le rollback journal garde l'ancien contenu des pages modifiées) ou la refaire (le fichier WAL, write-ahead log, ajoute le nouveau contenu), force ce fichier à atteindre le disque (opération dite fsync), et seulement alors annonce la réussite. Au redémarrage, la base lit ce fichier et remet les choses dans un état où chaque transaction est soit entière, soit absente.

Que trouve-t-on après une panne ?

La ligne du milieu est l'atomicité ; la dernière est la durabilité.

Le coût de la durabilité

Attendre que le disque confirme prend du temps : chaque validation durable est coûteuse. Grouper beaucoup d'écritures dans une seule transaction est donc souvent bien plus rapide que de valider chaque ligne séparément (à vérifier par mesure, comme à l'atelier 102). SQLite permet de régler ce compromis avec PRAGMA synchronous ; en le baissant, on gagne en vitesse mais on accepte qu'une coupure de courant puisse faire perdre des validations récentes ; selon le mode choisi, la base elle-même peut même être abîmée. Les bons réglages dépendent de ce que coûte une perte.

Les autres lettres d'ACID

On résume souvent ces garanties par l'acronyme ACID : Atomicité, Cohérence, Isolation, Durabilité. La cohérence (les règles de la base, comme CHECK, restent vraies) et l'isolation (des transactions simultanées ne se gênent pas) sont citées ici pour mémoire ; elles ne font pas partie de cet atelier.

Ce que cela ne garantit pas

• Durable ne veut pas dire sauvegardé. Si le disque meurt, la base meurt avec lui. Pour survivre à cela, il faut des copies ailleurs.
• L'atomicité vaut à l'intérieur d'une base. Si le débit est dans la base de votre opérateur et le crédit dans celle d'une autre banque, aucune transaction SQLite ne les unit : il faut des protocoles de coordination, que vous rencontrerez avec les systèmes distribués.
• Une transaction atomique peut contenir une règle métier fausse : elle garantit que le résultat est écrit en entier, pas qu'il est juste.
• La durabilité suppose que le matériel respecte les demandes d'écriture ; certains disques mentent sur ce point.

À retenir

Atomicité : un groupe d'écritures est appliqué en entier ou pas du tout. Durabilité : une validation réussie survit à une panne, grâce à un fichier de reprise écrit avant la réponse. Ni l'une ni l'autre ne protège d'un disque détruit, d'une règle erronée, ni d'un journal falsifié par quelqu'un qui contrôle la base.