CRDT - Conflict-free Replicated Data Types

Цели урока

• Понимать, почему обычные структуры данных не работают при конкурентных обновлениях
• Реализовывать G-Counter, PN-Counter, LWW-Register, OR-Set
• Различать CvRDT и CmRDT и выбирать подходящий тип
• Знать реальные системы, использующие CRDT (Redis, Figma, Automerge)

Предварительные знания

• Eventual consistency и CAP-теорема (урок ds-02-cap-theorem)
• Логические часы и Lamport timestamps (урок ds-04-clocks)
• Базовое понимание репликации и конфликтов при multi-master

Figma позволяет 10 дизайнерам редактировать один файл одновременно без конфликтов. Apple Notes синхронизирует изменения между iPhone и Mac без серверного арбитра. Под капотом - математика CRDT: коммутативные операции с гарантией сходимости.

• **Redis Enterprise** - G-Counter и PN-Counter для Active-Active репликации между дата-центрами на разных континентах без блокировок
• **Figma** - custom document CRDT для collaborative editing: позиции, цвета, слои сливаются без конфликтов
• **Apple iCloud / Notes** - CRDT для синхронизации между устройствами офлайн и онлайн
• **Automerge/Yjs** - библиотеки JSON CRDT, используемые в Linear, Actual Budget, Obsidian Sync
• **Amazon Shopping Cart** - исторически один из первых примеров AP + CRDT-подобной семантики (Dynamo Paper 2007)

Рождение CRDT: Shapiro и Preguica, 2011

Термин CRDT появился в статье Марка Шапиро и Нуно Прегика (INRIA, 2011): "Conflict-free Replicated Data Types". Авторы формализовали условия, при которых структура данных гарантирует eventual consistency без координации. До этого похожие идеи использовались в Dynamo (Amazon, 2007) и Bayou (Xerox PARC, 1994), но без единой математической основы. Сегодня CRDT лежат в основе collaborative tools, используемых сотнями миллионов людей ежедневно.

Проблема конкурентных обновлений

**Figma, 2020. 2 пользователя одновременно редактируют один слой: один меняет цвет, второй - позицию. Сервер получает оба изменения с разницей в 3 мс. Чьё изменение правильное?** Традиционный ответ - "последний записал": один из дизайнеров теряет работу. Figma решила эту задачу через CRDT - структуры данных, которые сливаются без конфликтов математически.

**CRDT (Conflict-free Replicated Data Type)** - структура данных с гарантией: любые два узла, получившие одинаковый набор операций (в любом порядке), придут к одинаковому состоянию. Без координирующего сервера, без блокировок.

Обычный счётчик при конкурентном обновлении ломается: узел A читает значение 5, прибавляет 1, пишет 6. Узел B читает то же значение 5, прибавляет 1, пишет 6. После синхронизации счётчик равен 6 вместо 7. Одна операция потеряна.

Результат без CRDT: счётчик равен 6, хотя было выполнено два инкремента от 5. Одна операция потеряна навсегда.

G-Counter и PN-Counter: счётчики без конфликтов

**G-Counter (Grow-only Counter)** - первый CRDT, понятный интуитивно. Вместо одного значения каждый узел хранит свой собственный счётчик. Глобальное значение - сумма всех. При слиянии берётся max по каждому узлу.

G-Counter обладает тремя математическими свойствами: **коммутативность** (merge(A,B) = merge(B,A)), **ассоциативность** (merge(merge(A,B),C) = merge(A,merge(B,C))), **идемпотентность** (merge(A,A) = A). Из этих трёх следует eventual consistency.

G-Counter умеет только расти. Для полноценного счётчика с декрементом используют **PN-Counter (Positive-Negative Counter)** - два G-Counter: один для инкрементов, второй для декрементов.

LWW-Register и OR-Set: регистр и множество

**LWW-Register (Last-Writer-Wins Register)** - CRDT для одиночного значения. При конкурентных записях побеждает та, у которой timestamp больше. Простота подкупает - но именно здесь часто ошибаются.

LWW с Date.now(): если часы двух узлов расходятся на 100 мс (реально в AWS multi-AZ), более поздняя запись с отставшими часами будет потеряна. Google Spanner решает это через GPS+атомные часы. В обычных системах используют HLC (Hybrid Logical Clock) из урока о логических часах.

**OR-Set (Observed-Remove Set)** решает классическую проблему: что происходит когда add и remove одного элемента происходят одновременно на разных узлах? Каждая операция add получает уникальный тег. Remove удаляет только наблюдаемые теги - те, которые уже были известны узлу в момент remove.

**Семантика OR-Set при конфликте:** Node A делает add(apple) одновременно с тем, как Node B делает remove(apple). После merge - apple присутствует. Побеждает add. Это интуитивно: кто-то добавил элемент, не зная об удалении - его намерение сохранено.

CvRDT, CmRDT и реальные применения

**Теория CRDT делит все структуры на два класса.** CvRDT (state-based) передают полное состояние при синхронизации - merge гарантирует сходимость. CmRDT (operation-based) передают только операции - нужен reliable broadcast. Все примеры выше - CvRDT.

**CRDT vs OT (Operational Transformation):** Google Docs использует OT - более старый подход, требующий центрального сервера для упорядочивания операций. CRDT работает без центра. Именно поэтому Figma, Apple и новые collaborative tools переходят на CRDT.

Вопросы для размышления

• Система хранит рейтинг продукта как сумму оценок пользователей. Пользователей миллионы, оценки приходят из 5 дата-центров параллельно. Какой CRDT подходит и какие трейдофы он несёт?

Связанные уроки

• ds-08-vector-clocks — CRDTs rely on vector clocks for conflict tracking
• ds-09-gossip-protocols — Gossip disseminates CRDT state across replicas
• dist-12-consistency — CRDTs provably achieve eventual consistency
• dist-11-replication — CRDT-based replication avoids coordination overhead
• crypto-04-algebraic-structures