commit 5df34bdd2e92584a5c3ed37b92683ae34f61c221
parent 82f397807661795fe1abcee3ad99e3a6bcf3b1bd
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 3 Nov 2017 11:54:55 +0300
Edit fail over section.
Diffstat:
2 files changed, 43 insertions(+), 105 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -3279,6 +3279,7 @@ IP-адреса: замена отображения IP-адресов на чт
кластера, а параллельная программа состоит из управляющих объектов, использующих
иерархию узлов для динамического распределения нагрузки и свою собственную
иерархию для перезапуска управляющих объектов в случае сбоя узла.
+
**** Динамическое распределение ролей.
Отказоуйстовчисть параллельной программы\nbsp{}--- это одна из проблем, которая
должна решаться планировщиком задач обработки больших данных или
@@ -3319,20 +3320,21 @@ IP-адреса: замена отображения IP-адресов на чт
Многие распределенные хранилища типа "ключ-значение" и параллельные файловые
системы имеют симметричную архитектуру, в которой роли руководителя и
подчиненного распределяются динамически, так что любой узел может выступать в
-роли руководитля, если текущий руководящий узел выходит из строя, однако, такая
-архитектура до сих пор не используется в планировщиках задач обработки больших
-данных и высокопроизводительных вычислений. Например, в планировщике задач
-обработки больших данных YARN, роли руководителя и подчиненного являются
-статическими. Восстановление после сбоя подчиненного узла осуществляется путем
-перезапуска работавшей на нем части задачи на одном из выживших узлов, а
-восстановление после сбоя руководящего узла осуществляется путем установки
-резервного руководящего узла\nbsp{}cite:murthy2011architecture. Оба руководящих
-узла управляются сервисом Zookeeper, который использует динамическое
-распределение ролей для обеспечения своей
-отказоустойчивости\nbsp{}cite:okorafor2012zookeeper. Таким образом, отсутствие
-динамического распределения ролей у планировщика YARN усложняет конфигурацию
-всего кластера: если бы динамические роли были доступны, Zookeeper был бы лишним
-в данной конфигурации.
+роли руководитля, если текущий руководящий узел выходит из
+строя\nbsp{}cite:ostrovsky2015couchbase,divya2013elasticsearch,boyer2012glusterfs,anderson2010couchdb,lakshman2010cassandra.
+Однако, такая архитектура до сих пор не используется в планировщиках задач
+обработки больших данных и высокопроизводительных вычислений. Например, в
+планировщике задач обработки больших данных YARN\nbsp{}cite:vavilapalli2013yarn,
+роли руководителя и подчиненного являются статическими. Восстановление после
+сбоя подчиненного узла осуществляется путем перезапуска работавшей на нем части
+задачи на одном из выживших узлов, а восстановление после сбоя руководящего узла
+осуществляется путем установки резервного руководящего
+узла\nbsp{}cite:murthy2011architecture. Оба руководящих узла управляются
+сервисом Zookeeper, который использует динамическое распределение ролей для
+обеспечения своей отказоустойчивости\nbsp{}cite:okorafor2012zookeeper. Таким
+образом, отсутствие динамического распределения ролей у планировщика YARN
+усложняет конфигурацию всего кластера: если бы динамические роли были доступны,
+Zookeeper был бы лишним в данной конфигурации.
Такая же проблема возникает в планировщиках задач для высокопроизводительных
вычислений, руководящий узел (на котором запущен главный процесс планировщика
@@ -3346,13 +3348,13 @@ IP-адреса: замена отображения IP-адресов на чт
Наконец, наиболее простой вариант высокой доступности руководящего узла
реализован в протоколе VRRP (Virtual Router Redundancy
-Protocol)\nbsp{}cite:knight1998rfc2338,hinden2004virtual,nadas2010rfc5798.
-Несмотря на то что протокол VRRP предоставляет динамическое распределение ролей,
-он не может быть использован в планировщиках задач, поскольку спроектирован для
-маршрутизаторов, за которыми стоят реверс прокси серверы. В таких серверах
-отсутствует состояние (очередь задач), которое необходимо восстановить после
-выхода из строя узла, поэтому их высокую доступность обеспечить проще. Это может
-быть реализовано даже без маршрутизаторов, используя вместо этого сервис
+Protocol)\nbsp{}cite:rfc2338,rfc3768,rfc5798. Несмотря на то что протокол VRRP
+предоставляет динамическое распределение ролей, он не может быть использован в
+планировщиках задач, поскольку спроектирован для маршрутизаторов, за которыми
+стоят реверс прокси серверы. В таких серверах отсутствует состояние (очередь
+задач), которое необходимо восстановить после выхода из строя узла, поэтому их
+высокую доступность обеспечить проще. Это может быть реализовано даже без
+маршрутизаторов, используя вместо этого сервис
Keepalived\nbsp{}cite:cassen2002keepalived.
Симметричная архитектура выгодна для планировщиков задач, поскольку позволяет
@@ -3383,72 +3385,17 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
соответствие между сервисами и узлами кластера, в данной работе они используются
как взаимозаменяемые термины.
-**** Иерархия управляющих объектов.
-Для распределения нагрузки узлы кластера объединяются в древовидную иерархию
-(см.\nbsp{}раздел [[#sec-node-discovery]]), и нагрузка распределяется между
-непосредственными соседями узла, так что при запуске управляющего объекта на
-подчиненном узле главный узел также получают часть его подчиненных объектов. Это
-делает систему симметричной и легкой в обслуживании: на каждом узле установлен
-один и тот же набор программного обеспечения, что позволяет заменить один узел
-другим при выходе из строя первого. Похожее архитектурное решение используется в
-хранилищах типа ключ-значение\nbsp{}cite:anderson2010couchdb,lakshman2010cassandra для
-обеспечения отказоустойчивости, однако автору неизвестны планировщики задач,
-которые используют данный подход.
-
-В отличие от функции ~main~ в программах на основе библиотеки передачи
-сообщений, первый (главный) управляющий объект выполняется только на одном узле,
-а дополнительные узлы используются по необходимости. Такое решение позволяет
-использовать произвольное количество узлов для запуска задачи и динамически
-менять это количество во время ее выполнения. Похожее решение используется в
-системах обработки больших объемов
-данных\nbsp{}cite:dean2008mapreduce,vavilapalli2013yarn \nbsp{}--- пользователь,
-запускающий задачу на кластере, не указывает количество узлов, фактические
-узлы\nbsp{}--- это узлы, на которых расположены входные файлы.
-
-С математической точки зрения управляющий объект \(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\)
-используется для остановки рекурсии, и передается в качестве аргумента главному
-управляющему объекту программы. Аргумент управляющего объекта интерпретируется
-следующим образом.
-- Если объект является только что созданным объектом, то аргумент\nbsp{}--- это его
- родительский объект.
-- В остальных случаях аргументом может являться любой объект (чаще всего
- дочерний по отношению к текущему).
-
-Объекты обрабатываются в цикле, который начинается с выполнением главного
-объекта, затем внутри главного объекта создаются и асинхронно выполняются другие
-объекты. Цикл продолжается до тех пор пока какой-либо объекта не вернет
-\(\mathbb{O}\). Поскольку вызов функции может породить сразу несколько объектов,
-они выполняются параллельно, что приводит к быстрому заполнению пула объектов.
-Поскольку объекты из пула могут выполняться в произвольном порядке, несколько
-потоков одновременно выбирают объекты для обработки, и при переполнении
-пула объекты могут быть переданы на другие узлы кластера без явного указания в
-исходном коде программы.
-
-Вычислительные объекты реализованы в виде замыканий (функторы в C++)\nbsp{}---
-объектов-функций, которые сохраняют в себе аргументы, ссылку на породивший их
-объект и данные из предметной области задачи. Данные обрабатываются либо при
-выполнении объекта, либо для параллельной обработки создаются подчиненные
-объекты. Когда обработка завершена, родительский объект вызывается с дочерним
-объектом в качестве аргумента для сбора результатов обработки.
-
**** Обработка выхода узлов из строя.
-Наиболее распространенная стратегия при выходе из строя подчиненного узла
-является перезапуск выполнявшихся на нем объектов на рабочих узлах\nbsp{}---
-стратегия, которой следует язык Erlang при перезапуске подчиненных процессов\nbsp{}cite:armstrong2003thesis. Для того что реализовать этот метод в рамках иерархии
-управляющих объектов, узел-отправитель сохраняет каждый объект, передаваемый на
-другие узлы кластера, и в случае отказа произвольного количества узлов, на
-которые были переданы объекты, их копии перераспределяются между оставшимися
-узлами без индивидуальной обработки программистом. Если больше не осталось
-узлов, на которые можно отправить объекты, то они выполняются локально. В
-отличие от "тяжеловесного" метода контрольных точек восстановления,
+Основной стратегией при выходе из строя подчиненного узла является перезапуск
+выполнявшихся на нем объектов на рабочих узлах\nbsp{}--- стратегия, которой
+следует язык Erlang при перезапуске подчиненных
+процессов\nbsp{}cite:armstrong2003thesis. Для того что реализовать этот метод в
+рамках иерархии управляющих объектов, узел-отправитель сохраняет каждый объект,
+передаваемый на другие узлы кластера, и в случае отказа произвольного количества
+узлов, на которые были переданы объекты, их копии перераспределяются между
+оставшимися узлами без индивидуальной обработки программистом. Если больше не
+осталось узлов, на которые можно отправить объекты, то они выполняются локально.
+В отличие от "тяжеловесного" метода контрольных точек восстановления,
используемого планировщиками задач HPC кластеров, древовидная иерархия узлов в
паре с иерархией объектов позволяет автоматически продолжить выполнение
программы при выходе из строя произвольного количества подчиненных узлов без
@@ -3540,24 +3487,15 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
**** Результаты тестирования.
Методы отказоустойчивости были протестированы на физическом кластере
-(см.\nbsp{}табл.\nbsp{}[[tab-cluster]]) на примере программы, генерирующей
-взволнованную морскую поверхность, подробно описанной в разделе
-[[#sec:arma-algorithms]]. Программа состоит из серии фильтров, каждый из которых
-применяется к результату работы предыдущего. Некоторые из фильтров вычисляются
-параллельно, так что вся программа состоит из последовательно выполняющихся
-шагов, некоторые из которых внутри реализованы параллельно из соображений
-эффективности. Только наиболее ресурсоемкий этап программы (генерация
-взволнованной морской поверхности) выполняется параллельно на всех узлах, другие
-этапы выполняются параллельно на всех процессорных ядрах главного узла.
-
-#+name: tab-cluster
-#+caption: Конфигурация кластера, на котором проводились эксперименты.
-#+attr_latex: :booktabs t
-| CPU | Intel Xeon E5440, 2.83GHz |
-| RAM | 4Gb |
-| HDD | ST3250310NS, 7200rpm |
-| Кол-во узлов | 12 |
-| Кол-во ядер на узел | 8 |
+(см.\nbsp{}табл.\nbsp{}[[tab-ant]]) на примере программы, генерирующей взволнованную
+морскую поверхность, подробно описанной в разделе [[#sec:arma-mpp]]. Программа
+состоит из серии фильтров, каждый из которых применяется к результату работы
+предыдущего. Некоторые из фильтров вычисляются параллельно, так что вся
+программа состоит из последовательно выполняющихся шагов, некоторые из которых
+внутри реализованы параллельно из соображений эффективности. Только наиболее
+ресурсоемкий этап программы (генерация взволнованной морской поверхности)
+выполняется параллельно на всех узлах, другие этапы выполняются параллельно на
+всех процессорных ядрах главного узла.
Программа была переписана под отказоустойчивую версию фреймворка, что
потребовало лишь небольших изменений исходного кода для корректной обработки
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3126,7 +3126,7 @@ architecture, in which principal and subordinate roles are dynamically
distributed, so that any node can act as a principal when the current principal
node
fails\nbsp{}cite:ostrovsky2015couchbase,divya2013elasticsearch,boyer2012glusterfs,anderson2010couchdb,lakshman2010cassandra.
-however, this architecture is still not used in big data and HPC job schedulers.
+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
