Алгоритм Лэмпорта

Алгоритм Лэмпорта (алгоритм часов Лэмпорта, логические часы Лэмпорта) — это механизм, используемый в распределённых системах для присвоения уникальных временных меток событиям и установления причинно-следственных связей между ними (отношения «произошло-до»). Разработан американским учёным Лесли Лэмпортом в 1978 году. В отличие от физических часов, логические часы Лэмпорта не связаны с реальным астрономическим временем, а представляют собой счётчик, который увеличивается по определённым правилам.

История

Проблема синхронизации времени в распределённых системах возникла с развитием компьютерных сетей. В 1978 году Лесли Лэмпорт, работавший в Xerox PARC, опубликовал статью «Time, Clocks, and the Ordering of Events in a Distributed System» (время, часы и упорядочивание событий в распределённой системе). В ней он предложил формальную модель, которая позволяет определить, какое из двух событий произошло раньше, даже если они случились на разных узлах сети, не имеющих общего физического времени. Эта работа заложила основы для решения задач, связанных с согласованностью данных, взаимным исключением и отказоустойчивостью в распределённых системах.

Основные понятия

Причинно-следственная связь (отношение «произошло-до»)

В распределённой системе события могут быть связаны отношением причинности (happened-before, обозначается →). Событие a считается произошедшим до события b (a → b), если выполняется одно из трёх условий:

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

Если ни одно событие не произошло раньше другого (то есть a → b и b → a не выполняется), они считаются конкурентными (concurrent). В этом случае их порядок во времени не определён.

Логические часы

Логические часы — это функция, которая каждому событию в распределённой системе ставит в соответствие целое число (временную метку). Алгоритм Лэмпорта гарантирует, что если событие a произошло до события b, то временная метка a будет меньше временной метки b (C(a) < C(b)). Обратное неверно: из C(a) < C(b) не обязательно следует, что a → b.

Алгоритм

Каждый процесс (узел) в системе поддерживает свой собственный счётчик — логическое время (C). Алгоритм состоит из трёх правил, которые выполняются при наступлении событий:

1. Правило локального события: перед выполнением любого события на узле его счётчик увеличивается на единицу: C := C + 1. Событие получает новое значение C.
2. Правило отправки сообщения: перед отправкой сообщения узел увеличивает свой счётчик на единицу, присваивает сообщению текущее значение C (временную метку) и отправляет его.
3. Правило получения сообщения: при получении сообщения узел:

• Извлекает из сообщения временную метку (C_msg).
• Устанавливает свой счётчик равным максимуму из своего текущего значения и полученной метки: C := max(C, C_msg).
• Увеличивает счётчик на единицу: C := C + 1.
• Присваивает событию получения новое значение C.

Пример

Рассмотрим два процесса P1 и P2, обменивающихся сообщениями.

В этом примере:

• Событие A (C=1) произошло до отправки M (C=2) на P1.
• Получение M на P2 (C=2) произошло до отправки ответа (C=3) на P2.
• Отправка ответа (C=3) произошла до получения ответа на P1 (C=4).
• Событие B (C=1) и событие A (C=1) — конкурентны, так как нет причинно-следственной связи между ними. Их временные метки случайно равны.

Свойства и ограничения

Свойства

• Корректность: если a → b, то C(a) < C(b).
• Простота: алгоритм легко реализуется и не требует сложной аппаратной поддержки.
• Децентрализованность: каждый узел работает независимо, используя только локальные данные и информацию из сообщений.

Ограничения

• Неполнота: из C(a) < C(b) не следует a → b. Два события могут иметь разные временные метки, но быть конкурентными. Это происходит, например, когда два узла одновременно выполняют локальные события, не обмениваясь сообщениями.
• Коллизии: разные события могут получить одинаковые временные метки. Для разрешения коллизий на практике часто добавляют идентификатор узла к временной метке, образуя пару (C, ID), что гарантирует полную упорядоченность.

Применение

Алгоритм Лэмпорта является фундаментальным для многих распределённых систем и протоколов:

• Взаимное исключение: алгоритм Лэмпорта для взаимного исключения (Lamport's bakery algorithm) использует временные метки для определения, какой процесс может войти в критическую секцию.
• Репликация данных: в системах с репликацией (например, в базах данных) логические часы помогают определить, какая копия данных является более новой.
• Распределённые транзакции: для обеспечения изоляции и согласованности транзакций в распределённых СУБД.
• Отладка распределённых систем: для восстановления последовательности событий и выявления причин ошибок.
• Протоколы консенсуса: алгоритмы, такие как Paxos и Raft, используют логическое время для упорядочивания предложений и голосов.

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

• Векторные часы: обобщение часов Лэмпорта, которое позволяет не только определять отношение «произошло-до», но и выявлять конкурентные события. Векторные часы хранят вектор логических времён всех узлов системы.
• Физические часы: реальные часы (например, NTP), которые могут быть неточными в распределённых системах из-за задержек и дрейфа. Алгоритм Лэмпорта не зависит от их точности.
• Глобальное состояние: снимок состояния распределённой системы, который может быть получен с помощью алгоритма Чанди-Лэмпорта.

Источники

1. Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558-565.
2. Tanenbaum, A. S., & Van Steen, M. (2007). Distributed systems: principles and paradigms. Pearson Prentice Hall.
3. Coulouris, G., Dollimore, J., Kindberg, T., & Blair, G. (2011). Distributed systems: concepts and design. Addison-Wesley.