Operational Transformation und konfliktfreie Auflösung für Echtzeit-Kollaboration

Ich spreche gerade mit einer Reihe von Unternehmen im Vereinigten Königreich, und dabei erfahre ich, vor welchen Problemen sie stehen. Eines davon ist Echtzeit-Kollaboration in der eigenen Anwendung.

Das hat mein Interesse geweckt, wie solche Technologien umgesetzt werden.

Dass mehrere Nutzer dasselbe Dokument bearbeiten, ist längst normal. So normal, dass Google Docs, Microsoft Word, Canva, Figma, Miro, Notion, Linear und viele andere es von Haus aus können. Es ist so normal, dass es inzwischen komisch wirkt, wenn eine Anwendung es nicht kann.

Ich will jetzt nur wissen, wie es funktioniert.

Techniken

Bei der Recherche bin ich auf zwei verbreitete Techniken gestoßen.

Operational Transformation (OT)

Dieser Algorithmus ist in der Echtzeit-Kollaboration am weitesten verbreitet. Er nimmt Änderungen am aktuellen Zustand des Dokuments entgegen und wendet sie serverseitig so an, dass die Reihenfolge der Operationen die Konsistenz nicht beeinflusst.

Conflict-free Replicated Data Types (CRDTs)

Wie bei OT sorgen CRDTs dafür, dass Kopien der Daten irgendwann zusammenlaufen, egal in welcher Reihenfolge die Änderungen eintreffen. Aktionen in CRDTs sind kommutativ, idempotent und assoziativ ausgelegt, was das Zusammenführen vereinfacht. CRDTs sind großartig, weil sie nicht zwingend einen Server brauchen und Peer-to-Peer arbeiten können. Nutzer können also offline weiterarbeiten und sich nach dem Wiederverbinden nahtlos abgleichen, ohne Angst, dass ihre Änderungen Inkonsistenzen auslösen.

Überlegungen

Es gibt noch eine Reihe weiterer Punkte, die man beachten sollte. Ich gehe hier aber nicht zu tief darauf ein.

Netzwerklatenz und Verbindungsabbrüche

Latenz und Verbindungsabbrüche müssen auf der Client-Seite sauber abgefangen werden. Veraltete Zustandsänderungen verfallen zu lassen, kann UI-Inkonsistenzen und Konflikte verringern.

Updates in Echtzeit

Statt zu pollen, lassen sich mit WebSockets oder gRPC Zustandsänderungen vom Server effizient in Echtzeit verwalten.

UX bei der Konfliktlösung

Die Oberfläche sollte Nutzern intuitive Mittel geben, um Konflikte zu verstehen und aufzulösen, wenn sie auftreten.

Chronologie und Alter einer Zustandsänderung

CRDTs sind nicht auf die Reihenfolge der Änderungen angewiesen, OT dagegen stützt sich auf vorherigen und nächsten Zustand. Der zeitliche Abstand zwischen Änderungen kann die Konfliktlösung verkomplizieren. Außerdem kann das Alter einer Zustandsänderung spätere Änderungen beeinflussen, wenn der Client sie nicht nach einer vernünftigen TTL verwirft. Anders gesagt: Schick keine uralten Zustandsänderungen aus der Zeit, als die Verbindung abgerissen ist. Schick nur die neueste. (Es sei denn, du speicherst die Chronologie und nutzt sie später serverseitig für die Konfliktlösung.)

Umsetzungen

Operational Transformation

Kurz gesagt geht es bei OT darum, dass der Endzustand konsistent ist, was auch immer du tust und in welcher Reihenfolge. Das ist entscheidend, denn in der Praxis weißt du nie, in welcher Reihenfolge die Änderungen der Nutzer beim Server ankommen. Du kannst Zeitstempel der Geräte sammeln, aber sie zwischen vielen Clients zu synchronisieren ist fast unmöglich. (Wie oben erwähnt, können sie bei der Konfliktlösung trotzdem sehr nützlich sein, wenn du eine Änderungshistorie führst.)

