commit d76a9a3235b84a6e0183459dfba2b01c86be993e
parent 55edf2a1d24c655fd27983d0c3cf25ef1e4f46e6
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Wed, 8 Nov 2017 13:46:10 +0300
Edit node failure handling.
Diffstat:
3 files changed, 152 insertions(+), 170 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -3265,35 +3265,35 @@ IP-адреса: замена отображения IP-адресов на чт
**** Симметричная архитектура.
Многие распределенные хранилища типа "ключ-значение" и параллельные файловые
-системы имеют симметричную архитектуру, в которой роли руководителя и
-подчиненного распределяются динамически, так что любой узел может выступать в
-роли руководителя, если текущий руководящий узел выходит из
+системы имеют симметричную архитектуру, в которой роли главного и подчиненного
+распределяются динамически, так что любой узел может выступать в роли главного,
+если текущий главный узел выходит из
строя\nbsp{}cite:ostrovsky2015couchbase,divya2013elasticsearch,boyer2012glusterfs,anderson2010couchdb,lakshman2010cassandra.
Однако, такая архитектура до сих пор не используется в планировщиках задач
обработки больших данных и высокопроизводительных вычислений. Например, в
-планировщике задач обработки больших данных YARN\nbsp{}cite:vavilapalli2013yarn,
-роли руководителя и подчиненного являются статическими. Восстановление после
-сбоя подчиненного узла осуществляется путем перезапуска работавшей на нем части
-задачи на одном из выживших узлов, а восстановление после сбоя руководящего узла
-осуществляется путем установки резервного руководящего
-узла\nbsp{}cite:murthy2011architecture. Оба руководящих узла управляются
-сервисом Zookeeper, который использует динамическое распределение ролей для
-обеспечения своей отказоустойчивости\nbsp{}cite:okorafor2012zookeeper. Таким
-образом, отсутствие динамического распределения ролей у планировщика YARN
-усложняет конфигурацию всего кластера: если бы динамические роли были доступны,
-Zookeeper был бы лишним в данной конфигурации.
+планировщике YARN\nbsp{}cite:vavilapalli2013yarn, роли главного и подчиненного
+являются статическими. Восстановление после сбоя подчиненного узла
+осуществляется путем перезапуска работавшей на нем части задачи на одном из
+выживших узлов, а восстановление после сбоя главного узла осуществляется путем
+установки резервного главного узла\nbsp{}cite:murthy2011architecture. Оба
+главных узла управляются сервисом Zookeeper, который использует динамическое
+распределение ролей для обеспечения своей
+отказоустойчивости\nbsp{}cite:okorafor2012zookeeper. Таким образом, отсутствие
+динамического распределения ролей у планировщика YARN усложняет конфигурацию
+всего кластера: если бы динамические роли были доступны, Zookeeper был бы лишним
+в данной конфигурации.
Такая же проблема возникает в планировщиках задач для высокопроизводительных
-вычислений, руководящий узел (на котором запущен главный процесс планировщика
-задач) является единой точкой сбоя.
+вычислений, главный узел (на котором запущен главный процесс планировщика задач)
+является единой точкой сбоя.
В\nbsp{}cite:uhlemann2006joshua,engelmann2006symmetric авторы копируют состояние
планировщика задач на резервный узел, чтобы обеспечить высокую доступность
-руководящего узла, но роль резервного узла задается статически. Такое решение
-близко к симметричной архитектуре, поскольку не использует внешний сервис для
+главного узла, но роль резервного узла задается статически. Такое решение близко
+к симметричной архитектуре, поскольку не использует внешний сервис для
обеспечения высокой доступности, но далеко от идеала, в котором резервный узел
выбирается динамически.
-Наконец, наиболее простой вариант высокой доступности руководящего узла
+Наконец, наиболее простой вариант высокой доступности главного узла
реализован в протоколе VRRP (Virtual Router Redundancy
Protocol)\nbsp{}cite:rfc2338,rfc3768,rfc5798. Несмотря на то что протокол VRRP
предоставляет динамическое распределение ролей, он не может быть использован в
@@ -3306,16 +3306,16 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
Симметричная архитектура выгодна для планировщиков задач, поскольку позволяет
- сделать физические узлы взаимозаменяемыми,
-- реализовать динамическое распределение ролей руководителя и подчиненного и
+- реализовать динамическое распределение ролей главного и подчиненного узла и
- реализовать автоматическое восстановление после сбоя любого из узлов.
В последующих разделах будут описаны компоненты необходимые для написания
параллельной программы и планировщика, которые устойчивы к сбоям узлов кластера.
**** Определения иерархий.
Для устранения неоднозначности иерархических связей между резидентными
-процессами и управляющими объектами и для того чтобы упростить изложение, мы
-будем использовать в тексте следующие условные обозначения. Если связь
-установлена между двумя резидентными процессами, то отношения обозначаются
+процессами и управляющими объектами и для того чтобы упростить изложение, в
+тексте используются следующие условные обозначения. Если связь установлена между
+двумя резидентными процессами, то отношения обозначаются
/руководитель-подчиненный/. Если связь установлена между двумя управляющими
объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
@@ -3323,7 +3323,7 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
иерархия сервисом используется для распределения нагрузки на узлы кластера,
иерархия управляющих объектов отображается на нее, и это отображение может быть
произвольным: обычна ситуация, когда руководящий управляющий объект находится на
-подчиненном узле, а его подчиненные управляющие объекта распределены равномерно
+подчиненном узле, а его подчиненные управляющие объекты распределены равномерно
между всеми узлами кластера (включая узел, где находится руководящий объект).
Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
предпочтительными для высоко параллельных программ, так как в них меньше
@@ -3352,7 +3352,7 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
запускается главный управляющий объект) заключается в копировании этого главного
объекта на резервный узел и синхронизации любых изменений между двумя копиями
объекта посредством распределенных транзакций, однако, этот подход не
-соотносится с асинхронностью вычислительных ядер и слишком сложна в реализации.
+соотносится с асинхронностью вычислительных ядер и слишком сложен в реализации.
На практике, оказывается, что главный управляющий объект обычно не выполняет
операции параллельно, а последовательно переходит от вычисления одного шага
программы к вычислению другого, и, значит, имеет не больше одного подчиненного в
@@ -3371,8 +3371,8 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
и которые имеют только один подчиненный объект в каждый момент времени, и
повторяет механизм работы контрольных точек восстановления. Преимуществом
данного подхода является то, что он
-- сохраняет состояние только между последовательными шагами вычислений (когда оно
-занимает минимальный объем памяти),
+- сохраняет состояние только между последовательными шагами вычислений (когда
+ оно занимает минимальный объем памяти),
- сохраняет только актуальное данные и
- использует для сохранения состояния оперативную память другого узла кластера,
а не дисковое хранилище.
@@ -3384,21 +3384,21 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
(рис.\nbsp{}[[fig-fail-over-example]]).
1. Исходное состояние. На начальном этапе вычислительный кластер не требует
никакой настройки за исключением настройки сети. Алгоритм предполагает полную
- связность узлов кластера и лучше всего работает с древовидными топологиями, в
- которых все узлы кластера соединены несколькими коммутаторами.
+ связность узлов кластера и лучше всего работает с древовидными топологиями
+ сети, в которых все узлы кластера соединены несколькими коммутаторами.
2. Построение иерархии узлов. При первичной загрузке на всех узлах кластера
запускаются резидентные процессы, которые совместно строят иерархию таких же
- процессов поверх топологии сети кластера. Положение процесса-сервиса в
+ процессов поверх топологии сети кластера. Положение резидентного процесса в
иерархии определяется позицией IP-адреса его узла в диапазоне IP-адресов
сети. Для установления связи каждый из процессов соединяется только с
- предполагаемым руководящим процессом. В данном случае процесс на узле \(A\)
- становится руководящим процессом для всех остальных. Иерархия может
- измениться, только если новый узел присоединяется к кластеру или какой-либо из
- узлов выходит из строя.
+ предполагаемым главным процессом. В данном случае процесс на узле \(A\)
+ становится главным процессом для всех остальных. Иерархия может измениться,
+ только если новый узел присоединяется к кластеру или какой-либо из узлов
+ выходит из строя.
3. Запуск главного управляющего объекта. Первый управляющий объект запускается
на одном из подчиненных узлов (узел \(B\)). Главный объект может иметь только
- один подчиненный объект в каждый момент времени, и резервная копия главного
- объекта посылается вместе с этим подчиненным объектом \(T_1\) на руководящий узел
+ один подчиненный объект в любой момент времени, а резервная копия главного
+ объекта посылается вместе с этим подчиненным объектом \(T_1\) на главный узел
\(A\). \(T_1\) представляет собой последовательный шаг программы. В программе
может быть произвольное количество последовательных шагов, и, когда узел
\(A\) выходит из строя, текущий шаг перезапускается с начала.
@@ -3445,7 +3445,7 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
всех процессорных ядрах главного узла.
Программа была переписана для распределенной версии фреймворка, что потребовало
-добавления методов чтения/записи для каждого управляющего объекта, которые
+добавления методов чтения/записи для каждого управляющего объекта, который
передается по сети и небольших изменений исходного кода для корректной обработки
выхода из строя узла с главным объектом. Главный объект был помечен, чтобы
фреймворк смог передать его на подчиненный узел вместе с подчиненным ему
@@ -3493,8 +3493,8 @@ digraph {
#+RESULTS: fig-master-slave-backup
[[file:build/master-slave-backup-ru.pdf]]
-Как и ожидалось, существует большая разница в производительности приложения при
-выходе из строя различных типов узлов. В случае отказа подчиненного узла главный
+Как и ожидалось, есть большая разница в производительности приложения при выходе
+из строя различных типов узлов. В случае отказа подчиненного узла главный
управляющий объект вместе с некоторыми подчиненными (которые были распределены
на подчиненный узел) теряются, но главный узел имеет копию главного объекта и
использует ее, чтобы продолжить выполнение. Таким образом, при выходе из строя
@@ -3536,9 +3536,8 @@ title(xlab="Размер взволнованной поверхности", yla
[[file:build/master-slave-failure-ru.pdf]]
Итого, если выход из строя узла происходит сразу после того как копия главного
-объекта сделана, лишь малая часть производительности теряется в случае выхода из
-строя главного узла; при выходе из строя подчиненного узла теряется больше
-производительности.
+объекта сделана, лишь малая часть производительности теряется в независимости от
+того, теряется главный объект или его копия.
**** Обсуждение результатов тестирования.
Поскольку выход из строя имитируется, сразу после того как первый подчиненный
@@ -3558,19 +3557,20 @@ title(xlab="Размер взволнованной поверхности", yla
Алгоритм восстановления после сбоев гарантирует обработку выхода из строя одного
узла на один последовательный шаг программы; больше сбоев может быть выдержано,
-если он не затрагивают руководящий узел. Алгоритм обрабатывает одновременный
-выход из строя всех подчиненных узлов, однако, если руководящий и резервный узлы
-вместе выходят из строя, у программы нет ни единого шанса продолжить работу. В
-этом случае состояние текущего шага вычислений теряется полностью, и его можно
-восстановить только перезапуском программы с начала.
-
-Управляющие объекты являются абстракциями, отделяющие распределенное приложение
+если они не затрагивают главный узел. Алгоритм обрабатывает одновременный выход
+из строя всех подчиненных узлов, однако, если главный и резервный узлы вместе
+выходят из строя, у программы нет ни единого шанса продолжить работу. В этом
+случае состояние текущего шага вычислений теряется полностью, и его можно
+восстановить только перезапуском программы с начала (что на данный момент не
+реализовано в Bscheduler).
+
+Управляющие объекты являются абстракциями, отделяющими распределенное приложение
от физических устройств: для непрерывной работы программы не важно, сколько
узлов кластера в данный момент работают. Управляющие объекты позволяют
отказаться от выделения физического резервного узла для обеспечения устойчивости
-к выходу из строя руководящего узла: в рамках иерархии управляющих объектов
-любой физический узел (кроме руководящего) может выполнять роль резервного.
-Наконец, иерархия управляющих объектов позволяет обрабатывать сбои прозрачно для
+к выходу из строя главного узла: в рамках иерархии управляющих объектов любой
+физический узел (кроме главного) может выполнять роль резервного. Наконец,
+иерархия управляющих объектов позволяет обрабатывать сбои прозрачно для
программиста, определяя порядок действий из внутреннего состояния объекта.
Проведенные эксперименты показывают, что параллельной программе необходимо иметь
@@ -3582,12 +3582,11 @@ title(xlab="Размер взволнованной поверхности", yla
почти завершилась. В общем случае, чем больше последовательных этапов вычислений
содержит параллельная программа, тем меньше времени потеряется в случае сбоя
резервного узла, и, аналогично, чем больше параллельных частей содержит каждый
-последовательный этап, тем меньше времени потеряется при сбое руководящего или
+последовательный этап, тем меньше времени потеряется при сбое главного или
подчиненного узла. Другими словами, чем больше количество узлов, на которое
-масштабируется программа, тем она становится более устойчива к сбою узлов
-кластера.
+масштабируется программа, тем она становится более устойчива к их сбоям.
-Хотя это не было показано в экспериментах, Фабрика не только обеспечивает
+Хотя это не было показано в экспериментах, Bscheduler не только обеспечивает
устойчивость к выходу из строя узлов кластера, но и позволяет автоматически
вводить новые узлы в кластер и распределять на них часть управляющих объектов из
уже запущенных программ. В контексте фреймворка этот процесс тривиален,
@@ -3608,16 +3607,16 @@ title(xlab="Размер взволнованной поверхности", yla
подход эффективнее контрольных точек восстановления.
Слабым местом описанных методов является период времени, начиная с отказа
-руководящего узла и заканчивая обнаружением сбоя подчиненным узлом,
-восстановлением главного объекта из копии и получением нового подчиненного
-объекта вместе с копией его родителя подчиненным узлом. Если в любой момент
-времени из этого периода резервный узел выходит из строя, то состояние
-выполнения программы полностью теряется без возможности его восстановить, кроме
-как перезапуском с самого начала. Протяженность этого опасного промежутка
-времени может быть минимизирована, но полностью исключить вероятность внезапного
-завершения программы невозможно. Этот результат согласуется с исследованиями
-/теории невыполнимости/ в рамках которой доказывается невозможность
-распределенного консенсуса с хотя бы одним процессом, дающим
+главного узла и заканчивая обнаружением сбоя подчиненным узлом, восстановлением
+главного объекта из копии и получением нового подчиненного объекта вместе с
+копией его родителя подчиненным узлом. Если в любой момент времени из этого
+периода резервный узел выходит из строя, то состояние выполнения программы
+полностью теряется без возможности его восстановить, кроме как перезапуском с
+самого начала. Протяженность этого опасного промежутка времени может быть
+минимизирована, но полностью исключить вероятность внезапного завершения
+программы невозможно. Этот результат согласуется с исследованиями /теории
+невыполнимости/ в рамках которой доказывается невозможность распределенного
+консенсуса с хотя бы одним процессом, дающим
сбой\nbsp{}cite:fischer1985impossibility и невозможность надежной передачи
данных в случае сбоя одного из узлов\nbsp{}cite:fekete1993impossibility.
@@ -3649,27 +3648,27 @@ title(xlab="Размер взволнованной поверхности", yla
кластере.
В данном разделе обсуждаются преимущества и недостатки этого подхода.
-В сравнении с переносимыми системами пакетных заданий (PBS) для распределения
-нагрузки на узлы кластера предлагаемый подход использует легковесные управляющие
-объекты вместо тяжеловесных параллельных задач. Во-первых, это позволяет иметь
-очереди объектов на каждом узле, вместо того чтобы иметь одну очередь задач на
-кластер. Зернистость управляющих объектов гораздо выше, чем у пакетных задач, и,
-несмотря на то что время их выполнения не может быть надежно спрогнозировано
-(также как и время выполнения пакетных задач), объекты из нескольких
-параллельных программ могут быть динамически распределены между одним и тем же
-множеством узлов кластера, делая нагрузку более равномерной. Недостатком
-является необходимость в большем количестве оперативной памяти для выполнения
-нескольких задач на одних и тех же узлах, а также в том что выполнение каждой
-программы может занять больше времени из-за общих очередей управляющих объектов.
-Во-вторых, предлагаемый подход использует динамическое распределение ролей
-руководителя и подчиненного среди узлов кластера вместо их статического
-присвоения конкретным физическим узлам. Это позволяет сделать узлы
-взаимозаменяемыми, что необходимо для обеспечения отказоустойчивости. Таким
-образом, одновременное выполнение нескольких параллельных программ на одном и
-том же множестве узлов может увеличить пропускную способность кластера, но также
-может уменьшить их производительность, взятую по отдельности, а динамическое
-распределение ролей является основанием, на котором строится устойчивость к
-сбоям.
+В сравнении с переносимыми системами пакетной обработки заданий (PBS) для
+распределения нагрузки на узлы кластера предлагаемый подход использует
+легковесные управляющие объекты вместо тяжеловесных параллельных задач.
+Во-первых, это позволяет иметь очереди объектов на каждом узле, вместо того
+чтобы иметь одну очередь задач на кластер. Зернистость управляющих объектов
+гораздо выше, чем у пакетных задач, и, несмотря на то что время их выполнения не
+может быть надежно спрогнозировано (также как и время выполнения пакетных
+задач), объекты из нескольких параллельных программ могут быть динамически
+распределены между одним и тем же множеством узлов кластера, делая нагрузку
+более равномерной. Недостатком является необходимость в большем количестве
+оперативной памяти для выполнения нескольких задач на одних и тех же узлах, а
+также в том что выполнение каждой программы может занять больше времени из-за
+общих очередей управляющих объектов. Во-вторых, предлагаемый подход использует
+динамическое распределение ролей главного и подчиненного между узлами
+кластера вместо их статического присвоения конкретным физическим узлам. Это
+позволяет сделать узлы взаимозаменяемыми, что необходимо для обеспечения
+отказоустойчивости. Таким образом, одновременное выполнение нескольких
+параллельных программ на одном и том же множестве узлов может увеличить
+пропускную способность кластера, но также может уменьшить их производительность,
+взятую по отдельности, а динамическое распределение ролей является основанием,
+на котором строится устойчивость к сбоям.
В сравнении с MPI для разбиения программы на отдельные сущности предлагаемый
подход использует легковесные управляющие объекты вместо тяжеловесных процессов.
@@ -3698,27 +3697,18 @@ title(xlab="Размер взволнованной поверхности", yla
повлиять на ее масштабируемость на большое количество узлов из-за дублирования
состояния хода выполнения.
-Может показаться, что три составляющих предлагаемого подхода\nbsp{}---
-управляющие объекты, конвейеры и иерархии\nbsp{}--- ортогональны, но, на самом
-деле, они дополняют друг друга. Если бы управляющие объекты не содержали в себе
-состояние хода выполнения программы, то было бы невозможно пересчитать
-завершившиеся некорректно подчиненные объекты и обеспечить отказоустойчивость.
-Если бы иерархии узлов не было, то было бы невозможно распределить нагрузку
-между узлами кластера, поскольку все узлы одинаковы без иерархии. Если бы для
-каждого устройства не было конвейера, то было бы невозможно обрабатывать
-управляющие объекты асинхронно и реализовать динамическую балансировку нагрузки.
-Эти три сущности образуют замкнутую систему, в которую нечего добавить и из
-которой нечего удалить\nbsp{}--- надежную основу для любой распределенной
-программы.
-
-Подводя итог, можно сказать, что управляющие объекты придают гибкости
-параллельным программам: они балансируют снижение производительности за счет
-использования общих очередей ее увеличением за счет динамической балансировки
-нагрузки. Требуя больше оперативной памяти для работы, они позволяют выполнять
-сразу несколько параллельных программ одновременно на всех узлах кластера без
-простаивания в очереди задач, и превращают кластер в единую вычислительную
-систему, которая делает все возможное для непрерывной работы распределенных
-приложений.
+Три составляющих предлагаемого подхода\nbsp{}--- управляющие объекты, конвейеры
+и иерархии\nbsp{}--- дополняют друг друга. Если бы управляющие объекты не
+содержали в себе состояние хода выполнения программы, то было бы невозможно
+пересчитать завершившиеся некорректно подчиненные объекты и обеспечить
+отказоустойчивость. Если бы иерархии узлов не было, то было бы невозможно
+распределить нагрузку между узлами кластера, поскольку все узлы одинаковы без
+иерархии. Если бы для каждого устройства не было конвейера, то было бы
+невозможно обрабатывать управляющие объекты асинхронно и реализовать
+динамическую балансировку нагрузки. Эти три сущности образуют замкнутую систему,
+в которой логика программы реализуется либо в управляющих объектах, либо в
+конвейерах, логика восстановления после сбоев в иерархия объектов, а логика
+передачи данных в иерархии узлов кластера.
** Реализация для систем с распределенной памятью (MPP)
:PROPERTIES:
@@ -3916,6 +3906,7 @@ Emacs, предоставляющего вычислительное окруж
- <<<HPC>>> :: High-performance computing.
- <<<РГШ>>> :: Распределение на основе ряда Грама---Шарлье.
- <<<АНР>>> :: Асимметричное нормальное распределение.
+- <<<PBS>>> :: Portable batch system.
- Трансцендентные функции :: математические функции, не являющиеся
алгебраическими (т.е.\nbsp{}логарифмические, тригонометрические и др.).
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3152,32 +3152,30 @@ nodes.
**** Symmetric architecture.
Many distributed key-value stores and parallel file systems have symmetric
-architecture, in which principal and subordinate roles are dynamically
-distributed, so that any node can act as a principal when the current principal
-node
+architecture, in which master and slave roles are dynamically distributed, so
+that any node can act as a master when the current master node
fails\nbsp{}cite:ostrovsky2015couchbase,divya2013elasticsearch,boyer2012glusterfs,anderson2010couchdb,lakshman2010cassandra.
However, this architecture is still not used in big data and HPC job schedulers.
-For example, in YARN big data job scheduler\nbsp{}cite:vavilapalli2013yarn
-principal and subordinate roles are static. Failure of a subordinate node is
-tolerated by restarting a part of a job, that worked on it, on one of the
-surviving nodes, and failure of a principal node is tolerated by setting up
-standby principal node\nbsp{}cite:murthy2011architecture. Both principal nodes
-are coordinated by Zookeeper service which uses dynamic role assignment to
-ensure its own fault-tolerance\nbsp{}cite:okorafor2012zookeeper. So, the lack of
-dynamic role distribution in YARN scheduler complicates the whole cluster
-configuration: if dynamic roles were available, Zookeeper would be redundant in
-this configuration.
-
-The same problem occurs in HPC job schedulers where principal node (where the
-main job scheduler process is run) is the single point of failure.
+For example, in YARN scheduler\nbsp{}cite:vavilapalli2013yarn master and slave
+roles are static. Failure of a slave node is tolerated by restarting a part of a
+job, that worked on it, on one of the surviving nodes, and failure of a master
+node is tolerated by setting up standby master
+node\nbsp{}cite:murthy2011architecture. Both master nodes are coordinated by
+Zookeeper service which uses dynamic role assignment to ensure its own
+fault-tolerance\nbsp{}cite:okorafor2012zookeeper. So, the lack of dynamic role
+distribution in YARN scheduler complicates the whole cluster configuration: if
+dynamic roles were available, Zookeeper would be redundant in this
+configuration.
+
+The same problem occurs in HPC job schedulers where master node (where the main
+job scheduler process is run) is the single point of failure.
In\nbsp{}cite:uhlemann2006joshua,engelmann2006symmetric the authors replicate
-job scheduler state to a backup node to make the principal node highly
-available, but backup node role is assigned statically. This solution is close
-to symmetric architecture, because it does not involve external service to
-provide high availability, but far from ideal in which backup node is
-dynamically chosen.
+job scheduler state to a backup node to make the master node highly available,
+but backup node role is assigned statically. This solution is close to symmetric
+architecture, because it does not involve external service to provide high
+availability, but far from ideal in which backup node is dynamically chosen.
-Finally, the simplest principal node high availability is implemented in VRRP
+Finally, the simplest master node high availability is implemented in VRRP
protocol (Virtual Router Redundancy
Protocol)\nbsp{}cite:rfc2338,rfc3768,rfc5798. Although VRRP protocol does
provide dynamic role distribution, it is designed to be used by routers and
@@ -3189,7 +3187,7 @@ Keepalived daemon\nbsp{}cite:cassen2002keepalived instead.
Symmetric architecture is beneficial for job schedulers because it
allows to
- make physical nodes interchangeable,
-- implement dynamic distribution of principal and subordinate roles, and
+- 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
parallel programme and job scheduler, that can tolerate failure of cluster
@@ -3197,7 +3195,7 @@ nodes.
**** Definitions of hierarchies.
To disambiguate hierarchical links between daemon processes and kernels and to
-simplify the discussion, we will use the following naming conventions throughout
+simplify the discussion, the following naming conventions are used throughout
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
@@ -3259,19 +3257,19 @@ The algorithm is best described by an example
(fig.\nbsp{}[[fig-fail-over-example]]).
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 topologies in which several network
- switches connect all cluster nodes.
+ 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
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 principal process. The hierarchy is changed only when
+ 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 principal node \(A\). \(T_1\) represents one sequential step of a
+ the 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
@@ -3306,13 +3304,13 @@ The algorithm is best described by an example
**** Evaluation results.
Fail over algorithm was evaluated on physical cluster (table\nbsp{}[[tab-ant]]) on
the example of distributed AR model application, which is described in detail in
-section [[#sec-arma-mpp]]. The application consists of a series of functions, each
+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
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 principal node.
+parallel across all cores of the master node.
The application was rewritten for the distributed version of the framework which
required adding read/write methods to each kernel which is sent over the network
@@ -3402,8 +3400,8 @@ title(xlab="Wavy surface size", ylab="Time, s")
[[file:build/master-slave-failure.pdf]]
To summarise, if failure occurs right after a copy if the main kernel is made,
-only a small fraction of performance is lost in case of master node failure, and
-more performance is lost in case of slave node failure.
+only a small fraction of performance is lost no matter whether the main kernel
+or its copy is lost.
**** Discussion of test results.
Since failure is simulated right after the first subordinate kernel reaches its
@@ -3445,9 +3443,9 @@ 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
-sequential step has the less time is lost in case of a principal or subordinate
-node failure. In other words, the more nodes a programme uses the more resilient
-to cluster node failures it becomes.
+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.
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
@@ -3545,32 +3543,24 @@ 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 principal and subordinate 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.
-
-It may seem as if three building blocks of the proposed approach\nbsp{}---
-control flow objects, pipelines and hierarchies\nbsp{}--- are orthogonal, but,
-in fact the complement each other. Without control flow objects carrying
-programme state it is impossible to recompute failed subordinate objects and
-provide fault tolerance. Without node hierarchy it is impossible to distribute
-the load between cluster nodes, because all nodes are equal without the
-hierarchy. Without pipelines for each device it is impossible to execute control
-flow objects asynchronously and implement dynamic load balancing. These three
-entities form a closed system with nothing to add and nothing to
-remove\nbsp{}--- a solid foundation for any distributed programme.
-
-To summarise, one can say that the control flow objects make parallel programmes
-more flexible: they balance the decrease in the performance due to shared object
-queues with the increase due to dynamic load balancing. Requiring more RAM, they
-allow to simultaneously run multiple parallel programmes on all cluster nodes
-without idling in the job queue, and transform the cluster into a unified
-computer system which makes best effort to execute distributed applications
-without interruption.
+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
+subordinate objects and provide fault tolerance. Without node hierarchy it is
+impossible to distribute the load between cluster nodes, because all nodes are
+equal without the hierarchy. Without pipelines for each device it is impossible
+to execute control flow objects asynchronously and implement dynamic load
+balancing. These three entities form a closed system, in which programme logic
+is implemented in kernels or pipelines, failure recovery logic\nbsp{}--- in
+kernel hierarchy, and data transfer logic\nbsp{}--- in cluster node hierarchy.
** MPP implementation
:PROPERTIES:
@@ -3757,6 +3747,7 @@ for Basic Research (projects no.\nbsp{}\mbox{16-07-01111}, \mbox{16-07-00886},
- <<<HPC>>> :: High-performance computing.
- <<<GCS>>> :: Gram---Charlier series.
- <<<SN>>> :: Skew normal distribution.
+- <<<PBS>>> :: Portable batch system.
- Transcendental functions :: non-algebraic mathematical functions
(i.e.\nbsp{}logarithmic, trigonometric etc.).
diff --git a/tex/legend-ru.tex b/tex/legend-ru.tex
@@ -10,7 +10,7 @@
\node[anchor=west] (X2) at (4.4,2) {\strut сетевое соединение};
\node[Daemon,scale=0.6] at (0,3) {\phantom{A}};
- \node[anchor=west] (X2) at (0.4,3) {\strut процесс-сервис};
+ \node[anchor=west] (X2) at (0.4,3) {\strut резидентный процесс};
\draw[DaemonLink] (3.8,3) -- (4.2,3);
\node[anchor=west,text width=5cm] (X2) at (4.4,3) {\strut иерархическая связь между узлами};
