Vector clock: как отличить причинно связанные события от конкурентных

Прямой ответ

Vector clock — механизм, позволяющий упорядочить события в распределённой системе по причинности, не полагаясь на физическое время. Каждый участник ведёт свой счётчик, а «часы» события — это вектор счётчиков всех известных участников. Сравнивая векторы, можно отличить три ситуации: «A произошло раньше B», «B произошло раньше A» и «A и B конкурентны».

Правила:

1. Локальное событие увеличивает свой компонент: V[i] += 1.
2. При отправке сообщения узел прикладывает свой вектор.
3. При получении узел берёт покомпонентный максимум и увеличивает свой компонент: V[i] = max(V[i], V[j]) + 1.

Сравнение векторов V и W:

• V < W, если все компоненты V[k] <= W[k] и хотя бы одна строго меньше — тогда V причинно раньше W;
• если ни V < W, ни W < V — события конкурентны (concurrent), то есть независимо возникли и конфликтуют.

Зачем это нужно:

• Детекция конфликтов. В системах типа Dynamo клиент получает несколько версий значения и по векторам понимает: это цепочка обновлений (можно взять последнюю) или независимые правки (нужно слияние). Именно так работает корзина покупок в классической статье о Dynamo.
• Причинная согласованность. Если «ответ» должен быть виден только после «вопроса», векторные часы позволяют обеспечить этот порядок без глобальной синхронизации — одна из моделей в обзоре моделей согласованности.

С чем часто путают:

• Timestamp (LWW). Метка времени не определяет причинность: часы узлов расходятся, а NTP даёт лишь приближение. Last-write-wins по времени способен молча потерять обновление.
• Lamport clock. Скалярные часы Лэмпорта гарантируют: если a → b, то L(a) < L(b). Обратное неверно — из L(a) < L(b) не следует причинность. Векторные часы дают именно эквивалентность: V(a) < V(b) ⇔ a → b.

Практика: применение и ограничения

Как это выглядит в данных. Версия значения хранится вместе с вектором:

{
  "key": "cart:user-42",
  "value": ["milk", "bread"],
  "version": {"nodeA": 2, "nodeB": 1}
}

При чтении с нескольких реплик клиент получает набор (value, version) и отбрасывает те версии, которые строго меньше других. Оставшиеся несопоставимые версии — конфликт, который разрешается приложением.

Практические ограничения, о которых нужно помнить:

1. Рост вектора. Размер вектора пропорционален числу участников. В системах с тысячами узлов и частой ротацией ( autoscaling ) векторы раздуваются, поэтому применяют усечения: ограничение числа компонентов, «короткие» векторы (dotted version vectors) или отказ от них в пользу версий-«точек».
2. Идентификаторы участников. Вектор привязан к стабильным id. Если узлы пересоздаются (Kubernetes-поды), нужен стабильный логический идентификатор, иначе история причинности теряется.
3. Слияние — задача приложения. Векторные часы только обнаруживают конфликт. Стратегию слияния выбирают отдельно: LWW, business-правило, CRDT.
4. Стоимость хранения. Каждая запись несёт вектор; при интенсивной записи это заметный overhead. Поэтому в промышленных системах (Cassandra) по умолчанию используется LWW по таймстампу, а векторные часы остаются инструментом для специфических задач.

Что делать вместо векторных часов в типовом веб-приложении:

• оптимистичная блокировка по версии строки (WHERE version = :old) в реляционной БД — см. уровни изоляции транзакций;
• монотонные счётчики на стороне писателя (единственный writer + последовательность);
• идемпотентные операции и явные ключи версий в API — см. идемпотентность API.

Практический сценарий: конфликт двух правок корзины

Контекст: сервис корзины с репликацией в три узла, клиенты пишут в разные узлы.

1. Событие. Пользователь на телефоне добавил «молоко» через узел A, а на ноутбуке добавил «хлеб» через узел B. Обе записи стартовали из одной версии {A:1}.
2. Версии. После записей получаем {A:2, B:1} и {A:1, B:2} — векторы несопоставимы, значит правки конкурентны.
3. Наивное решение. LWW по времени оставил бы одну корзину: часть товаров молча теряется. При расхождении часов в 200 мс «победителем» может стать более ранняя правка.
4. Корректное решение. Модель корзины как CRDT (OR-Set): добавление и удаление несут уникальные метки, поэтому слияние даёт {молоко, хлеб} автоматически.
5. Проверка. Интеграционный тест: две параллельные записи в разные реплики, затем repair/синхронизация, затем чтение кворумом — ожидаем объединённый результат. Как читать кворумом — в статье про quorum NWR.

Результат: правки объединяются, потери данных нет. Вывод: векторные часы дали диагностику конфликта, а устранил его выбор правильной структуры данных, а не более точные часы.

FAQ

Можно ли обойтись физическим временем вместо векторных часов? Для диагностики — частично, если использовать гибридные логические часы (HLC) и синхронизацию NTP/PTP с известной погрешностью. Для гарантии причинности — нет: любые часы могут быть сдвинуты, и вы не отличите «позже» от «независимо».

Что выбрать: Lamport clock или vector clock? Lamport дешевле (одно число) и достаточен, если нужен лишь частичный порядок «причина → следствие». Vector clock дороже, но точно определяет конкурентность, то есть отвечает на вопрос «это конфликт или нет». Если конфликт нужно разрешать — нужны векторы или CRDT.

Почему Cassandra не использует векторные часы по умолчанию? Из-за накладных расходов на хранение и сложность при большом числе узлов. Cassandra применяет LWW по таймстампу записи, что упрощает реализацию, но требует дисциплины: время на узлах должно быть синхронизировано, иначе возможны тихие потери обновлений.

Как связаны векторные часы и кворумные чтения? Кворум (W + R > N) гарантирует, что вы увидите последнюю подтверждённую запись, но не объясняет, как соотносятся две независимые записи. Векторные часы отвечают именно на второй вопрос — поэтому в Dynamo их использовали вместе с sloppy quorum и read repair.

Источники: Wikipedia (vector clock), Dynamo paper (SOSP 2007), Lamport «Time, Clocks…» — ссылки в шапке.