Причинно-следственное упорядочение, логические часы, репликация конечного автомата
Ключевые слова и синонимы
Репликация конечного автомата; активная репликация
Постановка задачи
Данная статья охватывает несколько задач, тесно связанных друг с другом. Первая задача заключается в поддержке отношения причинно-следственной связи между событиями в распределенной системе. Это нужно для того, чтобы дать распределенным системам без явного доступа к физическим часам какое-то представление о времени. Лэмпорт [5] определяет понятие логических часов, которые могут использоваться для генерации временных меток, согласующихся с отношениями причинно-следственной связи (в консервативном смысле слова). Он приводит в пример логические часы (также называемые часами Лэмпорта) с распределенным алгоритмом взаимного исключения. Этот алгоритм является иллюстрацией репликации конечного автомата. В сущности, он генерирует общее упорядочение событий, согласованное в масштабах всех процессов. Если все процессы начинаются в одном и том же состоянии, они развиваются согласованно, не требуя дальнейшей синхронизации.
Модель системы
Система состоит из набора процессов. Каждый процесс состоит из последовательности событий. Процессы не имеют общей памяти и общаются друг с другом только посредством обмена сообщениями. Точное определение события зависит от конкретной рассматриваемой системы и уровня абстракции, на котором она рассматривается. Различают три разновидности событий: внутреннее (влияет только на исполняющий его процесс), отправка и получение.
Причинно-следственное упорядочение
Причинно-следственное упорядочение относится к задаче, в которой появление некоторых событий может повлиять на другие события в будущем, тогда как другие события не могут влиять друг на друга. В случае процессов, не измеряющих время, понятие одновременности необходимо переопределить следующим образом: одновременными являются такие события, которые потенциально не способны повлиять друг на друга. Для этого необходимо определить, что имеет место, когда одно событие происходит ранее другого.
Следующее отношение «произошло ранее» определяется как нерефлексивное частичное упорядочение на множестве всех событий в системе [5].
Определение 1. Отношение "[math]\displaystyle{ \to }[/math]" на множестве событий в системе представляет собой наименьшее отношение, удовлетворяющее следующим трем условиям:
1. Если a и b – события в одном и том же процессе и a встречается раньше b, то [math]\displaystyle{ a \to b }[/math].
2. Если событие a представляет собой отправку сообщения одним процессом, а b – получение того же сообщения другим процессом, то [math]\displaystyle{ a \to b }[/math].
3. Если [math]\displaystyle{ a \to b }[/math] и [math]\displaystyle{ b \to c }[/math], то [math]\displaystyle{ a \to c }[/math] .
Определение 2. Два различных события a b называются одновременными, если [math]\displaystyle{ a \nrightarrow b }[/math] и [math]\displaystyle{ b \nrightarrow a }[/math].
Логические часы
Лэмпорт также дает общее определение часов следующим образом.
Определение 3. Часы [math]\displaystyle{ C_i \; }[/math] для процесса [math]\displaystyle{ p_i \; }[/math] представляют собой функцию, которая назначает число [math]\displaystyle{ C_i \langle a \rangle \; }[/math] любому событию [math]\displaystyle{ a \; }[/math] в этом процессе. Полная система часов представлена функцией C, которая назначает любому событию [math]\displaystyle{ b \; }[/math] число [math]\displaystyle{ C \langle b \rangle \; }[/math], где [math]\displaystyle{ C \langle b \rangle = C_j \langle b \rangle }[/math], если [math]\displaystyle{ b \; }[/math] является событием в процессе [math]\displaystyle{ p_j \; }[/math]. Система часов должна удовлетворять следующему условию:
для любых событий a и b, если [math]\displaystyle{ a \to b }[/math], то [math]\displaystyle{ C \langle a \rangle \lt C \langle b \rangle }[/math].
Предположим, что имеется некоторое произвольное полное упорядочение [math]\displaystyle{ \prec }[/math] процессов (например, уникальные имена, лексикографически упорядоченные). Лэмпорт расширяет отношение «произошло ранее» и определяет отношение "[math]\displaystyle{ \Rightarrow }[/math]" как полное упорядочение на множестве всех событий в системе.
Определение 4. Отношение полного упорядочения [math]\displaystyle{ \Rightarrow }[/math] определяется следующим образом. Если [math]\displaystyle{ a \; }[/math] – событие в процессе [math]\displaystyle{ p_i \; }[/math], а [math]\displaystyle{ b \; }[/math] – событие в процессе [math]\displaystyle{ p_j \; }[/math], тогда [math]\displaystyle{ a \Rightarrow b }[/math] в том и только том случае, когда удовлетворяется одно из следующих условий:
1. [math]\displaystyle{ C_i \langle a \rangle \lt C_j \langle b \rangle }[/math]
2. [math]\displaystyle{ C_i \langle a \rangle = C_j \langle b \rangle }[/math] и [math]\displaystyle{ p_i \prec p_j }[/math].
В работе [5] Лэмпорт также обсуждает адаптацию этих условий к физическим часам и предлагает простой алгоритм синхронизации часов. Здесь эти вопросы рассматриваться не будут.
Репликация конечного автомата
Задача репликации конечного автомата была изначально предложена Лэмпортом [4, 5]. В более позднем обзоре задачи Шнайдер [8] определяет ее следующим образом (формулировка адаптирована к контексту данной статьи).
Задача 1. (Репликация конечного автомата)
Дано: Множество одновременных запросов. Требуется: найти последовательность запросов, обрабатываемых каждым процессом, такую, что:
1. Координация реплик: все реплики получают и обрабатывают одну и ту же последовательность запросов.
2. Согласие: каждая реплика, не находящаяся в ошибочном состоянии, получает каждый запрос.
3. Порядок: каждая реплика, не находящаяся в ошибочном состоянии, обрабатывает получаемые запросы в одном и том же относительном порядке.
В работе [5], посвященной логическому времени и обсуждаемой в данной статье, Лэмпорт не учитывает ошибочные состояния. Он рассматривает их в другой работе, посвященной репликации конечного автомата для устойчивости к ошибкам [4] и опубликованной в том же году.
Основные результаты
Лэмпорт [5] изложил несколько важных результатов, имеющих отношение к вышеописанным задачам.
Логические часы
Лэмпорт [5] определяет элегантную систему организации логических часов, удовлетворяющую условию, изложенному в определении 3. Часы процессы [math]\displaystyle{ p_i \; }[/math] представлены регистром [math]\displaystyle{ C_i \; }[/math], таким, что [math]\displaystyle{ C_i \langle a \rangle }[/math] представляет собой значение, хранящееся в [math]\displaystyle{ C_i \; }[/math] в момент выполнения события [math]\displaystyle{ a \; }[/math]. Каждое сообщение m несет временную метку [math]\displaystyle{ T_m \; }[/math], которая равна времени отправки m. Система часов может быть описана при помощи следующих правил:
1. Каждый процесс [math]\displaystyle{ p_i \; }[/math] увеличивает [math]\displaystyle{ C_i \; }[/math] между любыми двумя последовательными событиями.
2. Если событие [math]\displaystyle{ a \; }[/math] заключается в отправке сообщения m процессом [math]\displaystyle{ p_i \; }[/math], то сообщение m содержит временную метку [math]\displaystyle{ T_m = C_i \langle a \rangle }[/math].
3. После получения сообщения m процесс [math]\displaystyle{ p_j \; }[/math] присваивает регистру [math]\displaystyle{ C_j \; }[/math] значение [math]\displaystyle{ max(C_j, T_m + 1) \; }[/math] (еще до выполнения события получения).
Репликация конечного автомата
Для иллюстрации использования логических часов Лэмпорт описывает [5] алгоритм взаимного исключения. Он также отмечает, что этот подход является более общим, и обсуждает понятие репликации конечного автомата, которое детально излагает в другой работе [4].
Алгоритм взаимного исключения основывается на следующей идее: каждый процесс поддерживает копию очереди запросов, а алгоритм гарантирует, что копии во всех процессах остаются согласованными. Это достигается за счет полного упорядочения сообщений с запросами согласно временным меткам, полученным от логических часов процессов-отправителей.
Описанный алгоритм работает при выполнении следующих упрощающих предположений:
• Каждое отправленное сообщение в конечном итоге оказывается получено.
• Для любых процессов [math]\displaystyle{ p_i \; }[/math] и [math]\displaystyle{ p_j \; }[/math] сообщения от [math]\displaystyle{ p_i \; }[/math] к [math]\displaystyle{ p_j \; }[/math] оказываются получены в том же порядке, в котором они были отправлены.
• Процесс может отправлять сообщения напрямую всем остальным процессам.
Алгоритм требует, чтобы каждый процесс поддерживал собственную очередь запросов, и гарантирует, что очереди запросов разных процессов всегда остаются согласованными. Вначале все очереди запросов содержат по одному сообщению [math]\displaystyle{ (T_0, p_0, request) \; }[/math], где [math]\displaystyle{ p_0 \; }[/math] – процесс, который содержит ресурс, а временная метка [math]\displaystyle{ T_0 \; }[/math] меньше исходного значения каждого экземпляра часов. Затем алгоритм работает следующим образом.
1. Когда процесс [math]\displaystyle{ p_i \; }[/math] запрашивает ресурс, он отправляет сообщение с запросом [math]\displaystyle{ (T_m, p_i, request) \; }[/math] всем остальным процессам и помещает его в свою очередь запросов.
2. Когда процесс [math]\displaystyle{ p_j \; }[/math] получает сообщение [math]\displaystyle{ (T_m, p_i, request) \; }[/math], он помещает его в свою очередь запросов и направляет уведомление [math]\displaystyle{ (T_{m'}, p_j, ack) \; }[/math] процессу [math]\displaystyle{ p_i \; }[/math].
3. Когда процесс [math]\displaystyle{ p_i \; }[/math] освобождает ресурс, он удаляет все экземпляры сообщений [math]\displaystyle{ ( - , p_i, request) \; }[/math] из своей очереди и отправляет сообщение об освобождении ресурса [math]\displaystyle{ (T_{m'}, p_i, release) \; }[/math] всем остальным процессам.
4. Когда процесс [math]\displaystyle{ p_j \; }[/math] получает сообщение об освобождении ресурса от процесса [math]\displaystyle{ p_i \; }[/math], он удаляет все экземпляры сообщений [math]\displaystyle{ ( - , p_i, request) \; }[/math] из своей очереди и отправляет процессу [math]\displaystyle{ p_i \; }[/math] уведомление, снабженное временной меткой.
5. Сообщения в очереди отсортированы согласно отношению полного упорядочения [math]\displaystyle{ \Rightarrow }[/math] из определения 4. Процесс [math]\displaystyle{ p_i \; }[/math] может использовать ресурс в случае, когда: (а) сообщение [math]\displaystyle{ (T_m, p_i, request) \; }[/math] оказывается первым в очереди, и (б) процесс [math]\displaystyle{ p_i \; }[/math] получил от всех остальных процессов сообщения с временными метками, большими, чем [math]\displaystyle{ T_m \; }[/math] (или равными ей – от любого процесса [math]\displaystyle{ p_j \; }[/math], где [math]\displaystyle{ p_i \prec p_j \; }[/math]).
Применение
Приведем краткий обзор вариантов применения понятий, представленных в данной статье.
Прежде всего, понятие причинно-следственной связи в распределенных системах (либо его отсутствие) приводит к известной проблеме, когда пользователь потенциально может увидеть ответ до того, как увидит соответствующий вопрос. Независимая от времени характеризация причинно-следственной связи Лэмпорта способствует разработке эффективных решений для организации причинно-следственного упорядочения в коммуникациях. В более поздней работе [3] Лэмпорт предлагает более общее определение отношения «произошло ранее», благодаря чему система может быть характеризована на различных уровнях абстракции.
Спустя десять лет после разработки Лэмпортом идеи логических часов Фидж [2] и Мэттерн [6] разработали понятие векторных часов, преимуществом которого является полная характеризация причинно-следственного упорядочения. И в самом деле, условие, которое является обязательным для логических часов Лэмпорта, является не более чем односторонней импликацией (см. определение 3). Напротив, векторные часы расширяют понятие логических часов Лэмпорта, гарантируя, что для любых событий [math]\displaystyle{ a \; }[/math] и [math]\displaystyle{ b \; }[/math] в случае [math]\displaystyle{ C \langle a \rangle \lt C \langle b \rangle }[/math] верно [math]\displaystyle{ a \to b }[/math]. Это может оказаться полезным, например, при выборе множества контрольных точек после восстановления распределенной системы, для распределенной отладки или обнаружения взаимоблокировок. Другие предлагавшиеся расширения идеи логических часов рассмотрели в своем обзоре Рейналь и Сингал [7].
Репликация конечного автомата также имеет много вариантов применения. В частности, она нередко используется для репликации распределенного сервиса по нескольким процессорам, благодаря чему сервис может продолжать работу даже в случае отказа некоторых процессоров. Репликация конечного автомата гарантирует согласованность различных реплик.
Алгоритм взаимного исключения, предложенный Лэмпортом в [5] и описанный в данной статье, является одним из первых известных решений задачи атомарной широковещательной передачи. Вкратце, для системы с несколькими процессами, одновременно отправляющими широковещательные сообщения, эта задача требует, чтобы все процессы доставляли (и обрабатывали) все сообщения в одном и том же порядке. На сегодня существует уже несколько подходов к решению этой задачи. Изучив множество алгоритмов, Дефаго и др. [1] классифицировали алгоритм Лэмпорта как алгоритм истории коммуникаций в силу способа генерации упорядочения.
См. также
Литература
1. Defago, X., Schiper, A., Urban, P.: Total order broadcast and multicast algorithms:Taxonomy and survey. ACM Comput. Surv. 36, 372^21 (2004)
2. Fidge, С J.: Logical time in distributed computing systems. IEEE Comput. 24,28-33 (1991)
3. Lamport, L.: On interprocess communication. Part I: Basic formalism. Distrib. Comput. 1, 77-85 (1986)
4. Lamport, L.: The implementation of reliable distributed multiprocess systems. Comput. Netw. 2,95-114 (1978)
5. Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21,558-565 (1978)
6. Mattern, F.: Virtual time and global states of distributed systems. In: Cosnard, M., Quinton, P. (eds.) Parallel and Distributed Algorithms, pp.215-226. North-Holland, Amsterdam (1989)
7. Raynal, M., Singhal, M.: Capturing causality in distributed systems. IEEE Comput. 29,49-56 (1996)
8. Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22,299-319(1990)
