Логические часы и упорядочивание событий

Проблема времени в распределённых системах

В распределённой системе нет единого источника времени. Физические часы на разных серверах идут с разной скоростью и могут расходиться.

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

Node A: 12:00:00.000          Node B: 12:00:00.050
         │                              │
         │ Event a₁ at 12:00:00.100     │
         │──────── message ────────────>│
         │                              │ Event b₁ at 12:00:00.120
         │                              │
         │ Вопрос: a₁ произошло до b₁?  │
         │                              │
         │ По часам Node A: a₁ = 12:00:00.100
         │ По часам Node B: b₁ = 12:00:00.120
         │                              │
         │ Но часы B опережают A на 50ms!
         │ Реально b₁ = 12:00:00.070 по часам A
         │ Значит b₁ РАНЬШЕ a₁?         │

Проблемы физических часов:

• Clock drift -- кварцевый генератор дрейфует ~10-100 ppm (10-100 мкс/сек)
• Clock skew -- разница часов между узлами в данный момент
• NTP корректирует с точностью ~1-10 мс (для LAN), что недостаточно для упорядочивания
• Leap seconds, NTP jumps -- время может пойти назад

Отношение "произошло до" (Happens-Before)

Лесли Лэмпорт в 1978 году формализовал понятие причинно-следственного порядка:

Определение: Событие a произошло до события b (обозначается a → b), если:

1. a и b на одном процессе, и a раньше b по локальному порядку
2. a -- отправка сообщения, b -- получение того же сообщения
3. Транзитивность: если a → b и b → c, то a → c

Если ни a → b, ни b → a, то события конкурентны: a || b.

Process P1:  a₁ ───────────── a₂ ──────────── a₃
                    │                    ▲
                    │ message            │ message
                    ▼                    │
Process P2:  b₁ ── b₂ ──── b₃ ──── b₄ ─┘

Happens-before:
  a₁ → a₂ → a₃  (same process)
  b₁ → b₂ → b₃ → b₄  (same process)
  a₁ → b₂  (message send → receive)
  b₃ → a₃  (message send → receive)

Concurrent:
  a₁ || b₁  (no causal relationship)
  a₂ || b₃  (no causal relationship)

Lamport Timestamps

Алгоритм

Каждый процесс поддерживает счётчик C:

1. Локальное событие: C = C + 1
2. Отправка сообщения: C = C + 1, приложить C к сообщению
3. Получение сообщения с timestamp t: C = max(C, t) + 1

Пример

P1 (C=0):  [1]─────────────[2]─────────────────[5]
                   │                        ▲
                   │ msg(C=1)               │ msg(C=4)
                   ▼                        │
P2 (C=0):  ──────[2]──────[3]─────[4]──────┘

P3 (C=0):  [1]────────────[2]────────────[3]

Шаг за шагом:
P1: event → C=1, send msg(1) → C=1
P2: receive msg(1) → C=max(0,1)+1=2, event → C=3, event → C=4, send msg(4)
P1: event → C=2, ... receive msg(4) → C=max(2,4)+1=5

Свойства Lamport Timestamps

Ограничение: Если L(a) < L(b), мы не можем сказать, произошло ли a до b или они конкурентны. Для этого нужны Vector Clocks.

Тотальный порядок с Lamport Timestamps

Для создания полного порядка: (timestamp, process_id). При одинаковых timestamp побеждает меньший process_id.

Event A: L=5, process=P1 → (5, 1)
Event B: L=5, process=P2 → (5, 2)
Order: A < B (потому что 5=5, но 1 < 2)

Vector Clocks

Vector Clocks решают проблему Lamport Timestamps -- они точно определяют конкурентность.

Алгоритм

Каждый процесс Pi поддерживает вектор V[0..N-1], где N -- число процессов:

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

Пример

P1: V=[0,0,0]    [1,0,0]─────────[2,0,0]────────────[3,2,0]
                      │                           ▲
                      │ msg([1,0,0])              │ msg([2,2,0])
                      ▼                           │
P2: V=[0,0,0]    [0,1,0]  [1,2,0]───[1,3,0]─[2,4,0]
                               │           ▲
                               │           │ msg([1,3,0])
                               ▼           │
