commit 72e337a0eeff07e3fc0a6570c878e3ec7dda4766
parent c1d4e2967b29db935a96c58b930d53d16246891d
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 13 Feb 2017 18:44:55 +0300
Merge fault tolerance and high availability sections. Sync them.
Diffstat:
| phd-diss-ru.org | | | 87 | ++++++++++++++++++++++++++++++++++++++++++++----------------------------------- |
| phd-diss.org | | | 122 | ++++++++++++++++++++++++++++++++++++------------------------------------------- |
2 files changed, 104 insertions(+), 105 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2773,45 +2773,54 @@ cite:dean2008mapreduce,vavilapalli2013yarn --- пользователь, зап
объекты. Когда обработка завершена, родительский объект вызывается с дочерним
объектом в качестве аргумента для сбора результатов обработки.
-**** Выход из строя одного узла.
-Наиболее распространенная стратегия при выходе из строя подчиненного узла ---
-перезапуск выполнявшихся на нем объектов на рабочих узлах. Этой стратегии
-следует язык Erlang для перезапуска подчиненных
-процессов cite:armstrong2003thesis. Для того что реализовать этот метод в
-рамках иерархии вычислительных объектов необходимо сохранять каждый объект
-передаваемый на другие узлы кластера. В случае отказа одного из узлов, на
-которые были переданы объекты, соответствующие их копии извлекаются из очереди
-на перераспределяются между оставшимися узлами без какой-либо дополнительной
-обработки. Если больше узлов не осталось, то объекты перенаправляются в
-локальную очередь. В отличие от "тяжеловесного" метода контрольных точек
-восстановления, древовидная иерархия узлов в паре с иерархией объектов позволяет
-автоматически продолжить выполнение программы при выходе из строя одного из
-узлов без перезапуска каких-либо процессов задачи.
-
-Возможная стратегия при выходе из строя узла, на котором хранится главный
-вычислительный объект задачи, заключается в копировании этого объекта на
-резервный узел и синхронизировать любые изменения между двумя копиями объекта
-посредством распределенных транзакций. Однако, эта стратегия не соотносится с
-асинхронностью вычислительных ядер и слишком сложна в реализации. На практике,
-оказывается, что главный объект программы обычно не создает больше одного
-дочернего объекта, каждый из которых представляет собой последовательный шаг
-вычислений (внутри которого может быть, а может не быть параллельных этапов).
-Поскольку шаги последовательны, то одновременно может существовать не более
-одного дочернего объекта, что позволяет упростить синхронизацию состояния
-главного объекта программы. Для этого главный объект передается на подчиненный
-узел вместе со своим дочерним объектом. Тогда при выходе из строя узла, на
-котором была запущена программа, резервный узел автоматически восстанавливает
-состояние главного объекта из копии, когда дочерний объект завершает свою
-работу.
-
-Описанный выше подход предназначен только для объектов, у которых нет
-объекта-родителя и которые создают по одному дочернему объекту за раз. Это
-означает, что метод работает как контрольная точка восстановления, которая
-сохраняет состояние только между последовательными шагами вычислений (когда оно
-занимает минимальный объем памяти) и которая для сохранения состояния
-использует оперативную память другого узла кластера, а не диск.
-
-**** Обеспечение высокой доступности.
+**** Обработка выхода узлов из строя.
+Наиболее распространенная стратегия при выходе из строя подчиненного узла
+является перезапуск выполнявшихся на нем объектов на рабочих узлах ---
+стратегия, которой следует язык Erlang при перезапуске подчиненных процессов
+cite:armstrong2003thesis. Для того что реализовать этот метод в рамках иерархии
+управляющих объектов, узел-отправитель сохраняет каждый объект, передаваемый на
+другие узлы кластера, и в случае отказа произвольного количества узлов, на
+которые были переданы объекты, их копии перераспределяются между оставшимися
+узлами без индивидуальной обработки программистом. Если больше не осталось
+узлов, на которые можно отправить объекты, то они выполняются локально. В
+отличие от "тяжеловесного" метода контрольных точек восстановления,
+используемого планировщиками задач HPC кластеров, древовидная иерархия узлов в
+паре с иерархией объектов позволяет автоматически продолжить выполнение
+программы при выходе из строя произвольного количества подчиненных узлов без
+перезапуска каких-либо процессов параллельной программы.
+
+Возможный подход к обработке выхода из строя главного узла (узла, на котором
+запускается главный управляющий объект) заключается в копировании этого главного
+объекта на резервный узел и синхронизации любых изменений между двумя копиями
+объекта посредством распределенных транзакций, однако, этот подход не
+соотносится с асинхронностью вычислительных ядер и слишком сложна в реализации.
+На практике, оказывается, что главный управляющий объект обычно не выполняет
+операции параллельно, а последовательно переходит от вычисления одного шага
+программы к вычислению другого, и, значит, имеет не больше одного подчиненного в
+каждый момент времени. (Каждый подчиненный объект представляет собой
+последовательный шаг вычислений, который может быть, а может не быть
+параллельным внутри.) Имея это ввиду, можно упростить синхронизацию состояния
+главного объекта программы: отправить главный объект на подчиненный узел вместе
+с его подчиненным объектом. Тогда при выходе из строя главного узла, копия
+главного объекта принимает подчиненный объект (поскольку оба объекта находятся
+на одном и том же узле), и время на восстановление не тратится. Если же выходит
+из строя подчиненный узел, на которым был отправлен подчиненный объект вместе с
+копией главного объекта, то подчиненный объект отправляется на оставшиеся узлы,
+и в худшем случае текущий шаг вычислений выполняется заново.
+
+Описанный выше подход предназначен для объектов, у которых нет объекта-родителя
+и которые имеют только один подчиненный объект в каждый момент времени, и
+повторяет механизм работы контрольных точек восстановления. Преимуществом
+данного подхода является то, что он
+- сохраняет состояние только между последовательными шагами вычислений (когда оно
+занимает минимальный объем памяти),
+- сохраняет только актуальное данные и
+- использует для сохранения состояния оперативную память другого узла кластера,
+ а не дисковое хранилище.
+Этот подход позволяет выдержать выход из строя не более одного /любого/ узла
+кластера за один шаг вычислений или произвольного количества подчинненых узлов в
+любой момент работы программы.
+
**** Результаты тестирования.
Методы отказоустойчивости были протестированы на физическом кластере
(см. [[tab:cluster]]) на примере программы, генерирующей взволнованную
diff --git a/phd-diss.org b/phd-diss.org
@@ -2671,74 +2671,47 @@ kernels are created to process it in parallel. When the processing is complete a
parent kernel closure with its subordinate kernel as an argument is called to
collect the resulting data from it.
-**** Handling single node failures.
+**** Handling nodes failures.
Basic strategy to overcome a failure of a subordinate node is to restart
-corresponding kernels on healthy node---a strategy employed in Erlang language
-to restart failed subordinate processes cite:armstrong2003thesis. To implement
-this we record every kernel that is sent to remote cluster nodes, and in an
-event of a node failure these kernels are simply rescheduled to other
-subordinate nodes with no special handling from a programmer. If there are no
-nodes to sent kernels to, they are scheduled locally. So, in contrast to
-heavy-weight checkpoint/restart machinery, tree hierarchy allows automatic and
-transparent handling of subordinate node failures without restarting parallel
-processes on every node.
-
-A possible way of handling a failure of a node where the first kernel is located
-is to replicate this kernel to a backup node, and make all updates to its state
-propagate to the backup node by means of a distributed transaction. However,
-this approach does not play well with asynchronous nature of computational
-kernels. Fortunately, the first kernel usually does not perform operations in
-parallel, it is rather sequentially launches execution steps one by one, so it
-has only one subordinate at a time. Keeping this in mind, we can simplify
-synchronisation of its state: we can send the first kernel along with its
-subordinate to the subordinate node. When the node with the first kernel fails,
-its copy receives its subordinate, and no execution time is lost. When the node
-with its copy fails, its subordinate is rescheduled on some other node, and a
-whole step of computation is lost in the worst case.
-
-Described approach works only for kernels that do not have a parent and have
-only one subordinate at a time, which means that they act as optimised
-checkpoints. The advantage is that they save results after each sequential step,
-when memory footprint of a programme is low, they save only relevant data, and
-they use memory of a subordinate node instead of stable storage.
-
-**** High availability.
-A possible way of handling a failure of a node where the first kernel is located
-(a master node) is to replicate this kernel to a backup node, and make all
-updates to its state propagate to the backup node by means of a distributed
-transaction. This approach requires synchronisation between all nodes that
-execute subordinates of the first kernel and the node with the first kernel
-itself. When a node with the first kernel goes offline, the nodes with
-subordinate kernels must know what node is the backup one. However, if the
-backup node also goes offline in the middle of execution of some subordinate
-kernel, then it is impossible for this kernel to discover the next backup node
-to return to, because this kernel has not discovered the unavailability of the
-master node yet. One can think of a consensus-based algorithm to ensure that
-subordinate kernels always know where the backup node is, but distributed
-consensus algorithms do not scale well to the large number of nodes and they are
-not reliable cite:fischer1985impossibility. So, consensus-based approach does
-not play well with asynchronous nature of computational kernels as it may
-inhibit scalability of a parallel programme.
-
-Fortunately, the first kernel usually does not perform operations in parallel,
-it is rather sequentially launches execution steps one by one, so it has only
-one subordinate at a time. Such behaviour is described by bulk-synchronous
-parallel programming model, in the framework of which a programme consists of
-sequential supersteps which are internally parallel cite:valiant1990bridging.
-Keeping this in mind, we can simplify synchronisation of its state: we can send
-the first kernel along with its subordinate to the subordinate node. When the
-node with the first kernel fails, its copy receives its subordinate, and no
-execution time is lost. When the node with its copy fails, its subordinate is
-rescheduled on some other node, and in the worst case a whole step of
-computation is lost.
-
-Described approach works only for kernels that do not have a parent and have
-only one subordinate at a time, and act similar to manually triggered
-checkpoints. The advantage is that they
-- save results after each sequential step when memory footprint of a programme
+corresponding kernels on a healthy node --- a strategy employed by Erlang
+language to restart failed subordinate processes 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 automatic and transparent handling of any number of subordinate
+node failures without restarting any processes of a parallel programme.
+
+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
+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 to 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.
+
+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,
-- they save only relevant data,
-- and they use memory of a subordinate node instead of stable storage.
+- saves only relevant data, and
+- uses memory of a subordinate node rather than disk storage.
+This simple approach allows tolerating at most one failure of /any/ cluster node
+per computational step or arbitrary number of subordinate nodes at any time
+during programme execution.
**** Evaluation.
Factory framework is evaluated on physical cluster (Table [[tab:cluster]]) on
@@ -2921,6 +2894,23 @@ the impossibility of the distributed consensus with one faulty
process cite:fischer1985impossibility and impossibility of reliable
communication in the presence of node failures cite:fekete1993impossibility.
+A possible way of handling a failure of a node where the first kernel is located
+(a master node) is to replicate this kernel to a backup node, and make all
+updates to its state propagate to the backup node by means of a distributed
+transaction. This approach requires synchronisation between all nodes that
+execute subordinates of the first kernel and the node with the first kernel
+itself. When a node with the first kernel goes offline, the nodes with
+subordinate kernels must know what node is the backup one. However, if the
+backup node also goes offline in the middle of execution of some subordinate
+kernel, then it is impossible for this kernel to discover the next backup node
+to return to, because this kernel has not discovered the unavailability of the
+master node yet. One can think of a consensus-based algorithm to ensure that
+subordinate kernels always know where the backup node is, but distributed
+consensus algorithms do not scale well to the large number of nodes and they are
+not reliable cite:fischer1985impossibility. So, consensus-based approach does
+not play well with asynchronous nature of computational kernels as it may
+inhibit scalability of a parallel programme.
+
* Conclusion
* Acknowledgements
The graphs in this work were prepared using R language for statistical
