CRDT

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

История

Концепция CRDT была впервые формально описана в 2011 году в работе «Conflict-free Replicated Data Types» (Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski). Однако предшествующие идеи и реализации существовали и ранее. Например, в 1980-х годах в системах групповой работы (Lotus Notes) применялись реплицируемые списки и счётчики, которые можно считать прототипами CRDT. В 2000-х годах развитие получили алгоритмы для совместного редактирования текста в реальном времени (например, в системе Google Wave, где использовалась операционная трансформация, OT). CRDT стали альтернативой операционной трансформации, предлагая более простую модель сходимости без необходимости в центральном сервере или сложной логике разрешения конфликтов.

Классификация

CRDT делятся на два основных типа в зависимости от способа обеспечения сходимости:

CRDT на основе операций (Operation-based CRDT, O-CRDT)

При каждом изменении данных на узле генерируется операция (например, «добавить элемент», «удалить элемент»), которая отправляется всем остальным узлам. Каждый узел применяет полученные операции в порядке их получения. Для обеспечения сходимости операции должны быть коммутативными (порядок применения не влияет на результат) или идемпотентными (повторное применение той же операции не меняет состояние). Пример: реплицируемый счётчик, где операция «увеличить на 1» коммутативна.

CRDT на основе состояния (State-based CRDT, CvRDT)

Каждый узел периодически отправляет своё полное состояние (или его сжатое представление) другим узлам. При получении состояния узел объединяет его со своим текущим состоянием с помощью операции слияния (merge). Операция слияния должна быть коммутативной, ассоциативной и идемпотентной (образовывать полурешётку). Пример: реплицируемый регистр (Last-Writer-Wins Register), где слияние выбирает значение с наибольшей временной меткой.

Основные виды CRDT

Реплицируемый счётчик (G-Counter, PN-Counter)

• G-Counter (Grow-only Counter): может только увеличиваться. Каждый узел хранит свой локальный счётчик. При слиянии берётся максимум по каждому узлу. Итоговое значение — сумма всех локальных счётчиков.
• PN-Counter (Positive-Negative Counter): позволяет как увеличивать, так и уменьшать значение. Реализуется как два G-Counter: один для положительных изменений, другой для отрицательных. Итоговое значение — разность между ними.

Реплицируемый регистр (Register)

• LWW-Register (Last-Writer-Wins Register): хранит значение и временную метку (например, логические часы). При слиянии выбирается значение с наибольшей временной меткой. При равенстве меток — значение с наибольшим идентификатором узла.
• MV-Register (Multi-Value Register): хранит набор значений, которые были установлены одновременно (конфликтующие). При слиянии все конфликтующие значения сохраняются. Пример: в системе Amazon DynamoDB используется для разрешения конфликтов при записи.

Реплицируемый набор (Set)

• G-Set (Grow-only Set): только добавление элементов. Удаление невозможно.
• 2P-Set (Two-Phase Set): состоит из двух G-Set: один для добавленных элементов, другой для удалённых. Элемент считается присутствующим, если он есть в первом наборе и нет во втором. Недостаток: нельзя повторно добавить удалённый элемент.
• OR-Set (Observed-Remove Set): решает проблему повторного добавления. Каждый элемент хранится с уникальным тегом (например, UUID). При удалении удаляются только те теги, которые были «увидены» узлом на момент удаления. Это позволяет повторно добавить элемент с новым тегом.

Реплицируемый список (List)

• RGA (Replicated Growable Array): используется для совместного редактирования текста. Каждый символ (или элемент) хранится с уникальным идентификатором и позицией в списке (например, в виде дерева или с помощью дробных индексов). Вставка и удаление элементов производятся с помощью операций, которые коммутативны. RGA является основой для многих систем совместного редактирования, таких как Yjs.

Применение

CRDT нашли широкое применение в областях, где требуется совместная работа в реальном времени или офлайн-режим:

• Совместное редактирование документов: Google Docs, Notion, Obsidian (с плагинами), Etherpad, и многие другие редакторы используют CRDT (или операционную трансформацию) для синхронизации изменений между пользователями.
• Базы данных: системы, работающие в режиме «все-на-все» (multi-master), например, Riak, Redis (с модулем CRDT), Cosmos DB (Azure) используют CRDT для разрешения конфликтов при репликации.
• Системы управления версиями: Git использует DAG (направленный ациклический граф) коммитов, который по своей сути является CRDT-подобной структурой для слияния веток.
• Мессенджеры и чаты: протоколы для синхронизации сообщений в офлайн-режиме (например, в Matrix) могут использовать CRDT для обеспечения согласованности.
• Распределённые системы управления конфигурациями: например, в Kubernetes для хранения состояния кластера (etcd использует Raft, а не CRDT, но концепция схожа).

Преимущества и недостатки

Преимущества

• Отсутствие центрального координатора: не требуется единый сервер, что повышает отказоустойчивость.
• Автоматическое разрешение конфликтов: не требуется ручное вмешательство пользователя.
• Офлайн-работа: изменения можно вносить локально, а затем синхронизировать при подключении к сети.
• Простота модели: математически доказанная сходимость.

Недостатки

• Избыточность данных: особенно для CRDT на основе состояния, где передаётся всё состояние или его большая часть.
• Сложность реализации: для некоторых типов данных (например, списков) требуется нетривиальная логика для обеспечения коммутативности.
• Проблема «мусора»: в некоторых CRDT (например, 2P-Set) удалённые элементы могут накапливаться, занимая память.
• Ограниченная выразительность: не все типы данных можно эффективно реализовать как CRDT (например, произвольные графы).

Сравнение с операционной трансформацией (OT)

Операционная трансформация (OT) — другой подход к совместному редактированию, исторически более ранний. Основные отличия:

• Механизм: OT требует центрального сервера, который преобразует (трансформирует) операции, чтобы они были применимы в любом порядке. CRDT не требует сервера.
• Сложность: OT сложнее в реализации, особенно при большом числе участников. CRDT проще математически, но может быть сложнее в реализации для некоторых типов данных.
• Производительность: OT может быть быстрее для небольших документов, но CRDT лучше масштабируется для больших документов с множеством участников.
• Офлайн-режим: CRDT естественно поддерживает офлайн-режим, OT требует дополнительных механизмов.

Известные реализации

• Yjs: библиотека на JavaScript, реализующая CRDT (RGA) для совместного редактирования текста. Используется в Notion, Obsidian, и других приложениях.
• Automerge: библиотека на JavaScript, реализующая CRDT на основе JSON. Используется в приложениях для совместной работы.
• Roshi: реализация CRDT на Go для хранения данных в распределённых системах.
• Redis CRDT: модуль для Redis, добавляющий поддержку CRDT-типов данных (счётчики, наборы, списки).

Интересные факты

• Термин «CRDT» был предложен в 2011 году, но сама идея бесконфликтной репликации использовалась в системах управления базами данных ещё в 1970-х годах (например, в системе Locus).
• В 2020 году компания Google объявила, что её внутренняя система для совместного редактирования документов (Google Docs) использует комбинацию OT и CRDT.
• CRDT лежат в основе протокола Matrix, используемого для децентрализованных мессенджеров (например, Element).

Источники

• Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). Conflict-free replicated data types.
• Baquero, C., & Moura, F. (2012). Using structural characteristics for autonomous operation.
• Yjs Documentation. (2023). Conflict-free Replicated Data Types.
• Automerge Documentation. (2023). CRDTs for collaborative applications.
• Redis CRDT Documentation. (2023). Conflict-free Replicated Data Types in Redis.