Представьте: вы и коллега в разных уголках планеты, но курсоры ваши встречаются в документе онлайн-редактора. Вы одновременно вставляете слова в одну и ту же позицию или удаляете фрагмент текста, который ваш коллега в этот момент редактирует. Казалось бы, результат должен превратиться в хаос, но всё складывается в единую, логичную версию текста — несмотря на расстояния, задержки и одновременные правки. При этом вы даже не ждете, пока ваши изменения согласуются с общим состоянием на сервере. Просто редактируете документ и можете быть уверены в том, что ваши изменения применятся.

На деле за этим волшебством часто скрываются CRDT — структуры данных, делающие возможной децентрализованную синхронизацию. Я сам столкнулся с этим, когда работал над онлайн-совместным редактором: CRDT и библиотека Yjs буквально спасли мой проект от хаоса и сделали синхронизацию прозрачной.

Меня зовут Никита Лыкосов, я занимаюсь фронтенд-разработкой в Doubletapp и предлагаю шаг за шагом разобраться, как устроена эта инженерная магия. Спойлер: это гораздо проще, чем кажется.

G-Counter — самый простой CRDT

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

Сначала Вася насчитал 5 белых кошек, Настя — 5 чёрных. Они смотрят друг на друга и складывают свои числа — всего во дворе 10 кошек.

После этого каждый продолжает считать своих кошек: Вася добавляет ещё 3 белых, Настя — ещё 2 чёрных.

Через некоторое время они снова сверяют свои записи и складывают результаты: теперь у Васи 8 белых, у Насти 7 черных, итого 15 кошек.

Их совместный итог всегда получается правильным, независимо от того, как часто и в каком порядке они сверяются. Такой подход лежит в основе самого простого CRDT — распределённого счётчика, который называется G-Counter.

G-Counter — распределенный счётчик, который умеет только увеличиваться. Каждый участник системы ведёт свой собственный счёт, а при обмене данными с другими участниками объединяет состояния. Вот как это выглядит на JS:

class GCounter {
  constructor(id) {
    this.id = id;
    this.state = { [id]: 0 };
  }

  inc() {
    this.state[this.id] += 1;
  }

  getValue() {
// сумма всех счетчиков в state
    return Object.values(this.state).reduce((a, b) => a + b, 0);
  }

  merge(counter) {
// объединяем все счетчики 2 g-counter в текущий state. Если они уже есть берем с большим значением
    for (const key in counter.state) {
      this.state[key] = Math.max(this.state[key] || 0, counter.state[key]);
    }
  }
}

Каждый участник хранит свою копию счётчика и может увеличивать только своё значение. При обмене состояниями любые две реплики просто сливают свои данные, беря максимум по каждому идентификатору. Итоговая сумма всегда будет одинаковой на всех участниках, независимо от порядка и количества слияний, и даже если будет дупликация данных, итог не изменится.

Какие правила CRDT выполняются на примере G-Counter и зачем это нужно?

CRDT (Conflict-free Replicated Data Type, бесконфликтный реплицируемый тип данных) — это просто структура данных, которая обладает следующими свойствами:

Коммутативность

merge(“Вася”, “Настя”) и merge(“Настя”, “Вася”) дают одинаковый результат. Например, если у двух участников такие состояния:{“Вася”: 2, “Настя”: 0} и {“Вася”: 1, “Настя”: 3}, после объединения у обоих будет {“Вася”: 2, “Настя”: 3} — не важно, кто первым отправил данные.

const counterVasia = new GCounter(“Вася”);
const counterNastia = new GCounter(“Настя”);

counterVasia.inc(); // {“Вася”: 1} 
counterNastia.inc(); // {“Настя”: 1}

counterVasia.merge(counterNastia);
counterNastia.merge(counterVasia);

console.log(counterVasia.getValue()); // {“Вася”: 1, “Настя”: 1} = 2
console.log(counterNastia.getValue()); // {“Настя”: 1, “Вася”: 1} = 2

Ассоциативность

Можно объединять состояния по парам в любом порядке: merge(merge(“Вася”, “Настя”), “Егор”) равно merge(“Вася”, merge(“Настя”, “Егор”)). Это важно, если участников больше двух — результат всё равно совпадает.

const counterVasia = new GCounter(“Вася”);
const counterNastia = new GCounter(“Настя”);
const counterEgor = new GCounter(“Егор”);

counterVasia.inc(); // {“Вася”: 1} 
counterVasia.inc(); // {“Вася”: 2}
counterEgor.inc(); // {“Егор”: 1}

// {“Вася”: 2, “Настя”: 0, “Егор”: 1}
const val1 = counterEgor.merge(counterNastia.merge(counterVasia)).getValue() 
// {“Настя”: 1, “Вася”: 2, “Егор”: 0}
const val2 = counterEgor.merge(counterVasia.merge(counterNastia)).getValue()

