Две реплики одновременно увеличивают распределённый счётчик при недоступной связи. Как CRDT-счётчик объединяет эти изменения без потери инкрементов?
CRDT-счётчик хранит вклад каждой реплики отдельно, поэтому одновременные инкременты не перезаписывают друг друга. При восстановлении связи реплики объединяют состояния операцией, сохраняющей максимум по каждому компоненту; итоговое значение вычисляется как сумма компонентов. Такое объединение идемпотентно, коммутативно и ассоциативно, поэтому порядок и повторная доставка состояний не приводят к потере инкрементов.
CRDT появились как способ поддерживать локальные изменения в распределённых копиях без постоянной синхронной связи и глобальной блокировки. Исходная проблема — конфликтующие обновления, которые при обычной перезаписи последнего значения приводят к потере одного из изменений.
Подход особенно полезен для доступности во время сетевых разделений: реплика может принимать допустимые локальные операции, а затем детерминированно объединять результат с другими репликами.
Пусть две реплики видят значение 10 и независимо выполняют по одному инкременту. Если каждая записывает только итоговое значение 11, обычное слияние может оставить 11 вместо ожидаемых 12.
Проблема усугубляется задержками, повторной доставкой сообщений и разным порядком их получения. Решение должно не зависеть от порядка слияния и не должно считать каждую доставку операции новым инкрементом.
Для G-Counter каждая реплика хранит отдельный компонент: например, реплика A — свой локальный счётчик, реплика B — свой. Инкремент изменяет только компонент инициировавшей его реплики. Полное значение равно сумме всех компонентов.
При синхронизации состояния объединяются поэлементно операцией максимума. Если одна реплика хранит компоненты 3 и 5, а другая — 4 и 5, результатом будет 4 и 5, то есть значение 9. Инкремент, уже известный второй реплике, не добавляется повторно, а новый вклад первой сохраняется.
Операция максимума является идемпотентной: повторное применение того же состояния ничего не меняет. Она также коммутативна и ассоциативна, поэтому сообщения можно доставлять повторно, в разном порядке или объединять пакетами.
Для декрементов обычно применяют PN-Counter: отдельно хранят счётчик положительных и отрицательных изменений, а итог вычисляют как разность. Это не делает произвольные операции над числом безопасными: нужно заранее определить допустимую модель изменений и правила слияния.
Главный компромисс — отказ от строгой немедленной согласованности ради доступности локальных операций. CRDT не гарантирует, что пользователь сразу увидит общий итог, а размер состояния может расти вместе с числом реплик и требованиями к учёту их вкладов.
Состояние также нельзя бездумно удалять или сжимать: если забыть компонент, который ещё может прийти от другой реплики, старое состояние способно восстановить уже учтённое значение. Безопасная компакция требует дополнительных гарантий о том, какие состояния больше не могут появиться.
В офлайн-режиме две мобильные реплики считают количество обработанных локально задач. После восстановления связи нужен общий счётчик, но одна и та же информация может быть отправлена несколько раз через промежуточный узел.
Рассматривались три варианта. Центральный лидер обеспечил бы простую строгую семантику, но сделал бы офлайн-инкременты невозможными. Подход с последней записью был бы дешевле, однако потерял бы один из одновременных инкрементов. Передача отдельных операций сохранила бы изменения, но потребовала бы дедупликации по уникальным идентификаторам операций.
Выбран G-Counter, потому что операция состоит только в увеличении, а реплики могут работать автономно. После обмена состояниями компоненты объединились по максимуму, повторная доставка не изменила результат, и итоговое число включило все локальные инкременты.
Если бизнес-правило запрещает значение ниже нуля или требует атомарной проверки лимита, одного CRDT недостаточно. В таком случае нужен отдельный механизм согласования, поскольку локальная доступность может позволить двум репликам независимо превысить общий лимит.
1. Почему нельзя просто хранить одно число и брать максимум итоговых значений?
Максимум итоговых значений не показывает, какие именно изменения уже учтены. Если обе реплики независимо увеличили 10 до 11, максимум даст 11 и потеряет один инкремент. Разделение по репликам сохраняет происхождение вклада, поэтому слияние может отличить новый компонент от уже известного.
2. Что произойдёт, если одно и то же состояние доставить несколько раз?
Ничего дополнительного не произойдёт: поэлементный максимум повторно выберет те же значения. Это важное свойство CRDT, поскольку транспорт обычно может дублировать сообщения, а промежуточные узлы могут повторно распространять уже объединённое состояние.
3. Можно ли с помощью CRDT безопасно поддержать общий лимит?
Не всегда. CRDT хорошо объединяет независимые изменения, но проверка условия вида не превышать общий лимит требует согласованного решения о совокупном состоянии. При сетевом разделении две реплики могут одновременно принять операции, каждая считая лимит ещё не исчерпанным. Для строгого лимита потребуются синхронная координация, предварительно распределённые квоты или другая модель, явно ограничивающая автономные изменения.