Векторные часы и часы Лэмпорта: порядок событий в распределённых системах

Почему в распределённой системе нельзя верить времени на часах, что такое отношение happens-before, как работают часы Лэмпорта и векторные часы, как найти конфликт версий. Код на Python.

11 мин чтениясистемный дизайн · распределённые системы · python

Коротко

ВопросЧасы ЛэмпортаВекторные часы
Что хранит узелОдно числоПо счётчику на каждый узел
Размер меткиO(1)O(1)O(n)O(n), где nn — число узлов
Если a→ba \to bL(a)<L(b)L(a) < L(b)V(a)<V(b)V(a) < V(b)
Обратное верно?Нет: из L(a)<L(b)L(a) < L(b) причинность не следуетДа: V(a)<V(b)V(a) < V(b) тогда и только тогда, когда a→ba \to b
Видит параллельностьНетДа: метки несравнимы
Где встречаютсяПолный порядок событий, термы в Raft, версииDynamo, Riak, обнаружение конфликтов при репликации
  • Физическим часам на разных машинах верить нельзя: они расходятся на миллисекунды, а иногда прыгают назад.
  • Вместо «когда произошло» распределённые системы отвечают на вопрос «что могло повлиять на что». Это отношение happens-before, введённое Лесли Лэмпортом в 1978 году.
  • Часы Лэмпорта — дешёвый способ получить порядок, согласованный с причинностью. Векторные часы — способ точно узнать, связаны ли два события или они конкурентны.
  • В современных базах часто используют гибридные логические часы (HLC): физическое время плюс логический счётчик.

Почему нельзя просто сравнить время

Два сервера принимают запись в один и тот же ключ. Первый ставит метку 12:00:00.105, второй — 12:00:00.103. Кажется, побеждает первый. Но:

  • часы синхронизируются по NTP с точностью в лучшем случае до долей миллисекунды в одном дата-центре, а между регионами и при проблемах с сетью — хуже;
  • после синхронизации часы могут прыгнуть назад;
  • виртуальная машина может «заснуть» на секунды и проснуться со старым временем.

Стратегия last-write-wins по физическому времени из-за этого молча теряет данные: запись, сделанная позже, может проиграть записи, сделанной раньше, просто потому что на её сервере часы отстают. Это не теоретическая проблема: Cassandra, например, разрешает конфликты именно по меткам времени, и рассинхронизация часов на узлах там приводит к «пропавшим» записям.

Google в Spanner решил это железом: атомные часы и GPS-приёмники в дата-центрах плюс API TrueTime, который возвращает не момент, а интервал неопределённости. Большинству систем такое недоступно, поэтому нужен логический подход.

Отношение happens-before

Лэмпорт предложил смотреть не на время, а на причинность. Событие aa произошло раньше события bb (a→ba \to b), если:

  1. aa и bb на одном узле, и aa было раньше в его локальном порядке;
  2. aa — отправка сообщения, а bb — получение этого же сообщения;
  3. есть cc, такое что a→ca \to c и c→bc \to b (транзитивность).

Если ни a→ba \to b, ни b→ab \to a, события конкурентны: a∥ba \parallel b. Это не значит «произошли одновременно». Это значит, что ни одно не могло узнать о другом, и никакой объективный порядок между ними не существует.

Пример: Алиса отправила сообщение в чат, Боб его прочитал и ответил. Ответ Боба причинно зависит от сообщения Алисы, и любой участник должен видеть их в этом порядке. А если Алиса и Боб одновременно написали независимые сообщения, их порядок не важен, но все участники должны договориться о каком-то одном. Это ровно тот вопрос, с которым сталкиваются при проектировании чата.

Часы Лэмпорта

Каждый узел хранит одно целое число и соблюдает три правила:

  1. Перед каждым локальным событием увеличить счётчик на 1.
  2. Отправляя сообщение, увеличить счётчик и приложить его к сообщению.
  3. Получив сообщение с меткой tt, установить счётчик в max⁡(свой,t)+1\max(\text{свой}, t) + 1.
class LamportClock: def __init__(self): self.time = 0 def tick(self): # локальное событие или отправка self.time += 1 return self.time def receive(self, remote_time): self.time = max(self.time, remote_time) + 1 return self.time a, b = LamportClock(), LamportClock() a.tick() # A: событие, 1 t = a.tick() # A: отправка сообщения, 2 b.tick() # B: своё событие, 1 b.receive(t) # B: получение, max(1, 2) + 1 = 3 print(a.time, b.time) # 2 3

Что гарантируется: если a→ba \to b, то L(a)<L(b)L(a) < L(b). Получение всегда «позже» отправки, потому что берётся максимум плюс один.