Konzepte

• Idempotenz: Das ist der Superheld unter den Konzepten der Echtzeit-Bearbeitung. Idempotenz heißt: Egal wie oft du eine Operation ausführst, das Ergebnis ist dasselbe wie nach dem ersten Mal. Stell dir vor, der Posten-Button bei Facebook würde deine letzten Gedanken immer wieder abschicken. Du hättest keine Freunde mehr! In kollaborativen Anwendungen sorgt Idempotenz dafür, dass wiederholte Updates den Endzustand nicht über die erste Anwendung hinaus verändern. Das ist entscheidend, um in gemeinsamen Sitzungen den Verstand zu behalten.
• Assoziativität: Denk an einen Mixer. Egal wie du deine Operationen gruppierst, das Ergebnis ist dasselbe. Zum Beispiel (a * b) * c = a * (b * c). Das ist sehr praktisch, wenn viele Änderungen zusammengeführt werden müssen und du nicht lange entwirren willst, was wovon abhängt.
• Kommutativität: Dieses Konzept stellt sicher, dass die Reihenfolge der Operationen keine Rolle spielt: a * b = b * a. Ob die Änderungen von Nutzer A vor denen von Nutzer B angewendet werden oder umgekehrt, der Endzustand ist derselbe. Das ist Gold wert, wenn Änderungen aus allen Richtungen hereinfliegen oder sogar offline entstehen.

Einfaches Implementierungsbeispiel

Das ist ein sehr einfaches Beispiel, das einen einzelnen String als Zustand nutzt. Beim Ändern des Zustands nehmen wir nur einen Index und fügen entweder Text ein oder löschen ihn.

Zum Beispiel:

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

CRDTs sind eine weitere Technik, um den Zustand in kollaborativen Echtzeit-Anwendungen zu verwalten. Sie gehen anders vor: Jede Änderung kann unabhängig zum selben Endergebnis zusammenlaufen, egal in welcher Reihenfolge sie angewendet wird. Das macht CRDTs besonders robust in Umgebungen mit häufigen Netzwerkstörungen.

CRDTs spielen ihre Stärke aus, wenn Latenz mehr ist als ein kleines Ärgernis. Denk an die Arbeit im Zug mit wackeliger Internetverbindung. Jede Aktion in einem CRDT-System ist so ausgelegt, dass sie sich unabhängig zusammenführen lässt, ohne sofort einen zentralen Server zu fragen. Nutzer können also offline weiterarbeiten und sich nach dem Wiederverbinden nahtlos abgleichen, ohne Angst, dass ihre Änderungen Inkonsistenzen auslösen.

Konzepte

Einfaches Implementierungsbeispiel

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

Fazit

Mir hat es Spaß gemacht zu erkunden, wie diese Konzepte funktionieren. Wir sind heute zwar extrem vernetzt, aber Anwendungen müssen mit dieser Komplexität trotzdem gut umgehen, sonst leidet die User Experience.

In der Praxis würde ich natürlich kein einzelnes String-Feld für den Zustand verwenden. Ich wollte dir nur zeigen, wie es in der Praxis aussehen könnte.

Außerdem würde ich versuchen, die Anwendungsschicht nicht für die Verarbeitung von Zustandsänderungen zu nutzen. Möglich ist es, aber ich weiß nicht, wie sich das auf die ACID-Konformität der Datenbank auswirkt, wenn mehrere Clients ständig Updates schicken. Vielleicht kann eine Queue das auffangen.

Ich habe ein paar Tools ausprobiert, die mir geholfen haben zu verstehen, wie das Ganze funktioniert. Ich hoffe, sie helfen dir auch.

• Firepad
• Convergence
• Etherpad

Danke

Ein großes Dankeschön an Tuhin Banerjee auf Medium. Sein Beitrag hat mir beim Einstieg in meine eigene Implementierung geholfen.