Временная метка Лампорта

Алгоритм, используемый для определения порядка событий в распределенной компьютерной системе

Алгоритм временных меток Лампорта — это простой алгоритм логических часов, используемый для определения порядка событий в распределенной компьютерной системе . Поскольку различные узлы или процессы обычно не будут идеально синхронизированы, этот алгоритм используется для обеспечения частичного упорядочения событий с минимальными накладными расходами и концептуально обеспечивает отправную точку для более продвинутого метода векторных часов . Алгоритм назван в честь его создателя Лесли Лампорта .

Распределенные алгоритмы, такие как синхронизация ресурсов, часто зависят от некоторого метода упорядочивания событий для функционирования. Например, рассмотрим систему с двумя процессами и диском. Процессы отправляют сообщения друг другу, а также отправляют сообщения на диск с запросом доступа. Диск предоставляет доступ в порядке получения сообщений . Например, процесс отправляет сообщение на диск с запросом доступа к записи, а затем отправляет сообщение с инструкцией чтения процессу . Процесс получает сообщение и в результате отправляет свое собственное сообщение с запросом чтения на диск. Если есть задержка по времени, из-за которой диск получает оба сообщения одновременно, он может определить, какое сообщение произошло раньше другого: происходит раньше , если можно перейти от к с помощью последовательности ходов двух типов: перемещение вперед, оставаясь в том же процессе, и следование сообщению от его отправки до его получения. Алгоритм логических часов предоставляет механизм для определения фактов о порядке таких событий. Обратите внимание, что если два события происходят в разных процессах, которые не обмениваются сообщениями напрямую или косвенно через сторонние процессы, то мы говорим, что два процесса являются параллельными, то есть ничего нельзя сказать о порядке двух событий. ^[1] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Лампорт изобрел простой механизм, с помощью которого порядок « произошло-раньше» может быть зафиксирован численно. Логические часы Лампорта — это числовое значение программного счетчика, поддерживаемое в каждом процессе.

Концептуально эти логические часы можно рассматривать как часы, которые имеют значение только в отношении сообщений, перемещающихся между процессами. Когда процесс получает сообщение, он повторно синхронизирует свои логические часы с этим отправителем. Вышеупомянутые векторные часы являются обобщением идеи в контексте произвольного числа параллельных, независимых процессов.

Алгоритм

Алгоритм следует нескольким простым правилам:

1. Процесс увеличивает свой счетчик перед каждым локальным событием (например, событием отправки сообщения);
2. Когда процесс отправляет сообщение, он включает значение своего счетчика в сообщение после выполнения шага 1;
3. При получении сообщения счетчик получателя обновляется, если необходимо, до большего из его текущего счетчика и временной метки в полученном сообщении. Затем счетчик увеличивается на 1, прежде чем сообщение считается полученным. ^[2]

В псевдокоде алгоритм отправки выглядит следующим образом:

# событие известновремя = время + 1;# событие происходитотправить(сообщение, время);

Алгоритм получения сообщения:

(сообщение, временная метка) = receive();время = макс(отметка времени, время) + 1;

Соображения

Для каждых двух различных событий и , происходящих в одном и том же процессе, и являющихся временной меткой для определенного события , необходимо, чтобы никогда не было равно . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle C(x)}$ ${\displaystyle x}$ ${\displaystyle C(a)}$ ${\displaystyle C(b)}$

Поэтому необходимо, чтобы:

• Логические часы должны быть установлены таким образом, чтобы между событиями и был как минимум один «тик» часов (увеличение счетчика) ; ${\displaystyle a}$ ${\displaystyle b}$
• В многопроцессной или многопоточной среде может потребоваться прикрепить идентификатор процесса (PID) или любой другой уникальный идентификатор к временной метке, чтобы можно было различать события , которые могут происходить одновременно в разных процессах. ${\displaystyle a}$ ${\displaystyle b}$

Причинно-следственный порядок

Для любых двух событий и , если есть способ, который мог повлиять на , то временная метка Лампорта будет меньше временной метки Лампорта . Также возможно иметь два события, о которых мы не можем сказать, какое из них произошло раньше; когда это происходит, это означает, что они не могли повлиять друг на друга. Если и не могут оказать никакого влияния друг на друга, то неважно, какое из них произошло раньше. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Подразумеваемое

Часы Лампорта могут использоваться для создания частичного порядка событий между процессами. При наличии логических часов, соответствующих этим правилам, справедливо следующее отношение: если то , где означает произошло-до . ${\displaystyle a\rightarrow b}$ ${\displaystyle C(a)<C(b)}$ ${\displaystyle \rightarrow \,}$

Это отношение действует только в одну сторону и называется условием согласованности часов : если одно событие предшествует другому, то логические часы этого события предшествуют другому. Сильное условие согласованности часов , которое является двусторонним (если то ), может быть получено другими методами, такими как векторные часы. Используя только простые часы Лампорта, из часов можно вывести только частичное причинно-следственное упорядочение. ${\displaystyle C(a)<C(b)}$ ${\displaystyle a\rightarrow b}$

