Реализация Operational Transform (OT) для real-time collaboration в мобильном приложении

Реализация Operational Transform (OT) для real-time collaboration в мобильном приложении

Operational Transform — алгоритм, на котором работают Google Docs, Notion, Etherpad. Не абстракция, а конкретная математика: каждое изменение документа — это операция (insert(pos, text) или delete(pos, len)), которая трансформируется относительно конкурентных операций так, чтобы все клиенты пришли к одному результату.

Понять OT важно не только для реализации с нуля, но и для осознанного выбора между OT и CRDT.

Суть проблемы, которую решает OT

Два пользователя редактируют документ "hello":

• Пользователь A: insert(5, " world") → "hello world"
• Пользователь B одновременно: delete(0, 5) → ""

Если просто применить обе операции в любом порядке — результаты разойдутся. OT трансформирует операцию A с учётом операции B:

• transform(insert(5, " world"), delete(0, 5)) → insert(0, " world") (позиция сдвигается, т.к. 5 символов удалено перед ней)

Результат: " world" — одинаков на обоих клиентах.

Серверная архитектура OT

OT требует сервер-координатор. Схема:

Client A ──→ Server ──→ Client B
   ↑             │           │
   └─────────────┘           │
        ACK + revision       │
                             ↓
                   Client B трансформирует
                   свои pending операции

Сервер хранит историю операций с номерами ревизий. Клиент отправляет операцию с номером базовой ревизии (от которой сформирована операция). Сервер трансформирует входящую операцию относительно операций, применённых после этой ревизии, применяет, возвращает клиенту подтверждение и рассылает всем трансформированную операцию.

Клиент хранит:

• revision — последняя подтверждённая ревизия от сервера
• pending — операция, отправленная, но не подтверждённая
• buffer — операции, введённые пока pending ещё не подтверждена

При получении серверной операции: если у клиента есть pending, нужно взаимно трансформировать серверную операцию и клиентскую через transform(client, server) и transform(server, client).

Алгоритм трансформации для текста

Для текстовых операций трансформация — это корректировка позиций:

transform(insert(p1, s1), insert(p2, s2)):
  if p1 < p2: return insert(p1, s1)  // позиция не меняется
  if p1 > p2: return insert(p1 + len(s2), s1)  // сдвигаем вправо
  if p1 == p2: return insert(p1, s1)  // tie-breaking по userId

transform(insert(p1, s1), delete(p2, len2)):
  if p1 <= p2: return insert(p1, s1)
  if p1 >= p2 + len2: return insert(p1 - len2, s1)
  else: return insert(p2, s1)  // вставка была внутри удалённого диапазона

Для форматирования (rich text) трансформация сложнее — операции на атрибуты имеют свою семантику.

Библиотеки: ot.js, sharedb

ot.js — чистый JavaScript OT-движок для простого text type. Работает в React Native без модификаций. Реализует compose и transform операций. Не включает транспорт.

ShareDB — полноценный фреймворк: OT-движок + WebSocket сервер + клиент. Поддерживает pluggable типы операций (json0, rich-text, кастомные). json0 позволяет делать OT на JSON-документах — полезно для структурированных данных (not just text).

Клиент ShareDB для React Native:

import ReconnectingWebSocket from 'reconnecting-websocket';
import ShareDB from 'sharedb/lib/client';

const socket = new ReconnectingWebSocket('wss://server.com/sharedb');
const connection = new ShareDB.Connection(socket);
const doc = connection.get('documents', documentId);

doc.subscribe(() => {
  doc.on('op', (op, source) => {
    if (!source) {
      // удалённая операция — обновляем UI
      applyOpToEditor(op);
    }
  });
});

ReconnectingWebSocket — важен для мобиля: при смене сети (Wi-Fi → 4G) автоматически переподключается и восстанавливает синхронизацию.

Composition: несколько операций в одну

При быстром наборе пользователь генерирует десятки операций в секунду. Батчинг: ot.js поддерживает compose(op1, op2) — объединение последовательных операций в одну. Отправляем compose-операцию каждые 50–100ms вместо каждой отдельной.

Условие для compose: операции должны быть последовательными (op2 применяется после op1). Если пришла серверная операция между op1 и op2 — compose уже нельзя, нужно трансформировать по отдельности.

OT vs CRDT: чем руководствоваться при выборе

OT выбираем, когда: нужна строгая история операций, уже есть сервер-координатор, офлайн не нужен. CRDT — когда важен офлайн-режим и P2P синхронизация.

Оценка

ShareDB-интеграция для текстового редактора на React Native — 6–10 недель (включая серверную часть). Если нужен JSON-документ OT (структурированные данные) — 10–16 недель. Реализация OT с нуля без ShareDB — не рекомендуем: алгоритм трансформации имеет граничные случаи, которые сложно протестировать.