Transformation opérationnelle et résolution sans conflit pour les applications de collaboration en temps réel

Je passe des entretiens dans plusieurs entreprises au Royaume-Uni en ce moment, et ça me permet de découvrir les défis de certaines boîtes. L’un d’eux : la collaboration en temps réel dans l’application d’une entreprise.

Ça a piqué ma curiosité sur la façon dont on implémente les technologies collaboratives en temps réel.

Que plusieurs personnes éditent le même document, c’est devenu courant. Tellement courant que Google Docs, Microsoft Word, Canva, Figma, Miro, Notion, Linear et bien d’autres le proposent d’office. Tellement, tellement courant que c’est presque bizarre de tomber sur une application qui ne le fait pas.

Je veux simplement savoir comment ça marche.

Les techniques

En creusant, j’ai trouvé deux techniques assez répandues.

Transformation opérationnelle (OT)

C’est l’algorithme le plus utilisé pour la collaboration en temps réel. Il traite les changements apportés à l’état courant du document et les applique côté serveur, de sorte que l’ordre des opérations n’affecte pas la cohérence.

Types de données répliqués sans conflit (CRDT)

Comme l’OT, les CRDT garantissent que les copies des données finissent par converger, quel que soit l’ordre des changements. Les actions d’un CRDT sont conçues pour être commutatives, idempotentes et associatives, ce qui simplifie la fusion. Les CRDT sont super parce qu’ils ne dépendent pas forcément d’un serveur et fonctionnent en pair-à-pair. Les utilisateurs peuvent donc continuer à travailler hors ligne et se resynchroniser sans accroc à la reconnexion, sans craindre que leurs changements créent des incohérences.

Les points d’attention

Il y a plein d’autres points à prendre en compte, mais je n’entre pas trop dans le détail ici.

Latence réseau et déconnexions

Côté client, gérer proprement la latence réseau et les déconnexions est crucial. Des stratégies qui font expirer les anciens changements d’état peuvent réduire les incohérences et les conflits dans l’interface.

Mises à jour en temps réel

Au lieu de faire du polling, des technologies comme les WebSockets ou gRPC gèrent efficacement les mises à jour d’état poussées par le serveur.

UX de la résolution de conflits

L’interface doit offrir des mécanismes intuitifs pour que les utilisateurs comprennent et résolvent les conflits quand ils surviennent.

Chronologie et ancienneté d’un changement d’état

Les CRDT ne dépendent pas de l’ordre des changements, alors que les OT s’appuient sur l’état précédent et le suivant. L’écart chronologique entre les changements peut compliquer la résolution des conflits. L’ancienneté d’un changement d’état peut aussi influencer les changements suivants si le client ne l’écarte pas après un TTL raisonnable. Autrement dit, n’envoie pas de vieux changements datant de la coupure réseau, envoie seulement le dernier. (Sauf si tu stockes la chronologie et t’en sers plus tard pour résoudre les conflits côté serveur.)

Les implémentations

Transformation opérationnelle

En bref, l’OT sert à garantir que, quoi que tu fasses, l’état final est cohérent, quel que soit l’ordre des opérations. C’est crucial, car dans la vraie vie, tu ne sais jamais dans quel ordre les changements des utilisateurs arriveront au serveur. Tu peux collecter les horodatages des appareils, mais les synchroniser entre de nombreux clients est quasi impossible (même si, comme je l’ai dit plus haut, ils peuvent être très utiles pour résoudre les conflits si tu gardes un historique des changements).

Concepts

Idempotence : le super-héros des concepts de l’édition en temps réel. L’idempotence veut dire que, peu importe combien de fois tu exécutes une opération, le résultat est le même que si tu l’avais exécutée une seule fois. Si le bouton « publier » de Facebook renvoyait tes dernières pensées en boucle, tu n’aurais plus d’amis. Dans une application collaborative, l’idempotence garantit que les mises à jour répétées n’affectent pas l’état final au-delà de la première application. C’est indispensable pour garder la raison pendant les sessions collaboratives.
Associativité : pense au mixeur. Peu importe comment tu regroupes tes opérations, le résultat final est le même. Prends (a * b) * c = a * (b * c). C’est très pratique quand tu as un tas de changements à fusionner et que tu n’as pas envie de passer ton temps à démêler qui dépend de quoi.
Commutativité : l’ordre des opérations n’a pas d’importance, a * b = b * a. Que les changements de l’utilisateur A soient appliqués avant ceux de l’utilisateur B ou l’inverse, le résultat est le même. Ça vaut de l’or quand les changements arrivent de tous les côtés, ou ont même été faits hors ligne.

