Реализация CRDT для конфликт-свободной синхронизации в мобильном приложении

Реализация CRDT для конфликт-свободной синхронизации в мобильном приложении

CRDT (Conflict-free Replicated Data Types) — математически гарантируют, что любые два реплики одного документа, получив одни и те же операции в любом порядке, придут к идентичному состоянию. Без координирующего сервера. Без разрешения конфликтов вручную.

Для мобильных приложений это особенно ценно: пользователь редактирует в метро (офлайн), синхронизируется дома (онлайн), партнёр делал то же самое — merge происходит автоматически и детерминировано.

Что такое CRDT на практике

Не один алгоритм, а семейство структур данных. Каждая решает свою задачу:

• G-Counter — счётчик, который только растёт. Merge = max по каждому узлу.
• LWW-Register (Last-Write-Wins) — одно значение, побеждает последнее по timestamp. Подходит для отдельных полей (название документа, статус).
• OR-Set (Observed-Remove Set) — множество с add и remove. Решает проблему «удалил, а партнёр добавил одновременно» через уникальные теги для каждого add-операции.
• RGA (Replicated Growable Array) — массив с insert/delete. Основа для текстового CRDT.
• YATA (Yet Another Transformation Approach) — алгоритм Y.js, разновидность RGA.

Y.js: детальный разбор

Y.js — наиболее зрелая реализация CRDT для JavaScript/TypeScript. Использует YATA-алгоритм для YText и YArray, LWW для YMap.

Внутренняя структура YText: связный список элементов (Item), каждый с id: {client, clock}. client — уникальный clientID (uint32, генерируется при создании Y.Doc). clock — логические часы, монотонно растут для каждого клиента. Merge двух YDoc = объединение всех Item с детерминированным порядком при конфликтах (меньший clientID идёт первым при одинаковом логическом времени).

Ключевое: операция никогда не теряется. Даже если insert произошёл офлайн на одном устройстве, а другое устройство одновременно удалило текст вокруг — insert применится, может оказаться в «пустом» месте, но не потеряется.

Провайдеры синхронизации в Y.js

Y.js — только алгоритм. Транспорт — отдельный провайдер:

Для мобильного приложения: y-websocket для онлайн-синхронизации + кастомный провайдер для SQLite (персистентность на устройстве). Готового y-sqlite для React Native нет — реализуем через Y.encodeStateAsUpdate() и Y.applyUpdate() с сохранением в react-native-sqlite-storage.

// Сохранение в SQLite при каждом изменении
ydoc.on('update', (update, origin) => {
  if (origin !== 'sqlite') {  // не сохраняем изменения из SQLite
    const state = Y.encodeStateAsUpdate(ydoc);
    db.executeSql('INSERT OR REPLACE INTO docs (id, state) VALUES (?, ?)',
      [docId, Buffer.from(state).toString('base64')]);
  }
});

// Загрузка при открытии документа
const [result] = await db.executeSql('SELECT state FROM docs WHERE id = ?', [docId]);
if (result.rows.length > 0) {
  const state = Buffer.from(result.rows.item(0).state, 'base64');
  Y.applyUpdate(ydoc, new Uint8Array(state), 'sqlite');
}

Automerge: альтернатива Y.js

Automerge — CRDT-библиотека с другим подходом: документ — это JSON-объект с deep merge семантикой. Automerge 2.x переписан на Rust, скомпилирован в WASM — производительность на порядок выше первой версии.

Для React Native: @automerge/automerge работает через WASM в JSC/Hermes. На Hermes — нужно проверить поддержку WASM (в последних версиях RN Hermes поддерживает WASM, но не все билды).

Преимущество Automerge перед Y.js: схема данных — обычный JSON, не специальные типы. Минус: Y.js активнее поддерживается, больше провайдеров синхронизации.

Векторные часы и detection конфликтов

Y.js автоматически отслеживает stateVector — map из {clientId: maxClock}. При синхронизации двух реплик:

1. Обмениваемся stateVector.
2. Запрашиваем Y.encodeStateAsUpdateV2(ydoc, remoteStateVector) — дельта от того, что удалённая сторона ещё не знает.
3. Применяем полученную дельту через Y.applyUpdateV2().

Это эффективная синхронизация без передачи всего документа. При переподключении после офлайна: отправляем свой stateVector, получаем только недостающие изменения.

Конвергентность: что гарантируют, чего нет

CRDT гарантирует Strong Eventual Consistency: если все реплики получили одни и те же операции — они сходятся к идентичному состоянию.

Не гарантируется: семантическая корректность. Если пользователь A переименовал файл в "Report Q1", а пользователь B одновременно удалил этот файл — CRDT может восстановить файл с новым именем. Это математически правильно (add побеждает remove в OR-Set), но семантически может быть неожиданно для пользователя.

Решение: UX-слой, который показывает пользователю факт конфликта и его автоматическое разрешение. Не ломать работу, но дать информацию.

Производительность с большими документами

Y.js lazy-загружает структуру документа: части, которые не были запрошены, не декодируются. Для документов 1MB+ — важно. Y.Doc с gc: true (по умолчанию) автоматически удаляет tombstone-записи удалённых элементов, сжимая историю.

При большом количестве правок история операций разрастается. Y.encodeStateAsUpdate() содержит все изменения с момента создания. Компакция через Y.encodeStateAsUpdate(ydoc, emptyStateVector) — snapshot текущего состояния без истории. Для офлайн-приложений: хранить snapshot + delta после snapshot.

Оценка

CRDT-синхронизация через Y.js для text/JSON документов в React Native — 6–10 недель (включая персистентность, reconnect-логику, conflict awareness UI). Для Flutter через Dart-биндингов к Y.js (через JS runtime) или нативного CRDT — 10–16 недель. Automerge 2 на Rust FFI для нативных платформ — 12–20 недель.