Hacker News Digest

Алгоритм CRDT для совместного текста

Каждый символ получает уникальный id: site (идентификатор узла) и clock (локальный счётчик, увеличиваемый после каждой операции), а также parent — указатель на предыдущий символ.

• Вставка
  parent ставится на символ перед точкой вставки (null — в начало). Порядок символов задаётся прямым обходом дерева: родители идут раньше потомков.

• Сортировка при одинаковом parent
  Сначала по убыванию counter, затем по site. При вставке перед символом с тем же parent берём его counter + 1.

• Удаление
  id символа попадает в множество удалённых (tombstone). Значение можно забыть, но позиция нужна для корректного порядка.

Оптимизации

1. Последовательные вставки одного узла объединяются в блок: массовая вставка стоит как одна операция.
2. Блоки хранятся в отсортированном массиве; вставка — O(log n) без явного дерева.
3. Удаления группируются диапазонами по site и clock.

Плюсы и минусы

• Плюсы: разумный расход памяти, быстрые запросы/обновления.
• Минусы: сложная логика слияния, только рост метаданных, сборка мусора требует координации.

Интерактивный пример
Четыре пира, задержка сети, редактирование кликом. Исходник — crdt-text-buffer.js.

Полезные ссылки

• josephg.com/blog/crdts-go-brrr/ — эффективная реализация.
• archagon.net/blog/2018/03/24/data-laced-with-history/ — деревья и сборка мусора.