РАЗРАБОТКА И АНАЛИЗ РАСПРЕДЕЛЁНЫХ АЛГОРИТМОВ

Никола Санторо

перевод Заняла Ю.С.

Design And Analysis of Distributed Algorithms,Published by John Wiley & Sons, Inc., Hoboken, New Jersey; pgs.541-549)

ГЛАВА 9

Непрерывные Вычисления

9.1 Введение

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

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

Благодаря этому качеству такие вычисления называют непрерывными вычислениями.

Мы уже встречали одно такое вычисление в главе 4, когда имели дело с проблемой обслуживания таблиц маршрутизации. Рассматривавшиеся протоколы действительно не заканчивались пока имели место изменения в топологии сети или в состоянии трафика.

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

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

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

Но прежде, попробуем ответить на простой, но провокационный вопрос: какова стоимость непрерывного вычисления?

Поскольку вычисление никогда не заканчивается, ответ, очевидно, "бесконечна". В таком случае, стоимость вообще не важна, поскольку тогда все непрерывные вычисления имеют одинаковую стоимость. На самом деле, этот ответ говорит о том, что мы не должны (т.к. не можем) измерять общую стоимость полного выполнения непрерывного вычисления. Наиболее подходящие измерения выбираются в зависимости от характера задачи. Рассмотрим протокол пульсации, общая стоимость которого бесконечна. В этом случае значимая мера стоимости - это общее количество сообщений, используемых в одном импульсе: 2. В случае протоколов, обслуживающих таблицы маршрутизации, значимая мера – это общее количество сообщений, которыми обменивается система для изменений топологии.

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

9.2 ХРАНЕНИЕ ВИРТУАЛЬНОГО ВРЕМЕНИ

9.2.1 Виртуальное время и причинно-следственная связь

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

Однако есть случаи, когда такое понятие было бы полезно. Рассмотрим, например, ситуацию, когда необходимо отменить некоторую операцию а (например, передачу сообщения), которая была выполнена ошибочно. В этом случае придется отменить и все остальные операции (например, передачу других сообщений), которые были вызваны событием a. В таком контексте, необходимо определить, не является ли некоторое событие или действие b (например, передача другого сообщения некоторым объектом) вызванным (непосредственно или косвенно) действием a. Если нам известно, что а случилось после b, то есть t(a)>t(b), можно исключить, что b было вызвано a, тогда можно отменить а. Таким образом, доступ к реальному времени, хоть и не решил бы проблему полностью, однако был бы полезен.

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

Когда мы говорим о понятии общего времени, мы подразумеваем функцию T, которая каждому событию в системе ставит в соответствие своё значение из частично упорядоченного множества, причём не обязательно уникальное; мы обозначим знаком < частичную упорядоченность. Для выполнения своего назначения, эта функция должна удовлетворять двум основным свойствам:

• Упорядочивание локальных событий: пусть а и b два события, возникающих в объекте x, такие что t(a) < t(b). Тогда T(a)
• Упорядочивание приёма/передачи: пусть а – событие объекта x, которое передает сообщение соседнему объекту у, пусть b – событие, принимающее сообщение в объекте y. Тогда T(a)

Любую функцию T, удовлетворяющую этим двум свойствам будем называть виртуальным временем. Ещё одно желательное свойство, это свойство, позволяющее нам моделировать реальное время в задачах отмены. То есть если событие а “случилось после” bв виртуальном времени (т. е. T (a)> T (b)), значит а не вызывало b (ни непосредственно, ни косвенно). Уточним. Речь идёт о том случае, когда событие a является предпосылкой для bили просто его вызывает. Обозначим такую ситуацию как a -> b, если она отвечает хотя бы одному из следующих условий:

1. а и b происходят в одном и том же объекте и t(a)
2. а – событие объекта x, которое передает сообщение соседнему объекту у, и b– событие, принимающее сообщение в объекте y;
3. существует последовательность событий e1, e2..., ek , такая, что e1 = a, ek = b, и ei -> ei+1.

Будем говорить, что два события а и b связаны причинно-следственной связью, если a -> b или b -> a. Иногда события бывают вообще причинно не связаны: будем говорить, что а и b независимы, если a +> b и b +> a.

Теперь можем формально определить искомое свойство:

• Причинно-следственная связь: для любых двух событий а и b, если a -> b, то T(a)

Интересно, что одновременное выполнение свойств упорядоченности локальных событий и приёма/передачи, является достаточным, чтобы гарантировать причинно-следственную связь (упражнение 9.6.1):

