Реалізація CRDT для безконфліктної синхронізації в мобільному додатку

Реалізація CRDT для конфлікт-свободної синхронізації в мобільному додатку

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

Для мобільних додатків це особливо цінно: користувач редагує в метро (offline), синхронізується дома (online), партнер робив то ж саме — 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 сталась offline на одному пристрої, а інший одночасно видалив текст навколо — insert застосується, може опинитися в «порожньому» місці, але не втратиться.

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

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

Для мобільного додатка: y-websocket для online-синхронізації + кастомний провайдер для 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().

Ефективна синхронізація без передачі всього документа. При переподключенні після offline: відправляємо свій 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 поточного стану без історії. Для offline-додатків: зберігати 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 тижнів.