ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Объясняем CRDT через strong eventual consistency, state- и operation-based модели, G-Counter, семантику удаления и ограничения бизнес-инвариантов.
Conflict-free Replicated Data Types позволяют обновлять несколько реплик без синхронной координации и гарантируют детерминированную сходимость, когда реплики получили один и тот же набор обновлений. Эта формулировка сильнее «последняя запись победила», но уже популярного обещания «CRDT автоматически решает любые конфликты». Тип данных заранее кодирует допустимые операции и правило слияния; бизнес-смысл конфликтов должен быть спроектирован отдельно.
Обычная eventual consistency обещает, что при прекращении обновлений реплики в конце концов сойдутся, но не всегда объясняет, почему. Для CRDT ключевое свойство называют strong eventual consistency: реплики, получившие одинаковые обновления, имеют эквивалентное состояние независимо от порядка доставки.
Для этого операции или состояния проектируют с математическими свойствами. Повторная доставка не должна ломать результат, перестановка сообщений — менять итог, а объединение уже объединённых состояний — создавать новые эффекты.
State-based CRDT, или CvRDT, периодически передаёт состояние. Состояния образуют join-semilattice, а merge вычисляет наименьшую верхнюю грань. Операции двигают состояние только вверх по частичному порядку; merge должен быть коммутативным, ассоциативным и идемпотентным. Поэтому дубликаты и иной порядок доставки безопасны.
Operation-based CRDT, или CmRDT, передаёт сами операции. Конкурирующие операции должны коммутировать, а транспорт обязан обеспечить условия доставки, заданные конкретным типом — например, reliable causal broadcast. Меньший payload не даётся бесплатно: часть требований перемещается в слой сообщений и метаданных.
Grow-only counter хранит отдельный неубывающий компонент для каждой реплики. Локальный increment меняет только свой компонент, merge берёт максимум покомпонентно, а значение равно сумме.
from dataclasses import dataclass
@dataclass(frozen=True)
class GCounter:
counts: dict[str, int]
def increment(self, replica: str) -> "GCounter":
next_counts = dict(self.counts)
next_counts[replica] = next_counts.get(replica, 0) + 1
return GCounter(next_counts)
def merge(self, other: "GCounter") -> "GCounter":
replicas = self.counts.keys() | other.counts.keys()
return GCounter({
replica: max(self.counts.get(replica, 0), other.counts.get(replica, 0))
for replica in replicas
})
@property
def value(self) -> int:
return sum(self.counts.values())
left = GCounter({}).increment("a").increment("a")
right = GCounter({}).increment("b")
assert left.merge(right).counts == right.merge(left).counts
assert left.merge(left) == left
print(left.merge(right).value) # 3Счётчик умеет только расти. Для decrement нужен PN-Counter из двух растущих компонент, но его семантика всё равно не предотвращает бизнес-инварианты вроде отрицательного остатка: две реплики могут независимо списать последние единицы товара.
Grow-only set объединяется обычным union, но удаление сложнее. Если одна реплика удаляет элемент, пока другая его добавляет, нужно заранее выбрать семантику: add-wins, remove-wins или другую. Observed-remove set отслеживает уникальные теги добавлений и удаляет только наблюдавшиеся экземпляры.
Такие теги и tombstones расходуют память. Garbage collection требует знания, что удаление увидели все релевантные реплики, а при динамическом membership это отдельная распределённая задача. CRDT уменьшает синхронную координацию на пути записи, но может увеличить метаданные, сложность протокола и стоимость сопровождения.
Совместное редактирование последовательности требует устойчивых идентификаторов позиций и детерминированного порядка конкурентных вставок. Разные sequence CRDT выбирают разные структуры идентификаторов и компромиссы. Даже если символы сходятся, продукт должен определить курсоры, undo, права, форматирование и поведение больших вставок.
Нельзя проверить «у нас CRDT» только сравнением финального текста на одном сценарии. Нужны перестановки, повторы и задержки операций, офлайн-редактирование, повторное подключение, удаление узлов и ограничение роста метаданных.
Гарантия сходимости условна: все обновления должны в итоге доставиться согласно требованиям типа, идентификаторы — оставаться уникальными, а реализация merge — соблюдать доказанные свойства. Потерянное навсегда сообщение или повреждённое состояние не исправляются математикой автоматически.
CRDT не обеспечивает линейризуемое чтение. Две доступные реплики могут временно показывать разные состояния. Это ожидаемая цена локальной доступности, а не ошибка сходимости. Если операция требует глобального инварианта — уникального имени, лимита бюджета или выдачи одного билета — может понадобиться координация, escrow-подход или изменение модели данных.
Для state-based варианта выпишите частичный порядок и merge. Докажите или протестируйте коммутативность, ассоциативность и идемпотентность. Сгенерируйте историю операций на нескольких репликах, доставьте состояния в разных порядках и сравните результат.
Для operation-based варианта зафиксируйте, какие операции считаются конкурентными, почему они коммутируют и какую доставку обеспечивает транспорт. Отдельно проверьте дубликаты, восстановление после snapshot и присоединение новой реплики.
CRDT — это не магический слой reconciliation, а способ перенести часть согласования из времени выполнения в конструкцию типа данных. Он особенно полезен там, где локальные операции естественно объединяются, временное расхождение допустимо, а семантика конкурентных изменений может быть описана заранее.
Самостоятельный редакционный разбор ЯдроКода по работам Shapiro, Preguiça, Baquero и Zawirski. Термины и гарантии атрибутированы первоисточникам, изложение и код созданы редакцией.
Реализация G-Counter и примеры созданы редакцией; схемы и псевдокод первоисточников не копируются.