Свойство 9.2.1 Пусть T - виртуальное временя. Тогда T удовлетворяет свойству причинно-следственной связи.

Вопрос в том, как могут объекты создавать виртуальное время T. По возможности, это должно быть сделано без генерации дополнительных сообщений. Для достижения этой цели, каждый объект x должен создавать и поддерживать виртуальные часы Tx, которые назначают целочисленное значение каждому событию, возникающему в локальном масштабе. Эти виртуальные часы полностью определяют функцию времени Т. Для события а, возникшего в x, T(a)=Tx(a); следовательно, часы должны быть разработаны и обслужены таким образом, чтобы функция T действительно являлась виртуальным временем. Наша цель состоит в том, чтобы спроектировать алгоритм, который определяет, как создать такие виртуальные часы и обслужить их. Ясно, что рассматриваемое виртуальное время является непрерывным вычислением.

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

Рассмотрим вновь случай операции отмены; причинно-следственная связь позволяет говорить только что если T(a)>T(b), то a +> b, в то время как нам необходимо на самом деле знать, выполняется ли a -> b. К примеру, было бы полезно, чтобы виртуальные часы удовлетворяли бы более строгому ограничению:

• Полная причинно-следственная связь: a>b тогда и только тогда, когда T(a)<T(b).

Если мы могли бы создать виртуальные часы, которые удовлетворяют свойству полной причинно-следственной связи, то было бы легко идентифицировать операции подлежащие отмене: чтобы окончательно отменить а мы должны отменить каждое b, для которого T(b)>T(a).

Обратите внимание, что реальное время не имеет полной причинно-следственной связи. Фактически, t(a)<t(b) не подразумевает, в общем, что а вызвало b! Другими словами, реальными часами не обеспечивается полная причинно-следственная связь. Это подразумевает что создание виртуальных часов с таким свойством – далеко не тривиальная задача.

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

В дальнейшем мы спроектируем алгоритм, создающий и поддерживающий виртуальные часы. Также мы разработаем систему виртуальных часов, которая удовлетворяет полной причинно-следственной связи. В обоих случаях, мы руководствуемся стандартными ограничениями IR (поиска информации): обеспечение связи, полная надежность и двунаправленные связи, а так же уникальные идентификаторы. Мы также учтем правило упорядочивания сообщений (т. е., связи по методу FIFO).

9.2.2 Причинно-следственная связь: «часы-счётчик»

Поскольку локальные события и действия сами по себе упорядочены с помощью локальных часов, то для создания и обслуживания виртуальных часов (то есть, часов, удовлетворяющих причинно-следственной связи), мы должны беспокоиться главным образом о взаимодействии между различными объектами. К счастью, объекты взаимодействуют непосредственно только с помощью сообщений; ясно что, операция передачи сообщения a генерирует событие получения сообщения b, то есть a -> b. Следовательно, мы должны обращаться с поступлением сообщения специфически, не так как с любым другим событием или локальным действием, ведь это - тот момент, когда локальные времена двух объектов, отправителя и получателя, входят в контакт. Мы должны убедиться, что причинно-следственная связь сохраняется разрабатываемыми часами. Приведем простой алгоритм для создания и обслуживания часов.

Алгоритм «часы-счётчик»:

1. Обеспечим каждый объект x локальным целочисленным счетчиком Cx для подсчёта локальных событий и действия, то есть Cx первоначально установлен в 0 и наращивается на 1 каждый раз, когда x реагирует на событие отличное от получения сообщения; наращивание происходит в начале действия.
2. Рассмотрим теперь взаимодействие между объектами. Всякий раз, когда объект x посылает сообщение соседнему объекту y, он добавляет в сообщение текущее значение своего локального счетчика. Всякий раз, когда объект y получает сообщение со значением счётчика count, он увеличивает свой локальный счётчик до Cy := 1 + max{Cy , count}

РИСУНОК 9.1: Виртуальное время, сгенерированное алгоритмом «часы-счётчик».

Рассмотрим, например, TED диаграмму, показанную на рисунке 9.1; сообщение, посланное от z к y содержит значение счётчика Cz = 5; как раз перед получением этого сообщения Cx = 3; при реакции на прибытие сообщения, x устанавливает Cx = 1 + max {5, 3} = 6.