P3: V=[0,0,0]    ────────[0,0,1]──[1,3,2]─┘

P2 receives msg([1,0,0]) from P1:
  V = max([0,1,0], [1,0,0]) = [1,1,0], then V[1]++ → [1,2,0]

P3 receives msg from P2([1,3,0]):
  V = max([0,0,1], [1,3,0]) = [1,3,1], then V[2]++ → [1,3,2]

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

V1 ≤ V2:  V1[i] ≤ V2[i] для всех i
V1 < V2:  V1 ≤ V2 и V1 ≠ V2
V1 || V2: ни V1 ≤ V2, ни V2 ≤ V1

Примеры:
[1,2,0] < [1,3,1]  → happens-before
[2,0,0] || [0,2,0] → concurrent (конкурентны)
[1,2,3] < [1,2,4]  → happens-before
[2,3,1] || [1,4,2] → concurrent

Свойства Vector Clocks

Проблема масштабируемости

Vector Clocks имеют размер O(N), где N -- число процессов. При тысячах узлов вектор становится слишком большим.

Решения:

• Dotted Version Vectors -- оптимизация для client-server
• Interval Tree Clocks -- динамическое число участников
• Hybrid Logical Clocks -- компромисс между физическим и логическим временем

Hybrid Logical Clocks (HLC)

HLC комбинирует физическое и логическое время. Предложены Kulkarni et al. в 2014 году.

Структура HLC

HLC = (physical_time, logical_counter)

physical_time: max из локальных физических часов и полученных значений
logical_counter: разрешает конфликты при одинаковом physical_time

Алгоритм

Для каждого процесса i:
  l = physical_time компонента HLC
  c = logical counter

Локальное событие или отправка:
  l' = max(l, PT)     // PT = текущее физическое время
  if l' == l:
    c = c + 1          // Same physical time, increment logical
  else:
    c = 0              // New physical time, reset counter
  l = l'

Получение сообщения с (l_m, c_m):
  l' = max(l, l_m, PT)
  if l' == l == l_m:
    c = max(c, c_m) + 1
  elif l' == l:
    c = c + 1
  elif l' == l_m:
    c = c_m + 1
  else:
    c = 0
  l = l'

Преимущества HLC

Где используются HLC

• CockroachDB -- для MVCC timestamps
• MongoDB -- для causal consistency sessions
• TiDB -- для snapshot isolation
• Cosmos DB -- для conflict resolution

Causal Ordering (Причинный порядок)

Уровни упорядочивания

Строгость упорядочивания (от слабого к сильному):

FIFO ordering
    │  Сообщения от одного отправителя доставляются в порядке отправки
    ▼
Causal ordering
    │  Если a → b, то все узлы видят a перед b
    ▼
Total ordering
    │  Все узлы видят все события в одинаковом порядке
    ▼
Linearizability
       Тотальный порядок + соответствие реальному времени

Causal Consistency на практике

User A posts: "I got a promotion!"
     │
     ▼ (causal dependency)
User B comments: "Congratulations!"

Все пользователи должны видеть пост ДО комментария.
Без causal ordering User C может увидеть:
  "Congratulations!" ← К чему это? Пост ещё не виден!

Реализация причинного порядка

CBCAST (Causal Broadcast):

• Каждое сообщение несёт vector clock
• Получатель буферизует сообщение, пока не получены все причинно-предшествующие
• Гарантирует: если m1 → m2, то все процессы доставят m1 перед m2

P1: send m1 with V=[1,0,0]
P2: receive m1, send m2 with V=[1,1,0]  (m1 → m2)
P3: receives m2 first
    Check: V(m2) requires V[0] ≥ 1 (from P1)
    P3 has V=[0,0,0], V[0]=0 < 1
    → Buffer m2, wait for m1
    Receives m1 → deliver m1, then deliver m2 ✓

Сравнительная таблица

Что говорить на интервью

1. Lamport Timestamps -- просто и достаточно для тотального порядка, но не определяют конкурентность
2. Vector Clocks -- точно определяют причинность, но O(N) по размеру
3. HLC -- практический компромисс для современных баз данных
4. TrueTime -- уникальное решение Google с атомными часами (Spanner)
5. Причинный порядок -- минимально достаточный для большинства приложений