Однако, через контрапозицию , верно, что подразумевает . Так, например, если то не может быть раньше . ${\displaystyle C(a)\nless C(b)}$ ${\displaystyle a\nrightarrow b}$ ${\displaystyle C(a)\geq C(b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Другими словами, это означает, что событие могло произойти до или быть несравнимым с событием в порядке «произошло до», но не произошло после . ${\displaystyle C(a)<C(b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Тем не менее, временные метки Лампорта могут быть использованы для создания общего порядка событий в распределенной системе, используя некоторый произвольный механизм для разрыва связей (например, идентификатор процесса). Предостережение в том, что этот порядок является искусственным и не может быть использован для указания причинно-следственной связи.

Логические часы Лэмпорта в распределенных системах

В распределенной системе на практике невозможно синхронизировать время между сущностями (обычно рассматриваемыми как процессы) внутри системы; поэтому сущности могут использовать концепцию логических часов, основанную на событиях, посредством которых они взаимодействуют.

Если два объекта не обмениваются сообщениями, то им, вероятно, не нужно использовать общие часы; события, происходящие в этих объектах, называются параллельными событиями.

Среди процессов на одной и той же локальной машине мы можем упорядочить события на основе локальных часов системы.

Когда два объекта взаимодействуют посредством передачи сообщений, то говорят, что событие отправки происходит раньше события получения, и между событиями можно установить логический порядок.

Говорят, что распределенная система имеет частичный порядок, если мы можем иметь отношение частичного порядка между событиями в системе. Если «тотальность», т. е. причинно-следственная связь между всеми событиями в системе, может быть установлена, то говорят, что система имеет полный порядок.

У одной сущности не может быть двух событий, происходящих одновременно. Если в системе есть полный порядок, мы можем определить порядок среди всех событий в системе. Если в системе есть частичный порядок между процессами, что является типом порядка, который обеспечивают логические часы Лампорта, то мы можем определить порядок только между взаимодействующими сущностями. Лампорт обратился к упорядочению двух событий с одинаковой временной меткой (или счетчиком): «Чтобы разорвать связи, мы используем любой произвольный полный порядок процессов». ^[2] Таким образом, две временные метки или счетчика могут быть одинаковыми в распределенной системе, но при применении алгоритма логических часов происходящие события всегда будут поддерживать по крайней мере строгий частичный порядок. ${\displaystyle <}$

Часы Лампорта приводят к ситуации, когда все события в распределенной системе полностью упорядочены. То есть, если , то мы можем сказать, что на самом деле произошло до . ${\displaystyle a\rightarrow b}$ ${\displaystyle a}$ ${\displaystyle b}$

Обратите внимание, что с часами Лэмпорта ничего нельзя сказать о фактическом времени и . Если логические часы показывают , это не означает, что в действительности это произошло раньше с точки зрения реального времени. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle C(a)<C(b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Часы Лампорта показывают отсутствие причинности, но не охватывают всю причинность. Знание и показывает , что не вызвало или, но мы не можем сказать, что инициировало . ${\displaystyle a\rightarrow c}$ ${\displaystyle b\rightarrow c}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

Такая информация может быть важна при попытке воспроизвести события в распределенной системе (например, при попытке восстановления после сбоя). Если один узел выходит из строя, и мы знаем причинно-следственные связи между сообщениями, то мы можем воспроизвести эти сообщения и соблюдать причинно-следственные связи, чтобы вернуть этот узел в состояние, в котором он должен находиться. ^[3]

Альтернативы потенциальной причинности

Отношение «произошло раньше» фиксирует потенциальную причинность, а не истинную причинность. В 2011–2012 годах Муниндар Сингх предложил декларативный многоагентный подход, основанный на истинной причинности, называемый информационными протоколами. Информационный протокол определяет ограничения на коммуникации между агентами, составляющими распределенную систему. ^[4] Однако вместо указания порядка сообщений (например, через конечный автомат, распространенный способ представления протоколов в вычислениях), информационный протокол определяет информационные зависимости между коммуникациями, которые могут отправлять агенты (конечные точки протокола). Агент может отправлять коммуникацию в локальном состоянии (его история коммуникаций) только в том случае, если коммуникация и состояние вместе удовлетворяют соответствующим информационным зависимостям. Например, информационный протокол для приложения электронной коммерции может указывать, что для отправки предложения с параметрами ID (уникификатор), товар и цена продавец должен уже знать ID и товар из своего состояния, но может генерировать любую цену, которую захочет. Примечательной особенностью информационных протоколов является то, что, хотя выбросы ограничены, приемы — нет. В частности, агенты могут получать сообщения в любом порядке — приемы просто приносят информацию, и нет смысла их задерживать. Это означает, что информационные протоколы могут быть введены в действие через неупорядоченные коммуникационные службы, такие как UDP .

Более масштабная идея — это семантика приложений, идея проектирования распределенных систем на основе содержания сообщений, идея, заложенная в принципе end-to-end . Текущие подходы в значительной степени игнорируют семантику и фокусируются на предоставлении независимой от приложения («синтаксической») доставки сообщений и гарантий упорядочения в коммуникационных сервисах, где помогают такие идеи, как потенциальная причинность. Но если бы у нас был подходящий способ реализации семантики приложений, то нам бы не понадобились такие коммуникационные сервисы. Неупорядоченной, ненадежной коммуникационной службы было бы достаточно. Реальная ценность подхода информационных протоколов заключается в том, что он обеспечивает основы для подхода семантики приложений.

Смотрите также

• Матричные часы
• Векторные часы
• Версия вектора

Ссылки

1. "Распределенные системы 3-е издание (2017)". DISTRIBUTED-SYSTEMS.NET . Получено 2021-03-20 .
2. Lamport, L. (1978). "Время, часы и порядок событий в распределенной системе" (PDF) . Communications of the ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID  215822405.
3. "Часы и синхронизация — альфа-документация распределенных систем". books.cs.luc.edu . Получено 13.12.2017 .
4. "Информационно-ориентированное интерактивное программирование: BSPL, ослепительно простой язык протоколов" (PDF) . Получено 24 апреля 2013 г.