Concevoir un moteur de synchronisation par fusion à trois voies pour un CMS local-first en Rust

Ferrum CMS est un CMS local-first, piloté par fichiers, que je construis en Rust. Chaque élément de contenu vit sous forme de fichier sur le disque, des schémas décrivent ce que ces fichiers peuvent contenir, et une CLI maintient synchronisées les copies du dossier de contenu. Le scénario auquel la synchronisation doit survivre est banal : un rédacteur écrit sur un ordinateur portable, parfois sans aucun réseau, et pousse ses changements plus tard vers une copie partagée. Le même après-midi, un autre rédacteur a fait la même chose sur le même document. Deux versions du même dossier prétendent désormais toutes les deux avoir raison.

La réponse évidente est « le dernier qui écrit gagne », et elle est mauvaise pour un CMS, parce que l'écriture qui perd est l'après-midi de travail de quelqu'un. La réponse un peu moins évidente est un diff à deux voies entre la copie locale et la copie distante, et elle échoue pour une raison plus subtile : sans savoir d'où les deux copies sont parties, le moteur ne peut pas distinguer une suppression d'un ajout. Le moteur de synchronisation de Ferrum répond par une fusion à trois voies. Cet article parcourt une façon de concevoir ce genre de moteur sur du contenu structuré, avec des conflits qui en sortent comme des valeurs ordinaires que l'on peut inspecter.

Pourquoi la fusion a besoin d'un ancêtre commun

Prenez un document avec un champ tags. En local, il contient ["rust"] ; à distance, il contient ["rust", "cms"]. Un diff à deux voies voit une différence et doit deviner. Le rédacteur local a-t-il retiré cms, ou le rédacteur distant l'a-t-il ajouté ? Les deux explications cadrent avec les faits. La seule façon de trancher est la troisième version, celle dont les deux copies sont parties. Si la base contenait déjà cms, le rédacteur local l'a retiré et la fusion doit le retirer aussi. Si la base ne le contenait pas, le rédacteur distant l'a ajouté et la fusion doit le garder. Mêmes données, décisions opposées.

Le moteur travaille donc avec trois entrées par document : base, locale et distante. La base est l'instantané pris la dernière fois que ce document s'est synchronisé avec succès. Une façon simple de le conserver est un dossier caché à côté du contenu, indexé par chemin de document, où l'instantané est remplacé après chaque synchronisation réussie. Git trouve le même genre d'ancêtre en remontant son historique jusqu'à la base de fusion ; un moteur de synchronisation sans cet historique en a besoin par document.

L'emplacement de la copie distante est une question de transport, et le moteur de fusion s'en moque. Il reçoit trois valeurs optionnelles, puisqu'un document peut manquer de n'importe quel côté, et renvoie un résultat. Réseau, authentification et nouvelles tentatives relèvent d'un autre module.

TOML pour les schémas, JSON pour le contenu

Ferrum garde les schémas en TOML et le contenu en JSON, et ce partage a sa logique. Un schéma est écrit et lu par une personne, et TOML s'y prête : des commentaires, des tables, et une syntaxe qui ne punit pas une virgule oubliée. Un document de contenu est écrit par un rédacteur ou par une CLI et lu par le moteur de fusion, et JSON s'y prête : un seul modèle d'arbre, aucune ambiguïté sur les types, et une correspondance directe avec un serde_json::Value que le moteur peut parcourir.

Voici une paire illustrative, écrite pour cet article et non tirée de Ferrum : un schéma, puis un document qu'il accepte.

# Schéma illustratif écrit pour cet article (schemas/post.toml)
name = "post"
 
[fields.title]
type = "string"
required = true
 
[fields.tags]
type = "list"
of = "string"
 
[fields.blocks]
type = "list"
of = "block"
key = "id"

{
  "blocks": [
    { "id": "b1", "kind": "paragraph", "text": "Why the merge needs a base." },
    { "id": "b2", "kind": "code", "lang": "rust", "text": "fn main() {}" }
  ],
  "tags": ["rust", "cms"],
  "title": "Why three versions"
}

La ligne key = "id" compte davantage pour la fusion que pour la validation, et j'y reviendrai. Une règle de plus, qui ne coûte rien et épargne des jours de débogage : écrire le contenu sous forme canonique, clés triées, indentation fixe, saut de ligne final. Deux documents de même sens ont alors les mêmes octets, et une comparaison de hash peut sauter la fusion entièrement dans le cas courant où un côté n'a pas changé.

La fusion, nœud par nœud

L'algorithme est un parcours récursif des trois arbres. À chaque nœud, il pose deux questions : la version locale s'est-elle éloignée de la base, et la version distante s'est-elle éloignée de la base. Les réponses décident du résultat.

