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

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

7.6. Восстановление 451

не входить в дополнительные детали, это делает такие вычисления достаточно

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

ных точек по сравнению с координированным созданием. Кроме того, как оказа-

лось,

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

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

кальных устойчивых хранилищах (см., например, [136]). Поэтому координиро-

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

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

Координированное создание контрольных точек

в соответствии с названием, при

координированном создании контрольных точек

(coordinated checkpointing)

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

пись их состояний в локальные устойчивые хранилища происходила одновре-

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

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

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

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

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

дали в главе 5. Этот алгоритм представляет собой пример неблокирующей коор-

динации контрольных точек.

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

ла блокировки. Сначала координатор рассылает всем процессам сообщение

CHECKPOINT_REQUEST.

Когда процесс получает это сообщение, он создает ло-

кальную контрольную точку, начинает выстраивать в очередь все последующие

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

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

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

CHECKPOINT_pONEy

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

полнение.

Легко заметить, что такой подход также приводит к записи глобально непро-

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

частью состояния контрольной точки. Это происходит потому, что никакие со-

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

частью локальной контрольной точки. В то же время исходящие сообщения (посы-

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

ложениям) сохраняются в локальной очереди до прихода сообщения

CHECK-

POINTJDONE,

Усовершенствованием этого алгоритма является групповая рассылка запроса

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

становления координатора. Процесс зависит от координатора, если он получает

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

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

ки.

Это приводит нас к понятию

инкрементного

снимка состояния (incremental

snapshot).

452 Глава 7. Отказоустойчивость

Для получения инкрементного снимка состояния координатор рассылает за-

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

та создания предыдущей контрольной точки посылал сообщения. Когда процесс Р

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

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

т.

д.

Процесс рассылает запрос только один раз. Когда будут определены все процес-

сы,

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

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

остановлены.

7.6.3. Протоколирование сообщений

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

—

довольно затратная

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

хранилище. Поэтому следует применять технологии сокращения числа кон-

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

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

—

это

протоколирование

coo6w,e7mu (message

logging).

Основная идея, лежащая в основании протоколирования сообщений, состоит

в том, что если удастся

воспроизвести

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

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

тойчивого хранилища. В этом случае, начиная от состояния контрольной точки,

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

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

Этот способ хорошо работает при соблюдении условий так называемой

кусоч-

но

детерминированной модели (piecewise deterministic

model).

Согласно этой моде-

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

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

которые мы обсуждали в главе 5 в контексте отношения «происходят раньше»

по Лампорту. Так, например, событием может быть выполнение инструкции, от-

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

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

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

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

детерминированных перед новым недетерминированным событием.

В результате интервал можно повторить с известным результатом, то есть аб-

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

детерминированного события. Соответственно, если мы запишем в журнал все

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

терминированным образом повторить все выполнение процесса.

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

становить для восстановления глобально непротиворечивого состояния, то для

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

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

7.6. Восстановление 453

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

они работают с процессами-сиротами.

Осиротевший процесс {orphan process) —

это процесс, состояние которого про-

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

цесса. В качестве примера рассмотрим ситуацию, представленную на рис. 7.18.

Процесс Qполучает от процессов PuR сообщения m1 ит2 соответственно, после

чего посылает сообщение тЗ процессу R. Однако в отличие от других сообщений

сообщение т2 в журнал не записывается. Если происходит отказ процесса

для

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

шем примере

—

m1. Поскольку сообщение т2 не сохранено в журнале, его пере-

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

изойдет, что и показано на рисунке.

Отказ от восстановления процесса Q

Поскольку нельзя воспроизвести т2,

^ . ^ также не удастся воспроизвести тЗ

Q ^Sr^;: Х--

^^-чж'.

Хч Х- I ^Д

т2 / \тЗ т2 / '^, тЗ

J. i4 /У,^^

Незапротоколированное сообщение Время ->

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

Рис. 7.18. Неправильное воспроизведение сообщений после восстановления

