Conception d'un système d'édition collaborative : OT ou CRDT, présence et synchronisation

Deux personnes tapent dans le même paragraphe au même instant. En une fraction de seconde, les deux écrans affichent le même texte, et les mots de personne n'ont disparu. Pour y parvenir, il faut résoudre un problème précis, les modifications concurrentes d'un état partagé, plus une série de problèmes d'infrastructure ordinaires : routage, persistance, présence et reconnexion.

Cet article conçoit un éditeur collaboratif en temps réel : le problème de concurrence sur un exemple détaillé, la transformation opérationnelle (OT) et les types de données répliqués sans conflit (CRDT) comparés, l'approche où le serveur fait autorité qu'utilise Figma, et l'architecture qui les entoure, avec un diagramme.

Le problème central, en cinq caractères

Partez du document ABC. Les positions se comptent à partir de zéro.

• Alice insère X à la position 1, ce qui donne AXBC sur son écran.
• Au même instant, Bob supprime la position 2, le C, ce qui donne AB sur le sien.

Chaque client reçoit maintenant l'opération de l'autre et l'applique telle quelle :

• Bob applique « insérer X en 1 » à AB et obtient AXB.
• Alice applique « supprimer la position 2 » à AXBC, supprime donc le B et obtient AXC.

Les documents ont divergé, et la copie d'Alice a perdu un caractère que personne n'a supprimé. Tout éditeur collaboratif existe pour empêcher cela. Il existe deux familles de solutions.

La transformation opérationnelle

L'OT conserve les opérations sous forme de positions et transforme chaque opération entrante par rapport aux opérations concurrentes qu'elle n'a pas vues. Le « supprimer la position 2 » de Bob a été émis avant l'insertion d'Alice en position 1, qui décale tout ce qui la suit d'un cran vers la droite. Transformé par rapport à l'insertion, il devient « supprimer la position 3 », et le AXBC d'Alice devient AXB, comme chez Bob.

Les systèmes OT en production utilisent un serveur central pour ordonner les opérations, une approche qui remonte au système Jupiter en 1995 et que Google Docs a décrite lors de la refonte de son éditeur en 2010 :

1. Chaque client envoie ses opérations étiquetées avec la révision du serveur sur laquelle elles se fondent.
2. Le serveur transforme chaque opération par rapport à tout ce qu'il a accepté depuis cette révision, attribue le numéro de révision suivant et diffuse le résultat.
3. Chaque client transforme les opérations entrantes par rapport à ses propres opérations non encore acquittées.

Les forces de l'OT sont des opérations compactes et un long historique pour le texte. Sa faiblesse, ce sont les fonctions de transformation elles-mêmes : pour le texte riche, les tableaux et les structures imbriquées, traiter correctement chaque paire de types d'opérations est notoirement difficile, et la conception dépend d'un serveur pour définir l'ordre.

Les CRDT

Un CRDT est un type de données conçu pour que des mises à jour concurrentes puissent être appliquées dans n'importe quel ordre tout en faisant converger chaque réplique ; Shapiro et ses collègues l'ont formalisé en 2011. Pour le texte, chaque caractère inséré reçoit un identifiant unique et ordonné, comme un identifiant de client et un compteur, et une insertion dit « après le caractère d'identifiant tel » plutôt que « en position 1 ». Les suppressions marquent les caractères comme retirés et laissent des tombstones. Comme les opérations désignent des identifiants stables plutôt que des positions mouvantes, il n'y a rien à transformer.

Dans l'exemple, l'insertion d'Alice dit « X vient après A », et la suppression de Bob dit « retirer C ». Appliquées dans n'importe quel ordre, les deux répliques aboutissent à AXB.

Des bibliothèques CRDT comme Yjs et Automerge rendent cela praticable. Leurs forces : aucun ordre central n'est nécessaire, si bien que l'édition hors ligne et la synchronisation pair à pair fonctionnent naturellement, et la fusion est possible à tout moment. Leurs coûts : des métadonnées supplémentaires par caractère, des tombstones à compacter, et des cas limites où le résultat fusionné est cohérent mais ne correspond à l'intention d'aucun des deux utilisateurs. Un serveur reste utile pour le contrôle d'accès, la persistance et le fan-out ; il n'a simplement pas à décider de l'ordre.