Эта система локальных счетчиков определяет глобальную меру времени C; для любого события а объекта x, C(a) – это просто Cx(a). Обратите внимание, что каждый локальный счетчик полностью совместим со своими локальными часами. Для любых двух локальных событий а и b, Cx(a)<Cx(b), тогда и только тогда когда cx(a)<cx(b); поскольку локальные часы удовлетворяют свойству причинно-следственной связи для локальных событий, эти счетчики удовлетворяют свойству упорядоченности локальных событий. В то же время, если а - передача сообщения и b – его прием, тогда C(a)=Cx(a)<Cx(b)=C(b), то есть сохраняется упорядоченность приёма/передачи.

Другими словами, алгоритм «часы-счётчик» создаёт и поддерживает виртуальные часы:

Теорема 9.2.1 Пусть C - глобальное время, определенное местными счетчиками алгоритма часы-счётчик. Для любых двух действий и/или событий а и b, если a -> b, то C(a)<C(b).

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

Обратите внимание, что, хотя функция времени С, созданная алгоритмом «часы-счётчик», удовлетворяет свойству причинно-следственной связи, как и реальное время t,она может сильно отличаться от реального времени. Например (упражнения 9.6.2 и 9.6.3), возможно, что t(a)>t(b), в то время как C(a)<C(b). Также возможно, что два независимых события, встречающиеся в различных объектах в различное время, имеют одно и то же виртуальное время.

9.2.3 Полная причинно-следственная связь: «векторные часы»

С помощью виртуальных часов, сгенерированными алгоритмом «часы-счётчик», мы обеспечили выполнение свойства причинно-следственной связи, то есть если a>b, то C(a)<C(b). Однако, обратное не обязательно истинно. Фактически, возможно, что C(a)<C (b), но a +> b. Это значит что, если C(a)<C(b), то невозможно решить действительно ли а повлекло за собой b. Однако, как мы упоминали ранее, это именно та информация, которая является наиболее полезной, к примеру, в случае операции отмены.

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

Для простоты предположим, что объекты полностью упорядочены, например, путем ранжирования их согласно их идентификаторам (см. задачу 2.9.4); таким образом, обозначим объекты как x1, x2..., xn, где индекс объекта обозначает его позицию.

Алгоритм «векторные часы»:

1. Обеспечим каждый объект хi локальным целочисленным счетчиком Ci локальных событий, то есть Ci первоначально установлен в 0 и увеличивается на 1 каждый раз, когда хi реагирует на событие; приращение происходит в начале действия. Обеспечим также каждый объект хi n-мерным вектором Vi, по одному значению в векторе для каждого объекта в сети. Значение Vi[i] – это всегда значение локального счетчика Ci. Значение Vi[j], i≠j, первоначально устанавливается в 0 и может измениться только когда сообщение достигает хi, согласно правилу 2(b) описанному ниже.
2. Рассмотрим теперь взаимодействие между объектами.
   1. Всякий раз, когда объект, хi посылает сообщение соседнему xj, в сообщение включается вектор значений Vi.
   2. Всякий раз, когда объект xj обрабатывает получение сообщения с вектором значений vect, это обновляет его локальный вектор Vj следующим образом: для всех i≠j, устанавливается Vj[i] := max{vect[i], Vj[i]}.

Например, в TED диаграмме, показанной на рисунке 9.2, когда x1 получает сообщение от x2, его вектор - [2 0 0], в то время как сообщение содержит вектор [1 2 0]. Реагируя на сообщение, x1 сначала увеличит свой локальный счетчик, преобразовывая свой вектор в [3 0 0], а затем обрабатывает сообщение, преобразовывая его вектор в [3 2 0].

Рассмотрим событиe a в момент времени хi. Мы определяем Vi(a) следующим образом: если а является приемом сообщения, тогда Vi(a) - значение вектора Vi после его обновления при обработке сообщения. Для всех других событий (импульсы, сигнал будильника), Vi(a) является значением вектора Vi, только когда событие а обработано (вспомните, что локальный счетчик увеличивается при первой операции обработки).

РИСУНОК 9.2: Виртуальное время, сгенерированное алгоритмом «векторные часы».

Эта система локальных векторов определяет глобальную функцию времени V. Для любого события а в момент времени хi, V(a) – это есть Vi(a). Обратите внимание, что значения назначенные событиям функцией времени V являются векторами.

Теперь определим частичную упорядоченность, которую мы будем использовать для векторов. Если даны два n-мерных вектора А и B, будем считать что А≤B если А[i]≤B[i] для всех i; считаем что А<B тогда и только тогда когда А≤B и А[i]<B[i] хотя бы для одного i. Так, например, [1 2 0]<[3 2 0].

