L'édition collaborative : plus dur qu'il n'y paraît

Google Docs gère l'édition collaborative en temps réel pour des millions d'utilisateurs. Ça semble sans effort : vous tapez, votre curseur bouge, et les modifications de votre collaborateur apparaissent instantanément. Cette simplicité est trompeuse. Sous le capot, l'édition collaborative est l'un des problèmes les plus ardus des systèmes distribués, et les deux principales approches (Operational Transformation et CRDT) ont chacune des compromis qui ne sautent pas aux yeux tant qu'on n'a pas essayé de construire quelque chose avec.

L'argumentaire en faveur des CRDT (Conflict-free Replicated Data Types) est séduisant : des structures de données qui fusionnent automatiquement sans conflit, sans serveur central, avec une convergence éventuelle garantie par les mathématiques. Mais la réalité, comme plusieurs équipes l'ont découvert après avoir choisi les CRDT pour leurs éditeurs collaboratifs, est plus compliquée. La théorie est magnifique. L'ingénierie, elle, est brutale.

Le problème : les modifications concurrentes

Le défi fondamental : deux utilisateurs éditent le même document en même temps, avec un délai réseau entre eux. L'utilisateur A insère « Hello » à la position 5. L'utilisateur B, qui n'a pas encore vu la modification de A, supprime le caractère en position 5. À quoi doit ressembler le document final ?

C'est ambigu. La suppression de B doit-elle s'appliquer au caractère qui se trouvait en position 5 avant l'insertion de A, ou après ? Si c'est avant, la suppression retire le caractère d'origine et « Hello » apparaît. Si c'est après, la suppression retire le « H » de « Hello ». Les deux interprétations sont raisonnables. Le système doit en choisir une et garantir que tous les clients convergent vers le même résultat : la divergence, c'est deux utilisateurs qui voient deux documents différents, et c'est le seul échec impardonnable.

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation (OT)

L'OT, l'approche la plus ancienne (1989), résout ce problème en transformant les opérations les unes par rapport aux autres. Quand A reçoit la suppression « à la position 10 » de B, le système de A vérifie les opérations déjà appliquées par A que B n'a pas encore vues. Il transforme l'opération de B pour tenir compte de ces changements : comme A a inséré 5 caractères en position 10, la suppression de B doit maintenant s'appliquer en position 15 (le caractère cible d'origine a glissé vers la droite).

Ça fonctionne, et Google Docs l'utilise. Le problème réside dans les fonctions de transformation. Pour un éditeur de texte avec des opérations d'insertion et de suppression, il faut définir comment chaque paire d'opérations se transforme par rapport à l'autre. Avec deux types d'opérations, cela fait quatre cas. Ajoutez la mise en forme, les tableaux, les images, les listes et les commentaires, et le nombre de cas explose de façon combinatoire. Chaque cas doit être correct, et de petits bugs provoquent une divergence du document presque impossible à reproduire et à déboguer.

L'OT exige aussi traditionnellement un serveur central pour établir un ordre total des opérations. Sans serveur, des opérations concurrentes peuvent être transformées dans des ordres différents selon les clients, produisant des résultats différents. Google peut se permettre un serveur central pour Docs. Une application pair à pair ne peut pas utiliser l'OT facilement.

Les CRDT : la promesse théorique

Les CRDT adoptent une approche fondamentalement différente. Au lieu de transformer les opérations, ils utilisent des structures de données où tous les ordres de fusion possibles produisent le même résultat. C'est une garantie mathématique : si la structure de données est un CRDT valide, la convergence est automatique. Pas de fonctions de transformation, pas de serveur central, pas de dépendance à l'ordre.

Pour l'édition de texte, les principales variantes de CRDT sont RGA (Replicated Growable Array) et les autres CRDT de séquence similaires. Au lieu de suivre des positions (qui se décalent à chaque modification), ils attribuent à chaque caractère un identifiant unique et ordonné globalement. Les insertions créent de nouveaux identifiants entre les existants. Les suppressions marquent un identifiant comme tombstone (pierre tombale : non supprimé, on y revient plus tard).

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

Les CRDT : la réalité du terrain

La promesse des CRDT (sans conflit, décentralisée, convergence garantie mathématiquement) est réelle. Mais les défis d'ingénierie sont considérables.

Les tombstones s'accumulent. Quand vous supprimez un caractère dans un CRDT, il ne peut pas être retiré de la structure : d'autres répliques n'ont peut-être pas encore vu la suppression et ont besoin de son identifiant pour positionner correctement leurs propres modifications. Les caractères supprimés sont donc marqués comme tombstones : invisibles mais toujours présents. Un document très édité accumule des milliers de tombstones. Un document de 1000 caractères peut contenir 50 000 tombstones issus de son historique d'édition. Cela alourdit la mémoire et ralentit les opérations.

La surcharge de métadonnées est massive. Chaque caractère a besoin d'un identifiant unique (identifiant utilisateur + horodatage logique), de pointeurs vers les identifiants voisins et d'un indicateur de tombstone. Les métadonnées par caractère peuvent peser 50 à 100 octets. Pour un document de 100 Ko, la représentation CRDT peut atteindre 5 à 10 Mo. C'est un problème pour la synchronisation : envoyer l'état complet du CRDT sur le réseau coûte cher.

