Распределённые системы
Логические часы Лэмпорта
Цели урока
- Понимать почему физическое время ненадёжно в распределённых системах
- Знать отношение happens-before и три его правила
- Реализовывать алгоритм Lamport clock (tick + receive)
- Различать partial order и total order, знать когда нужен каждый
- Понимать ограничения Lamport clocks и когда нужны Vector Clocks
Предварительные знания
- Базовое понимание что такое процесс и межпроцессное взаимодействие
- Знакомство с распределёнными системами на уровне ds-01-intro
- Понимание понятия 'порядок событий' в логах
1978 год. Лесли Лэмпорт пишет 8 страниц - и создаёт целую область computer science. Самая цитируемая работа в CS (15 000+ цитирований). Turing Award 2013. Идея: если нельзя синхронизировать часы - откажись от часов.
- **Apache Cassandra** использует Lamport timestamps для Last Write Wins - стандартный способ разрешения конфликтов при eventual consistency
- **Jaeger и Zipkin** (distributed tracing) упорядочивают spans по Lamport timestamps для восстановления цепочки запросов
- **Event sourcing** в микросервисах: порядок событий в одном aggregate stream определяется logical clock
- **Distributed mutex** по алгоритму Lamport 1978: процессы договариваются о блокировке без центрального координатора через обмен timestamps
- **Google Spanner** расширяет идею: TrueTime API + commit-wait = глобальный порядок с известной погрешностью 7 мс
Лесли Лэмпорт и рождение логического времени
Статья 'Time, Clocks, and the Ordering of Events in a Distributed System' (1978) - одна из основополагающих работ в CS. Лэмпорт показал: в распределённой системе нет и не может быть глобального времени, но есть causal ordering. Та же статья ввела понятие happens-before, которое используется в Java Memory Model, C++ memory model и всех современных моделях памяти. Сам Лэмпорт также создал LaTeX (1984), Paxos (1989), TLA+ (1999). Turing Award получил в 2013 году.
Почему физическое время не работает
**2012 год. Биржа NASDAQ. Два сервера торговой платформы получают один и тот же ордер на покупку акций. Сервер A говорит: 09:30:00.001 - мой первый. Сервер B говорит: 09:30:00.001 - мой первый. Оба правы по своим часам.** Так система списала деньги дважды - и обнаружили это только при аудите в конце дня. Физическое время в распределённых системах - ненадёжный арбитр.
NTP (Network Time Protocol) - стандарт синхронизации серверных часов - даёт погрешность 1-10 мс в локальной сети и до 100 мс через интернет. При частоте торгов в миллисекунды этого достаточно для коллизий. Дополнительно: при корректировке NTP время может прыгнуть назад - и событие окажется 'раньше' своей причины.
Три фундаментальные проблемы физического времени
| Проблема | Что происходит | Следствие |
|---|---|---|
| Clock drift | Кварцевые генераторы на разных серверах идут с разной скоростью (до 500 ppm разницы) | Через 1 час расхождение до 1.8 секунды без синхронизации |
| Clock skew | NTP корректирует время скачком - оно может прыгнуть назад | Событие B (после A) получает меньший timestamp, чем A |
| Нет арбитра | Нет сервера, знающего глобальное 'сейчас' с нулевой задержкой | Любая централизация добавляет latency и single point of failure |
Решение Лэмпорта 1978 года: вместо физического времени - **логический порядок**. Не 'когда произошло', а 'что до чего'. Если A отправил сообщение, а B его получил - A точно было раньше B. Это знание не требует часов.
Если синхронизировать часы достаточно точно (через GPS, PTP), проблема решена
Даже с атомными часами (Google Spanner) остаётся погрешность - и систему проектируют вокруг этого факта, добавляя commit-wait
Google Spanner использует GPS + атомные часы, погрешность ~7 мс. Но система не игнорирует её - каждый commit ждёт пока интервал погрешности пройдёт. Это дорого: тысячи tx/сек вместо миллионов. Lamport clocks решают задачу порядка без таких затрат.
Почему NTP недостаточно для упорядочивания событий в распределённой торговой системе?
Отношение 'произошло до' (Happens-Before)
**Лесли Лэмпорт, 1978, статья 'Time, Clocks, and the Ordering of Events in a Distributed System' - 8 страниц, самая цитируемая работа в computer science (15 000+ цитирований).** Ключевая идея: вместо абсолютного времени - бинарное отношение между событиями. Обозначается a -> b ('a произошло до b').
- **Локальный порядок:** если a и b - события на одном процессе, и a выполнилось раньше b в программе, то a -> b
- **Сообщения:** если a - отправка сообщения, а b - его получение, то a -> b (это аксиома - получение не может быть раньше отправки)
- **Транзитивность:** если a -> b и b -> c, то a -> c
**Параллельные события (a || b):** если ни a -> b, ни b -> a - события **concurrent**. Они причинно не связаны. Нельзя сказать, какое 'на самом деле' раньше - и это не проблема, это факт о системе.
Concurrent события в git merge
Два разработчика делают коммит в один момент в разных ветках. Ни один не знает о другом - их события concurrent. Git при merge не знает 'кто прав' по времени, поэтому требует ручного разрешения конфликта. Lamport clocks не дают ответа 'кто раньше' для concurrent событий - они честно говорят: 'эти два события несравнимы'.
Процесс A отправляет сообщение (событие e1). Процесс B получает его (событие e2). Процесс C не знает об этом обмене и делает локальное событие e3. Какое отношение между e2 и e3?
Алгоритм логических часов
Lamport предложил элегантный алгоритм: каждый процесс держит счётчик C, начиная с 0. Три правила - и порядок гарантирован. Overhead: одно целое число на каждое сообщение. Ни один другой механизм упорядочивания не дешевле.
**Ключевой инсайт правила receive:** max(local, msg) + 1 гарантирует C(receive) > C(send). Даже если local > msg - +1 обеспечивает строгое неравенство. Если local < msg - берём msg, чтобы учесть 'опыт' отправителя.
Шаг за шагом: три процесса
A: C=0. A делает локальное событие e1 -> C=1. A отправляет msg1 с timestamp=1. B: C=0. B получает msg1(ts=1) -> C=max(0,1)+1=2. B делает e3 -> C=3. B отправляет msg2 с ts=3. C: C=0. C получает msg2(ts=3) -> C=max(0,3)+1=4. A: C=1. A получает msg3(ts=3) -> C=max(1,3)+1=4. A делает e2 -> C=5. Итог: e1(1) -> e3(2) -> e2(5). Порядок соблюдён.
Процесс A (counter=5) получает сообщение с Lamport timestamp=3. Какой будет counter после receive?
Гарантии, ограничения и что дальше
**Lamport clock - инструмент с чёткими границами.** Понимать их критично: неправильное использование даёт ложное ощущение безопасности. Главное ограничение: C(a) < C(b) не означает a -> b. Означает лишь: если a -> b, то C(a) < C(b).
| Критерий | Lamport Clock | Vector Clock |
|---|---|---|
| Размер overhead | O(1) - одно число на сообщение | O(n) - массив из n чисел (n = число процессов) |
| a -> b гарантия | C(a) < C(b) - необходимое условие (не достаточное) | V(a) < V(b) - необходимое И достаточное условие |
| Concurrent detection | Невозможно: C(a) < C(b) может быть и для concurrent | Возможно: если V(a) несравним с V(b) - concurrent |
| Total order | Да - добавить process ID как tiebreaker | Нет из коробки - нужно дополнительное правило |
| Применение | Distributed mutex, event ordering в логах | Conflict detection, CRDTs, version vectors |
**Где Lamport clocks используются сегодня:** Apache Cassandra (write timestamps для LWW - Last Write Wins), event sourcing в микросервисах (порядок событий в одном потоке), distributed mutex по алгоритму Lamport 1978 года, трассировка запросов (Jaeger, Zipkin - span ordering).
**Антипаттерн:** использовать Lamport timestamp для определения 'кто последний записал' в AP-системе с concurrent записями. C(a) < C(b) не говорит a -> b - возможно они concurrent, и 'победитель' выбран произвольно. Для корректного conflict detection нужны векторные часы.
Главное из урока
- Физическое время в распределённых системах ненадёжно: drift, skew, нет глобального арбитра
- Happens-before (->): частичный порядок через локальный порядок + сообщения + транзитивность
- Параллельные (concurrent) события: не связаны причинно, не упорядочиваемы
- Lamport clock: tick() = C++, receive(ts) = max(C, ts)+1 - O(1) overhead
- Гарантия: a -> b => C(a) < C(b), но не наоборот - partial order, не causal
- Total order: Lamport ts + process ID. Для causal order нужны Vector Clocks
Lamport clock решает проблему определения 'кто последний' при конфликтных записях
Lamport clock решает total ordering, но не causal ordering - concurrent события получают искусственный порядок, не реальный
Cassandra использует Lamport timestamps для LWW и документирует это как known limitation: concurrent writes могут потерять данные. Amazon Dynamo для корзины покупок использовал Vector Clocks именно потому что LWW с Lamport timestamps неприемлем - пользователь теряет товары из корзины.
Вопросы для размышления
- В системе event sourcing каждый сервис публикует события в общую шину. Как упорядочить события от разных сервисов для восстановления полной картины? Достаточно ли Lamport timestamps или нужны Vector Clocks - и почему?
Связанные уроки
- ds-01-intro — Модель сбоёв и базовые понятия - узлы, сообщения, частичный порядок
- ds-05-replication — Репликация использует логические часы для упорядочивания операций на репликах
- ds-03-consensus — Paxos и Raft упорядочивают proposals через логические часы внутри
- ds-04-consistent-hashing — Consistent hashing и Lamport clocks - оба решают проблемы координации без центрального арбитра
- sd-04-database — Cassandra использует Lamport timestamps для LWW - конкретный production пример
- isd-14-consistency-models
- alg-18-topological