commit 3dceb6e4d3fdd4db295cc0fec135ab37bcd2ba05
parent 3f2425046b81ccb56f492b4832682ce3283f1508
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 23 Jan 2017 10:34:34 +0300
Copy tbe rest of the Russian text from final work.
Diffstat:
| phd-diss-ru.org | | | 526 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 526 insertions(+), 0 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2289,10 +2289,536 @@ arma.plot_factory_vs_openmp_overlap(
** Реализация для систем с распределенной памятью (MPP)
*** Обзор архитектур распределенных систем
+Многие распределенные системы построены по принципу /субординации/: в каждом
+кластере выбирается главный узел, который управляет очередью задач решаемых на
+кластере и мониторингом их выполнения. Роль главного узла может задаваться как
+/статически/, путем выделения конкретного физического узла под нее, так и
+/динамически/, путем избрания какого-либо из узлов кластера главным. В первом
+случае отказоустойчивость обеспечивается посредством резервирования
+дополнительного свободного узла, который займет место главного в случае отказа
+оборудования. Во втором случае отказоустойчивость обеспечивается выбором нового
+главного узла из оставшихся в случае отказа текущего. Несмотря на то что
+динамический распределение ролей требует наличия распределенного алгоритма, этот
+подход становится все более и более популярным, поскольку не требует наличия
+простаивающих резервных узлов на случай отказа главного узла.
+
+Алгоритмы выбора лидера (которые иногда называют алгоритмами распределенного
+консенсуса) являются частными случаями волновых алгоритмов. В
+cite:tel2000introduction Тель определяет их как алгоритмы, в которых событие
+завершения программы предваряется хотя бы одним каким-либо другим событием,
+происходящем в /каждом/ параллельном процессе. Волновые алгоритмы не определены
+для анонимных сетей, т.е. они работают только с теми параллельными процессами,
+которые могут себя уникально идентифицировать. Однако, количество процессов,
+которых затрагивает "волна" может быть определено по мере выполнения алгоритма.
+В рамках распределенных систем это означает, что волновые алгоритмы подходят для
+вычислительных кластеров с динамически меняющимся количеством узлов, так что
+включение и выключение отдельных узлов не влияет на работу алгоритма.
+
*** Алгоритм обнаружения узлов кластера
+**** Введение.
+Подход к динамическому выбору главного узла, исследованный в данной работе, не
+использует волновые алгоритмы, а значит не требует опроса кворума узлов для
+выбора лидера. Вместо этого каждый узел кластера составляет список других узлов
+подсети, в которой он находится, и простым алгоритмом преобразует список в
+/древовидную иерархию/ с заданным значением ветвления (максимальным
+количеством подчиненных вершин). Затем узел определяет уровень иерархии, на
+котором он находится и пытается соединиться с вышестоящими узлами, чтобы стать
+их подчиненным. Сначала он проверяет близко расположенные к нему узлы, а потом
+все остальные узлы вплоть до вершины иерархии. Если вышестоящих узлов нет или с
+ними невозможно соединиться, то этот узел становится главным.
+
+Древовидная иерархия узлов подсети определяет отношение строгого порядка на
+множестве всех узлов кластера. С технической точки зрения любая функция может
+быть выбрана для присвоения узлу подсети номера в списке, однако, на практике
+эта функция должна быть достаточно гладкой вдоль временной оси и иметь лишь
+редкие скачки: быстрые изменения в структуре иерархии узлов могут привести
+постоянной передачи роли главного узла от одного узла к другому, что сделает
+кластер неуправляемым. Простейшей такой функцией является позиция IP-адреса
+узла в диапазоне всех IP-адресов подсети.
+
+Основной особенностью алгоритма является многоуровневая субординация, т.е.
+выбор сразу нескольких лидеров в рамках одной подсети в зависимости от значения
+ветвления иерархии. Это позволяет делать локальные изменения в структуре
+иерархии, не затрагивающие всех узлов кластера, и определить адрес
+потенциального главного узла еще до начала алгоритма. Подход отличается от
+волновых алгоритмов наличием сразу нескольких лидеров в одной подсети,
+использованием IP-адресов узлов в качестве уникального идентификатора и
+критерия ранжирования, а также отсутствием какой-либо предварительной
+коммуникации между узлами, которая нужна для определения их ранга.
+
+Алгоритм /субординации/, исследованный в данной работе, позволяет объединить
+узлы вычислительного кластера в распределенную систему без какой-либо
+предварительной конфигурации, только лишь установив и запустив соответствующие
+сервисы на каждом из узлов. При выходе из строя одного из узлов эти сервисы
+способны самостоятельно найти исправный узел и стать его подчиненным, или же
+занять вершину иерархии. Такая автономность работы выгодно отличает субординацию
+от традиционных подходов к управлению вычислительным кластером, который включает
+в себя ручную настройку главного и подчиненных узлов, а также резервного узла
+для обеспечения отказоустойчивости.
+
+В отличие от других алгоритмов выбора лидера
+cite:brunekreef1996design,aguilera2001stable,romano2014design, алгоритм
+субординации не предназначен для управления одновременным обновлением записей в
+распределенной базе данных несколькими параллельными процессами; вместо этого
+основной областью применения алгоритма служит распределение нагрузки на большое
+количество узлов кластера. Обычно, кластер управляет одним главным узлов (или
+1-2 узлами для обеспечения отказоустойчивости), который собирает данные
+мониторинга, ведет учет потребленных пользователями ресурсов, позволяет изменять
+настройки всего кластера и ставит задачи в очередь для запуска. Для больших
+кластеров одного главного узла может быть недостаточно, чтобы справиться с
+нагрузкой, и в этом случае введение подчиненных узлов, управляющих отдельными
+частями кластера, может решить эту проблему.
+
+Алгоритм субординации предполагает, что IP-адрес узла изменяется редко (при
+этом один и тот же IP-адрес необязательно должен быть закреплен за определенным
+узлом). Практика показывает, что это предположение выполняется для кластеров,
+однако это может стать проблемой для виртуальных кластеров, создаваемых на
+ресурсах облачных провайдеров: в таких кластерах IP-адрес может меняться
+произвольно с сохранением DNS-имени узла. Использование алгоритм субординации в
+такой среде может привести к постоянному переназначению ролей узлов кластера,
+что не позволит эффективно распределять нагрузку.
+
+Суммируя вышесказанное, алгоритм субординации не подходит для сред, в которых
+IP-адреса меняются часто, основной сферой применения алгоритма является
+распределение нагрузки на вычислительный кластер и алгоритм не требует
+какой-либо предварительной конфигурации.
+**** Построение древовидной иерархии.
+Субординация на множестве $\mathcal{N}$ узлов одной подсети определяется как
+\begin{equation*}
+\forall n_1 \forall n_2 \in \mathcal{N},
+\forall f \colon \mathcal{N} \rightarrow \mathcal{R}^n
+\Rightarrow (f(n_1) < f(n_2) \Leftrightarrow \neg (f(n_1) \geq f(n_2))),
+\end{equation*}
+где $f$ --- отображение узла на его идентификационный номер, и $<$ --- оператор,
+определяющий отношение строго порядка на множестве $\mathcal{R}^n$. Функция $f$
+присваивает узлу его порядковый номер, а оператор $<$ делает этот номер
+уникальным.
+
+Простейшее отображение $f$ ставит в соответствие каждому узлу подсети позицию
+его IP-адреса в диапазоне всех адресов подсети. Без преобразования к древовидной
+структуре (когда в подсети выбирается только один лидер) рабочий узел, адрес
+которого занимает наименьшую позицию в диапазоне, становится главным. Если адрес
+узла занимает первую позицию в диапазоне, то для него невозможно выбрать лидера,
+и он будет находится на вершине иерархии вплоть до выхода из строя. Несмотря на
+то что идентификацию узлов на основе их IP-адресов легко реализовать в
+программе, такой подход устанавливает искусственную зависимость роли главного
+узла от IP-адреса. Тем не менее, этот подход полезен для первичного объединения
+узлов в кластер, когда более сложные методы идентификации узлов неприменимы.
+
+Для того чтобы алгоритм субординации масштабировался на большое количество
+узлов, структуру диапазона адресов подсети необходимо сделать древовидной. В
+древовидной иерархии каждый узел идентифицируется уровнем $l$ иерархии, на
+котором он находится и отступом $o$, который равен порядковому номеру узла на
+его уровне. Значения уровня и отступа определяются из следующей задачи
+оптимизации.
+\begin{equation*}
+ n = \sum\limits_{i=0}^{l(n)} p^i + o(n), \quad
+ l \rightarrow \min, \quad
+ o \rightarrow \min, \quad
+ l \geq 0, \quad
+ o \geq 0
+\end{equation*}
+где $n$ --- позиция IP-адреса узла в диапазоне IP-адресов подсети и $p$ ---
+значение ветвления (максимальное количество подчиненных, которых может иметь
+узел). Лидер узла на уровне $l$ с отступом $o$ будет иметь уровень $l-1$ и
+отступ $\lfloor{o/p}\rfloor$. Расстояние между любыми двумя узлами в иерархии,
+адреса которых занимают позиции $i$ и $j$ в диапазоне определяется как
+\begin{align*}
+ & \langle
+ \text{lsub}(l(j), l(i)), \quad
+ \left| o(j) - o(i)/p \right|
+ \rangle,\\
+ & \text{lsub}(l_1, l_2) =
+ \begin{cases}
+ \infty & \quad \text{if } l_1 \geq l_2, \\
+ l_1 - l_2 & \quad \text{if } l_1 < l_2.
+ \end{cases}
+\end{align*}
+Расстояние имеет составную запись, чтобы при определении близости двух узлов
+уровень иерархии учитывался в первую очередь.
+
+Для выбора лидера каждый узел ранжирует все узлы подсети в соответствии с
+$\langle{l(n),o(n)}\rangle$ и, используя формулу для определения расстояния,
+выбирает ближайший к потенциальному лидеру узел, имеющий наименьший ранг. Это
+позволяет пропустить IP-адреса выключенных и просто несуществующих узлов, но для
+разреженных сетей, в которых некоторые IP-адреса из середины списка не
+закреплены за работающими узлами, сбалансированность дерева не гарантируется.
+
+Поскольку узлу для выбора лидера нужно соединиться только с узлом, адрес
+которого известен заранее, то алгоритм субординации хорошо масштабируется на
+большое количество узлов. Соединение с другими узлами из ранжированного списка
+происходит только в том случае, если соединение с узлом из начала списка
+прерывается. Таким образом, если адреса рабочих узлов расположены плотно в
+диапазоне адресов подсети, каждый узел устанавливает соединение только со своим
+узлом-лидером, и ресурсоемкого и неэффективного сканирования всей сети каждым
+узлом не происходит.
+
+**** Результаты тестирования.
+Платформа, на которой осуществлялось тестирование, состоит из одного
+многопроцессорного узла, на котором развертывается виртуальный кластер из
+заданного количества узлов с помощью пространств имен Linux. Похожий подход
+используется в
+cite:lantz2010network,handigol2012reproducible,heller2013reproducible, где
+обосновывается целесообразность его применения для проведения экспериментов на
+виртуальных кластерах и сопоставляются результаты некоторых из них с реальными
+кластерами. Преимуществом данного подхода является низкие требования к
+оборудованию, на котором проводятся эксперименты, а также отсутствие влияния
+внешних процессов, выполняющихся параллельно с экспериментами.
+
+Тестирование производительности заключалось в построении графика зависимости
+времени, затрачиваемого на объединение узлов в кластер, от количества узлов. В
+процессе эксперимента любое изменение иерархии записывалось в файл и по
+прошествии 30 сек. все процессы вынужденно останавливались системой. Пробные
+запуски показали, что одновременный запуск более 100 виртуальных узлов искажал
+результаты, поэтому для этого эксперимента были использованы дополнительные
+физические узлы, на каждом из которых создавалось по 100 виртуальных.
+Эксперимент показал, что объединение от 100 до 400 узлов в кластер занимает в
+среднем 1,5 секунды (см. [[fig:bootstrap-local]]). Для полностью физического
+кластера это значение может увеличиться. Пример древовидной иерархии, полученной
+при запуске на 11 узлах представлен на [[fig:tree-hierarchy-11]].
+
+#+name: fig:bootstrap-local
+#+begin_src R
+# TODO
+#+end_src
+
+#+caption: Зависимость времени объединения узлов в кластер в зависимости от их количества.
+#+RESULTS: fig:bootstrap-local
+
+#+name: fig:tree-hierarchy-11
+#+begin_src R
+# TODO
+#+end_src
+
+#+caption: Древовидная иерархия для 11 узлов.
+#+RESULTS: fig:tree-hierarchy-11
+
*** Алгоритм восстановления после сбоев
**** Обеспечение отказоустойчивости.
+Отказы узлов распределенной системы можно разделить на три типа: отказ
+подчиненного узла, отказ главного узла и отказ одновременно всех узлов
+(отключение электричества). Для того чтобы запущенная на кластере задача могла
+продолжиться после отказа подчиненного узла, для нее периодически создаются и
+записываются в надежное хранилище контрольные точки восстановления. При
+создании контрольной точки все параллельные процессы задачи временно
+останавливаются, образ памяти, выделенной операционной системой для процессов
+задачи копируется на диск, и выполнение задачи продолжается в нормальном
+режиме. Для того чтобы отказ главного узла не повлиял на работу кластера,
+состояние сервисов, запущенных на нем, непрерывно копируется на резервный узел,
+который становится главным при отказе. При незапланированном отключении
+электричества состояние всех запущенных на момент отказа задач
+восстанавливается из контрольных точек восстановления.
+
+Оптимизации работы контрольных точек восстановления посвящено большое
+количество работ cite:egwutuoha2013survey, а альтернативным подходам
+уделяется меньше внимания. Обычно высокопроизводительные приложения используют
+передачу сообщений для обмена данными между параллельными процессами и хранят
+свое текущее состояние в глобальной памяти, поэтому не существует способа
+перезапустить завершившийся процесс, не записав образ всей выделенной для него
+памяти на диск. Обычно общее число процессов фиксировано и задается
+планировщиком, и в случае отказа перезапускаются сразу все процессы. Существуют
+некоторые обходные решения, которые позволяют перезапустить только часть
+процессов cite:meyer2012radic, восстановив их на других узлах, однако это
+может привести к перегрузке, если на этих узлах уже запущены другие задачи.
+Теоретически, перезапуск процесса необязателен если задача может быть
+продолжена на меньшем количестве узлов, но библиотека передачи сообщений не
+позволяет изменять количество параллельных процессов во время работы программы,
+и большинство программ все равно предполагают, что это значение является
+константой, и используют его для распределения нагрузки между узлами. Таким
+образом, не существует простого способа обеспечения отказоустойчивости на
+уровне библиотеки передачи сообщений кроме как путем перезапуска всех
+параллельных процессов из контрольной точки восстановления.
+
+В то же время, существует возможность продолжить выполнение задачи на меньшем
+количестве узлов, чем было изначально выделено под нее планировщиком. В этом
+случае нагрузка должна быть динамически перераспределена между оставшимися
+узлами. Несмотря на то что динамическое распределение нагрузки было реализовано
+в поверх библиотеки передачи сообщений в ряде
+работ cite:bhandarkar2001adaptive,lusk2010more, оно никогда не применялось в
+задаче обеспечения отказоустойчивости. В этом разделе исследуются методы
+обеспечения отказоустойчивости при выходе из строя подчиненных и главных узлов
+и показывается, как приемы объектно-ориентированного программирования могут
+быть использованы для сохранения минимального состояния программы, необходимого
+для ее перезапуска, в иерархии объектов, а не в глобальных и локальных
+переменных.
+
+**** Иерархия объектов вычисления.
+Для распределения нагрузки узлы кластера объединяются в
+древовидную иерархию. Нагрузка распределяется между непосредственными соседями
+узла, так что при запуске задачи на подчиненном узле главный узел также
+получают часть нагрузки. Это делает систему симметричной и легкой в
+обслуживании: на каждом узле установлен один и тот же набор программного
+обеспечения, что позволяет заменить один узел другим при выходе из строя
+первого. Похожее архитектурное решение используется в хранилищах типа
+"ключ-значение" cite:anderson2010couchdb,lakshman2010cassandra для
+обеспечения отказоустойчивости при выходе из строя одного из узлов, однако
+автору неизвестны планировщики задач, которые используют данный подход.
+
+Каждая программа, запущенная поверх иерархии узлов состоит из
+/вычислительных объектов/ --- объектов, которых содержат данные и код для
+их обработки. Для эффективного использования параллелизма, предоставляемого
+кластером и многопроцессорной машиной, объект может создать подчиненные
+(дочерние) объекты, которые система автоматически распределит сначала между
+доступными процессорными ядрами, затем между подчиненными узлами кластера. Сама
+программа также является вычислительным объектом, который либо решает
+прикладную задачу последовательно, либо создает подчиненные объекты для
+параллельного решения.
+
+В отличие от функции ~main~ в программах на основе библиотеки передачи
+сообщений, первый вычислительный объект выполняется только на одном узле, а
+дополнительные узлы используются либо при переполнении очереди объектов
+текущего узла, либо при явном указании в коде программы. Такая архитектура
+позволяет использовать произвольное количество узлов для запуска задачи и
+динамически менять это количество во время ее выполнения. Похожий принцип
+выполнения задач используется в системах обработки больших объемов
+данных cite:dean2008mapreduce,vavilapalli2013yarn --- при запуске задаче не
+требуется указывать количество узлов, вместо этого система сама выбирает узлы,
+на которых будет выполняться задача, в зависимости физического расположения
+входных файлов.
+
+С математической точки зрения вычислительный объект $K$ может быть определен
+как векторнозначный функционал, отображающий один вычислительный объект на
+$n$-компонентный вектор вычислительных объектов:
+\begin{equation*}
+ K(f): \mathbb{K} \rightarrow \mathbb{K}^n
+ \qquad
+ \mathbb{K}^n = \left\{ f: \mathbb{K} \rightarrow \mathbb{K}^n \right\}.
+\end{equation*}
+Специальный объект $\mathbb{O}: \mathbb{K} \rightarrow \mathbb{K}^0$
+используется для остановки рекурсии, и передается в качестве аргумента главному
+(первому созданному) объекту программы. Аргумент функционала интерпретируется
+следующим образом.
+- Если текущий объект является только что созданным объектом, то аргумент
+ функционала --- это главенствующий над ним объект (родитель).
+- Если текущий объект является родителем объекта, который его породил или
+ родителем какого-либо другого объекта, то аргумент функционала --- объект,
+ которые его породил.
+
+Объекты обрабатываются в цикле, который начинается с вызова функции главного
+объекта программы, затем вызываются функции всех порожденных им объектов. Цикл
+продолжается до тех пор пока функция какого-либо объекта не вернет
+$\mathbb{O}$. Поскольку вызов функции может породить сразу несколько объектов,
+они выполняются параллельно, что приводит к быстрому заполнению пула объектов,
+которые можно выполнять в произвольном порядке. Несколько потоков одновременно
+выбирают из пула объекты для обработки, и при переполнении пула объекты могут
+быть переданы на другие узлы кластера без явного указания в исходном коде
+программы.
+
+Вычислительные объекты реализованы в виде замыканий (функторов) ---
+объектов-функций, которые сохраняют в себе аргументы, ссылку на породивший их
+объект и данные из предметной области задачи. Данные обрабатываются либо при
+выполнении объекта, либо для параллельной обработки создаются дочерние объекты.
+Когда обработка завершена, родительский объект вызывается с дочерним объектов в
+качестве аргумента для сбора результатов обработки.
+
+**** Выход из строя одного узла.
+Наиболее распространенная стратегия при выходе из строя подчиненного узла ---
+перезапуск выполнявшихся на нем объектов на рабочих узлах. Этой стратегии
+следует язык Erlang для перезапуска подчиненных
+процессов cite:armstrong2003thesis. Для того что реализовать этот метод в
+рамках иерархии вычислительных объектов необходимо сохранять каждый объект
+передаваемый на другие узлы кластера. В случае отказа одного из узлов, на
+которые были переданы объекты, соответствующие их копии извлекаются из очереди
+на перераспределяются между оставшимися узлами без какой-либо дополнительной
+обработки. Если больше узлов не осталось, то объекты перенаправляются в
+локальную очередь. В отличие от "тяжеловесного" метода контрольных точек
+восстановления, древовидная иерархия узлов в паре с иерархией объектов позволяет
+автоматически продолжить выполнение программы при выходе из строя одного из
+узлов без перезапуска каких-либо процессов задачи.
+
+Возможная стратегия при выходе из строя узла, на котором хранится главный
+вычислительный объект задачи, заключается в копировании этого объекта на
+резервный узел и синхронизировать любые изменения между двумя копиями объекта
+посредством распределенных транзакций. Однако, эта стратегия не соотносится с
+асинхронностью вычислительных ядер и слишком сложна в реализации. На практике,
+оказывается, что главный объект программы обычно не создает больше одного
+дочернего объекта, каждый из которых представляет собой последовательный шаг
+вычислений (внутри которого может быть, а может не быть параллельных этапов).
+Поскольку шаги последовательны, то одновременно может существовать не более
+одного дочернего объекта, что позволяет упростить синхронизацию состояния
+главного объекта программы. Для этого главный объект передается на подчиненный
+узел вместе со своим дочерним объектом. Тогда при выходе из строя узла, на
+котором была запущена программа, резервный узел автоматически восстанавливает
+состояние главного объекта из копии, когда дочерний объект завершает свою
+работу.
+
+Описанный выше подход предназначен только для объектов, у которых нет
+объекта-родителя и которые создают по одному дочернему объекту за раз. Это
+означает, что метод работает как контрольная точка восстановления, которая
+сохраняет состояние только между последовательными шагами вычислений (когда оно
+занимает минимальный объем памяти) и которая для сохранения состояния
+использует оперативную память другого узла кластера, а не диск.
+
**** Обеспечение высокой доступности.
+**** Программная реализация.
+Из соображений эффективности методы обеспечения отказоустойчивости были
+реализованы во фреймворке на языке C++: с точки зрения автора язык C слишком
+низкоуровневый для написания распределенных программ, а использование языка
+Java влечет за собой накладные расходы, и не популярно в высокопроизводительных
+вычислениях. Для того чтобы использовать фреймворка без планировщика задач
+необходимо создать сервис, который бы автоматически обновлял состояние
+древовидной иерархии узлов и предоставлял программный интерфейс для запуска
+задач на ней. На данный момент фреймворк запускает сервис и приложение в одном
+процессе. Фреймворк называется "Фабрика" и находится на этапе проверки
+концепции.
+
+**** Результаты тестирования.
+Методы отказоустойчивости были протестированы на физическом кластере
+(см. [[tab:cluster]]) на примере программы, генерирующей взволнованную
+морскую поверхность, подробно описанной
+в cite:autoreg-stab,autoreg2011csit,autoreg1,autoreg2 и в данной работе.
+Программа состоит из серии фильтров, каждый из которых применяется к результату
+работы предыдущего. Некоторые из фильтров применяются параллельно, так что вся
+программа состоит из последовательно выполняющихся больших шагов, некоторые из
+которых внутри реализованы параллельно из соображений эффективности. Только
+наиболее ресурсоемкий этап программы (генерация взволнованной морской
+поверхности) выполняется параллельно на всех узлах, другие этапы выполняются
+параллельно на всех процессорных ядрах главного узла.
+
+#+name: tab:cluster
+#+caption: Конфигурация кластера.
+| CPU | Intel Xeon E5440, 2.83GHz |
+| RAM | 4Gb |
+| HDD | ST3250310NS, 7200rpm |
+| Кол-во узлов | 12 |
+| Кол-во ядер на узел | 8 |
+
+Программа была переписана под новую версию фреймворка, что потребовало лишь
+небольших изменений исходного кода для корректной обработки выхода из строя
+узла с главным объектом: главный объект был помечен, чтобы фреймворк смог
+передать его на подчиненный узел. Другие изменения исходного кода были связаны
+с изменением программного интерфейса фреймворка. Таким образом, обеспечение
+отказоустойчивости, в основном, прозрачно для программиста и требует лишь
+маркировки главного объекта для его репликации на резервный узел.
+
+В ряде экспериментов производительность новой версии программы была измерена
+при выходе из строя различных типов узлов во время выполнения программы (номера
+пунктов соответствуют номерам графиков [[fig:benchmark]]):
+- без выхода из строя узлов,
+- выход из строя подчиненного узла (на котором генерируется часть взволнованной
+ поверхности),
+- выход из строя главного узла (на котором запускается программа),
+- выход из строя резервного узла (на который копируется главный объект
+ программы).
+Древовидная иерархия узлов со значением ветвления равного 64 использовалась в
+экспериментах, для того чтобы удостовериться, что все подчиненные узлы соединены
+с первым узлом подсети кластера. При каждом запуске программы главный объект
+запускался не на главном узле, чтобы оптимально отобразить иерархию объектов на
+иерархию узлов (наложить одну на другую). Узел-жертва выводился из строя по
+прошествии фиксированного временного интервала после запуска программы равного
+примерно $1/3$ времени работы программы на одном узле. Способ запуска для
+каждого эксперимента представлен в [[tab:benchmark]] ("корень" и "лист" относятся к
+положению узла в древовидной иерархии). Результаты экспериментов приведены на
+[[fig:benchmark]] и [[fig:slowdown]].
+
+Графики 2 и 3 на [[fig:benchmark]] показывают, что производительность в
+случае выхода из строя главного и подчиненного узлов примерно одинакова. В
+случае отказа главного узла резервный узел сохраняет копию главного объекта и
+восстанавливает главный объект из нее, когда не обнаруживает, что главный узел
+вышел из строя. В случае отказа подчиненного узла, главный узел
+перераспределяет невернувшиеся объекты между оставшимися подчиненными узлами. В
+обоих случая состояние главного объекта программы не теряется, а значит не
+тратится время на его восстановление, что объясняет схожую производительность.
+
+График 4 на [[fig:benchmark]] показывает, что производительность в случае
+выхода из строя резервного узла гораздо ниже, чем в других случаях. Это
+происходит, потому что главный узел сохраняет состояние только текущего
+последовательного этапа программы, в то время как резервный узел не только
+хранит копию этого состояния, но и выполняет параллельные части этапа вместе с
+другими подчиненными узлами. Так что, когда резервный узел выходит из строя,
+главный узел начинает выполнение текущего этапа с самого начала.
+
+#+caption: Параметры экспериментов.
+#+name: tab:benchmark
+| Номер эксп. | Главный узел | Узел-жертва | Время до выхода из строя, сек. |
+| 1 | корень | | |
+| 2 | корень | лист | 10 |
+| 3 | корень | лист | 10 |
+| 4 | корень | лист | 10 |
+
+Для оценки количества времени, которое теряется при выходе из строя одного из
+узлов, можно поделить общее время работы программы со сбоем на время работы
+программы без сбоев, но с количеством узлов минус один. Это отношение
+представлено на [[fig:slowdown]]. Разница в производительности в случае
+выхода из строя главного узла и подчиненного узла находится в пределах 5\%, а в
+случае выхода из строя резервного узла --- в пределах 50\% для количества узлов
+меньше 6\footnote{Измерение разницы для большего количества узлов не имеет
+смысла, поскольку программа завершается еще до наступления сбоя.}. Разница в
+50\% больше, чем $1/3$ времени работы программы, после которого происходит
+сбой, однако отказ резервного узла требует некоторого времени, чтобы быть
+обнаруженным другими узлами. Сбой узла обнаруживается только тогда, когда
+подчиненный объект завершает свое выполнение и пытается вернуться на исходный
+узел к родителю. Мгновенное обнаружение сбоя узла требует остановки выполнения
+объектов, что может быть неприменимо для программ со сложной логикой.
+
+#+name: fig:benchmark
+#+begin_src R
+# TODO
+#+end_src
+
+#+caption: Производительность программы генерации взволнованной морской поверхности при различных типах сбоев узлов.
+#+RESULTS: fig:benchmark
+
+Результаты экспериментов позволяют сделать вывод о том, что /не важно,
+вышел ли из строя главный узел или подчиненный, итоговое время работы программы
+будет примерно равно времени ее работы без сбоев, но с уменьшенным на единицу
+количеством узлов/, однако, в случае выхода из строя резервного узла теряется
+гораздо больше времени.
+
+#+name: fig:slowdown
+#+begin_src R
+# TODO
+#+end_src
+
+#+caption: Замедление программы генерации взволнованной морской поверхности при различных типах сбоев по сравнению с запуском без сбоев но с уменьшенным на единицу количеством узлов.
+#+RESULTS: fig:slowdown
+
+**** Выводы по результатам тестирования.
+Проведенные эксперименты показывают, что параллельной программе необходимо
+иметь несколько последовательных этапов выполнения, чтобы сделать ее устойчивой
+к сбоям узлов. Несмотря на то что вероятность сбоя резервного узла меньше
+вероятности сбоя одного из подчиненных узлов, это не повод потерять все данные,
+когда выполнявшаяся несколько дней задача почти завершилась. В общем случае,
+чем больше последовательных этапов вычислений содержит программа, тем меньше
+времени потеряется в случае сбоя резервного узла, и, аналогично, чем больше
+параллельных частей содержит каждый этап, тем меньше времени потеряется при
+сбое главного или подчиненного узла. Другими словами, /чем больше
+количество узлов, на которое масштабируется программа, тем она более устойчива
+к сбою оборудования/.
+
+В проведенных экспериментах узел, на котором запускается программа, выбирается
+вручную, чтобы совместить иерархию объектов и иерархию узлов, однако, такой
+подход не применим в реальных системах. Разработанный фреймворк должен делать
+это автоматически и эффективно распределять нагрузку между подчиненными узлами
+в независимости от местоположения главного узла в иерархии: выделение одного и
+того же узла в качестве главного для запуска нескольких приложений уменьшает
+общую отказоустойчивость системы.
+
+Хотя это неочевидно из экспериментов, Фабрика не только обеспечивает
+отказоустойчивость, но и позволяет автоматически вводить новые узлы в кластер и
+распределять на них часть нагрузки уже запущенных программ. В контексте
+фреймворка этот процесс тривиален, поскольку не требует перезапуска
+незавершившихся объектов и копирования их состояния, и не изучался
+экспериментально в данной работе.
+
+Теоретически отказоустойчивость, основанная на иерархии может быть реализована
+поверх библиотеки передачи сообщений без потери общности. Хотя использование
+незагруженных узлов заместо вышедших из строя в рамках такой библиотеки
+представляет определенную сложность, поскольку количество узлов, на которых
+запущена программа фиксировано, но выделение достаточно большого количества
+узлов для программы будет достаточно для обеспечения отказоустойчивости.
+
+Слабым местом описанных методов является период времени, начиная с отказа
+главного узла и заканчивая обнаружением сбоя подчиненным узлом. Если до момента
+восстановления главного объекта из копии резервный узел выходит из строя, то
+состояние выполнения программы полностью теряется без возможности его
+восстановить, кроме как перезапуском с самого начала. Длина этого опасного
+промежутка времени может быть уменьшена, но исключить его полностью невозможно.
+Этот результат согласуется с исследованиями теории "невыполнимости" в рамках
+которой доказывается невозможность распределенного консенсуса с хотя бы одним
+процессом, дающим сбой cite:fischer1985impossibility и невозможность надежной
+передачи данных в случае сбоя одного из узлов cite:fekete1993impossibility.
+
* Заключение
**** Итоги исследования.
В изучении возможностей математического аппарата для имитационного моделирования
