Hybrid Logical Clocks (HLC)

Зачем

Распределённой системе нужны временные метки на события — чтобы упорядочить writes, сделать MVCC-snapshot, отсчитать TTL, выполнить range-scan «всё за последний час». Два классических подхода ломаются по-своему:

• Lamport clock — монотонный скаляр, но не привязан к wall-clock. ts=42 ничего не говорит о реальном времени. Range query по времени невозможен без отдельного timestamp в payload (а тот врёт из-за skew).
• Physical clock (NTP) — привязан к wall-clock, но дрейфует на 100–250 ms, прыгает назад при ресинке, замирает в VM-паузах. Cassandra использует physical timestamps + LWW и платит lost-write проблемой при skew.

HLC = (physical_part, logical_part) — кортеж, который монотонно растёт и близок к real time (с точностью до NTP-skew). Это даёт MVCC, range scans, expiry — и при этом сохраняет causality между событиями.

Используется как primary clock в CockroachDB, YugabyteDB, MongoDB (causal consistency tokens).

Mental model

«hlc = (pt, l). Если physical clock тикнул — pt подтягивается к нему, l обнуляется. Если physical застрял (burst событий за 1 ms, clock skew) — l++ поглощает burst. Compare лексикографически по (pt, l).»

Алгоритм в трёх правилах:

local event:
  pt_new = max(physical_now, hlc.pt)
  if pt_new > hlc.pt:  hlc = (pt_new, 0)
  else:                 hlc = (hlc.pt, hlc.l + 1)

on receive(msg):
  pt_new = max(physical_now, hlc.pt, msg.pt)
  if pt_new == hlc.pt == msg.pt: hlc = (pt_new, max(hlc.l, msg.l) + 1)
  elif pt_new == hlc.pt:          hlc = (pt_new, hlc.l + 1)
  elif pt_new == msg.pt:          hlc = (pt_new, msg.l + 1)
  else:                            hlc = (pt_new, 0)

Инвариант: |hlc.pt - physical_clock| ≤ ε (bounded by NTP-skew). При нарушении CockroachDB поднимает ClockOffset error и убивает ноду.

Что на диаграмме

Кластер из трёх нод (node-a, node-b, node-c) — CockroachDB-style replicas, синхронизированные через NTP. Каждая нода держит свой HLC и обменивается им при репликации writes. На рёбрах — TCP-репликация между всеми парами.

ADR на ноде A фиксирует два ключевых решения: выбор HLC-тапла вместо чистого Lamport и выбор HLC + uncertainty interval вместо TrueTime + commit-wait.

Сценарии

Happy path: физические часы растут, pt подтягивается, l обнуляется. Когда A шлёт сообщение B (B позади на 1 ms), B подтягивает свой pt к timestamp отправителя и инкрементит l, чтобы receive-событие было строго после send.

Burst событий за один physical tick — l инкрементится подряд (l=1, 2, 3), monotonicity сохраняется без помощи physical clock. Затем приходит сообщение с большим pt, чем у получателя (49 ms skew) — pt принудительно подтягивается вперёд. Финальная нота: если skew превысит max_offset (default 500 ms в CockroachDB), нода совершает самоубийство — HLC валиден только при bounded skew.

Сравнение трёх clock schemes на одной задаче — range query «events за последние 5 минут»:

• Lamport — провал, ts=42 без wall-clock binding;
• HLC — работает, pt уже в milliseconds since epoch;
• TrueTime — работает, но требует GPS/atomic clocks в каждом DC + commit-wait на каждой транзакции.

Verdict: HLC — sweet spot для commodity hardware.

Применение HLC в MVCC: read at (103, 0) возвращает версию x=1 (write at (100, 0)), пропуская x=2 (write at (105, 0)). Если существующий write попадает в uncertainty zone [103, 103 + max_offset] — транзакция перезапускается с обновлённым read_ts. Это даёт single-key linearizability без atomic clocks.

Trade-offs (ADR)

ADR-001: HLC = (pt, l) тапл вместо чистого Lamport. Lamport даёт causality, но ломает range queries и MVCC reads at timestamp. Чистый physical clock даёт wall-clock, но врёт. HLC — формальная композиция: pt = approximation физического времени, l = tie-breaker для одинаковых pt. Компромисс: требуется loosely-synced NTP; при превышении max_offset нода падает. Применяется в CockroachDB, YugabyteDB, MongoDB causal consistency.

