commit 1870883a310001626c8d2e9cba453abfc7930559
parent 5df34bdd2e92584a5c3ed37b92683ae34f61c221
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 3 Nov 2017 12:47:37 +0300
Finish editing fail over section.
Diffstat:
| arma-thesis-ru.org | | | 201 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
| arma-thesis.org | | | 59 | ++++++++++++++++++++++++++++++----------------------------- |
2 files changed, 135 insertions(+), 125 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -3486,120 +3486,129 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
[[file:build/fail-over-example-ru.pdf]]
**** Результаты тестирования.
-Методы отказоустойчивости были протестированы на физическом кластере
-(см.\nbsp{}табл.\nbsp{}[[tab-ant]]) на примере программы, генерирующей взволнованную
-морскую поверхность, подробно описанной в разделе [[#sec:arma-mpp]]. Программа
-состоит из серии фильтров, каждый из которых применяется к результату работы
-предыдущего. Некоторые из фильтров вычисляются параллельно, так что вся
-программа состоит из последовательно выполняющихся шагов, некоторые из которых
-внутри реализованы параллельно из соображений эффективности. Только наиболее
+Алгоритм обеспечения отказоустойчивости был протестирован на физическом кластере
+(см.\nbsp{}табл.\nbsp{}[[tab-ant]]) на примере распределенной программы для модели
+АР, подробно описанной в разделе\nbsp{}[[#sec:arma-mpp]]. Программа состоит из серии
+функций, каждая из которых применяется к результату работы предыдущей. Некоторые
+из функций вычисляются параллельно, так что вся программа состоит из
+последовательно выполняющихся шагов, некоторые из которых внутри реализованы
+параллельно, чтобы получить большую производительность. Только наиболее
ресурсоемкий этап программы (генерация взволнованной морской поверхности)
выполняется параллельно на всех узлах, другие этапы выполняются параллельно на
всех процессорных ядрах главного узла.
-Программа была переписана под отказоустойчивую версию фреймворка, что
-потребовало лишь небольших изменений исходного кода для корректной обработки
+Программа была переписана для распределенной версии фреймворка, что потребовало
+добавления методов чтения/записи для каждого управляющего объекта, которые
+передается по сети и небольших изменений исходного кода для корректной обработки
выхода из строя узла с главным объектом. Главный объект был помечен, чтобы
фреймворк смог передать его на подчиненный узел вместе с подчиненным ему
объектом. Другие изменения исходного кода были связаны с изменением программного
интерфейса фреймворка. Таким образом, обеспечение отказоустойчивости посредством
иерархии управляющих объектов, в основном, прозрачно для программиста и требует
-лишь маркировки главного объекта для его репликации на резервный узел.
+лишь маркировки главного объекта для его репликации на резервный узел и
+добавлении кода для чтения/записи объектов в байтовый буфер.
В ряде экспериментов была измерена производительность новой версии программы при
-выходе из строя различных типов узлов во время выполнения программы (номера
-пунктов соответствуют номерам графиков рис.\nbsp{}[[fig-benchmark]]):
-1) без выхода из строя узлов,
-2) выход из строя подчиненного узла (на котором генерируется часть взволнованной
- поверхности),
-3) выход из строя главного узла (на котором запускается программа),
-4) выход из строя резервного узла (на который копируется главный объект
- программы).
-Древовидная иерархия узлов со значением ветвления равного 64 использовалась в
-экспериментах, для того чтобы удостовериться, что все подчиненные узлы кластера
-соединены с узлом, имеющим первый IP-адрес в диапазоне адресов подсети.
-Узел-жертва выводился из строя по прошествии фиксированного временного интервала
-после запуска программы равного примерно \(1/3\) времени работы программы на
-одном узле. Приложение мгновенно узнавала о выходе из строя узла, поскольку
-закрывалось соответсвтвующие соединение; при реалистичном развитии событий,
-однако, выход из строя узла обнаружится по прошествии настраивомого тайм-аута.
-Способ запуска для каждого эксперимента представлен в табл.\nbsp{}[[tab-benchmark]].
-Результаты экспериментов приведены на рис.\nbsp{}[[fig-benchmark]]
-и\nbsp{}[[fig-slowdown]].
-
-Эксперименты показали большую разницу в общей производительности приложения при
-выходе из строя различных типов узлов. Графики\nbsp{}2 и\nbsp{}3 на
-рис.\nbsp{}[[fig-benchmark]] показывают, что производительность в случае выхода из
-строя руководящего и подчиненного узлов одинакова. В случае отказа руководящего
-узла резервный узел сохраняет копию главного объекта и восстанавливает главный
-объект из нее, когда обнаруживает, что главный узел вышел из строя. В случае
-отказа подчиненного узла, главный узел перераспределяет невернувшиеся объекты
-между оставшимися подчиненными узлами. В обоих случая состояние главного объекта
-программы не теряется, а значит не тратится время на его восстановление, что
-объясняет схожую производительность.
-
-График\nbsp{}4 на\nbsp{}[[fig-benchmark]] показывает, что производительность в
-случае выхода из строя резервного узла гораздо ниже, чем в других случаях. Это
-происходит, потому что руководящий узел сохраняет состояние только текущего
-последовательного шага программы, в то время как резервный узел не только хранит
-копию этого состояния, но и выполняет этот шаг параллельно с другими
-подчиненными узлами. Так что, когда резервный узел выходит из строя, главный
-узел начинает выполнение текущего этапа с самого начала на произвольно выбранном
-выжившем узле.
-
-#+caption: Параметры экспериментов с алгоритмово восстановления после сбоев.
-#+name: tab-benchmark
-#+attr_latex: :booktabs t
-| Номер эксп. | Время до выхода из строя, сек. |
-| 1 | |
-| 2 | 10 |
-| 3 | 10 |
-| 4 | 10 |
-
-Для оценки количества времени, которое теряется при выходе узла из строя, можно
-поделить общее время работы программы со сбоем на время работы программы без
-сбоев, но с количеством узлов минус один. Это отношение получается из того же
-самого эксперимента и представлено на рис.\nbsp{}[[fig-slowdown]]. Разница в
-производительности в случае выхода из строя руководящего и подчиненного узлов
-находится в пределах 5%, а в случае выхода из строя резервного узла\nbsp{}--- в
-пределах 50% для количества узлов меньше 6[fn::Измерение разницы для большего
-количества узлов не имеет смысла, поскольку программа завершается еще до
-наступления сбоя.]. Увеличение времени выполнения на 50%\nbsp{}--- это больше,
-чем \(1/3\) времени работы программы, после которого происходит сбой, однако
-отказ резервного узла требует некоторого времени, чтобы быть обнаруженным
-другими узлами: сбой узла обнаруживается только тогда, когда подчиненный объект,
-имеющий копию главного объекта, завершает свое выполнение и пытается вернуться
-на исходный узел к родителю. Мгновенное обнаружение сбоя узла требует внезапной
-остановки выполнения объектов, что может быть неприменимо для программ со
-сложной логикой.
-
-#+name: fig-benchmark
-#+begin_src R :file build/benchmark-xxx-ru.pdf
-# TODO
-#+end_src
+выходе из строя различных типов узлов во время выполнения:
+- без выхода из строя узлов,
+- выход из строя главного узла (на котором запускается главный объект),
+- выход из строя подчиненного узла (на который копируется главный объект
+ программы).
+Только два напрямую соеденных узла кластера были использованы в тесте. Выход из
+строя узла имитировался путем отправки сигнала ~SIGKILL~ резидентному процессу
+на соответствующем узле, сразу после того как копия главного объекта создана.
+Приложение сразу обнаруживало выход из строя узла, поскольку соответствующее
+соединение закрывалось; на практике, однако, выход узла из строя обнаруживается
+только по прошествии настраиваемого время ожидания протокола
+TCP\nbsp{}cite:rfc5482. Время выполнения этих запусков сравнивалось со временем
+выполнения без имитирования выхода из строя узлов. Результаты тестов
+представлены на рис.\nbsp{}[[fig-master-slave-failure]], а схема распределения
+управляющих объектов между двумя узлами на рис.\nbsp{}[[fig-master-slave-backup]].
+
+#+name: fig-master-slave-backup
+#+begin_src dot :exports results :file build/master-slave-backup-ru.pdf
+digraph {
+
+ node [fontname="Old Standard",fontsize=14,margin="0.055,0.055",shape=box,style=rounded]
+ graph [nodesep="0.30",ranksep="0.30",rankdir="BT"]
+ edge [arrowsize=0.66]
+
+ m1 [label="{{<master>Master | 10.0.0.1} | {<main>M | <slave1>S₁ | <slave3>S₃}}",shape=record]
+ m2 [label="{{<slave>Slave | 10.0.0.2} | {M' | <step>N | <slave2>S₂ | <slave4>S₄}}",shape=record]
-#+caption: Производительность программы генерации взволнованной морской поверхности при различных типах сбоев узлов.
-#+label: fig-benchmark
-#+RESULTS: fig-benchmark
-[[file:build/benchmark-xxx-ru.pdf]]
+ m2->m1
-Результаты экспериментов позволяют сделать вывод о том, что не важно, вышел ли
-из строя руководящий узел или подчиненный, общее время работы параллельной
-программы примерно равно времени ее работы без сбоев, но с уменьшенным на
-единицу количеством узлов, однако, в случае выхода из строя резервного узла
-потери в производительности гораздо больше.
+}
+#+end_src
-#+name: fig-slowdown
-#+begin_src R :file build/slowdown-xxx-ru.pdf
-# TODO
+#+name: fig-master-slave-backup
+#+caption: Главный и подчиненный узлы, а также отображение главного объекта \(M\), его копии \(M'\), объекта, соответствующего текущему шагу выполнения \(N\) и подчиненных объектов \(S_{1,2,3}\) на эти узлы.
+#+RESULTS: fig-master-slave-backup
+[[file:build/master-slave-backup-ru.pdf]]
+
+Как и ожидалось, существует большая разница в производительности приложения при
+выходе из строя различных типов узлов. В случае отказа подчиненного узла главный
+управляющий объект вместе с некоторыми подчиненными (которые были распределены
+на подчиненный узел) теряются, но главный узел имеет копию главного объекта и
+использует ее, чтобы продолжить выполнение. Таким образом, при выходе из строя
+подчиненного узла ничего не теряется, за исключением потенциала
+производительности подчиненного узла. В случае выхода из строя главного узла
+копия главного объекта, а также подчиненный объект, который переносит эту копию,
+теряются, но подчиненный узел имеет оригинальный главный объект и использует его
+для перезапуска вычислений с текущего шага, т.е.\nbsp{}отправляет подчиненный
+объект на один из оставшихся узлов кластера (в случае двух напрямую соединенных
+узлов он отправляет объект себе же). Таким образом, разница в производительности
+приложения объясняется разным количеством и разными ролями объектов, которые
+теряются при выходе из строя того или иного узла.
+
+Обнаружение выхода из строя подчиненного узла требует некоторого времени: это
+происходит, только когда подчиненный объект, переносящий копию главного,
+заканчивает выполнение и пытается добраться до родительского объекта.
+Мгоновенное обнаружение требует принудительной остановки подчиненного объекта,
+что может быть неприменимо для программ со сложной логикой.
+
+#+name: fig-master-slave-failure
+#+begin_src R :file build/master-slave-failure-ru.pdf
+source(file.path("R", "benchmarks.R"))
+par(family="serif")
+data <- arma.load_master_slave_failure_data()
+arma.plot_master_slave_failure_data(
+ data,
+ list(
+ master="Bscheduler (главный узел)",
+ slave="Bscheduler (подчиненный узел)",
+ nofailures="Bscheduler (без выхода из строя)"
+ )
+)
+title(xlab="Размер взволнованной поверхности", ylab="Время, сек.")
#+end_src
-#+caption: Замедление программы генерации взволнованной морской поверхности при различных типах сбоев по сравнению с запуском без сбоев но с уменьшенным на единицу количеством узлов.
-#+label: fig-slowdown
-#+RESULTS: fig-slowdown
-[[file:build/slowdown-xxx-ru.pdf]]
+#+caption: Производительность модели АР при выходе из строя узлов.
+#+name: fig-master-slave-failure
+#+RESULTS: fig-master-slave-failure
+[[file:build/master-slave-failure-ru.pdf]]
+
+Итого, если выход из строя узла происходит сразу после того как копия главного
+объекта сделана, лишь малая часть производительности теряется в случае выхода из
+строя главного узла; при выходе из строя подчиненного узла теряется больше
+производительности.
**** Обсуждение результатов тестирования.
+Поскольку выход из строя имитируется, сразу после того как первый подчиненный
+объект достигает точки назначения (узла, на котором предполагается его
+выполнить), выход из строя подчиненного узла приводит к потере небольшой доли
+производительности; на практике, где выход из строя может произойти в середине
+генерации взволнованной поверхности, потери производительности при выходе из
+строя /резервного/ узла (узла, где находится копия главного объекта) были бы
+выше. Аналогично, на практике количество узлов в кластере больше, а значит
+меньшее количество подчиненных объектов теряется при выходе из строя главного
+узла, из-за чего потери производительности меньше. В тесте потери в случае
+выхода из строя подчиненного узла выше, что является результатом отсутствия
+параллелизма в начале генерации взволнованной поверхности моделью АР: первая
+часть вычисляется последовательно, а другие части вычисляются, только когда
+первая доступна. Таким образом, потеря первого подчиненного объекта замедляет
+выполнение всех зависимых объектов в программе.
+
Алгоритм восстановления после сбоев гарантирует обработку выхода из строя одного
узла на один последовательный шаг программы; больше сбоев может быть выдержано,
если он не затрагивают руководящий узел. Алгоритм обрабатывает одновременный
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3285,29 +3285,30 @@ executed in parallel across all cluster nodes, and other steps are executed in
parallel across all cores of the principal node.
The application was rewritten for the distributed version of the framework which
-required adding marshalling methods to each kernel which is sent over the
-network 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 replicated kernels and adding code to
-read and write kernels to the byte buffer.
+required adding read/write methods to each kernel which is sent over the network
+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.
In a series of experiments performance of the new version of the application in
the presence of different types of failures was benchmarked:
-1) no failures,
-2) failure of a slave node (a node where a copy of the main kernel is stored),
-3) failure of a master node (a node where the main kernel is run).
+- no failures,
+- failure of a slave node (a node where a copy of the main kernel is stored),
+- failure of a master node (a node where the main kernel is run).
Only two directly connected cluster nodes were used for the benchmark. Node
failure was simulated by sending ~SIGKILL~ signal to the daemon process on the
corresponding node right after the copy of the main kernel is made. The
application immediately recognised node as offline, because the corresponding
connection was closed; in real-world scenario, however, the failure is detected
-after a configurable TCP user timeout\nbsp{}cite:rfc5482. The execution time of
-these runs were compared to the run without node failures, results are presented
-in fig.\nbsp{}[[fig-master-slave-failure]]. The diagram of how kernels are
-distributed between two nodes is shown in fig.\nbsp{}[[fig-master-slave-backup]].
+only after a configurable TCP user timeout\nbsp{}cite:rfc5482. The execution
+time of these runs were compared to the run without node failures. Results are
+presented in fig.\nbsp{}[[fig-master-slave-failure]], and a diagram of how kernels
+are distributed between two nodes is shown in
+fig.\nbsp{}[[fig-master-slave-backup]].
#+name: fig-master-slave-backup
#+begin_src dot :exports results :file build/master-slave-backup.pdf
@@ -3326,7 +3327,7 @@ digraph {
#+end_src
#+name: fig-master-slave-backup
-#+caption: Master and slave nodes and mapping of main kernel \(M\), a copy of main kernel \(M'\), current step kernel \(N\) and subordinate kernels \(S_{1,2,3}\) on them in the benchmark.
+#+caption: Master and slave nodes and mapping of main kernel \(M\), a copy of main kernel \(M'\), current step kernel \(N\) and subordinate kernels \(S_{1,2,3}\) on them.
#+RESULTS: fig-master-slave-backup
[[file:build/master-slave-backup.pdf]]
@@ -3338,15 +3339,15 @@ execution. So, in case of slave node failure nothing is lost except performance
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. send the subordinate kernel to the available
+current sequential step, i.e. 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 amount of
-execution state that is lost as a result of a failure is different.
+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
subordinate kernel carrying a copy of the main kernel finishes its execution and
-tries to reach its parent. Instant detection requires abrupt stopping of the
-subordinate kernel which may be inapplicable for programmes with complicated
+tries to reach its parent. Instant detection requires forcible termination of
+the subordinate kernel which may be inapplicable for programmes with complicated
logic.
#+name: fig-master-slave-failure
@@ -3375,19 +3376,19 @@ 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.
**** Discussion of test results.
-Since failure is simulated right after the first subordinate kernels reaches its
+Since failure is simulated right after the first subordinate kernel reaches its
destination (a node where it is supposed to be executed), slave node failure
results in a loss of a small fraction of performance; in real-world scenario,
where failure may occur in the middle of wavy surface generation, performance
loss due to /backup/ node failure (a node where a copy of the main kernel is
located) would be higher. Similarly, in real-world scenario the number of
-cluster nodes is larger, and less amount of subordinate kernels is lost due to
-master node failure, hence performance penalty would be lower for this case. In
-the benchmark the penalty is higher for the slave node failure, which is the
-result of absence of parallelism in the beginning of AR model wavy surface
-generation: the first part is computed sequentially, and other parts are
-computed only when the first one is available. So, failure of the first
-subordinate kernel delays execution of every dependent kernel in the programme.
+cluster nodes is larger, hence less amount of subordinate kernels is lost due to
+master node failure, so performance penalty is lower. In the benchmark the
+penalty is higher for the slave node failure, which is the result of absence of
+parallelism in the beginning of AR model wavy surface generation: the first part
+is computed sequentially, and other parts are computed only when the first one
+is available. So, the loss of the first subordinate kernel delays execution of
+every dependent kernel in the programme.
Fail over algorithm guarantees to handle one failure per sequential programme
step, more failures can be tolerated if they do not affect the master node. The
