Детекторы сбоев: различия между версиями

Частичная синхронность; тайм-ауты; информация о сбоях; распределенные оракулы

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

''Сбои'' и ''асинхронность'' являются основополагающими компонентами невозможности достижения консенсуса. Эта невозможность сохраняется даже в том случае, когда только ''один'' процесс выходит из строя, и делает это только путем ''отказа'', то есть прекращения своей деятельности. Терпимость к отказам – это самое малое, чего можно ожидать от распределенной системы, поскольку сама цель применения распределенного подхода, как правило, заключается в том, чтобы избежать единых точек сбоев в централизованных архитектурах. Обычно реальные распределенные приложения демонстрируют более серьезные сбои, когда процессы могут произвольно отклоняться от назначенного им протокола.

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

Чандра и Туэг [5] определяют абстракцию ''детектора сбоев'' как простой способ получения информации о сбоях, необходимой для обхода асинхронных невозможностей, в частности, невозможности консенсуса. Модель, рассмотренная в [5], представляет собой модель передачи сообщений, в которой могут возникать сбои процессов путем их ''аварийного завершения''. Такие процессы прекращают свою деятельность и не восстанавливаются. Процессы, не ведущие к аварийному завершению, считаются корректными. Предполагается, что в каждом выполнении системы хотя бы один процесс должен быть ''исправным''.

Грубо говоря, детектор сбоев представляет собой оракула, который предоставляет процессам информацию о сбоях. К оракулу обращаются на каждом шаге вычислений процесса, и он предоставляет процессу значение, содержащее некоторую информацию о сбое. Это значение выбирается из некоторого множества значений, называемого диапазоном детектора сбоев. Например, диапазон может представлять собой множество подмножеств процессов в системе, а каждое подмножество может изображать множество процессов, завершенных аварийно или считающихся исправными. Это соответствует ситуации, когда детектор сбоев реализован с использованием тайм-аута: каждый процесс q, который не общается в течение некоторого периода времени с некоторым процессом p, будет включен в подмножество процессов, для которых процесс p подозревает наличие отказа.

Более конкретно, детектор сбоев – это функция D, которая ассоциирует с каждой моделью сбоев F множество историй детектора сбоев fHi g = D(F). И модель отказа, и история детектора сбоев сами являются функциями.

• Модель сбоев F – это функция, связывающая с каждым временем t множество процессов F(t), переживших аварийное завершение к моменту t. Это понятие предполагает существование глобальных часов, не зависящих от процессов, а также конкретное понятие события аварийного завершения, связанное со временем. Множество шаблонов сбоев называется средой.

• История детектора сбоев H также является функцией, которая связывает с каждым процессом p и временем t некоторое значение v из диапазона значений детектора сбоев. (Диапазон детектора сбоев D обозначается RD). Считается, что это значение v было выдано детектором сбоев D для процесса p в момент времени t.

1. Идеальный детектор сбоев выдает подмножество процессов, т. е. диапазон детектора сбоев представляет собой множество подмножеств процессов в системе. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q обнаружен (как аварийно завершенный) процессом p. Идеальный детектор сбоев гарантирует два следующих свойства:

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

2. Эвентуально сильный детектор сбоев выдает подмножество процессов. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q подозревается (в наличии аварийного завершения) процессом p. Эвентуально сильный детектор сбоев гарантирует два следующих свойства:

• Каждый процесс, претерпевший аварийное завершение, в конечном итоге подпадает под подозрение;

Идеальный детектор сбоев надежен: если процесс q обнаружен, значит, он аварийно завершен. Эвентуально сильный детектор сбоев ненадежен: у нас никогда нет гарантии, что выданный результат точен. Использование термина «подозрение» передает эту идею. Различие между ненадежностью и надежностью было точно отражено в работе [14] для общего контекста, когда диапазон детектора сбоев может быть произвольным.

'''Теорема 1 (Чандра-Туэг [ ]). Существует алгоритм, который решает задачу нахождения консенсуса с помощью идеального детектора сбоев.'''

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

'''Теорема 2 (Чандра-Туэг [ ]). Существует алгоритм, который решает задачу консенсуса с помощью эвентуально сильного детектора сбоев в мажоритарной среде.'''

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

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

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

 

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

Если детектор сбоев D1 слабее D2 и наоборот, то считается, что D1 и D2 эквивалентны. В противном случае, если D1 слабее D2, а D2 не слабее D1, то говорят, что D1 строго слабее D2. Опять же, строго говоря, эти понятия зависят от рассматриваемой среды.

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

• Если существует алгоритм, который решает P с помощью некоторого детектора сбоев D0, то D слабее, чем D0.

'''Теорема 3 (Чандра-Хадзилакос-Туэг [ ]). Эвентуально сильный детектор сбоев является самым слабым для решения задачи консенсуса в мажоритарной среде.'''

 

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

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