Что не гарантируется: из L(a)<L(b)L(a) < L(b) не следует a→ba \to b. В примере событие B с меткой 1 и событие A с меткой 2 никак не связаны, хотя 1<21 < 2. Часы Лэмпорта не отличают «было раньше» от «просто получило меньшее число».

Полный порядок

Часы Лэмпорта дают простой способ упорядочить все события одинаково на всех узлах: сравнивать пары (время, id узла). Равные метки разных узлов разрешаются по id. Такой порядок согласован с причинностью, хотя для конкурентных событий он произволен.

Лэмпорт показал на этом примере, как построить распределённый мьютекс: запросы на вход в критическую секцию упорядочиваются по (время, id), и все узлы одинаково понимают, чья очередь. Подробнее о практических вариантах — в статье о распределённых блокировках.

Та же идея — монотонный счётчик, который при встрече с бо́льшим значением подтягивается до него, — лежит в основе термов в Raft и fencing-токенов.

Векторные часы

Чтобы различать «раньше» и «параллельно», одного числа мало. Векторные часы (Фидж и Маттерн, независимо друг от друга, 1988) хранят на каждом узле вектор счётчиков — по одному на каждый узел системы. Счётчик узла ii в векторе узла jj означает: «сколько событий узла ii узел jj уже видел (напрямую или через других)».

Правила:

  1. Перед локальным событием узел увеличивает свой элемент вектора.
  2. Отправляя сообщение, прикладывает к нему весь вектор.
  3. Получив вектор WW, берёт поэлементный максимум со своим VV, затем увеличивает свой элемент.

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

  • V≤WV \le W, если каждый элемент VV не больше соответствующего элемента WW;
  • V<WV < W (то есть a→ba \to b), если V≤WV \le W и V≠WV \ne W;
  • если ни V≤WV \le W, ни W≤VW \le V — события конкурентны.
class VectorClock: def __init__(self, node, clock=None): self.node = node self.clock = dict(clock or {}) def tick(self): self.clock[self.node] = self.clock.get(self.node, 0) + 1 return dict(self.clock) def receive(self, remote): for node, t in remote.items(): self.clock[node] = max(self.clock.get(node, 0), t) return self.tick() def compare(a, b): nodes = a.keys() | b.keys() le = all(a.get(n, 0) <= b.get(n, 0) for n in nodes) ge = all(a.get(n, 0) >= b.get(n, 0) for n in nodes) if le and ge: return "equal" if le: return "before" # a -> b if ge: return "after" # b -> a return "concurrent" # a || b A, B, C = VectorClock("A"), VectorClock("B"), VectorClock("C") a1 = A.tick() # {A:1} b1 = B.receive(a1) # {A:1, B:1} c1 = C.tick() # {C:1} b2 = B.receive(c1) # {A:1, B:2, C:1} a2 = A.tick() # {A:2} print(b2, a2) print(compare(a1, b2), compare(b2, a1), compare(a2, b2), compare(a1, a1)) # before after concurrent equal

Разберём результат:

  • a1 = {A:1} и b2 = {A:1, B:2, C:1}: каждый элемент a1 не больше, значит a1 → b2. Действительно, B получил сообщение от A.
  • a2 = {A:2} и b2: у a2 больше элемент A (2 против 1), у b2 больше B и C. Векторы несравнимы — события конкурентны. A сделал второе событие, ничего не зная о том, что происходило на B и C.

Отсутствующий ключ в словаре трактуется как 0 — так удобнее, чем заранее знать всех участников.

Применение: конфликты версий в репликации

Главное практическое применение — обнаружение конфликтующих записей в базах без лидера. Классический пример — корзина покупок из статьи Amazon о Dynamo (2007).

Каждая версия значения хранится вместе с векторной меткой. Когда приходит новая запись:

  • если старая версия причинно раньше новой — старую можно выбросить;
  • если версии конкурентны — хранить обе как «братьев» (siblings) и отдать клиенту при чтении, чтобы он их слил.
def put(siblings, new_value, new_clock): """Хранилище в стиле Dynamo: держим все версии, которые не устарели.""" kept = [ (v, c) for v, c in siblings if compare(c, new_clock) not in ("before", "equal") ] return kept + [(new_value, new_clock)] cart = put([], ["milk"], {"X": 1}) # Два клиента прочитали версию {X:1} и пишут через разные реплики cart = put(cart, ["milk", "bread"], {"X": 1, "Y": 1}) cart = put(cart, ["milk", "eggs"], {"X": 1, "Z": 1}) print(cart) # [(['milk', 'bread'], {'X': 1, 'Y': 1}), (['milk', 'eggs'], {'X': 1, 'Z': 1})] # Клиент читает обе версии, сливает и пишет с объединённым контекстом merged = sorted(set(cart[0][0]) | set(cart[1][0])) cart = put(cart, merged, {"X": 2, "Y": 1, "Z": 1}) print(cart) # [(['bread', 'eggs', 'milk'], {'X': 2, 'Y': 1, 'Z': 1})]

