Детектор отказов - Failure detector

В распределенных вычислений система, а детектор отказов это компьютерное приложение или подсистема который отвечает за обнаружение узел неудачи или аварии.[1] Детекторы отказов были впервые представлены в 1996 году Чандрой и Туегом в их книге. Ненадежные детекторы отказов для надежных распределенных систем. В книге детектор отказов изображен как инструмент для улучшения консенсус (достижение надежности) и атомная трансляция (та же последовательность сообщений) в распределенной системе. Другими словами, детекторы отказов ищут ошибки в процесс, а система будет поддерживать уровень надежность. На практике, после обнаружения сбоев детекторами сбоев, система блокирует процессы, допускающие ошибки, чтобы предотвратить дальнейшие серьезные сбои или ошибки.[2][3]

в 21-го века, детекторы отказов широко используются в распределенных вычислительных системах для обнаружения ошибки приложения, например программное приложение перестает нормально работать. Поскольку проекты распределенных вычислений (см. Список проектов распределенных вычислений ) становятся все более популярными, использование детекторов отказов также становится важным и критическим.[4][5]

Источник

Детектор ненадежного отказа

Чандра и Туег, соавторы книги Ненадежные детекторы отказов для надежной распределенной системыs (1996) подошли к концепции обнаружения узлов отказа, представив ненадежный детектор отказов.[6] Они описывают поведение ненадежного детектора отказов в распределенной вычислительной системе как: после каждого процесс в систему введен локальный компонент детектора отказа, каждый локальный компонент проверит часть всех процессов в системе.[5] Кроме того, каждый процесс также должен содержать программы которые в настоящее время подозреваются детекторами отказов.[5]

Детектор отказов

Этот рисунок описывает поведение типичного детектора отказа (FD).

Чандра и Туег утверждали, что ненадежный детектор отказов по-прежнему может быть надежным в обнаружении ошибок, допущенных системой.[6] Они распространяют ненадежные детекторы отказов на все виды детекторов отказов, поскольку ненадежные детекторы отказов и детекторы отказов имеют одинаковые свойства. Кроме того, Чандра и Туег указывают на важный факт, что детектор сбоев не предотвращает сбоев в системе, даже если ранее предполагалось, что сбой программы. Создание детектора отказов - важная, но очень сложная проблема, которая возникла при разработке отказоустойчивой компонент в распределенной компьютерной системе. В результате был изобретен детектор отказов из-за необходимости обнаружения ошибок в массивной информационной транзакции в распределенных вычислительных системах.[1][3][5]

Характеристики

Классы детекторов отказов различают по двум важным свойствам: полнота и точность. Полнота означает, что детекторы сбоев найдут программы, которые окончательно завершились сбоем в процессе, тогда как точность означает правильные решения, которые детекторы сбоев приняли в процессе.[5]

Степени полноты

Степень полноты зависит от того, сколько аварийных процессов заподозрит детектор сбоев за определенный период.[5]

  • Сильная полнота: "каждый неисправный процесс в конечном итоге постоянно подозревается всеми исправными процессами ".[6]
  • Слабая полнота: "каждый неисправный процесс в конечном итоге постоянно подозревается каким-либо исправным процессом ".[6]

Степени точности

Степень точности зависит от количества ошибок, которые детектор отказов допустил за определенный период.[5]

  • Высокая точность: «ни один процесс не подозревается (кем-либо) до того, как он выйдет из строя».[6]
  • Слабая точность: «о каком-то исправном процессе никогда не подозревать».[6]
  • Возможная высокая точность: «не подозревается ни один исправный процесс по прошествии некоторого времени с момента окончания начального периода хаоса, когда происходит последний сбой».[6]
  • Возможная слабая точность: «после некоторого начального периода неразберихи никогда не возникает подозрений о каком-либо исправном процессе».[6]

Классификация

Детекторы отказов можно разделить на следующие восемь типов:[1][7]

  1. Детектор идеального отказа (П)
  2. В конечном итоге совершенные детекторы отказов (♦ P)
  3. Детекторы сильных отказов (S)
  4. В конечном итоге сильные детекторы отказов (♦ S)
  5. Детекторы слабых отказов (W)
  6. В конечном итоге слабые детекторы отказов (♦ W)
  7. Квазиидеальные детекторы отказов (Q)
  8. Со временем квазиидеальные детекторы отказов (♦ Q)

Свойства этих детекторов отказов описаны ниже:[1]

Точность

Полный-
несса
Сильный
Вечный
Точность		Слабый
Вечный
Точность		Сильный
Возможный
Точность		Слабый
Возможный
Точность
Сильная полнотапS♦ P♦ S
Слабая полнотаQW♦ Q♦ W