Les règles pour un seul nœud

Si la valeur locale et la valeur distante sont égales, on prend cette valeur. Cela couvre le cas où personne n'a touché au champ et celui où les deux rédacteurs ont fait la même modification. Si un seul côté s'est éloigné de la base, on prend ce côté, y compris quand le mouvement est une suppression. Si les deux côtés se sont éloignés de la base dans des directions différentes et que les deux sont des objets, on descend dans les clés. Sinon, le nœud est un conflit.

Cette dernière règle est plus stricte qu'elle n'en a l'air. Un champ supprimé en local et modifié à distance est un conflit, parce que le moteur n'a aucune raison de préférer un côté à l'autre. Un champ ajouté des deux côtés avec des valeurs différentes est un conflit aussi. Deux scalaires modifiés vers des valeurs différentes constituent le cas évident.

Les tableaux sont la partie difficile

Une liste modifiée des deux côtés n'a pas de bonne réponse positionnelle. Insérez à l'index 2 en local, supprimez l'index 1 à distance, et la fusion par index produit quelque chose qu'aucun des deux rédacteurs n'a écrit. Pour les listes que le schéma déclare avec une key, le moteur peut les fusionner comme des dictionnaires indexés par ce champ : chaque bloc trouve son homologue par id, la récursion continue à l'intérieur de chaque bloc, et l'ordre vient du côté local, sauf si seul le côté distant a réordonné. Pour les listes sans clé, la règle sûre est d'accepter le changement quand un seul côté a bougé et de signaler un conflit quand les deux ont bougé. Deviner ici serait pire que demander.

Les conflits sont des valeurs

Un conflit porte le chemin du nœud sous forme de pointeur JSON et les trois versions, rien d'autre. La fusion termine le document entier, conserve la valeur locale au nœud en conflit pour que le fichier reste valide vis-à-vis de son schéma, et renvoie la liste. Dans cette conception, la CLI refuse alors de marquer le document comme synchronisé, écrit la liste des conflits à côté et affiche les chemins. Résoudre, c'est une modification suivie d'une nouvelle synchronisation. Pas de verrou et pas de choix silencieux.

Pourquoi Rust pour ça

Je travaille en Rust depuis 2023, et un moteur de fusion est le genre de code où le langage justifie son coût.

Modélisez la classification des changements comme un enum, et un match sur une paire d'enums devient exhaustif. Ajoutez une variante, et chaque règle de fusion qui l'a oubliée cesse de compiler. C'est la propriété que je veux dans la seule fonction qui décide si le travail de quelqu'un survit.

Une synchronisation touche chaque document d'un arbre de contenu, et une CLI de synchronisation doit sembler instantanée même quand cet arbre est grand. Rust le permet sans phase de chauffe ni pauses de ramasse-miettes, et comme chaque document fusionne indépendamment, le parcours peut tourner sur de simples threads sans état mutable partagé.

Rust compile une CLI en un binaire unique. On installe un seul fichier, sans environnement d'exécution à versionner et sans rien à télécharger à l'installation.

serde relie les deux formats : la crate toml lit un schéma dans une struct typée, serde_json lit un document dans un Value, et la même mécanique de derive sert aux deux. Dans la version ci-dessous, la fusion travaille sur Value, donc le chemin générique n'a besoin d'aucune connaissance du schéma ; le schéma n'intervient que comme indication, par exemple pour dire quelle clé identifie les éléments d'une liste.

Une fusion minimale sur des valeurs serde_json

Voici le cœur des règles, réduit aux objets et aux scalaires pour tenir dans une seule fonction. Les listes à clé ajouteraient une seconde branche sur Value::Array, de même forme.

// Fusion à trois voies minimale, exemple illustratif écrit pour cet article
use serde_json::{Map, Value};
use std::collections::BTreeSet;
 
#[derive(Debug, Clone, PartialEq)]
pub struct Conflict {
    pub path: String,
    pub base: Option<Value>,
    pub local: Option<Value>,
    pub remote: Option<Value>,
}
 
/// Merges one node. `None` means "absent on that side".
pub fn merge(
    base: Option<&Value>,
    local: Option<&Value>,
    remote: Option<&Value>,
    path: &str,
    out: &mut Vec<Conflict>,
) -> Option<Value> {
    if local == remote {
        return local.cloned();
    }
    if local == base {
        return remote.cloned();
    }
    if remote == base {
        return local.cloned();
    }
    match (local, remote) {
        (Some(Value::Object(l)), Some(Value::Object(r))) => {
            let b = base.and_then(Value::as_object);
            let mut keys: BTreeSet<&String> = l.keys().chain(r.keys()).collect();
            if let Some(b) = b {
                keys.extend(b.keys());
            }
            let mut merged = Map::new();
            for key in keys {
                let child_path = format!("{path}/{key}");
                let child = merge(b.and_then(|m| m.get(key)), l.get(key), r.get(key), &child_path, out);
                if let Some(value) = child {
                    merged.insert(key.clone(), value);
                }
            }
            Some(Value::Object(merged))
        }
        _ => {
            out.push(Conflict {
                path: path.to_string(),
                base: base.cloned(),
                local: local.cloned(),
                remote: remote.cloned(),
            });
            local.cloned()
        }
    }
}