Exemple d’implémentation de base

Voici un exemple très simple qui utilise une seule chaîne de caractères comme état. Pour modifier l’état, on prend un index et on insère ou on supprime du texte.

Par exemple :

interface Operation {
  id: string;
  index: number;
  length: number;
  text: string;
  type: 'insert' | 'delete';
  timestamp: number;
}

function applyOperation(currentState: string, operation: Operation): string {
  switch (operation.type) {
    case 'insert':
      return (
        currentState.slice(0, operation.index) +
        operation.text +
        currentState.slice(operation.index)
      );
    case 'delete':
      return (
        currentState.slice(0, operation.index) +
        currentState.slice(operation.index + operation.length)
      );
    default:
      return currentState;
  }
}

function transformOperation(
  baseOperation: Operation,
  newOperation: Operation
): Operation {
  if (newOperation.index > baseOperation.index) {
    switch (baseOperation.type) {
      case 'insert':
        newOperation.index += baseOperation.text.length;
        break;
      case 'delete':
        newOperation.index -= baseOperation.length;
        break;
    }
  }
  return newOperation;
}

function compareAndApplyOT(
  operations: Operation[],
  currentState: string
): string {
  let appliedOperations = new Map<string, Operation>();
  operations.sort((a, b) => a.timestamp - b.timestamp);

  for (const operation of operations) {
    if (!appliedOperations.has(operation.id)) {
      let transformedOperation = operation;
      appliedOperations.forEach((appliedOp) => {
        transformedOperation = transformOperation(
          appliedOp,
          transformedOperation
        );
      });
      currentState = applyOperation(currentState, transformedOperation);
      appliedOperations.set(operation.id, transformedOperation);
    }
  }
  return currentState;
}

Types de données répliqués sans conflit

Les CRDT sont une autre technique pour gérer l’état dans les applications collaboratives en temps réel. Ils s’y prennent autrement : chaque changement peut converger indépendamment vers le même résultat final, quel que soit l’ordre d’application. Les CRDT sont donc particulièrement robustes quand le réseau est très perturbé.

Les CRDT brillent quand la latence est bien plus qu’un petit désagrément. Pense au travail dans un train avec une connexion capricieuse. Chaque action ou édition dans un système CRDT est conçue pour fusionner indépendamment, sans avoir à consulter tout de suite un serveur central. Les utilisateurs peuvent donc continuer à travailler hors ligne et se resynchroniser sans accroc à la reconnexion, sans craindre que leurs changements créent des incohérences.

Concepts

Exemple d’implémentation de base

interface CRDTOperation {
  id: string;
  index: number;
  text: string;
  type: 'insert' | 'delete';
}

function applyOperation(currentState: string, operation: Operation): string {
  switch (operation.type) {
    case 'insert':
      return (
        currentState.slice(0, operation.index) +
        operation.text +
        currentState.slice(operation.index)
      );
    case 'delete':
      return (
        currentState.slice(0, operation.index) +
        currentState.slice(operation.index + operation.length)
      );
    default:
      return currentState;
  }
}

function compareAndApplyCRDT(
  operations: CRDTOperation[],
  currentState: string
): string {
  let operationMap = new Map<string, CRDTOperation>();
  operations.forEach((op) => operationMap.set(op.id, op)); // Ensures idempotency by overwriting duplicates

  let sortedOperations = Array.from(operationMap.values());
  // Sort by ID for consistency, but order does not change the result
  sortedOperations.sort((a, b) => a.id.localeCompare(b.id));

  for (const operation of sortedOperations) {
    currentState = applyOperation(currentState, operation); // Re-using the applyOperation function from OT
  }
  return currentState;
}

Conclusion

J’ai vraiment aimé explorer le fonctionnement de ces concepts. Même si on est ultra connectés aujourd’hui, il reste essentiel que les applications gèrent bien ce genre de complexité pour améliorer l’expérience utilisateur.

Évidemment, dans un vrai projet, je n’utiliserais pas un simple champ de type chaîne pour gérer l’état. Je voulais juste te montrer comment ça pourrait marcher en pratique.

Je chercherais aussi probablement à éviter de traiter les changements d’état dans la couche applicative. C’est possible, mais je ne sais pas quel effet ça aurait sur la conformité ACID de la base de données quand plusieurs clients envoient des mises à jour fréquentes. Une file d’attente pourrait peut-être s’en charger.

J’ai testé quelques outils qui m’ont aidé à comprendre comment tout ça fonctionne. J’espère qu’ils te serviront.

Remerciements

Un grand merci à Tuhin Banerjee sur Medium, dont le billet m’a aidé à démarrer ma propre implémentation.