Короче говоря, свойства детекторов отказов зависят от того, как быстро детектор отказов обнаруживает фактические неудачи и насколько хорошо он предотвращает ложное обнаружение. Идеальный детектор отказов обнаружит все ошибки без ошибок, тогда как слабый детектор отказов не обнаружит никаких ошибок и сделает множество ошибок.[3][8]

Приложения

Различные типы детекторов отказов могут быть получены путем изменения свойств детекторов отказов.[3][6] Первые примеры показывают, как повысить полноту детектора отказов, а второй пример показывает, как заменить один тип детектора отказа на другой.

Повышение полноты

Ниже приводится пример, взятый из Департамента компьютерных наук Йельского университета. Он работает за счет повышения полноты детектора отказов.[6]

первоначально подозревает = ∅ делать навсегда: для каждого процесса p: если мой слабый детектор подозревает p, то послать p всем процессам после получения p от некоторого процесса q: подозреваемые: = подозреваемые + p - q

Из приведенного выше примера, если p выйдет из строя, то в конечном итоге обнаружитель слабого заряда заподозрит это. Все детекторы отказов в системе в конечном итоге заподозрят p из-за бесконечного цикла, создаваемого детекторами отказов. Этот пример также показывает, что слабый детектор отказов полноты также может в конечном итоге заподозрить все сбои.[6] Проверка сбойных программ не зависит от полноты.[5]

Уменьшение детектора отказа W к детектору отказов S

Ниже приведены аргументы корректности для выполнения алгоритма замены детектора отказов. W к детектору отказов S.[1] Детектор отказов W слабая по полноте, а детектор отказов S силен в полноте. У них обоих слабая точность.[6]

  1. Он превращает слабую завершенность в сильную.[1]
  2. Он сохраняет вечную точность.[1]
  3. Это сохраняет возможную точность.[1]

Если все приведенные выше аргументы удовлетворены, уменьшение слабого детектора отказов W к сильному детектору отказов S согласен с алгоритм в распределенной вычислительной системе.[1]

Смотрите также

Рекомендации

  1. ^ а б c d е ж грамм час я Д., Кшемкаляни, Аджай (2008). Распределенные вычисления: принципы, алгоритмы и системы. Сингхал, Мукеш. Кембридж: Издательство Кембриджского университета. ISBN  9780521189842. OCLC  175284075.
  2. ^ Агилера, Маркос Кавазо; Чен, Вэй; Туег, Сэм (2000-04-01). «Обнаружение сбоев и консенсус в модели восстановления после сбоя». Распределенных вычислений. 13 (2): 99–125. Дои:10.1007 / s004460050070. HDL:1813/7330. ISSN  0178-2770.
  3. ^ а б c d Фишер, Майкл Дж .; Lynch, Nancy A .; Патерсон, Майкл С. (апрель 1985 г.). «Невозможность распределенного консенсуса с одним ошибочным процессом». J. ACM. 32 (2): 374–382. CiteSeerX  10.1.1.13.6760. Дои:10.1145/3149.214121. ISSN  0004-5411.
  4. ^ Холохан, Энн; Гарг, Анураг (01.07.2005). «Совместная работа в Интернете: пример распределенных вычислений». Журнал компьютерных коммуникаций. 10 (4): 00. Дои:10.1111 / j.1083-6101.2005.tb00279.x. ISSN  1083-6101.
  5. ^ а б c d е ж грамм час Чандра, Тушар Дипак; Туег, Сэм (1996). Детекторы ненадежных отказов для надежных распределенных систем. Журнал ACM. Том 43, выпуск 2. Нью-Йорк, Нью-Йорк, США: ACM. С. 225–267. Дои:10.1145/226643.226647. HDL:1813/7192. ISBN  978-0897914390.
  6. ^ а б c d е ж грамм час я j k л «Детекторы отказа». www.cs.yale.edu. Получено 2017-10-23.
  7. ^ Агилера, Маркос Кавазо; Туег, Сэм (1996-10-09). Рандомизация и обнаружение сбоев: гибридный подход к достижению консенсуса. Распределенные алгоритмы. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 29–39. CiteSeerX  10.1.1.88.1597. Дои:10.1007/3-540-61769-8_3. ISBN  978-3540617693.
  8. ^ Чен, Вэй; Toueg, S .; Агилера, М. К. (январь 2002 г.). «О качестве обслуживания детекторов неисправностей». Транзакции IEEE на компьютерах. 51 (1): 13–32. CiteSeerX  10.1.1.461.5630. Дои:10.1109/12.980014. ISSN  0018-9340.

внешняя ссылка