commit 50e7c760e065e8e30682ee5d0e66557eee5c9c10
parent 019fa8135b0eea2637e932ea20a57fa42395e05a
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 16 Nov 2017 20:44:54 +0300
Edit failure handling.
Diffstat:
| arma-thesis-ru.org | | | 256 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
| arma-thesis.org | | | 256 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
2 files changed, 257 insertions(+), 255 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -3251,13 +3251,13 @@ IP-адреса: замена отображения IP-адресов на чт
Сбои узлов распределенной системы можно разделить на два типа: сбой подчиненного
узла и сбой главного узла. Для того чтобы запущенная на кластере задача могла
пережить сбой подчиненного узла, планировщик задач периодически создает для нее
-контрольные точки восстановления и записывают их в надежное хранилище. Для того
-чтобы создать контрольную точку, планировщик временно останавливает все
-параллельные процессы задачи, копирует все страницы памяти и все структуры ядра
-операционной системы, выделенные для этих процессов, на диск, и продолжает
-выполнение задачи. Для того чтобы пережить сбой главного узла, резидентный
-процесс планировщика задач непрерывно копирует свое внутреннее состояние на
-резервный узел, который становится руководящим после сбоя.
+контрольные точки восстановления и записывает их в надежное (резервируемое)
+хранилище. Для того чтобы создать контрольную точку, планировщик временно
+останавливает все параллельные процессы задачи, копирует все страницы памяти и
+все структуры ядра операционной системы, выделенные для этих процессов, на диск,
+и продолжает выполнение задачи. Для того чтобы пережить сбой главного узла,
+резидентный процесс планировщика задач непрерывно копирует свое внутреннее
+состояние на резервный узел, который становится главным после сбоя.
Оптимизации работы контрольных точек восстановления посвящено большое количество
работ\nbsp{}cite:egwutuoha2013survey, а альтернативным подходам уделяется меньше
@@ -3275,32 +3275,31 @@ IP-адреса: замена отображения IP-адресов на чт
не позволяет изменять количество параллельных процессов во время работы
программы, и большинство программ все равно предполагают, что это значение
является константой. Таким образом, не существует надежного способа обеспечения
-отказоустойчивости на уровне библиотеки передачи сообщений кроме как путем
+отказоустойчивости на уровне библиотеки передачи сообщений, кроме как путем
перезапуска всех параллельных процессов из контрольной точки восстановления.
В то же время, существует возможность продолжить выполнение задачи на меньшем
количестве узлов, чем было изначально выделено изначально, реализовав
-отказоустойчивость на уровне приложения. В этом случае роли главного и
+отказоустойчивость на уровне планировщика задач. В этом случае роли главного и
подчиненного динамически распределяются между резидентными процессами
-планировщика задач, работающими на каждом узле кластера, образуя древовидную
-иерархию узлов кластера, а параллельная программа состоит из управляющих
-объектов, использующих иерархию узлов для динамического распределения нагрузки и
-свою собственную иерархию для перезапуска управляющих объектов в случае сбоя
-узла.
+планировщика, работающими на каждом узле кластера, образуя древовидную иерархию
+узлов кластера, а параллельная программа состоит из управляющих объектов,
+использующих иерархию узлов для динамического распределения нагрузки и свою
+собственную иерархию для перезапуска управляющих объектов в случае сбоя узла.
**** Динамическое распределение ролей.
Отказоустойчивость параллельной программы\nbsp{}--- это одна из проблем, которая
-должна решаться планировщиком задач обработки больших данных или
+решается планировщиками задач обработки больших данных или
высокопроизводительных вычислений, однако, большинство планировщиков
обеспечивают только отказоустойчивость подчиненных узлов. Такого рода сбои
обычно обрабатываются путем перезапуска затронутой задачи (из контрольной точки
-восстановления) или ее части на оставшихся узлах, а выход из строя главного
-узла считается либо маловероятным, либо слишком сложным для обработки и
-настройки на целевой платформе. Системные администраторы обычно находят
-альтернативы отказоустойчивости на уровне приложения: они изолируют главный
-процесс планировщика от остальных узлов кластера, размещая его на специально
-выделенной машине, или, вместо этого, используют технологии виртуализации. Все
-эти альтернативы усложняют конфигурацию и обслуживание, и, уменьшая вероятность
+восстановления) или ее части на оставшихся узлах, а выход из строя главного узла
+считается либо маловероятным, либо слишком сложным для обработки и настройки на
+целевой платформе. Системные администраторы обычно находят альтернативы
+отказоустойчивости на уровне приложения: они изолируют главный процесс
+планировщика от остальных узлов кластера, размещая его на специально выделенной
+машине, или, вместо этого, используют технологии виртуализации. Все эти
+альтернативы усложняют конфигурацию и обслуживание, и, уменьшая вероятность
выхода из строя машины, приводящей к выходу из строя всей системы, увеличивают
вероятность ошибки оператора.
@@ -3324,7 +3323,7 @@ IP-адреса: замена отображения IP-адресов на чт
узлов.
**** Симметричная архитектура.
-Многие распределенные хранилища типа "ключ-значение" и параллельные файловые
+Многие распределенные хранилища типа ключ-значение и параллельные файловые
системы имеют симметричную архитектуру, в которой роли главного и подчиненного
распределяются динамически, так что любой узел может выступать в роли главного,
если текущий главный узел выходит из
@@ -3368,53 +3367,53 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
- сделать физические узлы взаимозаменяемыми,
- реализовать динамическое распределение ролей главного и подчиненного узла и
- реализовать автоматическое восстановление после сбоя любого из узлов.
-В последующих разделах будут описаны компоненты необходимые для написания
-параллельной программы и планировщика, которые устойчивы к сбоям узлов кластера.
+В последующих разделах описаны компоненты необходимые для написания параллельной
+программы и планировщика, которые устойчивы к сбоям узлов кластера.
**** Определения иерархий.
Для устранения неоднозначности иерархических связей между резидентными
процессами и управляющими объектами и для того чтобы упростить изложение, в
тексте используются следующие условные обозначения. Если связь установлена между
-двумя резидентными процессами, то отношения обозначаются
-/руководитель-подчиненный/. Если связь установлена между двумя управляющими
-объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
-/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
-один управляющий объект не может иметь связь с резидентным процессом, и
-наоборот. Поскольку иерархия резидентных процессов используется для
-распределения нагрузки на узлы кластера, иерархия управляющих объектов
-отображается на нее, и это отображение может быть произвольным: обычна ситуация,
-когда руководящий управляющий объект находится на подчиненном узле, а его
-подчиненные управляющие объекты распределены равномерно между всеми узлами
-кластера (включая узел, где находится руководящий объект). Обе иерархии может
-быть сколь угодно глубокими, но "неглубокие" являются предпочтительными для
-высоко параллельных программ, так как в них меньше количество промежуточных
-узлов, через которые должны пройти управляющие объекты при распределении между
-узлами кластера. Поскольку существует однозначное соответствие между
-резидентными процессами и узлами кластера, в данной работе они используются как
-взаимозаменяемые термины.
+двумя резидентными процессами, то отношения обозначаются /главный-подчиненный/.
+Если связь установлена между двумя управляющими объектами, то отношения
+обозначаются либо /руководитель-подчиненный/, либо /родитель-потомок/. Две
+иерархии ортогональны друг к другу в том смысле, что ни один управляющий объект
+не может иметь связь с резидентным процессом, и наоборот. Поскольку иерархия
+резидентных процессов используется для распределения нагрузки на узлы кластера,
+иерархия управляющих объектов отображается на нее, и это отображение может быть
+произвольным: обычна ситуация, когда руководящий управляющий объект находится на
+подчиненном узле, а его подчиненные управляющие объекты распределены равномерно
+между всеми узлами кластера (включая узел, где находится руководящий объект).
+Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
+предпочтительными для программ с высокой степенью параллелизма, так как в них
+меньше количество промежуточных узлов, через которые должны пройти управляющие
+объекты при распределении между узлами кластера. Поскольку существует
+однозначное соответствие между резидентными процессами и узлами кластера, в
+тексте они используются как взаимозаменяемые термины.
**** Обработка выхода узлов из строя.
-Основной стратегией при выходе из строя подчиненного узла является перезапуск
-выполнявшихся на нем объектов на рабочих узлах\nbsp{}--- стратегия, которой
-следует язык Erlang при перезапуске подчиненных
-процессов\nbsp{}cite:armstrong2003thesis. Для того что реализовать этот метод в
-рамках иерархии управляющих объектов, узел-отправитель сохраняет каждый объект,
-передаваемый на другие узлы кластера, и в случае отказа произвольного количества
-узлов, на которые были переданы объекты, их копии перераспределяются между
-оставшимися узлами без индивидуальной обработки программистом. Если больше не
-осталось узлов, на которые можно отправить объекты, то они выполняются локально.
-В отличие от "тяжеловесного" метода контрольных точек восстановления,
+Основным методом восстановления при выходе из строя подчиненного узла является
+перезапуск выполнявшихся на нем объектов на рабочих узлах (такой же метод
+использует язык Erlang при перезапуске подчиненных
+процессов\nbsp{}cite:armstrong2003thesis). Для того чтобы реализовать этот метод
+в рамках иерархии управляющих объектов, узел-отправитель сохраняет каждый
+объект, передаваемый на другие узлы кластера, и в случае отказа произвольного
+количества узлов, на которые были переданы объекты, их копии перераспределяются
+между оставшимися узлами без индивидуальной обработки программистом. Если больше
+не осталось узлов, на которые можно отправить объекты, то они выполняются
+локально. В отличие от "тяжеловесного" метода контрольных точек восстановления,
используемого планировщиками задач для высокопроизводительных кластеров,
древовидная иерархия узлов в паре с иерархией объектов позволяет автоматически
продолжить выполнение программы при выходе из строя произвольного количества
-подчиненных узлов без перезапуска каких-либо процессов параллельной программы.
+подчиненных узлов без перезапуска каких-либо процессов параллельной программы, а
+процесссы выполняют роль единиц выделения ресурсов.
Возможный подход к обработке выхода из строя главного узла (узла, на котором
запускается главный управляющий объект) заключается в копировании этого главного
объекта на резервный узел и синхронизации любых изменений между двумя копиями
объекта посредством распределенных транзакций, однако, этот подход не
соотносится с асинхронностью вычислительных ядер и слишком сложен в реализации.
-На практике, оказывается, что главный управляющий объект обычно не выполняет
+На практике оказывается, что главный управляющий объект обычно не выполняет
операции параллельно, а последовательно переходит от вычисления одного шага
программы к вычислению другого, и, значит, имеет не больше одного подчиненного в
каждый момент времени. (Каждый подчиненный объект представляет собой
@@ -3424,16 +3423,16 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
с его подчиненным объектом. Тогда при выходе из строя главного узла, копия
главного объекта принимает подчиненный объект (поскольку оба объекта находятся
на одном и том же узле), и время на восстановление не тратится. Если же выходит
-из строя подчиненный узел, на которым был отправлен подчиненный объект вместе с
-копией главного объекта, то подчиненный объект отправляется на оставшиеся узлы,
-и в худшем случае текущий шаг вычислений выполняется заново.
+из строя подчиненный узел, на который был отправлен подчиненный объект вместе с
+копией главного объекта, то подчиненный объект отправляется на один из
+оставшихся узлов, и в худшем случае текущий шаг вычислений выполняется заново.
Описанный выше подход предназначен для объектов, у которых нет объекта-родителя
и которые имеют только один подчиненный объект в каждый момент времени, и
повторяет механизм работы контрольных точек восстановления. Преимуществом
данного подхода является то, что он
-- сохраняет состояние только между последовательными шагами вычислений (когда
- оно занимает минимальный объем памяти),
+- сохраняет состояние программы только между последовательными шагами вычислений
+ (когда оно занимает минимальный объем памяти),
- сохраняет только актуальное данные и
- использует для сохранения состояния оперативную память другого узла кластера,
а не дисковое хранилище.
@@ -3443,32 +3442,34 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
Далее следует пример работы алгоритма восстановления после сбоев
(рис.\nbsp{}[[fig-fail-over-example]]).
-1. Исходное состояние. На начальном этапе вычислительный кластер не требует
+1. *Исходное состояние.* На начальном этапе вычислительный кластер не требует
никакой настройки за исключением настройки сети. Алгоритм предполагает полную
связность узлов кластера и лучше всего работает с древовидными топологиями
- сети, в которых все узлы кластера соединены несколькими коммутаторами.
-2. Построение иерархии узлов. При первичной загрузке на всех узлах кластера
- запускаются резидентные процессы, которые совместно строят иерархию таких же
- процессов поверх топологии сети кластера. Положение резидентного процесса в
- иерархии определяется позицией IP-адреса его узла в диапазоне IP-адресов
- сети. Для установления связи каждый из процессов соединяется только с
- предполагаемым главным процессом. В данном случае процесс на узле \(A\)
- становится главным процессом для всех остальных. Иерархия может измениться,
- только если новый узел присоединяется к кластеру или какой-либо из узлов
- выходит из строя.
-3. Запуск главного управляющего объекта. Первый управляющий объект запускается
+ сети, в которых все узлы кластера соединены несколькими сетевыми
+ коммутаторами.
+2. *Построение иерархии узлов.* При первичной загрузке на всех узлах кластера
+ запускаются резидентные процессы, которые совместно строят иерархию поверх
+ топологии сети кластера. Положение резидентного процесса в иерархии
+ определяется позицией IP-адреса его узла в диапазоне IP-адресов сети. Для
+ установления связи каждый из процессов соединяется только с предполагаемым
+ главным процессом. В данном случае процесс на узле \(A\) становится главным
+ процессом для всех остальных. Иерархия изменяется, только если новый узел
+ присоединяется к кластеру или какой-либо из существующих узлов выходит из
+ строя.
+3. *Запуск главного управляющего объекта.* Первый управляющий объект запускается
на одном из подчиненных узлов (узел \(B\)). Главный объект может иметь только
один подчиненный объект в любой момент времени, а резервная копия главного
объекта посылается вместе с этим подчиненным объектом \(T_1\) на главный узел
\(A\). \(T_1\) представляет собой последовательный шаг программы. В программе
может быть произвольное количество последовательных шагов, и, когда узел
\(A\) выходит из строя, текущий шаг перезапускается с начала.
-4. Запуск подчиненных управляющих объектов. Управляющие объекты \(S_1\), \(S_2\),
- \(S_3\) запускаются на подчиненных узлах кластера. Когда узел \(B\), \(C\)
- или \(D\), соответствующий руководящий управляющий объект перезапускает
- завершившиеся некорректно подчиненные объекты (\(T_1\) перезапускает \(S_1\),
- главный объект перезапускает \(T_1\) и т.д.). Когда выходит из строя узел
- \(B\), главный объект восстанавливается из резервной копии.
+4. *Запуск подчиненных управляющих объектов.* Управляющие объекты \(S_1\),
+ \(S_2\), \(S_3\) запускаются на подчиненных узлах кластера. Когда узел \(B\),
+ \(C\) или \(D\) выходит из строя, соответствующий руководящий управляющий
+ объект перезапускает завершившиеся некорректно подчиненные объекты (\(T_1\)
+ перезапускает \(S_1\), главный объект перезапускает \(T_1\) и т.д.). Когда
+ выходит из строя узел \(B\), главный объект восстанавливается из резервной
+ копии.
#+name: fig-fail-over-example
#+header: :headers '("\\input{preamble}\\setdefaultlanguage{russian}")
@@ -3513,9 +3514,9 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
фреймворк смог передать его на подчиненный узел вместе с подчиненным ему
объектом. Другие изменения исходного кода были связаны с изменением программного
интерфейса фреймворка. Таким образом, обеспечение отказоустойчивости посредством
-иерархии управляющих объектов, в основном, прозрачно для программиста и требует
-лишь маркировки главного объекта для его репликации на резервный узел и
-добавлении кода для чтения/записи объектов в байтовый буфер.
+иерархии управляющих объектов, в основном, прозрачно для программиста: требует
+маркировки главного объекта для его репликации на резервный узел и добавления
+кода для чтения/записи объектов в байтовый буфер.
В ряде экспериментов была измерена производительность новой версии программы при
выходе из строя различных типов узлов во время выполнения:
@@ -3558,8 +3559,8 @@ digraph {
#+RESULTS: fig-master-slave-backup
[[file:build/master-slave-backup-ru.pdf]]
-Как и ожидалось, есть большая разница в производительности приложения при выходе
-из строя различных типов узлов. В случае отказа подчиненного узла главный
+Как и ожидалось, существует большая разница в производительности приложения при
+выходе из строя различных типов узлов. В случае отказа подчиненного узла главный
управляющий объект вместе с некоторыми подчиненными (которые были распределены
на подчиненный узел) теряются, но главный узел имеет копию главного объекта и
использует ее, чтобы продолжить выполнение. Таким образом, при выходе из строя
@@ -3569,9 +3570,9 @@ digraph {
теряются, но подчиненный узел имеет оригинальный главный объект и использует его
для перезапуска вычислений с текущего шага, т.е.\nbsp{}отправляет подчиненный
объект на один из оставшихся узлов кластера (в случае двух напрямую соединенных
-узлов он отправляет объект себе же). Таким образом, разница в производительности
-приложения объясняется разным количеством и разными ролями объектов, которые
-теряются при выходе из строя того или иного узла.
+узлов он отправляет объект сам себе). Таким образом, разница в
+производительности приложения объясняется разным количеством и разными ролями
+объектов, которые теряются при выходе из строя того или иного узла.
Обнаружение выхода из строя подчиненного узла требует некоторого времени: это
происходит, только когда подчиненный объект, переносящий копию главного,
@@ -3659,26 +3660,26 @@ title(xlab="Размер взволнованной поверхности", yla
поскольку не требует перезапуска незавершившихся управляющих объектов и
копирования их состояния, и не изучался экспериментально в данной работе.
-Теоретически, отказоустойчивость, основанная на иерархии узлов и управляющих
-объектов, может быть реализована поверх библиотеки передачи сообщений без потери
-общности. Хотя использование незагруженных узлов заместо вышедших из строя в
-рамках такой библиотеки представляет определенную сложность, поскольку
-количество узлов, на которых запущена программа, в таких библиотеках
-фиксировано, однако, выделение достаточно большого количества узлов для
-программы будет достаточно для обеспечения ее отказоустойчивости. В то же время,
-реализация отказоустойчивости, основанной на иерархии, внутри самой библиотеки
-передачи сообщений не практично, поскольку это потребует сохранения текущего
-состояния параллельной программы, объем которого эквивалентен всей занимаемой ей
-памятью на каждом узле кластера, что, в свою очередь, не позволит сделать такой
-подход эффективнее контрольных точек восстановления.
-
-Слабым местом описанных методов является период времени, начиная с отказа
+Теоретически, основанная на иерархии отказоустойчивость может быть реализована
+поверх библиотеки передачи сообщений без потери общности. Хотя использование
+незагруженных узлов вместо вышедших из строя в рамках такой библиотеки
+представляет определенную сложность, поскольку количество узлов, на которых
+запущена программа, в таких библиотеках фиксировано, выделение достаточно
+большого количества узлов для программы будет достаточно для обеспечения ее
+отказоустойчивости. В то же время, реализация основанной на иерархии
+отказоустойчивости внутри самой библиотеки передачи сообщений не практично,
+поскольку это потребует сохранения текущего состояния параллельной программы,
+объем которого эквивалентен всей занимаемой ей памятью на каждом узле кластера,
+что, в свою очередь, не позволит сделать такой подход эффективнее контрольных
+точек восстановления.
+
+Слабым местом описанного метода является период времени, начиная с отказа
главного узла и заканчивая обнаружением сбоя подчиненным узлом, восстановлением
главного объекта из копии и получением нового подчиненного объекта вместе с
-копией его родителя подчиненным узлом. Если в любой момент времени из этого
-периода резервный узел выходит из строя, то состояние выполнения программы
-полностью теряется без возможности его восстановить, кроме как перезапуском с
-самого начала. Протяженность этого опасного промежутка времени может быть
+копией его родителя подчиненным узлом. Если на протяжении этого промежутка
+резервный узел выходит из строя, то состояние выполнения программы полностью
+теряется без возможности его восстановить, кроме как перезапуском с самого
+начала. Протяженность этого опасного промежутка времени может быть
минимизирована, но полностью исключить вероятность внезапного завершения
программы невозможно. Этот результат согласуется с исследованиями /теории
невыполнимости/ в рамках которой доказывается невозможность распределенного
@@ -3688,11 +3689,12 @@ title(xlab="Размер взволнованной поверхности", yla
*** Выводы
Современный подход к разработке и запуску параллельных программ на кластере
-заключается в использовании библиотеки передачи сообщений MPI и планировщика
-задач, и, несмотря на то что этот подход имеет высокую эффективность с точки
-зрения параллельных вычислений, он недостаточно гибок, чтобы вместить в себя
+заключается в использовании библиотеки передачи сообщений и планировщика задач,
+и, несмотря на то что этот подход имеет высокую эффективность с точки зрения
+параллельных вычислений, он недостаточно гибок, чтобы вместить в себя
динамическую балансировку нагрузки и автоматическое обеспечение
-отказоустойчивости. Программы, написанные с помощью MPI обычно предполагают
+отказоустойчивости. Программы, написанные с помощью библиотеки передачи
+сообщений обычно предполагают
- равномерную загрузку каждого процессора,
- бесперебойное и надежное выполнение пакетных задач, и
- постоянное число параллельных процессов/потоков во время выполнения, равное
@@ -3704,9 +3706,9 @@ title(xlab="Размер взволнованной поверхности", yla
поскольку в угоду эффективности каждая часть записывается в файл отдельным
потоком асинхронно. Оставшееся предположение относится не к самой программе, а к
планировщику задач, и несправедливо для больших вычислительных кластеров, в
-которых узлы часто выходят из строя, а планировщик перезапускает задачу из
-контрольной точки восстановления, серьезно замедляя ее. Таким образом, идея
-предлагаемого подхода\nbsp{}--- дать параллельным программам больше гибкости:
+которых узлы часто выходят из строя, а планировщик восстанавливает задачу из
+контрольной точки, сильно увеличивая время ее выполнения. Идея предлагаемого
+подхода\nbsp{}--- дать параллельным программам больше гибкости:
- предоставить динамическую балансировку нагрузки путем выполнения
последовательных, параллельных изнутри шагов программы в режиме конвейера,
- перезапускать только затронутые выходом из строя узла процессы, и
@@ -3718,23 +3720,23 @@ title(xlab="Размер взволнованной поверхности", yla
распределения нагрузки на узлы кластера предлагаемый подход использует
легковесные управляющие объекты вместо тяжеловесных параллельных задач.
Во-первых, это позволяет иметь очереди объектов на каждом узле, вместо того
-чтобы иметь одну очередь задач на кластер. Зернистость управляющих объектов
-гораздо выше, чем у пакетных задач, и, несмотря на то что время их выполнения не
-может быть надежно спрогнозировано (также как и время выполнения пакетных
-задач\nbsp{}cite:zotkin1999job), объекты из нескольких параллельных программ
-могут быть динамически распределены между одним и тем же множеством узлов
-кластера, делая нагрузку более равномерной. Недостатком является необходимость в
-большем количестве оперативной памяти для выполнения нескольких задач на одних и
-тех же узлах, а также в том что выполнение каждой программы может занять больше
-времени из-за общих очередей управляющих объектов. Во-вторых, предлагаемый
-подход использует динамическое распределение ролей главного и подчиненного между
-узлами кластера вместо их статического присвоения конкретным физическим узлам.
-Это позволяет сделать узлы взаимозаменяемыми, что необходимо для обеспечения
-отказоустойчивости. Таким образом, одновременное выполнение нескольких
-параллельных программ на одном и том же множестве узлов может увеличить
-пропускную способность кластера, но также может уменьшить их производительность,
-взятую по отдельности, а динамическое распределение ролей является основанием,
-на котором строится устойчивость к сбоям.
+чтобы иметь несколько очередей задач на весь кластер. Зернистость управляющих
+объектов гораздо выше, чем у пакетных задач, и, несмотря на то что время их
+выполнения не может быть надежно спрогнозировано (также как и время выполнения
+пакетных задач\nbsp{}cite:zotkin1999job), объекты из нескольких параллельных
+программ могут быть динамически распределены между одним и тем же множеством
+узлов кластера, делая нагрузку более равномерной. Недостатком является
+необходимость в большем количестве оперативной памяти для выполнения нескольких
+задач на одних и тех же узлах, а также в том что выполнение каждой программы
+может занять больше времени из-за общих очередей управляющих объектов.
+Во-вторых, предлагаемый подход использует динамическое распределение ролей
+главного и подчиненного между узлами кластера вместо их статического присвоения
+конкретным физическим узлам. Это делает узлы взаимозаменяемыми, что необходимо
+для обеспечения отказоустойчивости. Одновременное выполнение нескольких
+параллельных программ на одном и том же множестве узлов увеличивает пропускную
+способность кластера, но также уменьшает их производительность, взятую по
+отдельности; динамическое распределение ролей является основанием, на котором
+строится устойчивость к сбоям.
В сравнении с MPI для разбиения программы на отдельные сущности предлагаемый
подход использует легковесные управляющие объекты вместо тяжеловесных процессов.
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3128,8 +3128,8 @@ To summarise, traversal algorithm is
Node failures in a distributed system are divided into two types: failure of a
slave node and failure of a master node. In order for a job running on the
cluster to survive slave node failure, job scheduler periodically creates
-checkpoints and writes them to a stable storage. In order to create the
-checkpoint, the scheduler temporarily suspends all parallel processes of the
+checkpoints and writes them to a stable (redundant) storage. In order to create
+the checkpoint, the scheduler temporarily suspends all parallel processes of the
job, copies all memory pages and all internal operating system kernel structures
allocated for these processes to disk, and resumes execution of the job. In
order to survive master node failure, job scheduler daemon process continuously
@@ -3155,25 +3155,25 @@ checkpoint.
At the same time, there is a possibility to continue execution of a job on
lesser number of nodes than it was initially requested by implementing fault
-tolerance on application level. In this case master and slave roles are
-dynamically distributed between job scheduler daemons running on each cluster
-node, forming a tree hierarchy of cluster nodes, and parallel programme consists
-of kernels which use node hierarchy to dynamically distribute the load and use
-their own hierarchy to restart kernels upon node failure.
+tolerance on job scheduler level. In this case master and slave roles are
+dynamically distributed between scheduler's daemon processes running on each
+cluster node, forming a tree hierarchy of cluster nodes, and parallel programme
+consists of kernels which use node hierarchy to dynamically distribute the load
+and use their own hierarchy to restart kernels upon node failure.
**** Dynamic role distribution.
-Fault tolerance of a parallel programme is one of the problems which is being
-solved by big data and HPC job schedulers, however, most schedulers provide
-fault tolerance for slave nodes only. These types of failures are
-routinely handled by restarting the affected job (from a checkpoint) or its part
-on the remaining nodes, and failure of a principal node is often considered
-either improbable, or too complicated to handle and configure on the target
-platform. System administrators often find alternatives to application level
-fault tolerance: they isolate principal process of the scheduler from the rest
-of the cluster nodes by placing it on a dedicated machine, or use virtualisation
-technologies instead. All these alternatives complexify configuration and
-maintenance, and by decreasing probability of a machine failure resulting in a
-whole system failure, they increase probability of a human error.
+Fault tolerance of a parallel programme is one of the problems which is solved
+by big data and HPC job schedulers, however, most schedulers provide fault
+tolerance for slave nodes only. These types of failures are routinely handled by
+restarting the affected job (from a checkpoint) or its part on the remaining
+nodes, and failure of a principal node is often considered either improbable, or
+too complicated to handle and configure on the target platform. System
+administrators often find alternatives to application level fault tolerance:
+they isolate principal process of the scheduler from the rest of the cluster
+nodes by placing it on a dedicated machine, or use virtualisation technologies
+instead. All these alternatives complexify configuration and maintenance, and by
+decreasing probability of a machine failure resulting in a whole system failure,
+they increase probability of a human error.
From such point of view it seems more practical to implement master node fault
tolerance at application level, but there is no proven generic solution. Most
@@ -3225,12 +3225,11 @@ that needs to be restored upon node failure, so it is easier for them to provide
high availability. The protocol can be implemented even without routers using
Keepalived daemon\nbsp{}cite:cassen2002keepalived instead.
-Symmetric architecture is beneficial for job schedulers because it
-allows to
+Symmetric architecture is beneficial for job schedulers because it allows to
- make physical nodes interchangeable,
- implement dynamic distribution of master and slave node roles, and
- implement automatic recovery after a failure of any node.
-The following sections will describe the components that are required to write
+The following sections describe the components that are required to write
parallel programme and job scheduler, that can tolerate failure of cluster
nodes.
@@ -3241,30 +3240,30 @@ the text. If the link is between two daemon processes, the relationship is
denoted as /master-slave/. If the link is between two kernels, then the
relationship is denoted as either /principal-subordinate/ or /parent-child/. Two
hierarchies are orthogonal to each other in a sense that no kernel may have a
-link to a daemon, and vice versa. Since daemon hierarchy is used to distribute
-the load on cluster nodes, kernel hierarchy is mapped onto it, and this mapping
-can be arbitrary: It is common to have principal kernel on a slave node with its
-subordinate kernels distributed evenly between all cluster nodes (including the
-node where the principal is located). Both hierarchies can be arbitrarily deep,
-but "shallow" ones are preferred for highly parallel programmes, as there are
-less number of hops when kernels are distributed between cluster nodes. Since
-there is one-to-one correspondence between daemons and cluster nodes, they are
-used interchangeably in the work.
+link to a daemon, and vice versa. Since daemon process hierarchy is used to
+distribute the load on cluster nodes, kernel hierarchy is mapped onto it, and
+this mapping can be arbitrary: It is common to have principal kernel on a slave
+node with its subordinate kernels distributed evenly between all cluster nodes
+(including the node where the principal is located). Both hierarchies can be
+arbitrarily deep, but "shallow" ones are preferred for highly parallel
+programmes, as there are less number of hops when kernels are distributed
+between cluster nodes. Since there is one-to-one correspondence between daemons
+and cluster nodes, they are used interchangeably in the text.
**** Handling nodes failures.
-Basic strategy to overcome a failure of a subordinate node is to restart
-corresponding kernels on a healthy node\nbsp{}--- a strategy employed by Erlang
-language to restart failed subordinate processes\nbsp{}cite:armstrong2003thesis.
-In order to implement this method in the framework of kernel hierarchy, sender
-node saves every kernel that is sent to remote cluster nodes, and in an event of
-a failure of any number of nodes, where kernels were sent, their copies are
-redistributed between the remaining nodes without custom handling by a
-programmer. If there are no nodes to sent kernels to, they are executed locally.
-So, in contrast to "heavy-weight" checkpoint/restart machinery employed by HPC
-cluster job schedulers, tree hierarchy of nodes coupled with hierarchy of
-kernels allow to automatically and transparently handle of any number of
-subordinate node failures without restarting any processes of a parallel
-programme.
+Basic method to overcome a failure of a subordinate node is to restart
+corresponding kernels on a healthy node (Erlang language uses the same method to
+restart failed subordinate processes\nbsp{}cite:armstrong2003thesis). In order
+to implement this method in the framework of kernel hierarchy, sender node saves
+every kernel that is sent to remote cluster nodes, and in an event of a failure
+of any number of nodes, where kernels were sent, their copies are redistributed
+between the remaining nodes without custom handling by a programmer. If there
+are no nodes to sent kernels to, they are executed locally. In contrast to
+"heavy-weight" checkpoint/restart machinery employed by HPC cluster job
+schedulers, tree hierarchy of nodes coupled with hierarchy of kernels allows to
+automatically and transparently handle any number of subordinate node failures
+without restarting any processes of a parallel programme, and processes act as
+resource allocation units.
A possible way of handling failure of the main node (a node where the main
kernel is executed) is to replicate the main kernel to a backup node, and make
@@ -3272,52 +3271,52 @@ all updates to its state propagate to the backup node by means of a distributed
transaction, but this approach does not correlate with asynchronous nature of
kernels and too complex to implement. In practice, however, the main kernel
usually does not perform operations in parallel, it is rather sequentially
-execution steps one by one, so it has only one subordinate at a time. (Each
-subordinate kernel represent sequential computational step which may or may not
-be internally parallel.) Keeping this in mind, one can simplify synchronisation
-of the main kernel state: send the main kernel along with its subordinate to the
-subordinate node. Then if the main node fails, the copy of the main kernel
-receives its subordinate (because both of them are on the same node) and no time
-is spent on recovery. When the subordinate node, to which subordinate kernel
-together with the copy of the main kernel was sent, fails, the subordinate
-kernel is sent to some other node, and in the worst case the current
-computational step is executed again.
+executes programme steps one by one, hence it has only one subordinate at a
+time. (Each subordinate kernel represents sequential computational step which
+may or may not be internally parallel.) Keeping this in mind, one can simplify
+synchronisation of the main kernel state: send the main kernel along with its
+subordinate to the subordinate node. Then if the main node fails, the copy of
+the main kernel receives its subordinate (because both of them are on the same
+node) and no time is spent on recovery. When the subordinate node, to which
+subordinate kernel together with the copy of the main kernel was sent, fails,
+the subordinate kernel is sent to a survived node, and in the worst case the
+current computational step is executed again.
The approach described above is designed for kernels that do not have a parent
and have only one subordinate at a time, which means that it functions as
checkpoint mechanism. The advantage of this approach is that it
-- saves results after each sequential step, when memory footprint of a programme
- is low,
+- saves programme state after each sequential step, when memory footprint of a
+ programme is low,
- saves only relevant data, and
- uses memory of a subordinate node rather than disk storage.
This simple approach allows to tolerate at most one failure of /any/ cluster node
per computational step or arbitrary number of subordinate nodes at any time
during programme execution.
-The algorithm is best described by an example
+An example of failure recovery algorithm in action follows
(fig.\nbsp{}[[fig-fail-over-example]]).
-1. Initial state. Initially, computer cluster does not need to be configured
+1. *Initial state.* Initially, computer cluster does not need to be configured
except setting up local network. The algorithm assumes full connectivity of
cluster nodes, and works best with tree network topologies in which several
network switches connect all cluster nodes.
-2. Build node hierarchy. When the cluster is bootstrapped, daemon processes
- start on all cluster nodes and collectively build hierarchy of such processes
+2. *Build node hierarchy.* When the cluster is bootstrapped, daemon processes
+ start on all cluster nodes and collectively build their hierarchy
superimposed on the topology of cluster network. Position of a daemon process
in the hierarchy is defined by the position of its node IP address in the
network IP address range. To establish hierarchical link each process
- connects to its assumed master process. The hierarchy is changed only when
- a new node joins the cluster or a node fails.
-3. Launch main kernel. The first kernel launches on one of the subordinate nodes
- (node \(B\)). Main kernel may have only one subordinate at a time, and backup
- copy of the main kernel is sent along with the subordinate kernel \(T_1\) to
- the master node \(A\). \(T_1\) represents one sequential step of a
+ connects to its assumed master process. The hierarchy is changed only when a
+ new node joins the cluster or an existing node fails.
+3. *Launch main kernel.* The first kernel launches on one of the subordinate
+ nodes (node \(B\)). Main kernel may have only one subordinate at a time, and
+ backup copy of the main kernel is sent along with the subordinate kernel
+ \(T_1\) to master node \(A\). \(T_1\) represents one sequential step of a
programme. There can be any number of sequential steps in a programme, and
when node \(A\) fails, the current step is restarted from the beginning.
-4. Launch subordinate kernels. Kernels \(S_1\), \(S_2\), \(S_3\) are launched on
- subordinate cluster nodes. When node \(B\), \(C\) or \(D\) fails,
+4. *Launch subordinate kernels.* Kernels \(S_1\), \(S_2\), \(S_3\) are launched
+ on subordinate cluster nodes. When node \(B\), \(C\) or \(D\) fails,
corresponding main kernel restarts failed subordinates (\(T_1\) restarts
\(S_1\), master kernel restarts \(T_1\) etc.). When node \(B\) fails, master
- kernel is recovered from backup.
+ kernel is recovered from backup copy.
#+name: fig-fail-over-example
#+header: :headers '("\\input{preamble}")
@@ -3349,7 +3348,7 @@ the example of distributed AR model application, which is described in detail in
section\nbsp{}[[#sec-arma-mpp]]. The application consists of a series of functions, each
of which is applied to the result of the previous one. Some of the functions are
computed in parallel, so the programme is written as a sequence of steps, some
-if which are made internally parallel to get better performance. In the
+of which are made internally parallel to get better performance. In the
programme only the most compute-intensive step (the surface generation) is
executed in parallel across all cluster nodes, and other steps are executed in
parallel across all cores of the master node.
@@ -3360,9 +3359,9 @@ and slight modifications to handle failure of a node with the main kernel. The
kernel was marked so that the framework makes a replica and sends it to some
subordinate node along with its subordinate kernel. Other code changes involved
modifying some parts to match the new API. So, providing fault tolerance by
-means of kernel hierarchy is mostly transparent to the programmer which only
-demands explicit marking of the main kernel and adding code to read and write
-kernels to the byte buffer.
+means of kernel hierarchy is mostly transparent to the programmer: it demands
+explicit marking of the main kernel and adding code to read and write kernels to
+the byte buffer.
In a series of experiments performance of the new version of the application in
the presence of different types of failures was benchmarked:
@@ -3413,9 +3412,9 @@ potential of the slave node. In case of master node failure, a copy of the main
kernel as well as the subordinate kernel, which carried the copy, are lost, but
slave node has the original main kernel and uses it to restart execution of the
current sequential step, i.e.\nbsp{}send the subordinate kernel to one of the
-survived cluster nodes (in case of two directly connected, it sends the kernel
-to itself). So, application performance is different, because the number of
-kernels that are lost as a result of a failure as well as their roles are
+survived cluster nodes (in case of two directly connected nodes, it sends the
+kernel to itself). So, application performance is different, because the number
+of kernels that are lost as a result of a failure as well as their roles are
different.
Slave node failure needs some time to be discovered: it is detected only when
@@ -3487,9 +3486,9 @@ multiple sequential steps to make it resilient to cluster node failures,
otherwise failure of backup node, in fact triggers recovery of the initial state
of the programme. Although, the probability of a master node failure is lower
than the probability of a failure of any of the slave nodes, it does not justify
-loosing all the data when the long programme run is near completion. In general,
-the more sequential steps one has in a parallel programme the less time is lost
-in an event of a backup node failure, and the more parallel parts each
+loosing all the data when the long-running programme is near completion. In
+general, the more sequential steps one has in a parallel programme the less time
+is lost in an event of a backup node failure, and the more parallel parts each
sequential step has the less time is lost in case of a master or slave node
failure. In other words, the more nodes a programme uses the more resilient to
their failures it becomes.
@@ -3497,27 +3496,27 @@ their failures it becomes.
Although it is not shown in the experiments, Bscheduler does not only provide
tolerance to cluster node failures, but allows for new nodes to automatically
join the cluster and receive their portion of kernels from the already running
-programmes. This is trivial process as it does not involve restarting failed
-kernels or copying their state, so it has not been studied experimentally in
-this work.
-
-Theoretically, fault tolerance based on a hierarchy of nodes and kernels can be
-implemented on top of the message-passing library without loss of generality.
-Although it would be complicated to reuse free nodes instead of failed ones in
-the framework of this library, as the number of nodes is often fixed in such
-libraries, allocating reasonably large number of nodes for the programme would
-be enough to make it fault-tolerant. At the same time, implementing
-hierarchy-based fault tolerance inside message-passing library itself is not
-practical, because it would require saving the state of a parallel programme
-which equals to the total amount of memory it occupies on each cluster node,
-which in turn would not make it more efficient than checkpoints.
-
-The weak point of the proposed algorithm is the period of time starting from a
+programmes. This is trivial process in the context of the framework as it does
+not involve restarting failed kernels or copying their state, so it has not been
+studied experimentally in this work.
+
+Theoretically, hierarchy-based fault tolerance based can be implemented on top
+of the message-passing library without loss of generality. Although it would be
+complicated to reuse free nodes instead of failed ones in the framework of this
+library, as the number of nodes is often fixed in such libraries, allocating
+reasonably large number of nodes for the programme would be enough to make it
+fault-tolerant. At the same time, implementing hierarchy-based fault tolerance
+inside message-passing library itself is not practical, because it would require
+saving the state of a parallel programme which equals to the total amount of
+memory it occupies on each cluster node, which in turn would not make it more
+efficient than checkpoints.
+
+The weak point of the proposed method is the period of time starting from a
failure of master node up to the moment when the failure is detected, the main
kernel is restored and new subordinate kernel with the parent's copy is received
-by a slave node. If at any time during this period backup node fails, execution
-state of a programme is completely lost, and there is no way to recover it other
-than restarting the programme from the beginning. The duration of the dangerous
+by a slave node. If backup node fails within this time frame, execution state of
+a programme is completely lost, and there is no way to recover it other than
+restarting the programme from the beginning. The duration of the dangerous
period can be minimised, but the probability of an abrupt programme termination
can not be fully eliminated. This result is consistent with the scrutiny of
/impossibility theory/, in the framework of which it is proved the impossibility
@@ -3528,24 +3527,25 @@ failures\nbsp{}cite:fekete1993impossibility.
*** Summary
Current state-of-the-art approach to developing and running parallel programmes
-on the cluster is the use of MPI message passing library and job scheduler, and
+on the cluster is the use of message passing library and job scheduler, and
despite the fact that this approach is highly efficient in terms of parallel
-computing, it is not flexible enough to accommodate dynamic load balancing and
-automatic fault-tolerance. Programmes written with MPI typically assume
+computation, it is not flexible enough to accommodate dynamic load balancing and
+automatic fault-tolerance. Programmes written with message passing library
+typically assume
- equal load on each processor,
- non-interruptible and reliable execution of batch jobs, and
- constant number of parallel processes/threads throughout the execution which
is equal to the total number of processors.
-The first assumption does not hold for sea wave simulation programme because
-AR model requires dynamic load balancing between processors to generate each
-part of the surface only when all dependent parts has already been generated.
-The last assumption also does not hold, because for the sake of efficiency each
-part is written to a file asynchronously by a separate thread. The remaining
+The first assumption does not hold for sea wave simulation programme because AR
+model requires dynamic load balancing between processors to generate each part
+of the surface only when all dependent parts have already been generated. The
+last assumption also does not hold, because for the sake of efficiency each part
+is written to a file asynchronously by a separate thread. The remaining
assumption is not related to the programme itself, but to the job scheduler, and
does not generally hold for very large computer clusters in which node failures
-occur regularly, and job scheduler slowly restores the failed job from the
-checkpoint severely hindering its performance. So, the idea of the proposed
-approach is to give parallel programmes more flexibility:
+occur regularly, and job scheduler restores the failed job from the checkpoint
+greatly increasing its running time. The idea of the proposed approach is to
+give parallel programmes more flexibility:
- provide dynamic load balancing via pipelined execution of sequential,
internally parallel programme steps,
- restart only processes that were affected by node failure, and
@@ -3553,6 +3553,25 @@ approach is to give parallel programmes more flexibility:
cluster.
In this section advantages and disadvantages of this approach are discussed.
+In comparison to portable batch systems (PBS) the proposed approach uses
+lightweight control flow objects instead of heavy-weight parallel jobs to
+distribute the load on cluster nodes. First, this allows to have per-node kernel
+queues instead of several cluster-wide job queues. The granularity of control
+flow objects is much higher than of the batch jobs, and despite the fact that
+their execution time cannot be reliably predicted (as is execution time of batch
+jobs\nbsp{}cite:zotkin1999job), objects from multiple parallel programmes can be
+dynamically distributed between the same set of cluster nodes, thus making the
+load more even. The disadvantage is that this requires more RAM to execute many
+programmes on the same set of nodes, and execution time of each programme may be
+greater because of the shared control flow object queues. Second, the proposed
+approach uses dynamic distribution of master and slave roles between cluster
+nodes instead of their static assignment to the particular physical nodes. This
+makes nodes interchangeable, which is required to provide fault tolerance.
+Simultaneous execution of multiple parallel programmes on the same set of nodes
+increases throughput of the cluster, but also decreases their performance taken
+separately; dynamic role distribution is the base on which resilience to
+failures builds.
+
In comparison to MPI the proposed approach uses lightweight control flow objects
instead of heavy-weight processes to decompose the programme into individual
entities. First, this allows to determine the number of entities computed in
@@ -3590,25 +3609,6 @@ makes it impossible to decide which object is responsible for restarting a
failed one, hence non-universal fault tolerance techniques are used
instead\nbsp{}cite:lifflander2014scalable.
-In comparison to portable batch systems (PBS) the proposed approach uses
-lightweight control flow objects instead of heavy-weight parallel jobs to
-distribute the load on cluster nodes. First, this allows to have node object
-queues instead of several cluster-wide job queues. The granularity of control
-flow objects is much higher than the batch jobs, and despite the fact that their
-execution time cannot be reliably predicted (as is execution time of batch
-jobs\nbsp{}cite:zotkin1999job), objects from multiple parallel programmes can be
-dynamically distributed between the same set of cluster nodes, thus making the
-load more even. The disadvantage is that this requires more RAM to execute many
-programmes on the same set of nodes, and execution time of each programme may be
-greater because of the shared control flow object queues. Second, the proposed
-approach uses dynamic distribution of master and slave roles between cluster
-nodes instead of their static assignment to the particular physical nodes. This
-makes nodes interchangeable, which is required to provide fault tolerance. So,
-simultaneous execution of multiple parallel programmes on the same set of nodes
-may increase throughput of the cluster, but may also decrease their performance
-taken separately, and dynamic role distribution is the base on which resilience
-to failures builds.
-
Three building blocks of the proposed approach\nbsp{}--- control flow objects,
pipelines and hierarchies\nbsp{}--- complement each other. Without control flow
objects carrying programme state it is impossible to recompute failed