La voie médiane où le serveur fait autorité

Tous les éditeurs ne modifient pas du texte long. Figma n'a choisi ni l'OT classique ni de vrais CRDT : son serveur définit l'ordre des événements, les documents sont des arbres d'objets dotés de propriétés, et quand deux personnes modifient la même propriété du même objet, la dernière valeur reçue par le serveur l'emporte. Ses serveurs exécutent un processus distinct pour chaque document multijoueur, et tous ceux qui modifient ce document s'y connectent. Pour les outils de design, les tableurs et les tableaux blancs, où les conflits se jouent propriété par propriété, c'est plus simple que les deux autres options.

L'architecture

Quel que soit l'algorithme choisi, le système qui l'entoure se ressemble :

1. Les clients se connectent en WebSocket à un service de collaboration et gardent la connexion ouverte tant que le document l'est.
2. Un seul serveur de session possède chaque document. Tous les clients de doc-123 doivent atteindre le même serveur, afin qu'il puisse ordonner ou fusionner les modifications en mémoire. Un annuaire, par exemple dans Redis, associe les documents aux serveurs avec un bail, et le répartiteur de charge ou une couche de routage y envoie les connexions. Le hachage cohérent sur l'identifiant du document fonctionne aussi, à condition que deux serveurs ne puissent jamais croire en même temps posséder un document.
3. Le serveur de session garde le document vivant en mémoire, applique chaque modification entrante et la diffuse aux autres clients.
4. Chaque modification est ajoutée à un journal d'opérations durable avant que le serveur ne l'acquitte. Un snapshot périodique du document entier part dans un stockage objet : charger un document revient à lire le dernier snapshot puis les opérations qui le suivent.
5. Les permissions sont vérifiées à la connexion et à chaque opération ; la modification d'un lecteur est rejetée, pas seulement masquée.

Les commentaires, l'historique des versions, la recherche et l'export sont des services distincts qui consomment le journal d'opérations ; ils n'ont pas leur place sur le chemin temps réel.

La présence est une autre donnée

Les curseurs, les sélections et le « qui est là » changent sans cesse, ne comptent que dans l'instant et ne valent plus rien une minute plus tard. Traitez la présence comme éphémère : diffusez-la par le même serveur de session, limitez-la à quelques mises à jour par seconde et par utilisateur, abandonnez-la quand un client se déconnecte et ne l'écrivez jamais dans le journal d'opérations. Yjs, par exemple, conserve la présence dans un canal d'awareness distinct, à côté de l'état du document.

Modifications hors ligne et reconnexion

Les connexions coupent en permanence, dans les trains et les ascenseurs. Le client conserve localement les opérations non acquittées et les renvoie à la reconnexion :

• Avec l'OT, le client envoie ses opérations en attente avec la dernière révision qu'il a vue ; le serveur les transforme par rapport à tout ce qui a suivi.
• Avec les CRDT, client et serveur échangent des résumés compacts de ce que chacun a vu, souvent appelés vecteurs d'état (state vectors), et ne s'envoient que les mises à jour manquantes.

Les longues périodes hors ligne sont le point fort des CRDT. Avec l'OT, un client resté hors ligne une journée peut toujours se reconnecter, mais le serveur doit transformer ses opérations par rapport à une journée entière d'opérations.

Passage à l'échelle et pannes

• Les documents chauds. Un document avec des milliers de lecteurs et quelques rédacteurs ne doit pas obliger le serveur de session à pousser lui-même chaque frappe vers des milliers de sockets ; diffusez aux lecteurs via une couche pub/sub et regroupez les mises à jour.
• Le plantage d'un serveur de session. Les clients se reconnectent, le bail de l'annuaire expire, un nouveau serveur charge le snapshot et le journal d'opérations, et les clients renvoient leurs opérations en attente. N'acquitter que les modifications journalisées durablement est ce qui rend cela sans perte.
• Le split brain. Deux serveurs possédant le même document accepteraient des ordres contradictoires. Protégez la propriété par le bail (fencing) et rejetez les écritures d'un serveur dont le bail a expiré.
• L'annulation doit défaire votre dernière modification, pas celle de votre collaborateur : elle devient donc une nouvelle opération inverse, transformée ou fusionnée comme n'importe quelle autre.

