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

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

7.6.1. Основные понятия

Основа отказоустойчивости — исправление после ошибок. Напомним, что ошиб­кой считается отказ части системы. Основная идея механизма исправления оши­бок состоит в замене ошибочного состояния безошибочным. Существует два ос­новных способа восстановления после ошибок.

При обратном исправлении (backward recovery) основная задача состоит в воз­вращении системы из текущего ошибочного состояния к предыдущему безоши­бочному состоянию. Чтобы сделать это, необходимо время от времени записы­вать состояние системы и восстанавливать ее в предыдущем состоянии, если дело пойдет плохо. При каждой записи текущего состояния системы (или его части) говорят, что создается контрольная точка (checkpoint).

Другой вариант исправления ошибок — прямое исправление (foiward reco­very). В этом случае при входе системы в ошибочное состояние вместо отката на­зад, к предыдущей контрольной точке, делается попытка перевести систему в но­вое корректное состояние, в котором она могла бы продолжать работать. Основ­ная проблема механизмов прямого исправления ошибок состоит в том, что для них необходимо заранее знать о возможных ошибках. Только в этом случае уда­стся исправить эти ошибки и перейти в новое состояние.

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

Альтернативный подход состоит в использовании так называемого метода коррекции разрушенной информации. В этом случае потерянный пакет создает­ся из других, успешно доставленных пакетов. Так, например, при использовании блочного кодирования от потерь (п, k) набор из k исходных пакетов преобразует­ся в набор п декодированных пакетов, так что любой набор из k декодированных пакетов подходит для реконструкции k исходных пакетов. Типичные значения k — 16 и 32, причем k<n<2k [383]. Если доставленных пакетов оказывается не­достаточно, отправителю придется продолжать передавать пакеты до тех пор, пока не удастся восстановить ранее потерянный пакет. Коррекция разрушенной ин­формации представляет собой типичный пример прямого исправления ошибки.

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

Однако обратное исправление ошибок также создает определенные проблемы [421]. Во-первых, восстановление системы или процесса в предыдущем состоя­нии — дело достаточно затратное с точки зрения производительности. Как мы увидим далее, обычно восстановление, например, отказавшего процесса или сай­та, обычно требует большого объема работы.

Во-вторых, поскольку механизмы обратного исправления ошибок не зависят от конкретного распределенного приложения, в котором они используются, не­возможно дать какие-либо гарантии того, что после исправления ошибок та же самая или похожая ошибка не возникнет вновь. Если подобные гарантии необ­ходимы, обработка ошибок обычно выполняется в цикле. Другими словами, при­менение механизмов обратного исправления ошибок не позволяет добиться пол­ностью прозрачного исправления ошибок.

И, наконец, хотя при обратном исправлении ошибок используются контроль­ные точки, в некоторые состояния вернуться просто невозможно. Например, ес­ли некий человек (возможно, злоумышленник) из-за неисправного банкомата внезапно получил 1000 долларов, шанс на то, что эти деньги удастся вернуть, очень невелик. Также невозможно и восстановление в предыдущее состояние большинства UNIX-систем после ввода следующей команды и выбора непра­вильного каталога:

/bin/пл -fr *

Некоторые вещи просто необратимы.

Контрольные точки позволяют вернуться в предыдущее правильное состоя­ние. Однако создание контрольной точки часто вызывает значительные затраты само по себе, что оборачивается значительными потерями производительности. Поэтому многие отказоустойчивые распределенные системы сочетают создание контрольных точек с протоколированием сообщений (message logging). В этом случае после создания контрольной точки процесс записывает свои сообщения перед отсылкой в журнал, что означает протоколирование отправителем (sender-based logging). Альтернативное решение — позволить принимающему процессу протоколировать приходящие сообщения перед их доставкой выполняемому приложению. Эта схема известна под названием протоколирования получателем (receiver-based logging). Если в принимающем процессе возникает отказ, он дол­жен восстановить состояние последней сохраненной контрольной точки, после чего может повторно запустить все принятые после нее сообщения. Таким обра­зом, комбинация из контрольных точек и протоколирования сообщений позво­ляет восстановить значительно более позднее состояние, чем состояние, сохра­ненное в последней контрольной точке, без дополнительных затрат на создание контрольных точек.

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

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

Устойчивые хранилища

Чтобы иметь возможность восстановить предыдущее состояние системы, требу­ется хранить нужную для восстановления информацию в безопасности. «В без­опасности» в данном случае означает, что хранимая информация должна выдержи­вать отказы системы и сайтов, а возможно, и различные повреждения хранилища. Устойчивые хранилища играют важную роль в восстановлении распределенных систем. Здесь мы кратко обсудим этот вопрос.

Хранилища делятся на три категории. Первая — это стандартная оперативная память, стирающаяся при отключении питания или перезагрузках машины. Сле­дующая категория — дисковые хранилища, переживающие ошибки процессора, но неспособные выжить при поломке головок диска.

И, наконец, существуют так называемые устойчивые хранилища (stable sto­rage), разработанные для выживания в любых «передрягах», кроме катастроф вроде наводнений или землетрясений. Устойчивые хранилища могут быть реа­лизованы в виде пары стандартных дисков, как это показано на рис. 7.15, а. Каж­дый блок устройства 2 является точной копией соответствующего блока устрой ства 1. Если блок диска изменяется, то сначала изменяется и проверяется блок устройства 1, а затем та же операция производится и с устройством 2.

Представим себе, что система отказала после изменения содержимого устрой­ства 1, но до изменения содержимого устройства 2, как показано на рис. 7.15, б. Во время исправления ошибок диски должны сравниваться поблочно. Если два соответствующих блока различны, это может означать, что правилен блок на устройстве 1 (поскольку устройство 1 всегда обновляется раньше устройства 2), а значит, новый блок копируется с устройства 1 на устройство 2. По завершении процесса восстановления оба диска снова будут идентичны.

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

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

Ниже мы подробнее рассмотрим вопросы, связанные с контрольными точка­ми и протоколированием сообщений. В [137] имеется обзор метода контрольных точек и протоколирования в распределенных системах. Различные детали алго­ритмов можно найти в [103].