Les trois retours anticipés encodent les règles à nœud unique. Comme Option<&Value> se compare par valeur, la première vérification gère déjà « supprimé des deux côtés » et « même modification des deux côtés », et les deux suivantes gèrent les changements d'un seul côté, suppressions comprises. Tout ce qui atteint le match a divergé des deux côtés.

Les tests

Les tests se lisent comme les règles, et c'est le but : n'importe qui peut confronter le comportement au paragraphe qui le décrit.

// Tests illustratifs de la fusion ci-dessus, écrits pour cet article
#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;
 
    fn run(base: Value, local: Value, remote: Value) -> (Option<Value>, Vec<Conflict>) {
        let mut conflicts = Vec::new();
        let value = merge(Some(&base), Some(&local), Some(&remote), "", &mut conflicts);
        (value, conflicts)
    }
 
    #[test]
    fn edits_to_different_fields_merge_cleanly() {
        let (value, conflicts) = run(
            json!({ "title": "Draft", "published": false }),
            json!({ "title": "Why three versions", "published": false }),
            json!({ "title": "Draft", "published": true }),
        );
        assert!(conflicts.is_empty());
        assert_eq!(value, Some(json!({ "title": "Why three versions", "published": true })));
    }
 
    #[test]
    fn same_field_edited_on_both_sides_is_a_conflict() {
        let (_, conflicts) = run(json!({ "title": "a" }), json!({ "title": "b" }), json!({ "title": "c" }));
        assert_eq!(conflicts.len(), 1);
        assert_eq!(conflicts[0].path, "/title");
    }
 
    #[test]
    fn delete_on_one_side_and_edit_on_the_other_is_a_conflict() {
        let (_, conflicts) = run(json!({ "summary": "old" }), json!({}), json!({ "summary": "new" }));
        assert_eq!(conflicts[0].path, "/summary");
    }
}

Les tests par exemples attrapent les cas auxquels j'ai pensé. Pour les autres, les tests par propriétés sur des arbres JSON aléatoires sont vite rentables, parce que la fusion a des invariants faciles à énoncer : fusionner une valeur avec elle-même des deux côtés renvoie cette valeur, une fusion où un côté est égal à la base renvoie l'autre côté, et échanger local et distant donne le même ensemble de chemins en conflit. Un générateur qui construit une base aléatoire et applique des modifications aléatoires à deux copies sollicite la récursion bien mieux que des cas écrits à la main.

Limites et suite

Les champs texte fusionnent comme des atomes. Deux rédacteurs qui changent des phrases différentes du même paragraphe produisent un conflit, là où un diff caractère par caractère aurait pu les fusionner. Les champs de texte long auraient besoin d'un second moteur en dessous, soit un diff-et-patch de texte, soit un CRDT par bloc, et c'est un projet à part avec ses propres compromis.

L'instantané de base double le stockage de chaque document. Pour du texte, c'est négligeable ; pour des ressources binaires, ce serait une erreur, donc elles ont leur place dans un stockage adressé par contenu qui ne passe jamais par la fusion.

Un document déplacé ou renommé ressemble à une suppression plus un ajout. Bien gérer ce cas exige une identité de document séparée du chemin, un id à l'intérieur du document, et un stockage de base indexé par cet id. Greffer l'identité après coup est pénible, ce qui m'amène à la dernière section.

Si vous en construisez un

Si vous construisez un moteur de ce genre, écrivez la sérialisation canonique et le stockage des instantanés de base avant de toucher à la fusion. Déboguer une fusion sur des fichiers qui ne diffèrent que par des espaces ou par l'ordre des clés fait perdre du temps sur des diffs qui ne veulent rien dire, et la forme canonique supprime cette classe de bruit pour de bon.

Ajoutez aussi l'identité de document dès le premier jour ; elle ne coûte presque rien à ce moment-là et coûte cher ajoutée plus tard. Et une fois que de vrais rédacteurs utilisent l'outil, surveillez le taux de conflits sur les listes à clé. Si la même liste revient dans les conflits semaine après semaine, la stratégie sur les tableaux doit devenir plus fine avant de livrer toute autre fonctionnalité.