Отметка времени Лэмпорта - Lamport timestamp

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

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

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

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

Алгоритм

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

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

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

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

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

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

Соображения

На каждые два разных события ${ displaystyle a}$ и ${ displaystyle b}$ происходящие в одном процессе, и ${ Displaystyle C (х)}$ метка времени для определенного события ${ displaystyle x}$ , необходимо, чтобы ${ Displaystyle C (а)}$ никогда не равняется ${ 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 С (а) <С (б)}$ , куда ${ Displaystyle rightarrow ,}$ средства случилось раньше.

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

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

Другой способ выразить это так: ${ Displaystyle С (а) <С (б)}$ Значит это ${ displaystyle a}$ можно иметь случилось раньше ${ displaystyle b}$ , или быть несравнимым с ${ displaystyle b}$ в случилось раньше заказ, но ${ displaystyle a}$ не произошло после ${ displaystyle b}$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[2] «Часы и синхронизация - альфа-документация распределенных систем». books.cs.luc.edu. Получено 2017-12-13.

[1]

[2]