← Alle berichten

Operational transformation en conflictvrije resolutie voor realtime-samenwerkingsapplicaties

Op deze pagina

Ik solliciteer op dit moment bij een stel bedrijven in het Verenigd Koninkrijk. Zo kom ik erachter met welke uitdagingen bepaalde bedrijven worstelen. Eén daarvan is realtime samenwerking binnen de applicatie van een bedrijf.

Dat zette me aan het denken over hoe realtime samenwerkingstechnologie eigenlijk wordt gebouwd.

Met meerdere gebruikers hetzelfde document bewerken is heel gewoon geworden. Zo gewoon dat Google Docs, Microsoft Word, Canva, Figma, Miro, Notion, Linear en nog veel meer applicaties het standaard ondersteunen. Het is zelfs raar geworden om een applicatie zonder te zien.

Nu wil ik alleen nog weten hoe het werkt.

Technieken

Tijdens het uitzoeken vond ik twee vrij gangbare technieken die kunnen helpen.

Operational Transformation (OT)

Dit algoritme gebruik je het vaakst bij realtime samenwerking. Het verwerkt wijzigingen op de huidige staat van het document en past ze aan de serverkant toe, zo dat de volgorde van de bewerkingen de consistentie niet beïnvloedt.

Conflict-free Replicated Data Types (CRDT’s)

Net als OT zorgen CRDT’s ervoor dat kopieën van de data uiteindelijk naar dezelfde staat toe groeien, ongeacht de volgorde van de wijzigingen. Acties in CRDT’s zijn ontworpen om commutatief, idempotent en associatief te zijn. Dat maakt het samenvoegen eenvoudiger. CRDT’s zijn fijn omdat ze niet per se een server nodig hebben en peer-to-peer kunnen werken. Gebruikers kunnen dus offline doorwerken en na het opnieuw verbinden naadloos synchroniseren, zonder bang te zijn dat hun wijzigingen inconsistenties veroorzaken.

Overwegingen

Er zijn nog een heleboel andere dingen om rekening mee te houden, maar daar ga ik hier niet diep op in.

Netwerklatentie en verbroken verbindingen

Netwerklatentie en verbroken verbindingen netjes afhandelen aan de clientkant is cruciaal. Strategieën om oudere statuswijzigingen te laten verlopen kunnen helpen om inconsistenties in de UI en conflicten te beperken.

Realtime updates

Gebruik geen polling, maar technologieën als WebSockets of gRPC. Daarmee beheer je realtime statusupdates van de server efficiënt.

UX van conflictresolutie

De gebruikersinterface moet gebruikers een intuïtieve manier geven om conflicten te begrijpen en op te lossen als ze zich voordoen.

Chronologie en leeftijd van een statuswijziging

CRDT’s zijn niet afhankelijk van de volgorde van de wijzigingen, OT’s wel: die hangen af van de vorige en de volgende staat. De afstand tussen chronologische wijzigingen kan conflictresolutie ingewikkeld maken. Ook kan de leeftijd van een statuswijziging latere wijzigingen beïnvloeden als de client die niet na een redelijke TTL weggooit. Met andere woorden: stuur geen supeloude statuswijzigingen in van toen de netwerkverbinding wegviel, stuur alleen de nieuwste. (Tenzij je de chronologie opslaat en die later gebruikt voor conflictresolutie aan de serverkant.)

Implementaties

Operational transformation

Kort door de bocht draait OT erom dat de eindstaat consistent is, wat je ook doet en in welke volgorde. Dat is cruciaal, want in de echte wereld weet je nooit in welke volgorde de wijzigingen van gebruikers de server bereiken. Je kunt tijdstempels van apparaten verzamelen, maar die synchroniseren tussen veel clients is bijna onmogelijk (al kunnen ze, zoals ik hierboven zei, superhandig zijn bij conflictresolutie als je een geschiedenis van wijzigingen bijhoudt).

Concepten

  • Idempotentie: dit is de superheld onder de concepten van realtime bewerken. Idempotentie betekent dat een bewerking, hoe vaak je die ook uitvoert, hetzelfde resultaat geeft als wanneer je hem één keer uitvoert. Stel je voor dat de knop Plaatsen op Facebook je laatste gedachten steeds opnieuw verstuurde. Je zou geen vrienden meer hebben! In samenwerkingsapplicaties zorgt idempotentie ervoor dat herhaalde updates de eindstaat niet meer beïnvloeden dan de eerste keer. Cruciaal om gezond te blijven in samenwerkingssessies.
  • Associativiteit: zie het als de mixer. Hoe je je bewerkingen ook groepeert, het eindresultaat is hetzelfde. Neem het voorbeeld (a * b) * c = a * (b * c). Superhandig als je een hoop wijzigingen moet samenvoegen en je geen zin hebt om uit te zoeken wat van wat afhangt.
  • Commutativiteit: dit concept zorgt dat de volgorde van bewerkingen niet uitmaakt, a * b = b * a. Of de wijzigingen van gebruiker A nu vóór die van gebruiker B worden toegepast of andersom, het eindresultaat is hetzelfde. Goud waard in omgevingen waar wijzigingen uit alle hoeken binnenvliegen of zelfs offline zijn gemaakt.

Basisvoorbeeld van een implementatie

Dit is een heel eenvoudig voorbeeld met één string als staat. Bij het wijzigen van de staat nemen we gewoon een index en voegen we tekst in of verwijderen we tekst.

Bijvoorbeeld:

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;
}

Conflict-free Replicated Data Types

CRDT’s zijn een andere techniek om de staat te beheren in realtime samenwerkingsapplicaties. Ze pakken het anders aan: elke wijziging kan zelfstandig naar hetzelfde eindresultaat toe groeien, in welke volgorde ze ook worden toegepast. Daardoor zijn CRDT’s vooral robuust in omgevingen met veel netwerkproblemen.

CRDT’s blinken uit in situaties waar latentie meer is dan een kleine ergernis. Denk aan werken in de trein met een wisselvallige internetverbinding. Elke actie of bewerking in een CRDT-systeem is ontworpen om zelfstandig samen te voegen, zonder meteen een centrale server te raadplegen. Gebruikers kunnen dus offline doorwerken en na het opnieuw verbinden naadloos synchroniseren, zonder bang te zijn dat hun wijzigingen inconsistenties veroorzaken.

Concepten

Basisvoorbeeld van een implementatie

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;
}

Conclusie

Ik vond het erg leuk om uit te zoeken hoe deze concepten werken. We zijn tegenwoordig superverbonden, maar het blijft cruciaal dat applicaties dit soort complexiteit goed afhandelen om de gebruikerservaring te verbeteren.

In een echte situatie zou ik natuurlijk geen enkel stringveld gebruiken om de staat te beheren. Ik wilde alleen laten zien hoe ze in de praktijk kunnen werken.

Verder zou ik waarschijnlijk proberen de applicatielaag niet te gebruiken om statuswijzigingen te verwerken. Het kan, maar ik weet niet wat dat betekent voor de ACID-garanties van de database als meerdere clients vaak updates insturen. Misschien kan een queue dat afvangen.

Ik heb met een paar tools gespeeld die me hielpen te begrijpen hoe het werkt. Ik hoop dat je er iets aan hebt.

Dank

Een grote pluim voor Tuhin Banerjee op Medium, wiens post me op weg hielp met mijn eigen implementatie.