ведет к появлению осиротевших процессов

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

туации до его восстановления. Так, в частности, процесс Я хранит сообщение

(тЗ)у

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

при воспроизведении событий, имевших место перед сбоем, не происходит. По-

нятно, что такого противоречия нужно избегать.

Характеристические схемы протоколирования

сообщений

Чтобы характеризовать различные схемы протоколирования сообщений, мы ис-

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

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

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

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

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

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

шим его приложением.

Сообщение называется

устойчивым

(stable)^

если оно не может быть потеря-

но,

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

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

Каждое сообщение т отвечает за набор процессов DEP(m), которые зависят

от доставки т. В частности, DEP(m) состоит из тех процессов, которым должно

454 Глава 7. Отказоустойчивость

прийти это сообщение. Кроме того, если другое сообщение, т', причинно завися-

щее от доставки

т,

доставляется процессу Q, то Q также входит в набор DEP(m).

Отметим, что причинная зависимость т' от доставки т означает, что оно посы-

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

ние,

причинно зависящее от доставки т.

Набор COPY(m) состоит из тех процессов, которые содержат копию т, но

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

он также становится членом COPY(m). Отметим, что COPY(m) состоит из тех

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

Если все эти процессы отказали, очевидно, что воспроизведение передачи т ока-

зывается невозможным.

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

цесс.

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

сов.

Пусть Q

—

один из сохранившихся процессов. Процесс

является сиротой,

если существует такое сообщение т, что Q оказывается в наборе DEP(m), в то

время как все процессы из СОРУ(т) отказали. Другими словами, осиротевший

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

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

Чтобы предотвратить появление осиротевших процессов, необходимо гаран-

тировать, что в DEP(m) не будет выживших процессов, если откажут все процес-

сы в COPY(m). Система оказывается в таком состояние, если каждый процесс,

являющийся членом набора DEP(m), также является и членом набора

СОРУ(т).

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

т,

должен

хранить копию этого сообщения.

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

них представлен так называемыми

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

протоколи-

рования

(pessimistic

logging

protocols).

В этих протоколах предполагается, что для

каждого неустойчивого сообщения т имеется хотя бы один зависящий от него

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

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

в один процесс. Отметим, что как только т доставляется, скажем, в процесс Р,

этот процесс становится членом набора COPY(m).

Самое плохое, что может произойти,

—

процесс Р откажет еще до того, как бу-

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

цессу Р после получения сообщения т нельзя рассылать какие-либо сообщения,

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

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

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

зом, мы полностью предотвращаем появление осиротевших процессов.

В противоположность этому в протоколе

оптимистического

протоколирова-

ния

{optimistic logging protocol)

реальная работа начинается после отказа процес-

са.

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

сы из набора

СОРУ(т).

Согласно оптимистическому подходу любой осиротевший

процесс из DEP(m) откатывается в такое состояние, когда он перестает входить

в набор DEP(m).

7.7. Итоги 455

Как было указано в

[137],

пессимистическое протоколирование значительно

проще оптимистического, так что этот способ протоколирования сообщений при

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

7.7. Итоги

Отказоустойчивость

—

это важная область построения распределенных систем.

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

ние ошибок и исправлять их. Другими словами, система отказоустойчива, если

она продолжает функционировать при наличии отказов.

Существуют разные типы отказов. Поломка означает простую остановку сис-

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

входящие запросы. Если процесс отвечает слишком быстро или слишком мед-

ленно, мы говорим об ошибке синхронизации. Отклик на входящий запрос с ошиб-

кой

—

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

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

вольными или византийскими.

Избыточность

—

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

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

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

доставления некоторой услуги. В отказоустойчивых группах один или более

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

ность услуги, реализуемой группой. Часто необходимо, чтобы взаимодействие

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

сти поддерживало свойства строгой упорядоченности и атомарности.

Надежное групповое взаимодействие, именуемое также надежной групповой

рассылкой, может существовать в различных формах. До тех пор пока группы

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

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

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

