Краткий ответ

Векторные часы связывают версию записи с логическими счётчиками реплик. Если все компоненты вектора одной версии не больше соответствующих компонентов другой и хотя бы одна компонента меньше, первая запись причинно предшествует второй. Если ни один вектор не доминирует над другим, записи считаются конкурентными; сами векторные часы обнаруживают конфликт, но не разрешают его.

Исторический контекст

В распределённых системах нельзя надёжно использовать физическое время для установления порядка событий: часы узлов расходятся, сообщения приходят с задержкой, а сетевые разделения нарушают обмен данными. Поэтому понадобился способ описывать не календарное время, а отношение причинности между событиями.

Логические часы и их векторное расширение позволяют определить, было ли событие известно другому узлу. Это особенно важно для асинхронной репликации, где несколько реплик могут независимо принять изменения.

Постановка проблемы

Пусть две реплики одновременно изменили один объект, не успев увидеть изменения друг друга. Сравнение только значений или временных меток не показывает, какая запись действительно новее: одна из них может быть продолжением другой, а может быть независимым изменением.

Если ошибочно считать одну конкурентную запись более новой, вторая информация будет потеряна. Если хранить обе версии без определения их отношения, клиент или прикладная логика не поймут, является ли это обычным обновлением или конфликтом.

Подробное решение

Векторная метка содержит счётчик для каждой реплики. Реплика увеличивает собственный счётчик перед созданием локального события. При получении чужой версии она сохраняет покомпонентный максимум известных счётчиков, а для нового локального события увеличивает свой компонент.

Например, вектор [3, 1] означает, что реплика знает о трёх событиях первой реплики и одном событии второй. Версия [3, 2] причинно новее версии [3, 1], потому что она содержит всю её историю и ещё одно событие.

Сравнение выполняется покомпонентно:

если вектор A не больше B по всем компонентам и меньше хотя бы по одной, A причинно предшествует B;
если B не больше A по всем компонентам и меньше хотя бы по одной, B причинно предшествует A;
если в одних компонентах A больше B, а в других меньше, записи конкурентны;
равные векторы обозначают один и тот же причинный контекст, но при корректной реализации отдельные события с одинаковыми векторами требуют дополнительного идентификатора или считаются ошибкой модели.

Конкурентность не означает, что записи произошли в одну физическую миллисекунду. Она означает, что ни одна реплика не имела причинной информации о другой записи к моменту своего изменения.

После обнаружения конкурентных версий система должна применить отдельную стратегию: объединить изменения по правилам домена, сохранить несколько вариантов для разрешения клиентом или использовать структуру данных с заранее определённым слиянием. Последняя запись по физическому времени может быть проще, но способна молча потерять конкурентное изменение.

Главный недостаток векторных часов — размер метаданных. При большом числе реплик вектор растёт, а при динамическом составе кластера нужны правила удаления неактивных участников и безопасного сжатия истории. Векторные часы также не обеспечивают консенсус, линейризуемость или автоматическое разрешение конфликтов.

Ситуация из практики

В сервисе корзины две реплики одновременно обслуживают одного пользователя во время сетевого разделения. Обе знали вектор [3, 1]. Первая добавила товар и создала версию [4, 1], вторая изменила количество другого товара и создала [3, 2]. Ни один вектор не доминирует над другим, поэтому изменения конкурентны.

Рассматривались три варианта. Последняя запись по времени проста и не требует хранения нескольких версий, но может удалить изменение, сделанное на другой реплике. Сохранение всех конфликтующих версий не теряет данные, однако переносит разрешение конфликта на клиент и усложняет чтение. Слияние по правилам предметной области сохраняет оба изменения, но требует формально определить, какие операции коммутативны и как обрабатывать удаления.

Для корзины выбрали векторные часы для обнаружения конкуренции и доменное слияние независимых изменений. В результате обычные последовательные обновления автоматически воспринимаются как новые версии, а конфликтующие изменения не затираются молча; операции, которые нельзя безопасно объединить, возвращаются на явное разрешение.

Что кандидаты часто упускают

Могут ли векторные часы сами определить, какая из конкурентных записей правильная?

Нет. Они определяют только отношение причинности: одна версия новее другой либо версии независимы. Выбор победителя требует политики приложения, например объединения полей, разрешения пользователем, идемпотентной операции или детерминированного правила вроде выбора максимального идентификатора. Такое правило может быть полезным, но не превращает конкурентные записи в причинно упорядоченные.

Почему нельзя заменить векторные часы физическими временными метками?

Физическая метка показывает локальную оценку времени, а не факт наблюдения события. Из-за рассинхронизации часы могут указать более позднее время для записи, которая фактически произошла независимо или даже раньше. Одинаковые метки, скачки системного времени и задержки доставки также не позволяют надёжно отличить причинную связь от конкуренции.

Что происходит с векторными часами при большом или меняющемся числе реплик?

Полный вектор требует компоненты для каждого участника, поэтому его размер может стать заметным для каждого сообщения или объекта. При добавлении и удалении реплик нужно сохранять однозначность идентификаторов и не удалять сведения, необходимые для сравнения ещё не доставленных версий.

На практике применяют ограничение времени жизни версий, компактные варианты вроде интервальных или пунктирных векторных меток, а также контролируемое удаление давно неактивных участников. Это уменьшает накладные расходы, но может ослабить способность обнаруживать старые конфликты, поэтому правила сжатия должны учитывать срок хранения и задержки репликации.