Реалізація Operational Transform (OT) для real-time collaboration у мобільному додатку

Реалізація Operational Transform для 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 вимагає сервер-координатор. Схема:

Клієнт A ──→ Сервер ──→ Клієнт B
   ↑             │           │
   └─────────────┘           │
      ACK + revision         │
                             ↓
                   Клієнт 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-документах — корисно для структурованих даних (не тільки текст).

Клієнт 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 вибираємо, коли: потрібна строга історія операцій, вже є сервер-координатор, offline не потрібен. CRDT — коли важлив offline-режим та P2P синхронізація.

Оцінка

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