Le diagramme de collaboration

Comment le lire :

• Deux clients se connectent en WebSocket via le répartiteur de charge.
• L'annuaire Redis indique quel serveur de session possède doc-123 ; les deux connexions aboutissent sur le serveur A.
• Le serveur A ordonne ou fusionne les modifications en mémoire et renvoie modifications et présence aux deux clients.
• Durabilité : chaque modification part dans le journal d'opérations Postgres avant d'être acquittée ; les snapshots vont dans le stockage objet.
• Le fournisseur d'identité vérifie l'accès à la connexion des clients ; le serveur B possède d'autres documents et montre comment le service passe à l'échelle horizontalement.
• Le bloc Markdown compare OT et CRDT en trois lignes.

Dessiner clairement les systèmes temps réel

• Montrez la propriété. Le fait le plus important ici est qu'un serveur possède un document ; dessinez l'annuaire et le routage.
• Séparez données durables et éphémères. Dessinez le journal d'opérations et les snapshots, et étiquetez la présence comme non persistée.
• Dessinez au moins deux clients. La concurrence est tout le problème ; un seul client la masque.
• Marquez le point d'acquittement : une modification est en sécurité dès qu'elle est dans le journal d'opérations.

Pour les connexions longues et le fan-out, le diagramme d'architecture d'une application de chat couvre un terrain voisin. Router les documents vers les serveurs applique les idées du diagramme de répartiteur de charge, et la méthode générale se trouve dans l'exemple de diagramme de conception de système.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez deux nœuds Appareil du pack Réseau pour les clients et un Répartiteur de charge cloud du pack Cloud comme entrée WebSocket.
3. Ajoutez un Cadre du pack Base pour le service de collaboration, avec deux nœuds Instance de calcul à l'intérieur : le serveur de session A, propriétaire de doc-123, et le serveur de session B.
4. Ajoutez un nœud Redis du pack Données pour l'annuaire des documents, un nœud Postgres pour le journal d'opérations et un nœud Stockage objet du pack Cloud pour les snapshots.
5. Ajoutez un Fournisseur d'identité du pack Sécurité, puis reliez le tout par des arêtes étiquetées : WebSocket, modifications et présence, ajout, snapshot, bail.
6. Ajoutez un bloc Markdown du pack Base avec la synthèse OT contre CRDT.

L'exemple utilise 11 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Quelle est la différence entre OT et CRDT ? L'OT transforme les opérations concurrentes les unes par rapport aux autres, généralement avec un serveur qui définit l'ordre. Les CRDT donnent à chaque élément une identité stable, si bien que les opérations commutent et que les répliques convergent dans n'importe quel ordre, sans ordre central.

Google Docs utilise-t-il l'OT ou des CRDT ? Google a décrit la refonte de son éditeur en 2010 comme reposant sur la transformation opérationnelle, avec un serveur qui ordonne les changements. Beaucoup d'éditeurs plus récents utilisent des bibliothèques CRDT comme Yjs ou Automerge.

Pourquoi tous les rédacteurs d'un document doivent-ils se connecter au même serveur ? Ce serveur détient le document vivant et décide de l'ordre des modifications. Si deux serveurs acceptaient indépendamment des modifications pour un même document, ils devraient se coordonner à chaque frappe.

Comment la présence est-elle stockée ? La plupart du temps, elle ne l'est pas. Curseurs et sélections sont diffusés en temps réel, limités en fréquence et abandonnés quand un client se déconnecte. Les persister ajoute de la charge sans apporter de valeur.

Un éditeur collaboratif peut-il fonctionner hors ligne ? Oui. Les clients mettent les opérations en file localement et se synchronisent à la reconnexion. Les CRDT gèrent le plus naturellement les longues périodes hors ligne ; l'OT fonctionne aussi, mais transforme davantage d'opérations au retour.

Commencez gratuitement — un siège, sans carte bancaire.