Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

5.2. Логические часы 291

^ V^[/]

—

это число событий, которые произошли с процессом Р, к настояще-

му времени.

> Если

Vi[j]

то процесс Р/ знает, что с процессом

Р,

произошло k событий.

Первое свойство поддерживается путем увеличения У, [г] на единицу при ка-

ждом новом событии, происходящем в процессе

Ру.

Второе свойство поддержива-

ется вложением векторов в посылаемые сообщения. Так, когда процесс Р/ посы-

лает сообщение т, он пересылает вместе с ним и его текущий вектор как отметку

времени vt.

Таким образом, получатель оказывается информированным о номере сообще-

ния, которое вызвало активность процесса Р/. Более важно, однако, что получа-

тель уведомляется о том, сколько сообщений от других процессов должны прий-

ти к нему до того момента, как процесс Р, послал ему сообщение т. Другими

словами, отметка времени vt в сообщении т говорит получателю, сколько собы-

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

может быть причинно-следственная связь. Когда процесс

получает т, это побужда-

ет его установить каждый элемент

Vj[k]

в собственном векторе в

max{Vj[k],

vt[k]}.

Вектор теперь отражает число сообщений, которые должен получить процесс Р/

и которые, как он видел, предшествовали посылке т. Затем элемент

Vj[i]

увели-

чивается на единицу, отражая факт получение сообщения ш, как следующего со-

общения от процесса Р,

[374].

Векторная отметка времени может использоваться для доставки сообщений

только без нарушения причинно-следственной связи. Рассмотрим далее пример

с электронной доской объявлений. Когда процесс Р, отправляет письмо, он осу-

ществляет множественную рассылку этого письма в виде сообщения а с помет-

кой времени

vt(a),

равной

Vi.

Когда другой процесс,

Pj,

получает а, он исправляет

свой собственный вектор, устанавливая

Vj[i] >

vt(a)[i].

Допустим теперь, что

посылает ответ на это письмо. Он делает это посред-

ством множественной рассылки сообщения г с отметкой времени vt(r)y равной Vj.

Отметим, что vt(r)[i] >vt(a)[i]. Если считать связь надежной, оба эти сообще-

ния

—

а, содержащее письмо, и г, содержащее ответ,

—

в конце концов достигнут

другого процесса,

Pk.

Поскольку мы не делали никаких предположений относи-

тельно очередности доставки сообщений, сообщение г может прийти процессу

раньше, чем сообщение

а.

Получив

г,

проверяет отметку времени vt(r) и реша-

ет отложить доставку до того момента, пока не будут приняты все сообщения,

которые по соображениям причинности идут перед г. Если подробнее, сообще-

ние г будет доставлено только в случае выполнения двух условий:

> vt(r)U] = Vklj] + 1.

> vt(r)[I] <

Vk[i]

для всех zVj.

Первое условие означает, что г — следующее сообщение, получаемое Pk от

процесса

Pj.

Второе условие означает, что

видит все те же сообщения, которые

видел процесс

Pj,

отправляя сообщение

г.

В частности, это означает, что процесс

уже получил сообщение а.

292 Глава 5. Синхронизация

Замечание по упорядоченной доставке сообщений

Некоторые системы промежуточного уровня, например ISIS и ее преемница

Horus [54], предоставляют поддержку полностью упорядоченной и упорядочен-

ной в плане причинности (надежной) групповой рассылки. В свое время шли

споры о том, должна ли эта поддержка быть реализована как часть уровня обмена