console.log(val1 === val2) // 2 = 2

Идемпотентность

Если несколько раз объединить одно и то же состояние merge(“Вася”, “Вася”), ничего не изменится. Например, если участник случайно получит дубликат состояния, итоговая сумма не увеличится.

const counterVasia = new GCounter(“Вася”);

const counterNastia = new GCounter(“Настя”);
counterNastia.inc(); // “Вася”: 0, “Настя”: 1

counterVasia.merge(counterVasia.state);
console.log(counterNastia.getValue()); // 1
counterVasia.merge(counterVasia.state);
console.log(counterNastia.getValue()); // 1

Давайте разберёмся, как эти три свойства помогают Васе и Насте всегда получать одинаковый результат, даже если они считают кошек независимо друг от друга и обмениваются результатами в разном порядке.

• Коммутативность означает, что если Вася сначала сложит свои данные с Настиными, а потом Настя — с Васиными или наоборот, итоговое число кошек будет одинаковым. 

• Ассоциативность позволяет добавлять к подсчетам третьего участника (например, Егора), и не важно, в какой последовательности объединять их результаты: Вася с Настей, потом с Егором, или сначала Настя с Егором, а потом с Васей — итоговая сумма всегда совпадает.

• Идемпотентность защищает от ошибок, если Вася и Настя случайно несколько раз обменяются одними и теми же данными. Даже если Вася дважды объединит свои записи с Настиными, общее число кошек не увеличится — результат останется корректным.

Всё это вместе означает, что Вася, Настя (и даже Егор) могут обмениваться своими подсчётами сколько угодно раз и в любом порядке, и у всех всегда получится одно и то же число кошек. Именно поэтому такие счётчики, как G-Counter, прекрасно работают в распределённых системах: согласованность достигается автоматически, без центрального контроля и сложных согласований между участниками. Поэтому CRDT смело заявляет о сходимости структуры к одному состоянию. Благодаря этому мы можем уверенно использовать CRDT в распределённых системах, где согласованность достигается сама собой.

Массивы

Теперь, когда мы поняли, как устроены CRDT-структуры, давайте попробуем сделать что-то сложнее. Рассмотрим, как нам сделать CRDT-массив (или текст).

В массивах важен не только набор элементов, но и их порядок. Если кто-то из участников вставил или удалил символ раньше вас, ваш индекс уже «уехал» и больше не соответствует ожидаемой позиции.

 Решение — структура RGA (Replicated Growable Array):

•  Каждый элемент получает уникальный идентификатор.

•  Вставка происходит не по индексу, а после конкретного элемента (по его id).

•  Удаление реализовано через специальную пометку, а не физическое удаление.

class RGAElement {
  constructor(id, value, deleted = false) {
    this.id = id; // уникальный id (например, [время, id пользователя])
    this.value = value;
    this.deleted = deleted;
    this.next = [];
  }
}

class RGA {
  constructor() {
    this.elements = {}; // id -> RGAElement
    this.head = new RGAElement('head', null);
    this.elements['head'] = this.head;
  }

  insert(afterId, id, value) {
    const elem = new RGAElement(id, value);
    this.elements[id] = elem;
    this.elements[afterId].next.push(id);
  }

  delete(id) {
    if (this.elements[id]) {
      this.elements[id].deleted = true;
    }
  }

  // обход для получения текста
  toText() {
    const traverse = (id) => {
      let res = '';
      for (const nextId of this.elements[id].next) {
        if (!this.elements[nextId].deleted) {
          res += this.elements[nextId].value;
        }
        res += traverse(nextId);
      }
      return res;
    };
    return traverse('head');
  }
  merge(externalRGA) {
    for (const externalId in externalRGA.elements) {
      if (!this.elements[externalId]) {
        const externalElem = externalRGA.elements[externalId];
        // Вставляем отсутствующий элемент
		const elem = new RGAElement(externalElem.id, externalElem.value);
	    this.elements[externalElem.id] = elem;
        // Обновляем статус удаления
        if (externalElem.deleted) {
          this.delete(externalId);
        }
      }
    }
    
    // Обновляем связи next с сортировкой по ID
    for (const id in this.elements) {
      const elem = this.elements[id];
      elem.next = [...new Set([...elem.next, ...(externalRGA.elements[id]?.next || [])])]
        .sort((a, b) => a < b ? -1 : a > b ? 1 : 0 );
    }
  }
}

После выполнения операции слияния (merge) каждый массив next всегда будет отсортирован в одном и том же порядке. Это гарантирует то, что мы заранее знаем, в какую ветку графа необходимо спуститься первой. 

