Распределённые системы

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

Цели урока

  • Понимать почему физические часы (NTP) недостаточны для упорядочивания событий
  • Объяснять отношение happened-before и его три правила
  • Реализовывать Lamport timestamps и знать их ограничение
  • Использовать Vector Clocks для обнаружения конкурентных событий
  • Различать Lamport, Vector Clocks и HLC по задачам

Предварительные знания

  • Базовое понимание распределённых систем (что такое узел, сообщение)
  • CAP-теорема: разница CP/AP систем
  • Понимание репликации данных

NTP точен до 100мс. Транзакция в базе данных длится микросекунды. Два сервера AWS в одной AZ могут расходиться по часам так, что порядок событий принципиально не определить без logical clocks.

  • **Amazon Dynamo (2007)** - vector clocks для обнаружения конфликтов в корзине покупок при eventual consistency
  • **Apache Cassandra** - Lamport timestamps для упорядочивания операций в ячейках при concurrent writes
  • **CockroachDB** - Hybrid Logical Clocks в каждой транзакции для глобального порядка без атомных часов
  • **Riak и CouchDB** - vector clocks для multi-master репликации без координатора
  • **Google Spanner TrueTime** - атомные часы + GPS + commit-wait 7мс как альтернатива logical clocks ценой железа

Лэмпорт 1978: 8 страниц, изменивших Computer Science

Статья "Time, Clocks, and the Ordering of Events in a Distributed System" вышла в Communications of the ACM в 1978 году. Лэмпорт работал в SRI International над верификацией программ, когда сформулировал простое наблюдение: в распределённой системе нет способа сказать, что "事件A произошло раньше события B" по физическому времени - но можно определить причинно-следственный порядок. Эта идея, изначально казавшаяся абстрактной, оказалась фундаментом для consensus-алгоритмов, репликации и распределённых баз данных. Turing Award 2013.

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

**Amazon DynamoDB, 2012: конфликт в корзине покупок. Пользователь на мобильном и браузере одновременно добавил товар. Оба сервера приняли запись. Какой timestamp больше - неизвестно: часы разошлись на 80мс через NTP. Dynamo решил проблему не синхронизацией часов, а vector clocks - и это подход, который использует весь современный интернет.**

NTP (Network Time Protocol) синхронизирует часы с точностью ~1-100мс в зависимости от сети. Для событий внутри одного дата-центра (микросекунды) это неприемлемо. Часы на разных серверах неизбежно расходятся: CPU частоты разные, температура влияет на кристалл, виртуализация добавляет джиттер.

Лесли Лэмпорт в 1978 году предложил другой подход: вместо синхронизации часов ввести понятие **causal ordering** - причинно-следственного порядка. Если событие A является причиной события B (A отправило сообщение, которое B получило), то A предшествует B по определению. Не по времени - по причинности.

МетодТочностьПроблема
NTP1-100мсСлишком грубо для микросекундных событий
GPS/атомные часы~7мс интервал (Spanner)Дорого, не везде доступно
Lamport timestampsЧастичный порядокКонкурентные события неразличимы
Vector clocksПолный causal порядокРазмер растёт с числом узлов

Если использовать хорошую синхронизацию часов (GPS, атомные часы), проблема упорядочивания решена

Даже идеальная синхронизация не даёт точного порядка конкурентных событий - нужна causal ordering

Google Spanner использует атомные часы и GPS, но всё равно вынужден делать commit-wait ~7мс. Физическое время - вероятностный инструмент, logical clocks - детерминированный.

Почему NTP-синхронизация не решает проблему упорядочивания событий в распределённой системе?

Lamport Timestamps и отношение Happened-Before

**Статья Лэмпорта 1978 года "Time, Clocks, and the Ordering of Events in a Distributed System" - 8 страниц, которые создали область distributed computing. Более 15 000 цитирований. Idея: ввести логические часы как монотонно растущий счётчик, связанный с сообщениями между процессами.**

Отношение Happened-Before (--->)

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

Если ни a ---> b, ни b ---> a - события **конкурентны** (a || b). Это не значит "одновременны" - это значит нет причинно-следственной связи между ними. Конкурентные события могут случиться в любом порядке без нарушения корректности системы.

Правила Lamport Clock

  • Каждый процесс хранит счётчик L, начиная с 0
  • При локальном событии: L = L + 1
  • При отправке сообщения: L = L + 1, отправить L вместе с сообщением
  • При получении сообщения с timestamp T: L = max(L, T) + 1