сообщениями или упорядочиванием должны заниматься приложения (см., к при-

меру, [59, 99].

В том чтобы поручить выяснение очередности сообщений уровню обмена со-

общениями, имеется две основные проблемы. Во-первых, поскольку уровень об-

мена сообщениями не знает, что на самом деле содержится в сообщениях, возмо-

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

одного отправителя, абсолютно независимые, на уровне обмена сообщениями

всегда будут считаться имеющими причинно-следственную связь. Подобный под-

ход слишком ограничен и может привести к проблемам с эффективностью.

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

удается выявить. Рассмотрим еще раз службу новостей. Представим себе, что

Алиса написала письмо. Если затем она позвонит Бобу и обсудит с ним написан-

ное,

Боб может написать ей в ответ другое письмо, не читая послания Алисы

в группе новостей. Другими словами, между письмом Боба и письмом Алисы име-

ется причинно-следственная связь, обусловленная внешним взаимодействием.

Такая причинно-следственная связь не выявляется системой сетевых новостей.

В сущности, вопросы упорядочивания, как и множество других вопросов свя-

зи,

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

рассмотрения приложений, с которыми осуществляется взаимодействие. Это явле-

ние [393] известно в проектировании систем под названием сквозного аргумента

{end-to-end argument). Оборотная сторона опоры исключительно на решения

прикладного уровня — в том, что разработчик вынужден сосредоточиваться на

вопросах, которые не относятся непосредственно к базовой функциональности

приложения. Так, например, упорядочение может не быть важнейшей пробле-

мой при разработке системы сообщений, например, сетевых новостей. В этом

случае наличие базового уровня передачи данных, обслуживающего упорядочен-

ность, может оказаться весьма кстати. Мы еще не раз вернемся к сквозным аргу-

ментам, в частности, при рассмотрении вопросов безопасности в распределен-

ных системах.

5.3. Глобальное состояние

Во многих случаях полезно знать глобальное состоянию, в соответствии с кото-

рым распределенная система функционирует в данное время. Глобальное состоя-

ние {global state) распределенной системы включает в себя локальные состояния

каждого процесса вместе с находящимися в пути сообщениями (то есть послан-

ными, но еще не доставленными). Что именно считать локальным состоянием

процесса, зависит от того, что нас интересует

[197].

В случае распределенной ба-

зы данных в него могут входить только те записи, из которых складывается часть

5.3. Глобальное состояние

293

базы данных, а временные записи, используемые для вычислений, можно исклю-

чить.

В нашем примере сборки мусора путем трассировки, который рассматри-

вался в предыдущей главе, локальное состояние могло бы состоять из перемен-

ных, представляющих метки для тех заместителей, скелетонов и объектов,

которые содержатся в адресном пространстве процесса.

Знание глобального состояния распределенной системы может быть полезно

по многим причинам. Так, например, если известно, что локальные вычисления

прекратились и ни одного сообщения в пути нет, ясно, что система перешла в со-

стояние прекращения всяческой деятельности. Анализируя глобальное состоя-

ние,

можно заключить, что мы либо зашли в тупик [71], либо распределенные

вычисления были корректно завершены. Пример такого анализа рассматривает-

ся ниже.

В простом способе непосредственный записи глобального состояния распре-

деленной системы, предложенном в [89], вводится понятие

распределенного

снимка состояния {distributed

snapshot),

отражающего состояние, в котором нахо-

дилась распределенная система. Важным его свойством является то, что он отра-

жает непротиворечивое глобальное состояние. В частности, это означает следую-

щее:

если в снимке записано, что процесс Р получил сообщение от процесса Q, то

там также должно быть записано, что процесс Q послал это сообщение. В про-

тивном случае снимок состояния содержал бы записи о сообщениях, которые бы-

ли приняты, но никогда никем не посылались. Тем не менее допустима обратная

ситуация, когда процесс Q послал сообщение, а процесс Р его еще не получил.

Непротиворечивый срез

Противоречивый срез

Р1

Р2

РЗ /

/ \

1 \

1 N.

время 1

-^^^т2

тЗ

Р1

Время-

Р2

РЗ /

/У ^

'--.-^^^^^^"-^2

-ч^рЗ

Отправителя сообщения т2

по этому срезу определить невозможно

а б

Рис. 5.9. Непротиворечивый срез (а). Противоречивый срез (б)

Понятие глобального состояния может быть представлено графически при

помощи так называемого

среза

{cut). На рис. 5.9, а непротиворечивый срез, пока-

занный пунктирной линией, пересекает оси времени трех процессов

—

Р1, Р2

иРЗ. Срез отражает последнее записанное событие для каждого из процессов.

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

общениях зафиксированы соответствующие события их отправки. В противопо-

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

т2

в процесс РЗ был записан, но в снимке состояния не зафиксировано соответ-

ствующего события его отправки.

294 Глава 5. Синхронизация

Для упрощения объяснения алгоритма создания распределенного снимка со-

стояния мы предположим, что распределенную систему можно представить в ви-

де набора процессов, соединенных друг с другом посредством однонаправленных

прямых коммуникационных каналов. Так, например, процессы могут на первом

этапе взаимодействия устанавливать соединения TCP.

Инициировать алгоритм может любой процесс. Инициировавший получение

распределенного снимка состояния процесс, скажем Р, начинает с записи собст-

венного локального состояния. Затем он посылает маркер по каждому из своих

исходящих каналов, давая понять, что получатель этого сообщения должен при-

нять участие в записи глобального состояния.

Когда процесс Q получает из входящего канала

маркер, все зависит от того,

записал он уже свое локальное состояние или нет. Если нет, он сначала записыва-

ет свое локальное состояние, а затем также рассылает маркеры по всем исходящим

каналам. Если же Q уже записал свое состояние, маркер, пришедший из кана-

ла С, показывает, что Q должен записать состояние канала. Это состояние скла-

дывается из последовательности сообщений, которые были приняты процессом Q

с момента записи им своего локального состояния и до прихода маркера. Запись

этого состояния иллюстрирует рис. 5.10.

Маркер F~~^ Локальная

^'**-—^ файловая

система

НТКЕНёН

-DOQH

ЩШЦ

НЕЕ

LUEEE

Записанное

состояние

Рис. 5.10. Организация процесса и каналов в распределенном снимке состояния (а).

Процесс О получает маркер впервые и записывает свое локальное состояние (б).

Процесс О записывает все входящие сообщения {в).

Процесс О получает маркер из входящего канала и заканчивает запись

состояния входящего канала (г)

Процесс сообщает о том, что он закончил свою часть алгоритма, после полу-

чения и обработки маркера от каждого из своих входящих каналов. В этот мо-

мент записанное локальное состояние, а также состояние, записанное для каждо-

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

инициировавшему создание снимка состояния. Последний может затем проана-

5.3. Глобальное состояние 295

лизировать текущее состояние. Отметим, что тем временем распределенная сис-

тема в целом продолжает работать обычным образом.

Следует отметить, что поскольку алгоритм может быть инициирован любым

процессом, одновременно может создаваться несколько снимков состояния. По-

этому маркер должен иметь идентификатор (а возможно, и номер версии) про-

цесса, который инициировал алгоритм. Только после того, как процесс получит

этот маркер по всем входным каналам, он может закончить построение своей

части ассоциированного с маркером снимка состояния.

Пример

—

определение момента завершения

Выяснив, как приложение получает снимок состояния, рассмотрим, как опреде-

лить момент завершения распределенных вычислений. Если процесс Q получает

маркер, запрашиваюгций снимок состояния, в первый раз, он рассматривает про-

цесс,

приславший этот маркер, как предшественника. Когда

завершает создание

своей части снимка состояния, он посылает своему предшественнику сообщение

ГОТОВО. Рекурсивным образом, когда инициатор создания распределенного

снимка состояния получает сообщения ГОТОВО от всех своих преемников, он

знает, что снимок состояния полностью готов.

Однако снимок состояния может показать глобальное состояние, в котором

сообщения еще находятся в пути. В частности, представим себе записи процесса

том, что он получил сообщение по одному из своих входящих каналов в период

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

Ясно,

что мы не можем сделать заключения об окончании распределенных вы-

числений, поскольку это сообщение может породить новые сообщения, которые

уже не будут частью снимка состояния.

Нам нужно получить снимок состояния со всеми пустыми каналами. Соот-

ветствующая несложная модификация алгоритма описывается ниже. Когда про-

цесс

заканчивает создание своей части снимка состояния, он посылает предшест-

веннику либо сообщение

ГОТОВО,

либо сообщение

ПРОДОЛЖИТЬ.

Сообщение

ГОТОВО

возвращается только в том случае, если выполнены условия:

4 все предшественники Q вернули сообщение

ГОТОВО;

между записью своего состояния и получением маркера процесс Q не при-

нимал сообщений ни по одному из своих входящих каналов.

Во всех прочих случаях процесс Q посылает предшественнику сообщение

ПРОДОЛЖИТЬ.

Существенно, что инициатор создания снимка состояния, скажем, процесс Р,

может получать от каждого из своих преемников либо сообщение

ПРОДОЛЖИТЬ,

либо сообщение

ГОТОВО.

Если были получены только сообщения

ГОТОВО,

то

понятно, что обычный обмен сообщениями отсутствует, а значит, вычисления

завершены. В противном случае процесс Р инициирует создание нового снимка

состояния и продолжает делать это, пока не получит полного комплекта сообще-

ний

ГОТОВО.

Были разработаны и другие решения задачи определения момента заверше-

ния вычислений, рассмотренной в этом пункте. Дополнительные ссылки и при-

296 Глава 5. Синхронизация

меры можно почерпнуть из [17, 421]. Обзор и сравнение различных решений

можно найти также в [285, 372].

5.4. Алгоритмы голосования

Многие распределенные алгоритмы требуют, чтобы один из процессов был коор-

динатором, инициатором или выполнял другую специальную роль. Обычно не

важно, какой именно процесс выполняет эти специальные действрш, главное, что-

бы он вообще существовал. В этом разделе мы рассмотрим алгоритмы, предна-

значенные для выбора координатора (это слово мы будем использовать в качест-

ве обобщенного имени специального процесса).

Если все процессы абсолютно одинаковы и не имеют отличительных характе-

ристик, способа выбрать один из них не существует. Соответственно, мы должны

считать, что каждый процесс имеет уникальный номер, например сетевой адрес

(для простоты будем считать, что на каждую машину приходится по процессу).

В общем, алгоритмы голосования пытаются найти процесс с максимальным

номером и назначить его координатором. Алгоритмы разлршаются способами

поиска.

Мы также считаем, что каждый процесс знает номера всех остальных процес-

сов.

Чего процессы не знают, так это то, какие из них в настоящее время работают,

а какие нет. Алгоритм голосования должен гарантировать, что если голосование

началось, то оно, рассмотрев все процессы, решит, кто станет новым координато-

ром. Известны различные алгоритмы, например, [153, 159, 419].

5.4.1.

Алгоритм забияки

в качестве первого примера рассмотрим

алгоритм

забияки

{bully

algorithm),

пред-

ложенный в

[159].

Когда один из процессов замечает, что координатор больше не

отвечает на запросы, он инициирует голосование. Процесс, например Р, проводит

голосование следующим образом.

Р посылает всем процессам с большими, чем у него, номерами сообщение

ГОЛОСОВАНИЕ.

Далее возможно два варианта развития событий:

> если никто не отвечает, Р выигрывает голосование и становится координа-

тором;

^ если один из процессов с большими номерами отвечает, он становится ко-

ординатором, а работа Р на этом заканчивается.

В любой момент процесс может получить сообщение

ГОЛОСОВАНИЕ

от од-

ного из своих коллег с меньшим номером. По получении этого сообщения полу-

чатель посылает отправителю сообщение

ОК,

показывая, что он работает и готов

стать координатором. Затем получатель сам организует голосование. В конце

концов, все процессы, кроме одного, отпадут, этот последний и будет новым ко-

5.4. Алгоритмы голосования 297

ординатором. Он уведомит

своей победе посылкой всем процессам сообщения,

гласящего, что

он

новый координатор

приступает

работе.

Если процесс, который находился

нерабочем состоянии, начинает работать,

он организует голосование. Если он оказывается процессом с самым большим

из

работающих процессов номером,

он

выигрывает голосование

берет

на

себя

функции координатора. Итак, побеждает всегда самый большой парень

горо-

дишке, отсюда

название «алгоритм забияки».

На рис. 5.11 приведен пример работы алгоритма забияки. Группа состоит

из

восьми процессов, пронумерованных

от

до 7.

Ранее коордршатором

был

про-

цесс

7, но он

завис. Процесс

первым замечает

это и

посылает сообщение

ГОЛОСОВАНИЕ

всем процессам

номерами больше, чем

него,

то

есть процес-

сам 5,

6 и 7,

как показано

на

рис. 5.11, а. Процессы

5 и 6

отвечают ОК, как пока-

зано на рис. 5.11, б. После получения первого

из

этих ответов процесс

понима-

ет,

что

«ему

не

светит»

коордршатором будет одна

из

этих более важных

личностей.

Он

садится

на

место

ожидает,

кто

станет победителем (хотя

уже

сейчас

он

может сделать довольно точное предположение).

D^*»

координатор «завис»

^ ©

Рис. 5.11. Голосование по алгоритму забияки

На ppic. 5.11,

показано, как оба оставшихся процесса,

5 и 6,

продолжают го-

лосование. Каждый посылает сообщения только

тем

процессам, номера

кото-

рых больше

их

собственных.

На

рис. 5.11,

процесс

сообгцает процессу

5, что

298 Глава 5. Синхронизация

голосование будет вести он. В это время

понимает, что процесс

мертв,

зна-

чит, победитель

—

он

сам. Если информация

состоянии сохраняется

на

диске

или где-то еще, откуда

ее

можно достать, когда

прежним координатором что-

нибудь случается, процесс 6 должен записать все что нужно на диск. Готовый за-

нять свою должность процесс

заявляет

об

этом путем рассылки сообщения

КООРДИНАТОР всем работающим процессам. Когда

получит

это

сообщение,

он продолжит работу

с той

операции, которую пытался выполнить, когда обна-

ружил, что процесс

мертв, используя теперь

качестве координатора процесс

Таким образом, мы обошли сбой

процессе 7,

работа продолжается.

Если процесс

запустится снова, ему будет достаточно послать всем осталь-

ным сообщение

КООРДИНАТОР

и вынудить

их

подчиниться.

5.4.2. Кольцевой алгоритм

Другой алгоритм голосования основан

на

использовании кольца.

отличие

от

некоторых других кольцевых алгоритмов

этом

не

требуется маркер. Мы пред-

полагаем, что процессы физически или логически упорядочены, так что каждый

из процессов знает, кто его преемник. Когда один из процессов обнаруживает, что

координатор не функционирует, он строит сообщение

ГОЛОСОВАНИЕ,

содержа-

щее его номер процесса,

посылает его своему преемнику. Если преемник не ра-

ботает, отправитель пропускает его

переходит

следующему элементу кольца

или

следующему, пока не найдет работающий процесс. На каждом шаге отпра-

витель добавляет свой номер процесса

списку в сообщении, активно продвигая

себя

качестве кандидата

координаторы.

В конце концов, сообщение вернется

процессу, который начал голосование.

Процесс распознает это событие

по

приходу сообщения, содержащего его номер

процесса. В этот момент тип сообщения изменяется на

КООРДИНАТОР

и вновь

отправляется

по

кругу,

на

этот

раз с

целью сообщить всем процессам,

кто

стал

координатором (элемент списка с максимальным номером)

какие процессы вхо-

дят

новое кольцо. После того

как

это сообщение один раз обойдет все кольцо,

оно удаляется

процессы кольца возвращаются

обычной работе.

координатор

выбыл

из

строя

Не отвечает

Сообщение

о голосовании

[2]

Рис. 5.12. Кольцевой алгоритм голосования

5.5. Взаимное исключение 299

На рис. 5.12 мы видим, что происходит, когда два процесса, 2 и 5, одновре-

менно обнаруживают, что предыдущий координатор, процесс 7, перестал рабо-

тать.

Каждый из них строит сообщение

ГОЛОСОВАНИЕ

и запускает это сообще-

ние в путь по кольцу независимо от другого. В конце концов, оба сообщения

проходят все кольцо, и процессы 2 и 5 превращают их в сообщения

КООРДИ-

НАТОР,

которые пересылаются тем же элементам кольца и в том же порядке.

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

Больше не происходит ничего такого, что потребовало бы дополнительного об-

мена сообщениями. Даже в наихудшем случае все проделанное столь незначи-

тельно загружает сеть, что это нельзя назвать расточительством.

5.5. Взаимное исключение

Системы, состоящие из множества процессов, обычно проще всего программиро-

вать,

используя критические области. Когда процесс нуждается в том, чтобы счи-

тать или обновить совместно используемые структуры данных, он сначала вхо-

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

ни один из процессов не использует одновременно с ним общие структуры дан-

ных. В однопроцессорных системах критические области защищаются семафорами,

мониторами и другими конструкциями подобного рода. Теперь мы рассмотрим

несколько примеров того, как именно критические области и взаимные исключе-

ния реализуются в распределенных системах. Описание этих методов и библио-

графию по ним можно найти в [373, 420].

5.5.1.

Централизованный алгоритм

Наиболее простой способ организации взаимных исключений в распределенных

системах состоит в том, чтобы использовать методы их реализации, принятые в

однопроцессорных системах. Один из процессов выбирается координатором (на-

пример, процесс, запущенный на машине с самым большим сетевым адресом).

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

сылает координатору сообщение с запросом, в котором уведомляет, в какую кри-

тическую область он собирается войти, и запрашивает разрешение на это. Если

ни один из процессов в данный момент не находится в этой критической области,

координатор посылает ответ с разрешением на доступ, как показано на рис.

5.13,

а.

После получения ответа процесс, запросивший доступ, входит в критическую об-

ласть.

Предположим теперь, что другой процесс, 2, запрашивает разрешение на вход

в ту же самую область (рис. 5.13, б). Координатор знает, что в этой критической

области уже находится другой процесс, и не дает разрешения на вход. Конкрет-

ный способ запрещения доступа зависит от особенностей системы. На рис. 5.13, б

координатор просто не отвечает, блокируя этим процесс 2, который ожидает от-

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

он ставит запрос от процесса 2 в очередь и ожидает дальнейших сообщений.

300 Глава 5. Синхронизация

Запрос

Координатор

Запрос /^ Освобождение

Ответа критической >1г /ОК

нет области

Очередь

пуста

Рис. 5.13. Процесс

запрашивает у координатора разрешение на вход в критическую

область, и разрешение дано (а). Процесс 2 запрашивает разрешение на вход в ту же

критическую область, и координатор не отвечает (б). Когда процесс

выходит

из критической области, он сообщает об этом координатору,

который разрешает доступ процессу 2 (е)

Когда процесс 1 покидает критическую область, он посылает координатору

сообщение, отказываясь от эксклюзивного доступа на область, как показано на

рис.

5.13, в. Координатор выбирает первый элемент из очереди отложенных за-

просов и посылает процессу разрешающее сообщение. Если процесс был блоки-

рован (то есть для него это первое сообщение от координатора), он разблокиру-

ется и входит в критическую область. Если процессу было отослано сообщение

с запретом на доступ, он будет опрашивать приходящие сообщения или блоки.

любом случае, увидев разрешение, он войдет в критическую область.

Легко заметить, что алгоритм гарантирует взаимное исключение: координа-

тор позволяет войти в каждую критическую область только одному процессу за

раз.

Это, П0МР1М0 всего прочего, честно, поскольку разрешения выдаются в том

же порядке, в каком они запрашивались. Никакой процесс никогда не ждет веч-

но (зависания отсутствуют). Схема также проста в реализации и использует для

работы с критической областью всего три сообщения (запросить, разрешить и

высвободить). Подобный алгоритм может использоваться и для другого выделе-

ния ресурсов, а не только для работы с критическими областями.

5.5.2. Распределенный алгоритм

Наличие даже одного неработающего места в централизованных алгоритмах час-

то недопустимо, поэтому исследователи обратились к распределенным алгорит-

мам взаимного исключения

[380].

Рассматриваемый алгоритм требуют наличия полной упорядоченности собы-

тий в системе. То есть в любой паре событий, например отправки сообщений,

должно быть однозначно известно, какое из них произошло первым. Алгоритм

Лампорта, представленный в пункте

5.2.1,

является одним из способов введения

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

времени распределенных взаимных исключений.

Алгоритм работает следующим образом. Когда процесс собирается войти в

критическую область, он создает сообщение, содержащее имя критической облас-

ти,

свой номер и текущее время. Затем он отсылает это сообщение всем процес-