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

В этом сообщении блога мы углубимся в то, что такое CRDT, изучим их использование и типы, поймем, как они работают, и научимся их реализовывать, уделяя особое внимание JavaScript и мощной библиотеке Yjs.

Варианты использования CRDT

CRDT особенно полезны в сценариях, где решающее значение имеют сотрудничество в режиме реального времени и поддержка в автономном режиме:

1. Совместные текстовые редакторы: Google Docs, Notion и Etherpad используют структуры, подобные CRDT, для редактирования в реальном времени.
2. Инструменты совместного проектирования: Figma, популярный веб-инструмент проектирования, использует CRDT для обеспечения совместной работы над дизайнерскими проектами в режиме реального времени. Несколько дизайнеров могут одновременно работать над одним и тем же файлом, при этом изменения легко синхронизируются между всеми пользователями.
3. Распределенные базы данных: RxDB и Riak используют CRDT для бесконфликтной репликации.
4. Многопользовательские игры: для поддержания одинакового состояния игры между игроками.

Типы CRDT

Существует два основных типа CRDT:

1. CRDT на основе состояния: они копируют все состояние структуры данных. Слияние осуществляется путем сравнения и согласования состояний разных реплик.
2. CRDT на основе операций: они копируют операции, выполняемые со структурой данных. Слияние осуществляется путем коммутативного применения операций из разных реплик.

Как работают CRDT

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

Ключевые свойства

1. Коммутативность: это свойство гарантирует, что порядок операций не влияет на конечный результат. Например, в счетчике CRDT увеличение на 2, а затем на 3 дает тот же результат, что и увеличение на 3, а затем на 2.
2. Ассоциативность: это означает, что группировка операций не имеет значения. Снова используя пример счетчика, (1 2) 3 — то же самое, что 1 (2 3).
3. Идемпотентность: многократное применение одной и той же операции имеет тот же эффект, что и ее однократное применение. Это крайне важно для обработки повторяющихся сообщений в распределенных системах.

Разрешение конфликтов

CRDT автоматически разрешают конфликты:

• Для CRDT на основе состояния (CvRDT) это достигается за счет функции слияния, которая объединяет состояния двух реплик. Эта функция слияния должна быть коммутативной, ассоциативной и идемпотентной.
• Для CRDT, основанных на операциях (CmRDT), операции спроектированы так, чтобы быть коммутативными, гарантируя, что их применение в любом порядке приведет к одному и тому же конечному состоянию.

Логические часы

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

Использование CRDT в JavaScript с Yjs

Внедрение CRDT с нуля может оказаться сложной задачей. Однако существуют библиотеки, которые упрощают этот процесс. Для JavaScript одна из самых популярных CRDT-библиотек — Yjs. Это высокопроизводительная реализация CRDT, поддерживающая различные типы данных. Давайте создадим простое приложение списка дел, используя Yjs, имитирующее работу нескольких пользователей над одним и тем же документом в памяти.

Вот пример реализации общего списка задач с помощью Yjs:

Давайте воспользуемся созданными документами:

В этом примере мы создаем два документа Yjs (ydoc1 и ydoc2), чтобы имитировать двух пользователей, работающих над одним списком задач. Каждый документ имеет собственную общую карту задач.

Мы определяем функции для добавления, обновления и удаления задач, а также функцию syncDocs для ручной синхронизации состояния между двумя документами. Это моделирует то, что произойдет в сетевой среде, где между клиентами происходит обмен обновлениями.

Заключение

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

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

1. Да
2. CRDT
3. Tiptap — текстовый редактор для совместной работы