**Критическое ограничение Lamport timestamps:** если L(a) < L(b), это НЕ значит, что a ---> b. Только если a ---> b, то гарантированно L(a) < L(b). Отношение однонаправленное. Это делает Lamport timestamps непригодными для обнаружения конкурентных записей.

P1 имеет Lamport counter = 3. Получает сообщение с timestamp = 7. Каким будет новый counter P1?

Vector Clocks: полный causal порядок

**Amazon Dynamo, 2007: корзина покупок - это AP-система (доступность важнее consistency). При конфликте Dynamo не выбирает победителя - он показывает оба варианта пользователю и просит разрешить. Для обнаружения конфликтов используются Vector Clocks. Без них Dynamo не мог бы отличить конфликт от нормальной последовательной записи.**

Vector Clock - это массив счётчиков, по одному на каждый процесс в системе. Вместо одного числа (Lamport) каждый процесс хранит вектор `[L1, L2, L3, ...]` где Li - сколько событий произошло на i-м процессе с точки зрения текущего узла.

Пример: обнаружение конфликта при репликации

ОперацияVector ClockСтатус
A: write(x=1)[A:1, B:0]ОК - первая запись
B: write(x=2) независимо[A:0, B:1]ОК - но конкурентно с A
A синхронизируется с BA видит [A:0, B:1]КОНФЛИКТ: [A:1,B:0] || [A:0,B:1]
Merge + разрешение[A:2, B:1]x = merge(1, 2) - приложение решает

Dynamo показывал конфликтные версии корзины пользователю - он видел все варианты и мог выбрать. Это называется "shopping cart semantics": лучше показать лишний товар, чем потерять. Riak и CouchDB используют аналогичный подход.

Vector clocks автоматически разрешают конфликты

Vector clocks только обнаруживают конфликты - разрешение это задача приложения

Dynamo при обнаружении [A:1,B:0] || [A:0,B:1] не знает, какое значение правильное. Он возвращает обе версии клиенту. Разрешение зависит от семантики данных: для корзины - union, для счётчика - сложение, для имени - спросить пользователя.

Vector clock A = [A:2, B:1], Vector clock B = [A:1, B:3]. Каков их порядок?

Hybrid Logical Clocks и применения

**CockroachDB, 2015: задача создать открытый аналог Google Spanner без атомных часов. Решение - Hybrid Logical Clocks (HLC). Принцип: совместить физическое время (NTP) с логическим счётчиком. Физическое время даёт привязку к реальности, счётчик гарантирует строгий порядок при совпадении timestamps. CockroachDB работает в production у тысяч компаний - и в основе каждой транзакции HLC.**

HLC хранит пару `(l, c)`, где `l` - максимальное наблюдённое физическое время, `c` - счётчик для разрешения коллизий при одинаковом `l`. Это позволяет читать HLC как обычное время (для дебага, мониторинга), но иметь строгий порядок как у Lamport clock.

Сравнение подходов

МеханизмПорядокЧитаемостьРазмерКто использует
LamportЧастичный (causal)Нет (счётчик)O(1)Базовые алгоритмы, Cassandra
Vector ClockПолный (causal + concurrent)НетO(N узлов)Dynamo, Riak, CouchDB
HLCЧастичный + физически близкийДа (читается как time)O(1)CockroachDB, YugabyteDB
TrueTime (Spanner)Глобальный strongДаO(1)Google Spanner

Vector Clocks имеют проблему масштабирования: вектор растёт с числом узлов. При 1000 узлах каждое сообщение несёт 1000 счётчиков. Dynamo решал это через version pruning - отбрасывание старых записей в векторе по времени или LRU.

В чём главное практическое преимущество HLC перед чистыми Lamport timestamps?

Вопросы для размышления

  • Dynamo показывает пользователю конфликтные версии корзины, когда vector clocks выявляют concurrent writes. Какие данные в реальных приложениях можно безопасно разрешать автоматически (без вмешательства пользователя), а какие - нет, и почему?

Связанные уроки

  • ds-04-clocks — Logical clocks are the basis for vector clocks
  • dist-06-ordering — Vector clocks implement causal ordering
  • ds-08-vector-clocks — Advanced patterns build on this introduction
  • ds-10-crdts — CRDTs use vector clocks for conflict detection
  • alg-18-topological
Логические часы и упорядочивание событий

0

1

Войти