Детекторы сбоев
Ключевые слова и синонимы
Частичная синхронность; тайм-ауты; информация о сбоях; распределенные оракулы
Постановка задачи
Распределенная система состоит из набора процессов. Процессы обычно стремятся решить некоторую общую задачу, взаимодействуя посредством передачи сообщений или разделяемой памяти. Большинство интересных задач требуют, по крайней мере, на определенных этапах вычислений, некоторой формы согласования между процессами. Абстрактной формой такого согласования является консенсус, когда процессам необходимо договориться об одном значении из множества предложенных. Решение этой, казалось бы, элементарной задачи лежит в основе надежных распределенных вычислений и, в частности, распределенных баз данных, полного упорядочения сообщений и эмуляции многих типов общих объектов.
Фундаментальный результат Фишера, Линч и Патерсона в теории распределенных вычислений [13] гласит, что консенсус не может быть получен детерминированным образом в асинхронной распределенной системе, подверженной сбоям процессов. Эта невозможность сохраняется для всех задач распределенных вычислений, которые сами полагаются на консенсус.
Сбои и асинхронность являются основополагающими компонентами невозможности достижения консенсуса. Эта невозможность сохраняется даже в том случае, когда только один процесс выходит из строя, и делает это только путем аварийного завершения, то есть прекращения своей деятельности. Устойчивость к аварийным завершениям – это самое малое, чего можно ожидать от распределенной системы, поскольку сама цель применения распределенного подхода, как правило, заключается в том, чтобы избежать единых точек сбоев в централизованных архитектурах. Обычно реальные распределенные приложения демонстрируют более серьезные сбои, когда процессы могут произвольно отклоняться от назначенного им протокола.
Асинхронность означает отсутствие предположений о скорости процессов и задержках связи. Такое отсутствие предположений не позволяет любому процессу отличить аварийно завершенный процесс от корректного, и именно эта неспособность приводит к невозможности консенсуса. Однако на практике распределенные системы не являются полностью асинхронными: обычно можно сделать некоторые допущения относительно времени. В лучшем случае, если принять точные нижние и верхние границы на задержки связи и скорости процессов, то легко показать, что консенсус и связанные с ним невозможности можно обойти даже в условиях аварийного завершения любого количества процессов [20].
Интуитивно понятно, что способ, которым такие допущения относительно времени обходят асинхронные невозможности, заключается в предоставлении процессам информации о сбоях, обычно через механизмы тайм-аута (или пульса), часто лежащие в основе реальных распределенных приложений. Хотя определенную информацию о сбоях можно получить и в распределенных системах, точность такой информации может варьироваться от системы к системе в зависимости от базовой сети, нагрузки приложения и механизмов обнаружения сбоев. Важнейшей проблемой в этом контексте является определение характеристик такой информации максимально абстрактным и точным способом.
Основные результаты
Абстракция детектора сбоев
Чандра и Туэг [5] определяют абстракцию детектора сбоев как простой способ получения информации о сбоях, необходимой для обхода асинхронных невозможностей, в частности, невозможности консенсуса. Модель, рассмотренная в [5], представляет собой модель передачи сообщений, в которой могут возникать сбои процессов путем их аварийного завершения. Такие процессы прекращают свою деятельность и не восстанавливаются. Процессы, не ведущие к аварийному завершению, считаются исправными. Предполагается, что в каждом выполнении системы хотя бы один процесс должен быть исправным.
Грубо говоря, детектор сбоев представляет собой оракула, который предоставляет процессам информацию о сбоях. К оракулу обращаются на каждом шаге вычислений процесса, и он предоставляет процессу значение, содержащее некоторую информацию о сбое. Это значение выбирается из некоторого множества значений, называемого диапазоном детектора сбоев. Например, диапазон может представлять собой множество подмножеств процессов в системе, а каждое подмножество может изображать множество процессов, завершенных аварийно или считающихся исправными. Это соответствует ситуации, когда детектор сбоев реализован с использованием тайм-аута: каждый процесс q, который не общается в течение некоторого периода времени с некоторым процессом p, будет включен в подмножество процессов, для которых процесс p подозревает наличие отказа.
Более конкретно, детектор сбоев – это функция D, которая ассоциирует с каждой моделью сбоев F множество историй детектора сбоев [math]\displaystyle{ \{ H_i \} = D(F) }[/math]. И модель отказа, и история детектора сбоев сами являются функциями.
• Модель сбоев F – это функция, связывающая с каждым временем t множество процессов F(t), переживших аварийное завершение к моменту t. Это понятие предполагает существование глобальных часов, не зависящих от процессов, а также конкретное понятие события аварийного завершения', связанное со временем. Множество моделей сбоев называется средой.
• История детектора сбоев H также является функцией, которая связывает с каждым процессом p и временем t некоторое значение v из диапазона значений детектора сбоев. (Диапазон детектора сбоев D обозначается [math]\displaystyle{ R_D }[/math]). Считается, что это значение v было выдано детектором сбоев D для процесса p в момент времени t.
Здесь следует сделать два замечания.
• По построению выдача детектора сбоев не зависит от вычислений, то есть от фактических шагов, выполняемых процессами, от их алгоритма и от входных данных такого алгоритма. Выдача детектора сбоев зависит исключительно от модели сбоев, а именно от того, произошло ли аварийное завершение у процессов и когда именно.
• Детектор сбоев может связывать несколько историй с каждой моделью сбоев. Каждая история представляет собой набор возможных комбинаций выданных результатов для одной и той же модели сбоев. Он отражает присущий механизму обнаружения сбоев недетерминизм. Такой механизм обычно реализуется в виде распределенного алгоритма, и вариации задержек связи, например, могут привести к тому, что один и тот же механизм будет выдавать разную (пусть даже незначительно отличающуюся) информацию для одной и той же модели сбоев.
Чтобы проиллюстрировать эти концепции, рассмотрим два классических примера детекторов сбоев.
1. Идеальный детектор сбоев выдает подмножество процессов, т. е. диапазон детектора сбоев представляет собой множество подмножеств процессов в системе. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q обнаружен (как аварийно завершенный) процессом p. Идеальный детектор сбоев гарантирует два следующих свойства:
• каждый процесс, претерпевший аварийное завершение, в конечном итоге обязательно обнаруживается;
• ни один исправный процесс не обнаруживается как аварийно завершенный.
2. Эвентуально сильный детектор сбоев выдает подмножество процессов. Когда процесс q выводится в некоторое время t процессом p, то говорят, что q подозревается (в наличии аварийного завершения) процессом p. Эвентуально сильный детектор сбоев гарантирует два следующих свойства:
• каждый процесс, претерпевший аварийное завершение, в конечном итоге подпадает под подозрение;
• некоторый корректный процесс в конечном итоге никогда не попадает под подозрение.
Идеальный детектор сбоев надежен: если процесс q обнаружен, значит, он аварийно завершен. Эвентуально сильный детектор сбоев ненадежен: у нас никогда нет гарантии, что выданный результат точен. Использование термина «подозрение» передает эту идею. Различие между ненадежностью и надежностью было точно отражено в работе [14] для общего контекста, когда диапазон детектора сбоев может быть произвольным.
Алгоритмы достижения консенсуса
В работе [5] были получены два важных результата.
Теорема 1 (Чандра-Туэг [5]). Существует алгоритм, который решает задачу нахождения консенсуса с помощью идеального детектора сбоев.
Данная теорема неявно говорит о том, что если распределенная система предоставляет средства для реализации идеального обнаружения сбоев, то невозможность консенсуса можно обойти, даже если все процессы, кроме одного, завершаются аварийно. Фактически этот результат справедлив для любой модели сбоя, то есть в любой среде.
Вторая теорема, приведенная ниже, связывает существование алгоритма консенсуса с предположением об устойчивости. Говоря более конкретно, данная теорема справедлива в мажоритарной среде, которая представляет собой множество моделей сбоев, где более половины процессов исправны.
Теорема 2 (Чандра-Туэг [5]). Существует алгоритм, который решает задачу консенсуса с помощью эвентуально сильного детектора сбоев в мажоритарной среде.
Алгоритм, лежащий в основе приведенного выше результата, похож на алгоритмы эвентуально синхронного консенсуса [10], а также имеет некоторое сходство с алгоритмом Паксос [1] [18].
В работе [5] было показано, что ни один алгоритм, использующий только эвентуально сильный детектор сбоев, не может решить задачу консенсуса без предположения о большинстве. (В [14] этот результат обобщен на любой ненадежный детектор сбоев). Эта нижняя граница устойчивости интуитивно объясняется возможностью наличия разбиений в системе передачи сообщений, где по крайней мере половина процессов может завершиться аварийно, а детектор сбоев ненадежен. Скажем, в разделяемой памяти такой возможности нет, и задача консенсуса может быть решена с помощью эвентуально сильного детектора сбоев [19].
Редукции детекторов сбоев
Детекторы сбоев можно сравнивать друг с другом. Считается, что детектор сбоев [math]\displaystyle{ D_2 }[/math] слабее детектора сбоев [math]\displaystyle{ D_1 }[/math], если существует асинхронный алгоритм, называемый алгоритмом редукции, который может эмулировать [math]\displaystyle{ D_2 }[/math], используя [math]\displaystyle{ D_1 }[/math]. Здесь важно сделать три замечания.
• То, что алгоритм редукции является асинхронным, означает, что он не использует никакого другого источника информации о сбоях, кроме [math]\displaystyle{ D_1 }[/math].
• Эмуляция детектора сбоев [math]\displaystyle{ D_2 }[/math] означает реализацию распределенной переменной, которая имитирует выходной результат, который мог бы предоставить [math]\displaystyle{ D_2 }[/math].
• Существование алгоритма редукции зависит от среды. Поэтому, строго говоря, тот факт, что один детектор сбоев слабее другого, зависит от рассматриваемой среды.
Если детектор сбоев [math]\displaystyle{ D_1 }[/math] слабее [math]\displaystyle{ D_2 }[/math] и наоборот, то считается, что [math]\displaystyle{ D_1 }[/math] и [math]\displaystyle{ D_2 }[/math] эквивалентны. В противном случае, если [math]\displaystyle{ D_1 }[/math] слабее [math]\displaystyle{ D_2 }[/math], а [math]\displaystyle{ D_2 }[/math] не слабее [math]\displaystyle{ D_1 }[/math], то говорят, что [math]\displaystyle{ D_1 }[/math] строго слабее [math]\displaystyle{ D_2 }[/math]. Опять же, строго говоря, эти понятия зависят от рассматриваемой среды.
Возможность сравнивать детекторы сбоев помогает определить понятие самого слабого детектора сбоев для решения этой задачи. Детектор сбоев D является самым слабым для решения задачи P, если выполняются два следующих условия:
• Существует алгоритм, который решает задачу P с помощью детектора D.
• Если существует алгоритм, который решает P с помощью некоторого детектора сбоев D', то D слабее, чем D'.
Теорема 3 (Чандра-Хадзилакос-Туэг [4]). Эвентуально сильный детектор сбоев является самым слабым для решения задачи консенсуса в мажоритарной среде.
Самый слабый детектор сбоев для реализации задачи консенсуса в любой среде был позже представлен в [8].
Применение
Практические аспекты
Определение концепции детектора сбоев оказало положительное влияние на проектирование надежных распределенных архитектур.
По сути, детектор сбоев можно рассматривать как службу распределенной системы высшей категории, того же уровня, что служба имен или файловая служба. Механизмы тайм-аута и пульса могут быть скрыты под абстракцией детектора сбоев, которая затем может экспортировать унифицированный интерфейс в приложения более высокого уровня, включая алгоритмы консенсуса и репликации конечного автомата [2, 11, 21].
Что еще более важно, служба детектора сбоев может инкапсулировать предположения о синхронности, позволяя изменять их без влияния на остальные приложения. Можно изучить минимальные предположения о синхронности для разработки конкретных детекторов сбоев, что приведет к любопытным теоретическим результатам [1, 7, 12].
Теоретические аспекты
Второе применение концепции детекторов сбоев – это теория распределенной вычислимости. Детекторы сбоев позволяют классифицировать задачи. Задача A сложнее (или строго сложнее) задачи B, если самый слабый детектор сбоев для решения B слабее (или строго слабее) самого слабого детектора сбоев для решения A. (Это понятие, конечно, параметризуется конкретгной средой).
Может показаться удивительным, что индуцированная редукция детекции сбоев между разными задачами не вполне соответствует классическому понятию редукции к «черному ящику». Например, хорошо известно, что не существует асинхронного распределенного алгоритма, который мог бы использовать абстракцию очереди (Queue) для реализации абстракции сравнения с обменом (Compare-Swap) в системе из n > 2 процессов, где n – 1 процессов могут претерпеть сбой в виде аварийного завершения [15]. В этом смысле абстракция сравнения с обменом строго более мощная (в смысле «черного ящика»), чем абстракция очереди. Имеет место следующий результат:
Теорема 4 (Дельпорт-Фоконье-Геррауи [9]). Самый слабый детектор сбоев для решения задачи очереди также является самым слабым для решения задачи сравнения с обменом в системе из n > 2 процессов, где n – 1 процессов могут претерпеть сбой в виде аварийного завершения.
В некотором смысле эта теорема подчеркивает, что сводимость, определяемая понятием детектора сбоев, отличается от традиционной редукции к черному ящику.
Открытые вопросы
Некоторые проблемы, лежащие в основе концепции детектора сбоев, все еще остаются нерешенными. Одна из таких проблем заключается в определении самого слабого детектора сбоев для решения фундаментальной задачи согласования множеств [6]: это задача на принятие решений, в которой процессы должны согласовать до k значений, а не одно значение, как в случае задачи консенсуса. Три независимые группы исследователей [3, 16, 22] доказали невозможность решения этой задачи в асинхронной системе с k сбоями, обобщив невозможность консенсуса [ ]. Определение самого слабого детектора сбоев, позволяющего обойти эту невозможность, несомненно, поможет понять основы сводимости детекции сбоев.
Еще одно любопытное направление исследований – связь сложности распределенного алгоритма с лежащим в его основе детектором сбоев [ ]. Очевидно, что детекторы сбоев позволяют обойти асинхронные невозможности, но насколько они повышают сложность распределенных алгоритмов? Конечно, можно ожидать, что сложность решения задачи будет выше, если детектор сбоев слабее – но насколько именно?
См. также
Литература
1. Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: On implementing Omega with weak reliability and synchrony assumptions. In: 22th ACM Symposium on Principles of Distributed Computing, pp. 306-314 (2003)
2. Bertier, M., Marin, O., Sens, P.: Performance analysis of a hierarchical failure detector. In: International Conference on Dependable Systems and Networks (DSN 2003), San Francisco, CA, USA, Proceedings, pp. 635-644. 22-25 June 2003
3. Boroswsky, E., Gafni E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 91-100, ACM Press
4. Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685-722 (1996)
5. Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225-267 (1996)
6. Chauduri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput. 105(1),132-158(1993)
7. Chen, W., Toueg, S., Aguilera, M.K.: On the quality of service of failure detectors. IEEE Trans. Comput. 51 (1), 13-32 (2002)
8. Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: Failure detection lower bounds on registers and consensus. In: Proceedings of the 16th International Symposium on Distributed Computing, LNCS 2508 (2002)
9. Delporte-Gallet, C., Fauconnier, H., Guerraoui, R.: Implementing atomic objects in a message passing system. Technical report, EPFL Lausanne (2005)
10. Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288-323 (1988)
11. Felber, P., Guerraoui, R., Fayad, M.: Putting oo distributed programming to work. Commun. ACM 42(11), 97-101 (1999)
12. Fernandez, A., Jimenez, E., Raynal, M.: Eventual leader election with weak assumptions on initial knowledge, communication reliability and synchrony. In: Proc International Symposium on Dependable Systems and Networks (DSN), pp. 166-178 (2006)
13. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374-382(1985)
14. Guerraoui, R.: Indulgent algorithms. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, Portland, Oregon, USA, pp. 289-297, ACM, July 2000
15. Herlihy, M.: Wait-free synchronization. ACM Trans. Programm. Lang. Syst. 13(1), 123-149 (1991)
16. Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 111-120, May 1993
17. Keidar, I., Rajsbaum, S.:On the cost of fault-tolerant consensus when there are no faults-a tutorial. In: Tutorial 21th ACM Symposium on Principles of Distributed Computing, July 2002
18. Lamport, L.: The Part-Time parliament. ACM Trans. Comput. Syst. 16(2), 133-169(1998)
19. Lo, W.-K., Hadzilacos, V.: Using failure detectors to solve consensus in asynchronous shared memory systems. In: Proceedings of the 8th International Workshop on Distributed Algorithms, LNCS 857, pp. 280-295, September 1994
20. Lynch, N.: Distributed Algorithms. Morgan Kauffman (1996)
21. Michel, R., Corentin,T.: In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement. Technical Report TR 06-1811, INRIA, August 2006
22. Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 101-110, ACM Press, May 1993
