Разрешение конфликтов в AP-системах
Предпосылки: CAP-теорема (AP-системы, eventual consistency, network partition), модели консистентности.
← Модели консистентности | Распределённый консенсус →
AP-система принимает записи на любом доступном узле, даже если сеть разделена. Когда partition заканчивается и узлы снова видят друг друга, обнаруживается, что разные узлы приняли разные записи для одних и тех же данных. Нужен механизм, который приведёт данные к единому состоянию.
Last-Write-Wins (LWW)
Каждая запись получает timestamp. При конфликте побеждает запись с бо́льшим timestamp.
Node1: balance = 50, timestamp: 1001
Node2: balance = 200, timestamp: 1003
Синхронизация: 1003 > 1001 → побеждает balance = 200
Стратегия простая и детерминированная: все узлы придут к одному результату, не нужно хранить историю версий. Но balance = 50 исчезает молча — данные теряются без уведомления.
LWW работает хорошо, когда потеря данных допустима: кэш, сессии, статус «пользователь онлайн». Записи редко конфликтуют (разные пользователи пишут разные ключи), а если конфликт случился — данные легко восстановить повторной записью.
LWW не работает для счётчиков. Если Node1 увеличил likes со 100 до 101, и Node2 независимо тоже увеличил likes до 101, LWW выберет 101 — но правильный результат 102. Один лайк потерян.
Проблема синхронизации физических часов
LWW опирается на timestamp, а timestamp — на часы сервера. Часы серверов синхронизируются по NTP (Network Time Protocol), но синхронизация неточная.
| Контекст | Типичная точность NTP |
|---|---|
| Внутри датацентра | 1–10 ms |
| Между датацентрами | 10–100 ms |
| Между континентами | 50–200 ms |
NTP может резко сдвинуть время на секунды, если обнаружил сильное расхождение — запись «из прошлого» внезапно побеждает в LWW. Кварцевые генераторы дрейфуют примерно на 10–20 ppm (частей на миллион): за час между синхронизациями набегает до 50ms расхождения. Leap seconds (добавление секунды координации) приводили к реальным инцидентам — Cloudflare и Reddit сталкивались с некорректной обработкой.
Google Spanner решает эту проблему аппаратно: атомные часы и GPS-приёмники в каждом датацентре, API TrueTime возвращает интервал неопределённости [earliest, latest]. Но такое решение дорого и доступно немногим.
В распределённых системах физическое время — ненадёжный источник порядка. Поэтому vector clocks используют логическое время.
Vector Clocks: отслеживание причинности
LWW не различает два случая: запись B «видела» запись A перед собой (B новее) и записи A и B возникли независимо (конкурентные). Vector clock — структура, которая позволяет это различить.
Каждая запись несёт вектор счётчиков, по одному на каждый узел: {NodeA: счётчик, NodeB: счётчик, NodeC: счётчик}. При записи узел увеличивает свой счётчик на единицу.
Начальное состояние:
Node A: balance = 100, VC = {A:0, B:0}
Node B: balance = 100, VC = {A:0, B:0}
Клиент пишет на Node A:
Node A: balance = 50, VC = {A:1, B:0}
Другой клиент (не видя первой записи) пишет на Node B:
Node B: balance = 200, VC = {A:0, B:1}
При синхронизации сравниваются векторы. Вектор X больше вектора Y, если каждый элемент X ≥ соответствующего в Y, и хотя бы один строго больше. Это означает, что запись X «видела» запись Y перед собой — X новее.
{A:2, B:1} > {A:1, B:1} → первая запись новее, вторую можно отбросить
{A:1, B:0} и {A:0, B:1} → ни один вектор не больше → конкурентные записи, конфликт
Три результата сравнения:
| Результат | Интерпретация |
|---|---|
| X > Y | X видел Y, X новее — безопасно взять X |
| Y > X | Y видел X, Y новее — безопасно взять Y |
| Ни один не больше | Конкурентные записи — конфликт, нужно разрешение |
Vector clock обнаруживает конфликт, но не разрешает его автоматически. Варианты разрешения: отдать все конфликтующие версии клиенту (Amazon Dynamo так и делает — при конфликте возвращает список версий), применить автоматическое слияние (для подходящих типов данных) или использовать LWW как fallback.
CRDT: структуры данных без конфликтов
CRDT (Conflict-free Replicated Data Types) — структуры данных, спроектированные так, что любые конкурентные изменения можно объединить автоматически. Порядок применения операций не влияет на результат: операции коммутативны и ассоциативны.
G-Counter: растущий счётчик
Простейший CRDT. Каждый узел хранит свой локальный счётчик, значение G-Counter — сумма всех счётчиков. Слияние — поэлементный max.
Начало: Node A: {A:0, B:0, C:0} = 0
Node B: {A:0, B:0, C:0} = 0
+1 на A: Node A: {A:1, B:0, C:0} = 1
+1 на B: Node B: {A:0, B:1, C:0} = 1
Merge (поэлементный max):
{A: max(1,0), B: max(0,1), C: max(0,0)}
= {A:1, B:1, C:0} = 2
Независимо от порядка синхронизации результат всегда 2. Ни одно приращение не потеряно — в отличие от LWW, который дал бы 1.
PN-Counter: счётчик с инкрементом и декрементом
G-Counter только растёт. Для поддержки вычитания используются два G-Counter: один для прибавлений (P), другой для вычитаний (N). Значение = sum(P) − sum(N).
+1 на A: P:{A:1, B:0}, N:{A:0, B:0} → 1 − 0 = 1
−1 на B: P:{A:0, B:0}, N:{A:0, B:1} → 0 − 1 = −1
Merge: P:{A:1, B:0}, N:{A:0, B:1} → 1 − 1 = 0
PN-Counter имеет ограничения. Размер вектора растёт линейно с числом узлов: при 100 узлах каждый счётчик хранит 200 чисел (P и N). Для миллиона счётчиков в системе — ощутимый overhead. Решения: иерархическая агрегация по датацентрам или периодическое сжатие неактивных счётчиков.
Другое ограничение — счётчик может уйти в минус, если декременты от разных узлов наложились. На практике показывают max(0, value) или ограничивают декремент дополнительной проверкой.
PN-Counter хранит только число, а не список пользователей. Если нужно «пользователь может поставить только один лайк» — нужен OR-Set (множество user_id), а количество лайков получается как размер множества.
Другие CRDT
| CRDT | Что хранит | Операция слияния |
|---|---|---|
| G-Set | Множество (только добавление) | Объединение множеств |
| OR-Set | Множество (добавление и удаление) | Объединение с метаданными для корректного удаления |
| LWW-Register | Одно значение | Last-write-wins (LWW — тоже CRDT) |
| MV-Register | Одно значение | Хранит все конкурентные версии |
Где CRDT применяются
Redis Enterprise использует CRDT для geo-distributed кластеров. Riak — KV-хранилище с CRDT из коробки. Счётчики Cassandra внутри устроены по принципу, похожему на PN-Counter. Collaborative editing (Figma, некоторые реализации Google Docs) опирается на CRDT для бесконфликтного слияния изменений.
Выбор стратегии
| Стратегия | Потеря данных | Сложность | Когда подходит |
|---|---|---|---|
| LWW | Да, молча | Низкая | Кэш, статусы, некритичные данные |
| Vector Clocks | Нет, но требует ручного разрешения | Средняя | Когда клиент или приложение может решить конфликт |
| CRDT | Нет, автоматически | Высокая (ограниченный набор типов) | Счётчики, множества, специфичные структуры |
Стратегии можно комбинировать. Vector clocks обнаруживают конфликт, а CRDT или LWW его разрешают — в зависимости от типа данных.
Sources
- DeCandia et al., 2007, Dynamo: Amazon’s Highly Available Key-value Store — vector clocks в production
- Shapiro et al., 2011, Conflict-free Replicated Data Types — формальное определение CRDT
- Kleppmann, 2017, Designing Data-Intensive Applications, Chapter 5: Replication — LWW, vector clocks, разрешение конфликтов