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

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

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

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

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

Алгоритм

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

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

В псевдокоде алгоритм отправки такой:

# event is known
time = time + 1;
# event happens
send(message, time);

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

(message, time_stamp) = receive();
time = max(time_stamp, time) + 1;

Соображения

На каждые два разных события $a$ и $b$ происходящие в одном и том же процессе, и $C(x)$ быть меткой времени для определенного события $x$ , необходимо, чтобы $C(a)$ никогда не равен $C(b)$ .

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

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

Причинный порядок

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

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

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

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

Однако, через контрапозитив , это правда, что $C(a)\nless C(b)$ подразумевает $a\nrightarrow b$ . Так, например, если $C(a)\geq C(b)$ затем $a$ не могло случиться-раньше $b$ .

Другой способ выразить это так: $C(a)<C(b)$ означает, что $a$ возможно, это произошло раньше $b$ или быть несравнимым с $b$ в случившемся-перед заказом, но $a$ не произошло после $b$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.
^ Перейти обратно: ^а ^б Лэмпорт, Л. (1978). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 .
^ «Часы и синхронизация — альфа-документация по распределенным системам» . book.cs.luc.edu . Проверено 13 декабря 2017 г.
^ «Информационно-ориентированное программирование, ориентированное на взаимодействие: BSPL, ослепительно простой язык протоколов» (PDF) . Проверено 24 апреля 2013 г.

[1] «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.

[Lamport_1978-2] Перейти обратно: ^а ^б Лэмпорт, Л. (1978). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 .

[3] «Часы и синхронизация — альфа-документация по распределенным системам» . book.cs.luc.edu . Проверено 13 декабря 2017 г.

[4] «Информационно-ориентированное программирование, ориентированное на взаимодействие: BSPL, ослепительно простой язык протоколов» (PDF) . Проверено 24 апреля 2013 г.

[1]

[2]

[3]

[4]