Временная метка Лампорта
Алгоритм временных меток Лампорта — это простой алгоритм логических часов, используемый для определения порядка событий в распределенной компьютерной системе . Поскольку различные узлы или процессы, как правило, не полностью синхронизированы, этот алгоритм используется для обеспечения частичного упорядочения событий с минимальными издержками и концептуально обеспечивает отправную точку для более продвинутого метода векторных часов . Алгоритм назван в честь его создателя Лесли Лэмпорта .
Распределенные алгоритмы, такие как синхронизация ресурсов, часто зависят от некоторого метода упорядочивания функционирования событий. Например, рассмотрим систему с двумя процессами и диском. Процессы отправляют сообщения друг другу, а также отправляют сообщения на диск с запросом доступа. Диск предоставляет доступ в том порядке, в котором сообщения были получены . Например, процесс отправляет сообщение на диск с запросом доступа на запись, а затем отправляет сообщение с инструкцией чтения для обработки . Процесс получает сообщение и в результате отправляет на диск собственное сообщение с запросом на чтение. Если существует временная задержка, из-за которой диск получает оба сообщения одновременно, он может определить, какое сообщение произошло раньше другого: случается-раньше если можно получить от к последовательностью ходов двух типов: движение вперед, оставаясь в том же процессе, и отслеживание сообщения от его отправки до его получения. Алгоритм логических часов предоставляет механизм для определения фактов о порядке таких событий. Обратите внимание: если два события происходят в разных процессах, которые не обмениваются сообщениями прямо или косвенно через сторонние процессы, то мы говорим, что два процесса являются параллельными, то есть ничего нельзя сказать об упорядочении двух событий. [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;
Соображения
[ редактировать ]На каждые два разных события и происходящие в одном и том же процессе, и быть меткой времени для определенного события , необходимо, чтобы никогда не равен .
Поэтому необходимо, чтобы:
- Логические часы должны быть установлены так, чтобы между событиями был минимум один тактовый «тик» (приращение счетчика). и ;
- В многопроцессной или многопоточной среде может потребоваться прикрепить идентификатор процесса (PID) или любой другой уникальный идентификатор к метке времени, чтобы можно было различать события. и которые могут происходить одновременно в разных процессах.
Причинный порядок
[ редактировать ]Для любых двух событий и , если есть какой-то способ могло повлиять , затем временная метка Лампорта будет меньше временной метки Лампорта . Также возможно иметь два события, из которых мы не можем сказать, какое из них произошло первым; когда это происходит, это означает, что они не могли повлиять друг на друга. Если и не могут оказать никакого влияния друг на друга, тогда не имеет значения, кто из них появился первым.
Подразумеваемое
[ редактировать ]Часы Лампорта можно использовать для создания частичного упорядочения событий между процессами. Для логических часов, следующих этим правилам, справедливо следующее соотношение: если затем , где значит произошло-раньше .
Это соотношение действует только в одном направлении и называется условием согласованности часов : если одно событие происходит раньше другого, то логические часы этого события предшествуют другим. Условие строгой согласованности часов , которое является двусторонним (если затем ), можно получить с помощью других методов, таких как векторные часы. Используя только простые часы Лэмпорта, по часам можно вывести только частичный причинно-следственный порядок.
Однако, через контрапозитив , это правда, что подразумевает . Так, например, если затем не могло случиться-раньше .
Другой способ выразить это так: означает, что возможно, это произошло раньше или быть несравнимым с в случившемся-перед заказом, но не произошло после .
Тем не менее, временные метки Лампорта можно использовать для создания общего порядка событий в распределенной системе, используя какой-либо произвольный механизм разрыва связей (например, идентификатор процесса). Предостережение состоит в том, что этот порядок является искусственным, и на него нельзя полагаться как на причинно-следственную связь.
Логические часы Лэмпорта в распределенных системах
[ редактировать ]В распределенной системе на практике невозможно синхронизировать время между объектами (обычно рассматриваемыми как процессы) внутри системы; следовательно, сущности могут использовать концепцию логических часов, основанную на событиях, посредством которых они общаются.
Если два объекта не обмениваются сообщениями, то им, вероятно, не нужно использовать общие часы; события, происходящие на этих объектах, называются одновременными событиями.
Среди процессов на одной и той же локальной машине мы можем упорядочивать события на основе локальных часов системы.
Когда два объекта взаимодействуют посредством передачи сообщений, считается, что событие отправки происходит до события получения, и между событиями может быть установлен логический порядок.
Говорят, что распределенная система имеет частичный порядок, если мы можем установить отношения частичного порядка между событиями в системе. Если можно установить «тотальность», т. е. причинно-следственную связь между всеми событиями в системе, то говорят, что система обладает полным порядком.
У одной сущности не может быть одновременного возникновения двух событий. Если в системе существует общий порядок, мы можем определить порядок среди всех событий в системе. Если в системе существует частичный порядок между процессами (это тип порядка, который обеспечивают логические часы Лэмпорта), тогда мы можем определить порядок только между взаимодействующими сущностями. Лэмпорт обратился к упорядочиванию двух событий с одной и той же меткой времени (или счетчиком): «Чтобы разорвать связь, мы используем любой произвольный общий порядок процессов». [2] Таким образом, две временные метки или счетчики могут быть одинаковыми в распределенной системе, но при применении алгоритма логических часов происходящие события всегда будут поддерживать по крайней мере строгий частичный порядок.
Часы Лэмпорта приводят к ситуации, когда все события в распределенной системе полностью упорядочены. То есть, если , то мы можем сказать на самом деле это произошло раньше .
Обратите внимание, что с помощью часов Лэмпорта ничего нельзя сказать о фактическом времени. и . Если логические часы говорят , это не означает на самом деле, что на самом деле это произошло раньше в плане реального времени.
Часы Лэмпорта показывают отсутствие причинности, но не отражают всю причинность. Зная и шоу не вызвал или но мы не можем сказать, что инициировало .
Информация такого рода может быть важна при попытке воспроизведения событий в распределенной системе (например, при попытке восстановления после сбоя). Если один узел выходит из строя и мы знаем причинно-следственные связи между сообщениями, мы можем воспроизвести эти сообщения и учесть причинно-следственную связь, чтобы вернуть этот узел в то состояние, в котором он должен находиться. [3]
Альтернативы потенциальной причинности
[ редактировать ]Отношение «произошло до» отражает потенциальную, а не истинную причинность. В 2011–2012 годах Муниндар Сингх предложил декларативный мультиагентный подход, основанный на истинной причинности, называемый информационными протоколами. Информационный протокол определяет ограничения на связь между агентами, составляющими распределенную систему. [4] Однако вместо определения порядка сообщений (например, с помощью конечного автомата, распространенного способа представления протоколов в вычислениях), информационный протокол определяет информационные зависимости между сообщениями, которые могут отправлять агенты (конечные точки протокола). Агент может отправлять сообщение в локальном состоянии (его истории сообщений) только в том случае, если сообщение и состояние вместе удовлетворяют соответствующим информационным зависимостям. Например, информационный протокол для приложения электронной коммерции может указывать, что для отправки предложения с параметрами ID (уникификатором), товаром и ценой Продавец уже должен знать идентификатор и товар из его состояния, но может генерировать любую цену, которую он хочет. . Замечательная особенность информационных протоколов заключается в том, что хотя выбросы ограничены, прием — нет. В частности, агенты могут получать сообщения в любом порядке — прием просто приносит информацию, и нет смысла его задерживать. Это означает, что информационные протоколы могут применяться к неупорядоченным службам связи, таким как Протокол пользовательских датаграмм .
Более масштабная идея — это идея семантики приложений, идея проектирования распределенных систем на основе содержания сообщений, идея, заложенная в сквозном принципе . Современные подходы в значительной степени игнорируют семантику и фокусируются на обеспечении независимой от приложения («синтаксической») доставки сообщений и гарантий их упорядочения в коммуникационных службах, и именно здесь помогают такие идеи, как потенциальная причинность. Но если бы у нас был подходящий способ реализации семантики приложений, нам не понадобились бы такие коммуникационные сервисы. Достаточно неупорядоченной и ненадежной службы связи. Реальная ценность подхода информационных протоколов заключается в том, что он обеспечивает основу для подхода семантики приложений.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Распределенные системы, 3-е издание (2017 г.)» . РАСПРЕДЕЛЕННЫЕ-СИСТЕМЫ.NET . Проверено 20 марта 2021 г.
- ^ Jump up to: а б Лэмпорт, Л. (1978). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 .
- ^ «Часы и синхронизация — альфа-документация по распределенным системам» . book.cs.luc.edu . Проверено 13 декабря 2017 г.
- ^ «Информационно-ориентированное программирование, ориентированное на взаимодействие: BSPL, ослепительно простой язык протоколов» (PDF) . Проверено 24 апреля 2013 г.