Обе версии корзины выросли из {X:1}, но ни одна не знает о другой. Last-write-wins выбросил бы хлеб или яйца. Векторные часы позволяют это заметить и слить. Новая запись с объединённым вектором «покрывает» обе старые версии, и они удаляются.

Слияние — забота приложения. Для корзины подходит объединение множеств (с известным недостатком: удалённый товар может «воскреснуть»). Структуры данных, которые сливаются автоматически, называются CRDT.

Строго говоря, в хранилищах это обычно называют version vectors: счётчики ведутся по репликам и считают версии одного ключа, а не все события. Механика та же. Riak начинал с классических векторных часов, а позже перешёл на dotted version vectors, которые точнее отслеживают конфликты при большом числе клиентов.

Подробнее о том, как такие хранилища устроены целиком, — в статье о key-value хранилище и о шардировании и репликации.

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

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

Состав участников меняется. Узлы добавляются и исчезают, а их записи в векторах остаются навсегда, если не чистить специально.

Ничего не говорят о реальном времени. Векторные часы скажут, что две записи конкурентны, но не скажут, какая из них сделана позже по часам пользователя. Иногда это важно, например для TTL или отображения.

Гибридные логические часы

Компромисс между физическим и логическим временем — HLC (hybrid logical clocks, Kulkarni и соавторы, 2014). Метка — пара «физическое время + логический счётчик»:

  • метка всегда близка к реальному времени, её можно показать человеку и использовать для запросов «на момент времени»;
  • при этом она, как часы Лэмпорта, гарантирует: если a→ba \to b, то HLC(a)<HLC(b)HLC(a) < HLC(b), даже если часы на машинах немного расходятся;
  • размер постоянный, как у Лэмпорта.

HLC используют CockroachDB и YugabyteDB для упорядочивания транзакций и MVCC-версий. Конкурентность они, как и часы Лэмпорта, не обнаруживают, поэтому дополняются проверкой максимального расхождения часов.

Что выбрать

ЗадачаИнструмент
Нужен любой порядок, согласованный с причинностьюЧасы Лэмпорта
Нужно обнаружить конфликт параллельных записейВекторные часы / version vectors
Нужен порядок, близкий к реальному времениHLC
Нужен строгий глобальный порядок операцийКонсенсус: один лог, один лидер
Нужны уникальные и примерно упорядоченные idГенератор вроде Snowflake

Последняя строка связана с темой генерации уникальных ID: Snowflake-подобные id тоже содержат время и номер узла, но причинность не гарантируют.

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

Типичные ошибки и вопросы на собеседовании

«Часы Лэмпорта показывают, какое событие было раньше». Только в одну сторону: причинность влечёт меньшую метку, но меньшая метка не влечёт причинность.

«Конкурентные — значит одновременные». Нет. Конкурентные события могут быть разнесены на минуты реального времени. Важно лишь то, что они не знали друг о друге.

«Сравниваем векторы по сумме элементов». Сумма теряет информацию. Сравнивать нужно поэлементно, и результат может быть «несравнимы».

«Last-write-wins по timestamp — нормально». Нормально, только если потеря одной из параллельных записей допустима. Для корзины, документов и счётчиков — нет.

Частые вопросы:

  1. Почему нельзя упорядочить события по времени сервера? — Часы расходятся и прыгают; более поздняя запись может получить меньшую метку.
  2. Чем векторные часы лучше часов Лэмпорта? — Они точно определяют причинность и умеют сказать «события конкурентны».
  3. Как Dynamo обнаруживает конфликт? — Сравнивает векторные метки версий: если несравнимы — это конфликт, обе версии отдаются клиенту.
  4. Какая цена векторных часов? — Размер O(n)O(n) в каждом сообщении и в каждой версии данных.

Итог

В распределённой системе нет общего «сейчас», зато есть причинность: что могло повлиять на что. Часы Лэмпорта — одно число, которое не противоречит причинности и даёт общий порядок. Векторные часы — вектор, который восстанавливает причинность точно и видит конкурентные события, а значит позволяет находить конфликты в репликах. HLC сочетают логическую гарантию с близостью к реальному времени. Если на собеседовании речь зашла о multi-leader или leaderless репликации, будьте готовы объяснить, как система поймёт, что две записи конфликтуют, — это и есть векторные часы.

Потренироваться в спокойной обстановке

Все задачи