Получение текста из такой структуры можно представить как классический обход графа в глубину (DFS), с тем отличием, что порядок обхода ветвей заранее определён благодаря сортировке.

Рассмотрим пример: изначально в структуре хранится слово «привет». Затем три пользователя добавили свои ветки: «мир», «Вася» и «пока». После этого кто-то добавил «!» после «мир». В результате, в массиве next у буквы «т» из слова «привет» появляется три элемента. При обходе графа мы следуем порядку, установленному на этапе слияния.

Таким образом, при восстановлении текста мы получим следующую последовательность:

«приветмир!Васяпока»

Итак, что мы получили: благодаря уникальным идентификаторам и сортировке связей, структура RGA позволяет всем участникам видеть один и тот же текст после слияния изменений — независимо от порядка и времени действий. При этом мы по-прежнему сохраняем ключевые свойства CRDT: коммутативность, ассоциативность и идемпотентность. Это значит, что результат объединения всегда будет одинаковым, независимо от порядка, группировки или повторения операций. Всё это обеспечивает автоматическое разрешение конфликтов и делает совместное редактирование предсказуемым и надежным.

Yjs: как устроено совместное редактирование на практике

Из всех библиотек, реализующих CRDT, мне больше всего понравилась Yjs — из-за производительности. На это решение сильно повлияла вот эта статья, советую ознакомиться, если будете решать, какую реализацию брать себе в проект.   

Основные структуры данных Yjs (Shared Types)

Yjs абстрагирует низкоуровневую логику CRDT через концепцию Shared Types. Это привычные структуры данных JavaScript, такие как Map или Array, но с «суперспособностями»: любые изменения, внесенные в них, автоматически распределяются между другими пирами и объединяются без конфликтов.

• Y.Text: это основной Shared Type для работы с текстом. Он поддерживает как обычный, так и форматированный (rich text) текст.

• Y.Array: используется для упорядоченных списков элементов.

• Y.Map: для ключ-значение пар, где при конфликте последнее записанное значение для ключа «побеждает».

• Также существуют более специализированные типы, такие как Y.XmlElement, Y.XmlFragment и Y.XmlText, которые обычно используются для создания сложных rich-text редакторов (например, на базе ProseMirror или Quill).

Экосистема Yjs

Yjs не привязан к конкретному протоколу. Существуют готовые провайдеры для различных сценариев: y-websocket для клиент-серверной архитектуры, y-webrtc для полностью P2P-синхронизации без центрального сервера, а также интеграции с другими протоколами. Эта гибкость позволяет выбрать наиболее подходящую архитектуру для приложения. Также его поддерживают некоторые WYSIWYG-редакторы из коробки, к примеру, lexical. По моему опыту, часто не хватает нужного функционала, так что в моем проекте от y-websocket осталась только пара строк, а все остальное было переписано.

Пример синхронизации

import * as Y from 'yjs'

// Документы Yjs — это коллекции
// общих объектов, которые синхронизируются автоматически.
const ydoc = new Y.Doc()
// Определяем общий экземпляр Y.Map
const ymap = ydoc.getMap()
ymap.set('keyA', 'valueA')

// Создаём другой документ Yjs (симуляция удалённого пользователя)
// и создаём некоторые конфликтующие изменения
const ydocRemote = new Y.Doc()
const ymapRemote = ydocRemote.getMap()
ymapRemote.set('keyB', 'valueB')

// Объединяем изменения с удалённого документа
const update = Y.encodeStateAsUpdate(ydocRemote)
Y.applyUpdate(ydoc, update)

// Можно заметить, что изменения были объединены
console.log(ymap.toJSON()) // => { keyA: 'valueA', keyB: 'valueB' }

Заключение

Мы разобрались, как CRDT обеспечивают согласованность данных в распределённых системах без центрального сервера — от простого G-Counter до механизмов совместного редактирования текста. Yjs берёт на себя всю эту сложность, предоставляя удобные Shared Types, которые позволяют вам легко создавать коллаборативные приложения.

CRDT — мощное решение для любых задач, требующих синхронизации без конфликтов. Если вы столкнулись с подобными вызовами, Yjs может стать тем инструментом, который сделает вашу разработку намного проще и эффективнее.

Попробуйте Yjs в своём проекте – это проще, чем кажется!

Doubletapp имеет практический опыт внедрения CRDT и Yjs в фронтенд-проекты — от настройки клиентской синхронизации до интеграции с существующими архитектурами. Готовы помочь с оценкой применимости подхода, адаптацией библиотек и построением устойчивой клиентской логики. Если вы ищете надёжного технологического партнёра — обращайтесь, будем рады обсудить ваш проект.