CRDT типы

Два пользователя одновременно кладут товар в корзину с разных устройств - у них разные данные и нет связи с сервером. Как корзина останется консистентной без единого lock-а?

• **Apple Notes** использует CRDT (OR-Set) для синхронизации заметок между iPhone и Mac: конкурентные правки без конфликтов слияния - в 2023 году это 600M+ устройств с offline-first редактированием.
• **Figma** хранит состояние canvas как CRDT-документ: 100+ пользователей редактируют одновременно, каждая операция применяется локально немедленно, синхронизация происходит фоново без блокировок - задержка восприятия < 50 мс.
• **Riak** (Basho) применяет G-Counter и PN-Counter для счётчиков метрик с 2010 года: 30 узлов, запись без координатора, merge при read-repair. Twitter использовал Riak для счётчиков tweet-ов до 2015 года при нагрузке 500K RPS.
• **Redis Enterprise Active-Active** строит реплицированные базы на OR-Set: корзины покупок в e-commerce реплицируются между регионами EU и US, конфликты add/remove разрешаются автоматически с семантикой add-wins.

G Counter

G-Counter (Grow-only Counter) - счётчик, который умеет только увеличиваться. Каждый узел кластера хранит свой локальный счётчик, а глобальное значение - сумма всех локальных. Узлы никогда не перезаписывают чужие значения: при merge берётся максимум по каждому узлу.

Riak использует G-Counter для подсчёта просмотров страниц с 2012 года: 30+ узлов пишут локально без координации, merge происходит при read-repair. Задержка записи - 1-2 мс против 15-20 мс при strong consistency.

Свойство CvRDT (state-based): merge коммутативен, ассоциативен и идемпотентен. Это гарантирует eventual consistency без координатора - любой порядок merge-ов даёт одинаковый результат.

Pn Counter

PN-Counter (Positive-Negative Counter) решает главный изъян G-Counter - невозможность декрементировать. Идея проста: два G-Counter под капотом. P-вектор накапливает все прибавления, N-вектор - все вычитания. Итоговое значение: sum(P) - sum(N).

SoundCloud применял PN-Counter для счётчиков лайков в 2015-2018: пользователи могли лайкать и убирать лайк без блокировок. При 40M активных пользователей это давало экономию ~120K координирующих запросов в секунду в пиковые часы.

Размер состояния PN-Counter растёт линейно с числом узлов: O(2N) числел. При 100 узлах это 1600 байт на счётчик - приемлемо. Но при 10K микросервисов передача состояния становится узким местом: тогда переходят на delta-CRDT (передают только изменения).

G Set

G-Set (Grow-only Set) - множество, из которого нельзя удалять элементы. Операция merge - объединение (union). Добавление элемента идемпотентно: повторное добавление не меняет состояние. Конфликтов при слиянии не бывает по определению.

Cloudflare использует G-Set для распространения конфигурационных правил WAF по 300+ дата-центрам: новое правило добавляется в центральный G-Set и реплицируется в любом порядке. Среднее время распространения - 35 секунд, без двухфазного коммита.

G-Set идеален для append-only журналов событий, списков участников вебинара, тегов контента - там где удаление либо не нужно, либо реализуется мягким способом (soft-delete через добавление элемента-маркера удаления в другой G-Set).

Or Set

OR-Set (Observed-Remove Set) решает проблему G-Set - добавляет поддержку удаления. Трюк: каждый элемент при добавлении получает уникальный тег (UUID). Удаление убирает конкретные теги, а не сам элемент. Если элемент добавлен повторно - он получает новый тег и снова присутствует в множестве.

Redis позиционирует OR-Set как основу для CRDT-совместимых структур в Redis Enterprise Active-Active (2020+): корзина покупок в e-commerce. Пользователь добавил товар на телефоне и удалил на десктопе одновременно - OR-Set разрешает этот конфликт детерминированно: побеждает добавление (add-wins семантика).

Add-wins семантика OR-Set означает: если add и remove произошли конкурентно (без happens-before), победит add. Это интуитивно для корзины покупок, но не для списка заблокированных пользователей. Для remove-wins нужна другая структура - RW-Set (Remove-Wins Set).

Итоги

• **G-Counter** - вектор из N счётчиков (один на узел), merge = max по каждой позиции, value = sum. Только инкремент. Размер O(N).
• **PN-Counter** = два G-Counter: P (плюс) и N (минус), value = sum(P) - sum(N). Поддерживает декремент ценой удвоения размера состояния.
• **G-Set** - множество только с добавлением, merge = union. Идемпотентен, коммутативен, ассоциативен - три свойства CvRDT, гарантирующие eventual consistency.
• **OR-Set** добавляет удаление через уникальные теги: add присваивает новый UUID, remove убирает наблюдённые теги. Add-wins при конкурентных add+remove без координатора.

Связанные темы

CRDT-типы лежат в основе distributed state - они связаны с фундаментальными компромиссами распределённых систем.

• CAP теорема — CRDT выбирают AP из CAP: доступность + partition tolerance, eventual consistency вместо strong consistency
• Vector Clocks — G-Counter - это частный случай vector clock, адаптированный для числовых агрегатов
• Eventual Consistency — CRDT - математическое доказательство достижимости eventual consistency: merge-функция гарантирует сходимость

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

• G-Set не поддерживает удаление - как реализовать soft-delete используя только G-Set (без OR-Set)?
• PN-Counter может стать отрицательным. Как бы проектировали счётчик лайков, где отрицательное значение недопустимо?
• OR-Set использует UUID как теги - что произойдёт если UUID сгенерирован неуникально (коллизия) на двух узлах одновременно?

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

• ds-10-crdts