Les performances se dégradent avec l'historique. Les opérations sur un CRDT de séquence ne sont pas en O(1) : insérer un caractère demande de trouver la bonne position dans la séquence ordonnée par identifiants, ce qui dépend du nombre total d'identifiants (tombstones compris). Pour les documents avec un long historique d'édition, cela devient nettement plus lent.

Préserver l'intention est difficile. Les CRDT garantissent la convergence : toutes les répliques atteignent le même état. Mais atteignent-elles le bon état ? Quand deux utilisateurs modifient simultanément le même mot, le CRDT entremêle leurs caractères de façon déterministe. Le résultat converge, mais peut être dénué de sens. L'OT peut être conçu pour conserver la modification d'un utilisateur intacte et appliquer celle de l'autre autour. Les CRDT, eux, fusionnent mécaniquement.

Yjs et le compromis pragmatique

Yjs est la bibliothèque CRDT la plus populaire pour JavaScript et alimente les fonctionnalités collaboratives de nombreuses applications web. Elle est bien conçue et répond à beaucoup des problèmes théoriques des CRDT grâce à des optimisations pratiques : un encodage binaire compact réduit la surcharge de métadonnées, et le ramassage des tombstones fonctionne lorsque tous les clients sont en ligne.

Mais Yjs n'est pas magique. Les équipes qui l'adoptent découvrent qu'une bibliothèque CRDT résout le problème de convergence, mais pas le problème de la collaboration. Il vous faut encore : un serveur de signalisation pour la découverte des pairs, une couche de persistance pour les modifications hors ligne, une résolution de conflits pour les opérations de haut niveau (que se passe-t-il quand deux utilisateurs restructurent la même section ?), le suivi de présence (curseurs, sélections), une annulation et un rétablissement qui respectent les modifications des autres utilisateurs, et la gestion des permissions.

Certaines équipes, après avoir construit un éditeur collaboratif sur Yjs, ont conclu que l'approche CRDT ajoute une complexité dont elles n'avaient pas besoin. Si votre application dispose d'un serveur central (c'est le cas de la plupart), l'OT ou des approches plus simples (le dernier écrit gagne avec détection de conflits) peuvent être plus pratiques. Les CRDT brillent dans les scénarios réellement pair à pair : applications hors ligne d'abord, logiciels local-first et systèmes où aucune autorité centrale ne peut être supposée.

Ce que la plupart des applications devraient faire

Si vous ajoutez l'édition collaborative à votre application, voici le cadre de décision pragmatique.

• Si vous avez un serveur central et que vos documents sont petits : utilisez l'OT. L'approche de Google fonctionne. Des bibliothèques comme ShareDB implémentent l'OT pour Node.js. Le serveur central simplifie tout : l'ordonnancement, la persistance, la résolution de conflits, les permissions.
• Si vous avez besoin du hors ligne ou du pair à pair : utilisez les CRDT (Yjs ou Automerge). Les CRDT sont la seule approche qui gère correctement l'édition hors ligne réelle et la synchronisation pair à pair. Acceptez la surcharge de métadonnées et l'accumulation de tombstones comme le prix de la décentralisation.
• Si vos collaborateurs éditent rarement la même section en même temps : vous n'avez peut-être besoin ni de l'un ni de l'autre. Un simple verrouillage (un seul éditeur par section) ou le dernier écrit gagne avec une bonne interface de gestion des conflits couvre de nombreux cas réels de collaboration, sans la complexité de l'OT ou des CRDT.
• Si vous construisez un concurrent de Google Docs : il vous faut une équipe d'ingénieurs en systèmes distribués et des années de développement. Ce n'est pas un projet de week-end. La simplicité apparente de l'édition collaborative cache une complexité extraordinaire.

Le bilan honnête

L'édition collaborative fait partie de ces problèmes dont la difficulté n'est pas évidente. Le cas nominal (deux utilisateurs qui font des modifications sans chevauchement) fonctionne avec presque n'importe quelle approche. Les cas difficiles (modifications concurrentes sur la même zone, édition hors ligne avec synchronisation ultérieure, structures de documents complexes comme les tableaux, listes imbriquées et objets intégrés) exigent une compréhension approfondie des compromis entre OT et CRDT.

Aucune approche n'est strictement meilleure. L'OT est plus simple avec un serveur, plus difficile sans. Les CRDT fonctionnent sans serveur mais impliquent une surcharge de métadonnées et une accumulation de tombstones. Les deux demandent une ingénierie soignée au-delà de l'algorithme central, et cette ingénierie (présence, persistance, permissions, annulation) est souvent plus difficile que le problème de convergence lui-même.

Le secteur converge lentement vers un hybride pragmatique : des CRDT pour le modèle de données (garanties de fusion automatique), et un serveur pour la coordination (présence, permissions, ramassage des déchets). Vous obtenez ainsi le meilleur des deux mondes : convergence mathématique et infrastructure pratique. Mais vous héritez aussi de la complexité des deux mondes, ce qui explique pourquoi l'édition collaborative reste un problème difficile après 35 ans de recherche.