зации масштабируемости становится снижение числа откликов, возвращающих

отчет об удачном (или неудачном) приеме разосланного сообщения.

Проблемы усложняются, когда требуется соблюсти атомарность. В протоко-

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

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

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

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

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

надежно. Сообщения никогда не пересекают границ.

Механизм изменения членства в группе

—

это пример того, что каждый про-

цесс должен согласиться с единым списком членов. Такое соглашение может

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

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

протокола двухфазного подтверждения координатор сначала проверяет готов-

456 Глава 7. Отказоустойчивость

ность всех процессов к выполнению одной и той же операции (то есть к ее под-

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

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

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

жения соглашения дожидаясь восстановления координатора.

Восстановление в отказоустойчивых системах неизменно организуется на ос-

нове регулярного сохранения информации о состоянии системы. Работа с кон-

трольными точками полностью распределена. К сожалению, создание контроль-

ной точки

—

довольно затратная операция. Для повышения производительности

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

ванием сообщений. Благодаря протоколированию взаимодействия между про-

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

Вопросы и задания

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

чему?

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

ломок?

Рассмотрим web-браузер, возвращающий устаревшие страницы из кэша, а не

обновленные с сервера. Является ли это ошибкой, и если да, какой это тип

ошибки?

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

справиться с византийскими ошибками?

Сколько отказавших элементов (обычных устройств и устройств голосова-

ния) может быть обработано схемой, представленной на рис. 7.1? Дайте при-

мер ошибки, которая может быть замаскирована.

6. Можно ли обобщить тройное модульное резервирование на пять элементов

в группе вместо трех? Если да, какие свойства будет оно иметь?

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

дойдет семантика «минимум однажды» или «максимум однажды»? Дайте раз-

вернутое объяснение.

^ Чтение и запись файлов на файловый сервер.

• Компиляция программы.

^ Домашний банк.

8. В случае асинхронных вызовов RPC клиент блокируется до момента получе-

ния его запроса сервером (см. рис. 7.12). В какой степени наличие ошибок

влияет на семантику асинхронных вызовов RPC?

9. Приведите пример, когда для группового взаимодействия вообще не нужно

никаких синхронизирующих сообщений.

10.

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

копии сообщений сохранялись на коммуникационном уровне с целью по-

вторной посылки?

7.7. Итоги 457

И. В какой степени важна масштабируемость для атомарных групповых рассы-

лок?

12.

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

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

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

тельно было сделано?

13.

Виртуальная синхронность аналогична слабой непротиворечивости распреде-

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

чек синхронизации. В этом контексте что будет аналогом строгой непротиво-

речивости?

14.

Каков разрешенный порядок доставки для комбинации FIFO и полностью

упорядоченной групповой рассылки (см. табл. 7.3)?

15.

Адаптируйте протокол для установки следующего представления G/+i в слу-

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

цессах.

16.

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

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

тора?

17.

Из нашего объяснения механизма трехфазного подтверждения можно по-

нять,

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

ли это?

18.

В случае кусочно детерминированной модели достаточно ли заносить в жур-

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

тия?

19.

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

пределенных транзакциях журнал с упреждающей записью.

20.

Нуждается ли в создании контрольных точек сервер без фиксации состоя-

ния?

21.

Протоколирование сообщений получателем обычно считается более правиль-

ным, чем протоколирование отправителем. Почему?

Глава 8

Защита

8.1.

Общие вопросы защиты

8.2. Защищенные каналы

8.3. Контроль доступа

8.4. Управление защитой

8.5. Пример — Kerberos

8.6. Пример — SESAME

8.7. Пример — электронные платежные системы

8.8. Итоги

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

—

это защита. Хотя мы рассматриваем защиту последней, по значимости она далеко

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

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

Единственная брешь в системе защиты может сделать бесполезными все пред-

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

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

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

Мы начнем с разговора о базовых понятиях защиты. Построение механизмов

защиты всех типов в системе на самом деле бессмысленно, если неизвестно, как

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

Для этого нужно знать реализуемые правила защиты. Сначала мы рассмотрим

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

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

вопросов криптографической защиты информации.

Системы защиты в распределенных системах можно разделить на две незави-

симые части. Одна из них

—

это связь между пользователями или процессами,

возможно, расположенными на различных машинах. Принципиальный способ

гарантировать защиту взаимодействия

—

это защищенный канал. Защищенные

каналы, и более конкретно, идентификация, целостность сообщений и конфи-

денциальность, обсуждаются в отдельном разделе.

8.1.

Общие вопросы защиты 459

Другая часть систем защиты

—

это авторизация, которая позволяет гаранти-

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

деленной системы, на которые имеют право. Авторизацию и контроль доступа

можно рассматривать совместно. В добавление к традиционным механизмам кон-

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

кодом, например с агентами.

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

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

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

зывается управлением защитой. В отдельном разделе мы рассмотрим вопросы,

связанные с управлением криптографическими ключами, управлением защитой

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

ступ к определенным ресурсам.

И, наконец, мы конкретизируем наше обсуждение, разобрав два примера реали-

зации средств защиты в распределенных системах. SESAME

—

это законченная

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

их

защР1ты.

Чтобы продемонстрировать абсолютно иной подход к защите распреде-

ленных систем, мы кратко рассмотрим электронные платежные системы, позволя-

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

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

8.1.

Общие вопросы защиты

Мы начнем наш разговор о защите распределенных систем с рассмотрения общих

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

система. Затем мы отделим правила защиты от механизмов защиты и обсудим

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

образом. Нашей второй темой станет обсуждение общих вопросов разработки

систем защиты. И наконец, мы кратко обсудим некоторые криптографические

алгоритмы, играющие ключевую роль в разработке протоколов защиты.

8.1.1.

Угрозы, правила и механизмы

Защита в компьютерных системах жестко связана с понятием

надежности

{de-

pendability). Говоря неформально, надежной компьютерной системой считается

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

[256].

Как мы говорили в

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

ремонтопригодность. Однако, если мы собираемся доверять компьютерной сис-

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

Под

конфиденциальностью

{confidentiality) мы понимаем свойство компьютер-

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

доверенных лиц.

Целостность

{integrity)

—

это характеристика, указывающая на

то,

что изменения могут быть внесены в систему только авторизованными лица-

ми или процессами. Другими словами, незаконные изменения в защищенной

460 Глава

Защита

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

ти компьютерной системы

—

это аппаратура, программы и данные.

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

—

считать, что

мы стараемся защитить службы и данные от угроз

защиты {security

threats). Мы

выделяем четыре типа угроз защите

[351]:

> перехват (interception);

4 прерывание (interruption);

модификация (modification);

> подделка (fabrication).

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

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

—

когда связь

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

Примером прерывания может служР1ть повреждение или потеря файла. Обыч-

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

вятся недоступными, уничтожаются, их невозможно использовать и т. п. В этом

смысле атаки типа «отказ в обслуживании» (denial of service), при которых кто-

то злонамеренно старается сделать определенную службу недоступной для дру-

гих,

—

это угроза защите, классифицируемая как прерывание.

Модификации включают в себя неавторизованные изменения данных или

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

ному предназначению. Примеры модификации включают перехват сообщений с

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

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

пользователей.

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

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

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

базу данных. Кроме того, иногда удается войти в систему, воспроизведя отправ-

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

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

как формы фальсификации данных.

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

всевозможным угрозам защите

—

это не метод построения защищенных систем.

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

Правила защиты

{security

policy) точно описывают разрешенные и запрещенные

действия для системных сущностей. В понятие «системные сущности» входят

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

ты можно сосредоточиться на механизмах

защиты {security

mechanisms),

посред-

ством которых реализуются эти правила. Наиболее важные из них:

> шифрование (encryption);

аутентификация (authentication);

4 авторизация (authorization);

4 аудит (auditing).