ADR-002: CockroachDB chose HLC over TrueTime. Spanner решает ту же задачу через TrueTime API (GPS + atomic clocks + commit-wait на uncertainty bound ~7 ms). CockroachDB строится для commodity cloud hardware, где atomic clocks недоступны, а NTP даёт 100–250 ms — commit-wait непрактичен. Вместо commit-wait — uncertainty restart: read попадает в uncertainty zone существующего write → транзакция перезапускается с большим read_ts. Cost: extra latency на overlapping reads. НЕ guaranteed: external consistency между независимыми транзакциями (Spanner это даёт, HLC — нет). Acceptable для большинства OLTP. Источник: Spencer Kimball, «Living Without Atomic Clocks» (CockroachDB blog, 2016).

Реальные системы

• CockroachDB — primary clock, max_offset=500ms default, uncertainty restart при skew;
• YugabyteDB — те же принципы, тот же uncertainty-механизм;
• MongoDB 3.6+ — causal consistency tokens используют HLC под капотом ($clusterTime в каждом ответе сервера);
• CRDT-системы с last-writer-wins (Riak, Akka Distributed Data) — HLC как timestamp для tie-breaking, более устойчивый к skew, чем чистый wall-clock.

Anti-patterns

1. Использовать HLC при unsynced NTP. Если ноды не синхронизированы (или NTP конфигурирован неправильно), pt может разъехаться на секунды/минуты. HLC формально остаётся монотонным (через l), но pt уходит в будущее и блокирует все будущие writes на скачок. CockroachDB защищается suicide-механизмом; кастомная имплементация без него — тихая поломка.

2. Сравнивать HLC из разных кластеров. HLC валиден только внутри одного логического кластера, где все ноды видят сообщения друг друга. Два независимых кластера могут иметь пересекающиеся HLC-значения для несвязанных событий.

3. Хранить только pt, выбрасывая l. Соблазн «сжать» HLC до int64 wall-clock timestamp — теряется tie-breaker, и burst-события за один ms становятся неотличимыми. MVCC с такими timestamps развалится.

4. Использовать HLC для external consistency. HLC даёт single-key linearizability и causality внутри транзакции. Между независимыми транзакциями на разных нодах — нет (для этого нужен TrueTime или commit-wait). Если бизнес-логика требует «после ответа клиенту это должно быть видно всем» — HLC недостаточно.

5. Игнорировать max_offset. Слишком маленький max_offset (50 ms) — ноды падают при любом NTP-glitch. Слишком большой (5 s) — uncertainty restart почти на каждый read, throughput падает. Default 500 ms — разумный компромисс для public cloud.

Когда НЕ использовать

• Single-node системы — overkill, обычный physical clock с monotonic flag (Linux CLOCK_MONOTONIC) проще и достаточен.
• Полностью offline / partitioned системы — HLC требует периодического message exchange чтобы подтягивать pt друг к другу. Долгие partitions без коммуникации = drift между нодами, который HLC не лечит (он его только absorb-ит, не корректирует).
• Требуется external consistency — выбирайте Spanner / TrueTime или 2PC с distributed locks. HLC явно отказывается от этой гарантии.
• NTP недоступен / unreliable — embedded-системы, edge без интернета, isolated networks. Без bounded skew HLC превращается в Lamport с лишним полем.
• Чисто causal consistency без wall-clock потребностей — vector clocks дают precise causality (можно отличить concurrent от ordered), HLC даёт только total order. Если нужно знать «эти два события concurrent» — HLC соврёт «упорядочены».

Дальше читать

Базовые ссылки:

• Kulkarni, Demirbas, Madappa, Avva, Leone — «Logical Physical Clocks» (2014, оригинальная статья).
• Spencer Kimball — «Living Without Atomic Clocks» (CockroachDB blog, 2016, объясняет выбор HLC vs TrueTime).
• Murat Demirbas — «Hybrid Logical Clocks» (блог автора алгоритма, intuition + примеры).

Связанные концепты:

• [CONCEPT]lamport-clocks — предшественник, понимание origin для HLC;
• [CONCEPT]vector-clocks — альтернатива для precise causality detection;
• [CONCEPT]linearizability-deep — что именно HLC даёт (single-key linearizability) и не даёт (external consistency);
• [CONCEPT]happens-before — формальная модель причинности, которую HLC сохраняет.

Применяется в кейсах:

• [CASE]distributed-transactions — MVCC + uncertainty restart как реализация snapshot isolation поверх HLC.