Обратите внимание, что из определения следует, что некоторые значения не сопоставимы; к примеру, [1 3 0][3 2 0] и [3 2 0][1 3 0].

Легко заметить, что глобальное частично упорядоченное время V, определенное таким образом, является виртуальным временем, то есть удовлетворяет свойству причинно-следственной связи. Фактически, по определению,

Свойство 9.2.2 Для любых двух событий а и b объекта хi, Vi(a)<Vi(b), тогда и только тогда, когда t(a)<t(b).

Это означает, что V удовлетворяет свойству упорядоченности локальных событий. Затем заметим, что эти локальные векторы удовлетворяют также свойству упорядоченности приёма/передачи (упражнение 9.6.4):

Свойство 9.2.3 Пусть а – событие, вследствие возникновения которого сообщение было передано от хi, пусть b - событие приема этого сообщения объектом xj. Тогда V(a)=Vi(a)<Vj(b)=V(b).

Исходя из этого, эти локальные векторы - действительно являются виртуальными часами:

Лемма 9.2.1 Для любых двух событий а и b, если a -> b, то V(a)<V(b).

Интересно, что, как уже упоминалось, истинно и обратное (упражнение 9.6.5):

Лемма 9.2.2 Для любых двух событий а и b, если V(a)<V(b), то a -> b.

Из лемм 9.2.1 и 9.2.2 следует, что локальные векторы удовлетворяют полному причинному порядку:

Теорема 9.2.2 Пусть V - глобальное время, определенное локальными счетчиками алгоритма «векторные часы». Для любых двух событий а и b, V(a)<V(b), тогда и только тогда, когда a -> b.

Векторные часы также имеют много других интересных свойств. Например, рассмотрим работу векторных часов, когда объект хi реагирует на событие a. Значение каждой компоненты векторных часов Vi(a) может дать точную информацию о том, сколько предшествующих событий причинно связано с a. Фактически,

Свойство 9.2.4 Пусть а - случай, возникший в объекте хi .

1. Vi(a)[j] - номер событий e, произошедших в объекте xi такой, что это e -> a.
2. Общее количество событий e, где e -> a равняется .

Также возможно для объекта xi сказать являются ли два полученных сообщения М’ и М” причинно связанными или независимыми;

Свойство 9.2.5 Пусть vect’ и vect” являются векторами, включенными, соответственно, в сообщения M’ и M”, которые были получены объектом xi. Если vect’<vect” или vect’>vect”, то события, которые вызвали передачу этих сообщений причинно связанны, иначе - они независимы.

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

Подсчитаем теперь стоимость алгоритма «векторные часы». Этот алгоритм требует, чтобы n-мерный вектор счетчиков был включен в каждое сообщение. В то же время, он гарантирует намного более сильную упорядоченность, которую не могут обеспечить даже реальные часы. Действительно, необходима размерность n чтобы обеспечить полную причинно-следственная связь, используя временные метки(задача 9.6.1).

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

Для больших систем с множеством связей, этот подход может значительно уменьшить общую сумму переданных данных относительно посылки полного вектора. Недостатком является увеличение памяти и накладных расходов: каждый объект xi должен хранить для каждого соседа xj и для каждого элемента вектора k последнее значение Vi[k], которое xi послал к xj. Другой недостаток состоит в том, что свойство 9.2.5 теперь не выполняется (упражнение 9.6.8).

9.2.4 Заключительные замечания

Особенность. В представленном алгоритме «векторные часы», мы предположили, что объекты изначально полностью упорядочены, и что каждый объект знает и свой порядковый номер, и общее количество объектов n. Это может быть выполнено, например, при помощи ранжирующего протокола по идентификаторам объектов. Стоимость для этой операции велика - O(n2) сообщений в худшем случае, даже если уже выбран первый объект и имеется покрывающее дерево. Однако, эти затраты были бы понесены только один раз, перед созданием часов.

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

Мы назовем этот алгоритм «псевдовекторные часы» и оставим его для самостоятельного рассмотрения и анализа в качестве упражнения (задача 9.6.2 и упражнение 9.6.9).

Ограничение «часовых» алгоритмов. Главная проблема, возникающая и с «часами-счётчиком», и с «векторными часами», это - то, что значения счетчиков непрерывно увеличиваются. Они всё время растут. Это означает что эти значения и, следовательно, разрядность сообщения не ограничены.

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

Любая стратегия по предотвращению этих неприятных последствий (задача 9.6.3) связана с увеличением стоимости и нарушением структуры алгоритма.