commit acb2cb56dea0b04c60b011ee8faae5d4e9a1f8a3
parent c290b82246a08e504c1fd90f62518dc0ef25f39e
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Wed, 8 Nov 2017 11:55:12 +0300
Edit node discovery.
Diffstat:
| arma-thesis-ru.org | | | 219 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
| arma-thesis.org | | | 157 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
2 files changed, 191 insertions(+), 185 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -2353,6 +2353,10 @@ OpenGL увеличивает производительность путем и
отправить сетевой пакет между любой парой узлов кластера.
**** Уровень резидентных процессов.
+:PROPERTIES:
+:CUSTOM_ID: sec-daemon-layer
+:END:
+
Состоит из процессов, запущенных на узлах кластера и иерархических логических
связей (главный/подчиненный) между ними. На каждом узле запущен ровно один
процесс, поэтому эти понятия взаимозаменяемы в данной работе. Роль главного и
@@ -2852,14 +2856,14 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
природы шагов программы. Эта модель является основой модели отказоустойчивости,
которая будет описана далее.
-*** Алгоритм обнаружения узлов кластера
+*** Обнаружение узлов кластера
:PROPERTIES:
:CUSTOM_ID: sec-node-discovery
:END:
**** Алгоритмы выбора лидера.
Многие системы пакетной обработки задач построены по принципу /субординации/: в
-каждом кластере выбирается руководящий узел, который управляет очередью задач,
+каждом кластере выбирается главный узел, который управляет очередью задач,
планирует их запуск на подчиненных узлах и следит за их состоянием. Роль
главного узла назначается либо /статически/ системным администратором
определенному физическому узлу, либо /динамически/, путем периодического
@@ -2872,32 +2876,32 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
поскольку не требует наличия простаивающих резервных узлов на случай отказа
главного
узла\nbsp{}cite:hunt2010zookeeper,lakshman2010cassandra,divya2013elasticsearch и
-в общем случае приводит к симметричной архитектуре системе, в которой один и тот
+в общем случае приводит к симметричной архитектуре системы, в которой один и тот
же стек программного обеспечения с одними и теми же настройками установлен на
каждом узле кластера\nbsp{}cite:boyer2012glusterfs,ostrovsky2015couchbase.
Алгоритмы выбора лидера (которые иногда называют алгоритмами /распределенного
консенсуса/) являются частными случаями волновых алгоритмов.
-В\nbsp{}cite:tel2000introduction Тель определяет их как алгоритмы, в которых
+В\nbsp{}cite:tel2000introduction автор определяет их как алгоритмы, в которых
событие завершения программы предваряется хотя бы одним каким-либо другим
событием, происходящем в /каждом/ параллельном процессе. Волновые алгоритмы не
-определены для анонимных сетей, т.е. они работают только с теми параллельными
-процессами, которые могут себя уникально идентифицировать. Однако, количество
-процессов, которых затрагивает "волна", может быть определено по мере выполнения
-алгоритма. В рамках распределенных систем это означает, что волновые алгоритмы
-подходят для вычислительных кластеров с динамически меняющимся количеством
-узлов, так что включение и выключение отдельных узлов не влияет на работу
-алгоритма.
+определены для анонимных сетей, т.е.\nbsp{}они работают только с теми
+параллельными процессами, которые могут себя уникально идентифицировать. Однако,
+количество процессов, которые затрагивает "волна", может быть определено по мере
+выполнения алгоритма. В рамках распределенных систем это означает, что волновые
+алгоритмы подходят для вычислительных кластеров с динамически меняющимся
+количеством узлов, так что включение и выключение отдельных узлов не влияет на
+работу алгоритма.
Подход к поиску узлов кластера не использует волновые алгоритмы, а значит не
требует опроса всех узлов кластера для выбора лидера. Вместо этого каждый узел
кластера нумерует все узлы подсети, в которой он находится, и преобразует список
-в /древовидную иерархию/ с заданным максимальным значением ветвления
-(максимальным количеством подчиненных вершин). Затем узел определяет свой
-уровень иерархии и пытается соединиться с вышестоящими узлами, чтобы стать их
-подчиненным. Сначала он проверяет близко расположенные к нему узлы, а потом все
-остальные узлы вплоть до вершины иерархии. Если вышестоящих узлов нет или с ними
-невозможно соединиться, то узел сам становится главой всей иерархии.
+в /древовидную иерархию/ с заданным значением /ветвления/ (максимальным
+количеством подчиненных вершин, которых может иметь узел). Затем узел определяет
+свой уровень иерархии и пытается соединиться с вышестоящими узлами, чтобы стать
+их подчиненным. Сначала он проверяет близко расположенные к нему узлы, а потом
+все остальные узлы вплоть до вершины иерархии. Если вышестоящих узлов нет или с
+ними невозможно соединиться, то узел сам становится главой всей иерархии.
Древовидная иерархия узлов подсети определяет отношение строгого порядка на
множестве всех узлов кластера. Несмотря на то что с технической точки зрения
@@ -2909,7 +2913,7 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
для распределения нагрузки. Простейшей такой функцией является позиция IP-адреса
узла в диапазоне всех IP-адресов подсети.
-**** Алгоритм обхода древовидной иерархии.
+**** Алгоритм создания древовидной иерархии.
Отношение строго порядка на множестве \(\mathcal{N}\) узлов одной подсети
определяется как
\begin{equation*}
@@ -2917,23 +2921,24 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
\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\)\nbsp{}--- отображение узла на его ранг, а \(<\)\nbsp{}--- оператор, определяющий
-отношение строго порядка на множестве \(\mathcal{R}^n\). Функция \(f\) присваивает
-узлу порядковый номер, а оператор \(<\) делает этот номер уникальным.
+где \(f\)\nbsp{}--- отображение узла на его ранг, а \(<\)\nbsp{}--- оператор,
+определяющий отношение строго порядка на множестве \(\mathcal{R}^n\). Функция
+\(f\) присваивает узлу порядковый номер, а оператор \(<\) делает этот номер
+уникальным.
Простейшее отображение \(f\) ставит в соответствие каждому узлу подсети позицию
-его IP-адреса в диапазоне всех адресов подсети. Без преобразования к древовидной
-иерархии (когда в подсети выбирается только один лидер) рабочий узел, адрес
-которого занимает наименьшую позицию в диапазоне, становится руководящим. Если
-адрес узла занимает первую позицию в диапазоне, то для него невозможно выбрать
-лидера, и он будет находится на вершине иерархии вплоть до выхода из строя.
-Несмотря на то что идентификацию узлов на основе их IP-адресов легко реализовать
-в программе, такой подход устанавливает искусственную зависимость роли
-руководителя от IP-адреса узла. Тем не менее, этот подход полезен для первичного
-объединения узлов в кластер, когда более сложные отображения неприменимы.
+его IP-адреса в диапазоне всех адресов подсети. Без использования древовидной
+иерархии (когда в подсети выбирается только один лидер) узел, адрес которого
+занимает наименьшую позицию в диапазоне, становится главным. Если адрес узла
+занимает первую позицию в диапазоне, то для него невозможно выбрать лидера, и он
+будет находится на вершине иерархии вплоть до выхода из строя. Несмотря на то
+что идентификацию узлов на основе их IP-адресов легко реализовать в программе,
+такой подход устанавливает искусственную зависимость роли главного узла от
+IP-адреса узла. Тем не менее, этот подход полезен для первичного объединения
+узлов в кластер, когда более сложные отображения неприменимы.
Для того чтобы алгоритм обнаружения масштабировался на большое количество узлов,
-диапазона IP адресов подсети отображается на древовидную иерархию. В такой
+диапазон IP адресов подсети отображается на древовидную иерархию. В такой
иерархии каждый узел определяется уровнем \(l\) иерархии, на котором он
находится, и отступом \(o\), который равен порядковому номеру узла на его
уровне. Значения уровня и отступа определяются из следующей задачи оптимизации.
@@ -2944,11 +2949,11 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
l \geq 0, \quad
o \geq 0
\end{equation*}
-где \(n\)\nbsp{}--- позиция IP-адреса узла в диапазоне IP-адресов подсети и \(p\)\nbsp{}---
-значение ветвления (максимальное количество подчиненных, которых может иметь
-узел). Руководитель узла на уровне \(l\) с отступом \(o\) имеет уровень \(l-1\) и
-отступ \(\lfloor{o/p}\rfloor\). Расстояние между любыми двумя узлами в иерархии,
-адреса которых занимают позиции \(i\) и \(j\) в диапазоне определяется как
+где \(n\)\nbsp{}--- позиция IP-адреса узла в диапазоне IP-адресов подсети и
+\(p\)\nbsp{}--- значение ветвления. Главный узел для узла на уровне \(l\) с
+отступом \(o\) имеет уровень \(l-1\) и отступ \(\lfloor{o/p}\rfloor\).
+Расстояние между любыми двумя узлами в иерархии, адреса которых занимают позиции
+\(i\) и \(j\) в диапазоне определяется как
\begin{align*}
& \langle
\text{lsub}(l(j), l(i)), \quad
@@ -2963,9 +2968,9 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
Расстояние является составным, чтобы уровень иерархии учитывался в первую
очередь.
-Для выбора руководителя каждый узел ранжирует все узлы подсети в соответствии с
-их позицией \(\langle{l(n),o(n)}\rangle\) и, используя формулу для определения
-расстояния, выбирает ближайший к потенциальному руководителю узел, имеющий
+Для выбора главного каждый узел ранжирует все узлы подсети в соответствии с их
+позицией \(\langle{l(n),o(n)}\rangle\) и, используя формулу для определения
+расстояния, выбирает ближайший к потенциальному главному узлу узел, имеющий
наименьший ранг. Это позволяет пропустить IP-адреса выключенных узлов, однако,
для разреженных сетей (в которых узлы занимают непоследовательные IP-адреса)
сбалансированность дерева не гарантируется.
@@ -2977,7 +2982,7 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
поскольку не нужно хранить ранжированный список всех узлов, вместо этого он
перебирает все IP-адреса сети в порядке, определяемом значением ветвления.
Алгоритм работает следующим образом. Сначала базовый узел (узел, который ищет
-руководителя) вычисляет адрес своего потенциального руководителя и пытается
+главного) вычисляет адрес своего потенциального главного узла и пытается
установить соединение с ним. Если соединение не удается, базовый узел
последовательно пытается соединиться с каждым узлом, находящимся на более
высоком уровне иерархии, пока не достигнет вершины иерархии (корня дерева). Если
@@ -3039,9 +3044,9 @@ digraph {
физическому ядру, чтобы уменьшить накладные расходы на миграцию процессов между
ядрами. Алгоритм обхода древовидной иерархии имеет низкие требования к
процессорному времени и пропускной способности сети, поэтому запуск нескольких
-процессов на одном физическом ядре целесообразно, в отличие от кодов
-высокопроизводительных приложений, в которых это часто ведет к низкой
-производительности. Конфигурация тестовой системы показана в
+процессов на одном физическом ядре целесообразен, в отличие от кодов
+высокопроизводительных приложений, в которых это часто снижает
+производительность. Конфигурация тестовой системы показана в
табл.\nbsp{}[[tab-ant]].
#+name: tab-ant
@@ -3056,13 +3061,13 @@ digraph {
Похожий подход используется
в\nbsp{}cite:lantz2010network,handigol2012reproducible,heller2013reproducible,
где авторы воспроизводят разнообразные практические эксперименты на виртуальных
-кластерах и сопоставляют результаты с физическими. Преимущество данного подхода
-заключается в возможности проведения экспериментов на больших виртуальных
-кластерах, используя сравнительно небольшое количество физических узлов.
-Преимущество подхода, используемого в данной работе, в котором не применяются
-пространства имен Linux, заключается в том, что он более легковесный и большее
-количество резидентных процессов можно протестировать на одном и том же
-физическом кластере.
+кластерах, созданных на основе пространств имен Linux, и сопоставляют результаты
+с физическими. Преимущество данного подхода заключается в возможности проведения
+экспериментов на больших виртуальных кластерах, используя сравнительно небольшое
+количество физических узлов. Преимущество подхода, используемого в данной
+работе, в котором не применяются пространства имен Linux, заключается в том, что
+он более легковесный и большее количество резидентных процессов можно
+протестировать на одном и том же физическом кластере.
Производительность обнаружения узлов была протестирована путем измерения
времени, которое необходимо для того чтобы все узлы кластера нашли друг друга,
@@ -3075,7 +3080,7 @@ digraph {
подчиненных, а иерархия не меняется произвольным образом в результате разного
времени запуска процессов. Эта искусственная задержка впоследствии была вычтена
из результатов тестирования. Таким образом, результаты теста представляют собой
-время обнаружения узлов в "идеальном" кластере, к котором каждый резидентный
+время обнаружения узлов в "идеальном" кластере, в котором каждый резидентный
процесс находит главного с первой попытки.
Тест запускался несколько раз, варьируя количество резидентных процессов на
@@ -3083,10 +3088,10 @@ digraph {
узлов по 64 процесса на узел) друг друга занимает не более двух секунд
(рис.\nbsp{}[[fig-discovery-benchmark]]). Это значение меняется незначительно с
увеличением количества физических узлов. Использование более 8 узлов по 64
-процесса на узел приводит к большой колебаниям времени обнаружения, ввиду того
-что большое количества процессов одновременно устанавливает соединение с одним
-и тем же главным процессов (значение ветвления во всех тестах равнялось 10000),
-поэтому эти результаты были исключены.
+процесса на узел приводит к большим колебаниям времени обнаружения, ввиду того
+что большое количество процессов одновременно устанавливает соединение с одним и
+тем же главным процессом (значение ветвления во всех тестах равнялось 10000),
+поэтому эти результаты были исключены из рассмотрения.
#+name: fig-discovery-benchmark
#+header: :width 7 :height 5
@@ -3104,44 +3109,42 @@ bscheduler.plot_discovery(
[[file:build/discovery-benchmark-ru.pdf]]
**** Обсуждение.
-Поскольку узлу для выбора руководителя нужно соединиться с узлом, адрес которого
+Поскольку узлу для выбора главного нужно соединиться с узлом, адрес которого
известен заранее, то обнаружение узлов масштабируется на большое количество
узлов. Соединение с другими узлами происходит только в том случае, если текущий
-узел-руководитель выходит из строя. Таким образом, если адреса узлов кластера
+главный узел выходит из строя. Таким образом, если адреса узлов кластера
расположены непрерывно в диапазоне адресов подсети, каждый узел устанавливает
-соединение только со своим руководителем, и неэффективного сканирования всей
+соединение только со своим главным узлом, и неэффективного сканирования всей
сети каждым узлом не происходит.
Следующие ключевые особенности отличают предложенный подход от некоторых
-существующих
-подходов\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
-- *Многоуровневая иерархия.* Количество руководящих узлов в сети зависит от
- значения ветвления. Если оно меньше количества IP-адресов в подсети, то в
- кластере будет несколько руководящих узлов. Если оно больше или равно
- количеству IP-адресов в подсети, то в кластере будет только один руководящий
- узел. Когда какой-либо узел выходит из строя, многоуровневая иерархия
- изменятся локально, только узлы, примыкающие к вышедшему из строя,
- взаимодействуют друг с другом.
+существующих\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
+- *Многоуровневая иерархия.* Количество главных узлов в сети зависит от значения
+ ветвления. Если оно меньше количества IP-адресов в подсети, то в кластере
+ будет несколько главных узлов. Если оно больше или равно количеству IP-адресов
+ в подсети, то в кластере будет только один главный узел. Когда какой-либо узел
+ выходит из строя, многоуровневая иерархия изменятся локально, только узлы,
+ примыкающие к вышедшему из строя, взаимодействуют друг с другом.
- *Отображение IP-адресов.* Поскольку структура иерархии зависит только от
IP-адресов узлов, то в алгоритме отсутствует фаза выбора лидера. Чтобы сменить
- руководителя, каждый узел отправляет сообщение только прежнему и новому
- руководителю.
+ главного, каждый узел отправляет сообщение только прежнему и новому главному
+ узлу.
- *Полностью основан на событиях.* Сообщения отправляются только при выходе из
строя узла, поэтому постоянной нагрузки на сеть нету. Поскольку алгоритм
допускает ошибку при отправке любого сообщения, то нет необходимости в
- heartbeat-пакетах, являющихся индикацией нахождения узла в сети; вместо этого
- все сообщения выполняют роль heartbeat-пакетов и настраивается время ожидания
- отправки пакета.
+ heartbeat-пакетах, являющихся индикацией работоспособности узла в сети; вместо
+ этого все сообщения выполняют роль heartbeat-пакетов и настраивается время
+ ожидания отправки пакета\nbsp{}cite:rfc5482.
- *Отсутствие ручной конфигурации.* Узлу не требуется никаких предварительных
- знаний, чтобы найти руководителя: он определяет сеть, узлом которой он
- является, вычисляет IP-адрес потенциального руководителя и отправляет ему
- сообщение. Если это не срабатывает, то процесс повторяется для следующего
- потенциального руководителя. Таким образом, алгоритм подходит для начальной
- загрузки кластера без ручной настройки, для этого требуется только запустить
+ знаний, чтобы найти главного: он определяет сеть, узлом которой он является,
+ вычисляет IP-адрес потенциального главного узла и отправляет ему сообщение.
+ Если это не срабатывает, то процесс повторяется для следующего потенциального
+ главного узла. Таким образом, алгоритм подходит для начальной загрузки
+ кластера без ручной настройки, для этого требуется только запустить
соответствующий сервис на каждом узле.
Суммируя вышесказанное, достоинством алгоритма является то, что он
- масштабируется на большое количество узлов посредством иерархии с несколькими
- руководящими узлами,
+ главными узлами,
- не нагружает сеть отправкой сообщений с текущим состоянием узлов и
heartbeat-пакетами,
- не требует ручной настройки для первичной загрузки кластера.
@@ -3161,16 +3164,16 @@ IP-адреса: замена отображения IP-адресов на чт
будет нарушена.
Алгоритм обнаружения узлов спроектирован для балансировки нагрузки на кластер
-вычислительных узлов, и его применение в других приложениях не рассматривается в
-данной работе. Когда распределенная или параллельная программа запускается на
-одном из узлов кластера, ее подзадачи распределяются между всеми примыкающими
-узлами иерархии (включая главный узел, если есть). Для того чтобы равномерно
-распределить нагрузку, когда программа запускается на подчиненном узле, каждый
-узел хранит вес каждого из примыкающих узлов иерархии. Вес равен количеству
-узлов дерева, находящегося "за" примыкающим узлом. Например, если вес первого
-примыкающего узла равен 2, то циклический алгоритм балансировки нагрузки
-распределит две подзадачи на первый узел перед тем как перейти к следующему
-узлу.
+вычислительных узлов (см.\nbsp{}разд.\nbsp{}[[#sec-daemon-layer]]), и его применение
+в других приложениях не рассматривается в данной работе. Когда распределенная
+или параллельная программа запускается на одном из узлов кластера, ее подзадачи
+распределяются между всеми примыкающими узлами иерархии (включая главный узел,
+если есть). Для того чтобы равномерно распределить нагрузку, когда программа
+запускается на подчиненном узле, каждый узел хранит вес каждого из примыкающих
+узлов иерархии. Вес равен количеству узлов дерева, находящегося "за" примыкающим
+узлом. Например, если вес первого примыкающего узла равен 2, то циклический
+алгоритм балансировки нагрузки распределит две подзадачи на первый узел перед
+тем как перейти к следующему узлу.
Суммируя вышесказанное, алгоритм обнаружения узлов
- спроектирован для облегчения распределения нагрузки на кластер,
@@ -3309,26 +3312,26 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
В последующих разделах будут описаны компоненты необходимые для написания
параллельной программы и планировщика, которые устойчивы к сбоям узлов кластера.
-**** Определения иерархий. Для устранения неоднозначности иерархических связей
-между резидентными процессами и управляющими объектами и для того чтобы
-упростить изложение, мы будем использовать в тексте следующие условные
-обозначения. Если связь установлена между двумя резидентными процессами, то
-отношения обозначаются /руководитель-подчиненный/. Если связь установлена между
-двумя управляющими объектами, то отношения обозначаются либо
-/руководитель-подчиненный/, либо /родитель-потомок/. Две иерархии ортогональны
-друг к другу в том смысле, что ни один управляющий объект не может иметь связь
-с сервисом, и наоборот. Поскольку иерархия сервисом используется для
-распределения нагрузки на узлы кластера, иерархия управляющих объектов
-отображается на нее, и это отображение может быть произвольным: обычна
-ситуация, когда руководящий управляющий объект находится на подчиненном узле, а
-его подчиненные управляющие объекта распределены равномерно между всеми узлами
-кластера (включая узел, где находится руководящий объект). Обе иерархии может
-быть сколь угодно глубокими, но "неглубокие" являются предпочтительными для
-высоко параллельных программ, так как в них меньше количество промежуточных
-узлов, через которые должны пройти управляющие объекты при распределении между
-узлами кластера. Поскольку существует однозначное соответствие между
-резидентными процессами и узлами кластера, в данной работе они используются как
-взаимозаменяемые термины.
+**** Определения иерархий.
+Для устранения неоднозначности иерархических связей между резидентными
+процессами и управляющими объектами и для того чтобы упростить изложение, мы
+будем использовать в тексте следующие условные обозначения. Если связь
+установлена между двумя резидентными процессами, то отношения обозначаются
+/руководитель-подчиненный/. Если связь установлена между двумя управляющими
+объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
+/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
+один управляющий объект не может иметь связь с сервисом, и наоборот. Поскольку
+иерархия сервисом используется для распределения нагрузки на узлы кластера,
+иерархия управляющих объектов отображается на нее, и это отображение может быть
+произвольным: обычна ситуация, когда руководящий управляющий объект находится на
+подчиненном узле, а его подчиненные управляющие объекта распределены равномерно
+между всеми узлами кластера (включая узел, где находится руководящий объект).
+Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
+предпочтительными для высоко параллельных программ, так как в них меньше
+количество промежуточных узлов, через которые должны пройти управляющие объекты
+при распределении между узлами кластера. Поскольку существует однозначное
+соответствие между резидентными процессами и узлами кластера, в данной работе
+они используются как взаимозаменяемые термины.
**** Обработка выхода узлов из строя.
Основной стратегией при выходе из строя подчиненного узла является перезапуск
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -2292,6 +2292,10 @@ network connectivity, i.e.\nbsp{}an ability to send network packet between any
pair of cluster nodes.
**** Daemon process layer.
+:PROPERTIES:
+:CUSTOM_ID: sec-daemon-layer
+:END:
+
Consists of daemon processes running on cluster nodes and hierarchical
(master/slave) logical links between them. Only one daemon process is launched
per node, so these terms are use interchangeably in this work. Master and slave
@@ -2766,23 +2770,23 @@ So, computational model with a pipeline can be seen as /bulk-asynchronous
model/, because of the parallel nature of programme steps. This model is the
basis of the fault-tolerance model which will be described later.
-*** Cluster node discovery algorithm
+*** Cluster node discovery
:PROPERTIES:
:CUSTOM_ID: sec-node-discovery
:END:
**** Leader election algorithms.
Many batch job scheduling systems are built on the principle of /subordination/:
-there is principal node in each cluster which manages job queue, schedules job
-execution on subordinate nodes and monitors their state. Principal role is
-assigned either /statically/ by an administrator to a particular physical node,
-or /dynamically/ by periodically electing one of the cluster nodes as principal.
-In the former case fault tolerance is provided by reserving additional spare
-node which takes principal role when current principal fails. In the latter case
-fault tolerance is provided by electing new principal node from survived nodes.
-Despite the fact that dynamic role assignment requires leader election
-algorithm, this approach becomes more and more popular as it does not require
-spare reserved nodes to recover from principal node
+there is master node in each cluster which manages job queue, schedules job
+execution on subordinate nodes and monitors their state. Master role is assigned
+either /statically/ by an administrator to a particular physical node, or
+/dynamically/ by periodically electing one of the cluster nodes as master. In
+the former case fault tolerance is provided by reserving additional spare node
+which takes master role when current master fails. In the latter case fault
+tolerance is provided by electing new master node from survived nodes. Despite
+the fact that dynamic role assignment requires leader election algorithm, this
+approach becomes more and more popular as it does not require spare reserved
+nodes to recover from master node
failure\nbsp{}cite:hunt2010zookeeper,lakshman2010cassandra,divya2013elasticsearch
and generally leads to a symmetric system architecture, in which the same
software stack with the same configuration is installed on every
@@ -2802,24 +2806,23 @@ is unaffected by some nodes going on-line and off-line.
The approach for cluster node discovery does not use wave algorithms, and hence
does not require communicating with each node of the cluster to determine a
leader. Instead, each node enumerates all nodes in the network it is part of,
-and converts this list to a /tree hierarchy/ with a user-defined maximal fan-out
-value (maximal number of subordinate nodes a node may have). Then the node
-determines its hierarchy level and tries to communicate with nodes from higher
-levels to become their subordinate. First, it checks the closest ones and then
-goes all the way to the top. If there is no top-level nodes or the node cannot
-connect to them, then the node itself becomes the principal of the whole
-hierarchy.
+and converts this list to a /tree hierarchy/ with a user-defined fan-out value
+(maximal number of subordinate nodes a node may have). Then the node determines
+its hierarchy level and tries to communicate with nodes from higher levels to
+become their subordinate. First, it checks the closest ones and then goes all
+the way to the top. If there is no top-level nodes or the node cannot connect to
+them, then the node itself becomes the master of the whole hierarchy.
Tree hierarchy of all hosts in a network defines strict total order on a set of
cluster nodes. Although, technically any function can be chosen to map a node to
a number, in practise this function should be sufficiently smooth along the time
axis and may have infrequent jumps: high-frequency oscillations (which are often
-caused by measurement errors) may result in constant passing of principal role
-from one node to another, which makes the hierarchy unusable for load balancing.
-The simplest such function is the position of an IP address in network IP
-address range.
+caused by measurement errors) may result in constant passing of master role from
+one node to another, which makes the hierarchy unusable for load balancing. The
+simplest such function is the position of an IP address in network IP address
+range.
-**** Tree hierarchy traversal algorithm.
+**** Tree hierarchy creation algorithm.
Strict total order on the set \(\mathcal{N}\) of cluster nodes connected to a
network is defined as
\begin{equation*}
@@ -2832,12 +2835,12 @@ order on \(\mathcal{R}^n\). Function \(f\) defines node's sequential number, and
\(<\) makes this number unique.
The simplest function \(f\) maps each node to its IP address position in network
-IP address range. A node with the lowest position in this range becomes the
-principal of the whole hierarchy. If IP-address of a node occupies the first
-position in the range, then there is no principal for it, and it continues to be
-at the top of the hierarchy until it fails. Although, IP address mapping is
-simple to implement, it introduces artificial dependence of the principal role
-on the address of a node. Still, it is useful for initial configuration of a
+IP address range. Without the use of tree hierarchy a node with the lowest
+position in this range becomes the master. If IP-address of a node occupies the
+first position in the range, then there is no master for it, and it continues to
+be at the top of the hierarchy until it fails. Although, IP address mapping is
+simple to implement, it introduces artificial dependence of the master role on
+the address of a node. Still, it is useful for initial configuration of a
cluster when more complex mappings are not applicable.
To make node discovery scale to a large number of nodes, IP address range is
@@ -2854,7 +2857,7 @@ computed from the following optimisation problem.
\end{align*}
where \(n\) is the position of node's IP address in network IP address range and
\(p\) is fan-out value (the maximal number of subordinates, a node can have).
-The principal of a node with level \(l\) and offset \(o\) has level \(l-1\) and
+The master of a node with level \(l\) and offset \(o\) has level \(l-1\) and
offset \(\lfloor{o/p}\rfloor\). The distance between any two nodes in the tree
hierarchy with network positions \(i\) and \(j\) is computed as
\begin{align*}
@@ -2870,29 +2873,29 @@ hierarchy with network positions \(i\) and \(j\) is computed as
\end{align*}
The distance is compound to account for level in the first place.
-To determine its principal each node ranks all nodes in the network according to
+To determine its master each node ranks all nodes in the network according to
their position \(\langle{l(n),o(n)}\rangle\), and using distance formula chooses
-the node which is closest to potential principal position and has lower level.
+the node which is closest to potential master position and has lower level.
That way IP addresses of offline nodes are skipped, however, for sparse networks
(in which nodes occupy non-contiguous IP addresses) perfect tree is not
guaranteed.
Formula for computing distance can be made arbitrary complex (to account for
network latency and throughput or geographical location of the node), however,
-for its simplest form it is more efficient to use node traversal algorithm. The
-algorithm requires less memory as there is no need to store ranked list of all
-nodes, but iterates over IP addresses of the network in the order defined by the
-fan-out value. The algorithm is as follows. First, the /base/ node (a node which
-searches for its principal) computes its potential principal address and tries
-to connect to this node. If the connection fails, the base node sequentially
-tries to connect to each node from the higher hierarchy levels, until it reaches
-the top of the hierarchy (the root of the tree). If none of the connections
-succeeds, the base node sequentially connects to all nodes on its own level
-having lesser position in IP address range. If none of the nodes respond, the
-base node becomes the principal node of the whole hierarchy, and the traversal
-repeats after a set period of time. An example of traversal order for a cluster
-of 11 nodes and a tree hierarchy with fan-out value of 2 is shown
-in\nbsp{}fig.\nbsp{}[[fig-tree-hierarchy-11]].
+for its simplest form it is more efficient to use cluster node traversal
+algorithm. The algorithm requires less memory as there is no need to store
+ranked list of all nodes, but iterates over IP addresses of the network in the
+order defined by the fan-out value. The algorithm is as follows. First, the
+/base/ node (a node which searches for its master) computes its potential master
+address and tries to connect to this node. If the connection fails, the base
+node sequentially tries to connect to each node from the higher hierarchy
+levels, until it reaches the top of the hierarchy (the root of the tree). If
+none of the connections succeeds, the base node sequentially connects to all
+nodes on its own level having lesser position in IP address range. If none of
+the nodes respond, the base node becomes the master node of the whole hierarchy,
+and the traversal repeats after a set period of time. An example of traversal
+order for a cluster of 11 nodes and a tree hierarchy with fan-out value of 2 is
+shown in\nbsp{}fig.\nbsp{}[[fig-tree-hierarchy-11]].
#+name: fig-tree-hierarchy-11
#+begin_src dot :exports results :file build/tree-hierarchy-11.pdf
@@ -2944,12 +2947,11 @@ number of processes per physical core varied from 2 to 16. Each process was
bound to a particular physical core to reduce overhead of process migration
between cores. Tree hierarchy traversal algorithm has low requirements for
processor time and network throughput, so running multiple processes per
-physical core is feasible, in contrast to HPC codes, where it often leads to
-poor performance. Test platform configuration is shown in
-table\nbsp{}[[tab-ant]].
+physical core is feasible, in contrast to HPC codes, where it often lowers
+performance. Test platform configuration is shown in table\nbsp{}[[tab-ant]].
#+name: tab-ant
-#+caption: Test platform configuration.
+#+caption: "Ant" system configuration.
#+attr_latex: :booktabs t
| CPU | Intel Xeon E5440, 2.83GHz |
| RAM | 4Gb |
@@ -2973,11 +2975,11 @@ hierarchy of nodes to reach stable state. Each change of the hierarchy, as seen
by each node, was written to a log file and after a set amount of time all
daemon processes (each of which models cluster node) were forcibly terminated.
Daemon processes were launched sequentially with a 100ms delay to ensure that
-principal nodes are always come online before subordinates and hierarchy does
+master nodes are always come online before subordinates and hierarchy does
not change randomly as a result of different start time of each process. This
artificial delay was subsequently subtracted from the results. So, benchmark
results represent discovery time in an "ideal" cluster, in which every daemon
-process always finds its principal on the first try.
+process always finds its master on the first try.
The benchmark was run multiple times varying the number of daemon processes per
cluster node. The experiment showed that discovery of 512 nodes (8 physical
@@ -2986,7 +2988,8 @@ nodes with 64 processes per node) each other takes no more than two seconds
with the increase in the number of physical nodes. Using more than 8 nodes with
64 processes per node causes large variation in discovery time due to a large
total number of processes connecting simultaneously to one master process (a
-fan-out value of 10000 was used for all tests), so these results were excluded.
+fan-out value of 10000 was used for all tests), so these results were excluded
+from consideration.
#+name: fig-discovery-benchmark
#+header: :width 7 :height 5
@@ -3002,40 +3005,40 @@ bscheduler.plot_discovery(xlabel="No. of physical nodes",toplabel="ppn")
**** Discussion.
Node discovery scales to a large number of nodes, because in order to determine
-its principal, a node is required to communicate to a node address of which it
+its master, a node is required to communicate to a node address of which it
knows beforehand. Communication with other nodes occurs only when the current
-principal node fails. So, if cluster nodes occupy contiguous addresses in
-network IP address range, each node connects only to its principal, and
+master node fails. So, if cluster nodes occupy contiguous addresses in
+network IP address range, each node connects only to its master, and
inefficient scan of the whole network by each node does not occur.
The following key features distinguish the proposed approach with respect to
some existing
approaches\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
-- *Multi-level hierarchy.* The number of principal nodes in a network depends on
+- *Multi-level hierarchy.* The number of master nodes in a network depends on
the fan-out value. If it is lesser than the number of IP-addresses in the
- network, then there are multiple principal nodes in the cluster. If it is
+ network, then there are multiple master nodes in the cluster. If it is
greater or equal to the number of IP-addresses in the network, then there is
- only one principal node. When some node fail, multi-level hierarchy changes
+ only one master node. When some node fail, multi-level hierarchy changes
locally, and only nodes that are adjacent to the failed one communicate.
However, node weight changes propagate to every node in the cluster via
hierarchical links.
- *IP-address mapping.* Since hierarchy structure solely depends on the nodes'
IP addresses, there is no election phase in the algorithm. To change the
- principal each node sends a message to the old principal and to the new one.
+ master each node sends a message to the old master and to the new one.
- *Completely event-based.* The messages are sent only when some node fails, so
- there is no constant load on the network. Since the algorithm allows
- to tolerate failure of sending any message, there is no need in heartbeat
- packets indicating presence of a node in the network; instead, all messages
- play the role of heartbeats and packet send time-out is adjusted.
+ there is no constant load on the network. Since the algorithm allows to
+ tolerate failure of sending any message, there is no need in heartbeat packets
+ indicating node serviceability in the network; instead, all messages play the
+ role of heartbeats and packet send time-out is adjusted\nbsp{}cite:rfc5482.
- *No manual configuration.* A node does not require any prior knowledge to find
- the principal: it determines the network it is part of, calculates potential
- principal IP-address and sends the message. If it fails, the process is
- repeated for the next potential principal node. So the algorithm is suitable
+ the master: it determines the network it is part of, calculates potential
+ master IP-address and sends the message. If it fails, the process is
+ repeated for the next potential master node. So the algorithm is suitable
to bootstrap a cluster without manual configuration, the only requirement is
to start the corresponding service on each node.
To summarise, the advantage of the algorithm is that it
- scales to a large number of nodes by means of hierarchy with multiple
- principal nodes,
+ master nodes,
- does not constantly load the network, as node state updates are sent only when
the state changes,
- does not require manual configuration to bootstrap a cluster, other than
@@ -3058,15 +3061,15 @@ the algorithm cease to be fully event-based as metric need to be collected on
every node and propagated to each node in the cluster.
Node discovery algorithm is designed to balance the load on a cluster of compute
-nodes, its use in other applications is not studied here. When distributed or
-parallel programme starts on any of cluster nodes, its kernels are distributed
-to all adjacent nodes in the hierarchy (including principal node if applicable).
-To distribute the load evenly when the application is run on a subordinate node,
-each node maintains the weight of each adjacent node in the hierarchy. The
-weight equals to the number of nodes in the tree "behind" the adjacent node. For
-example, if the weight of the first adjacent node is 2, then round-robin load
-balancing algorithm distributes two kernels to the first node before moving to
-the next one.
+nodes (see sec.\nbsp{}[[#sec-daemon-layer]]), its use in other applications is not
+studied here. When distributed or parallel programme starts on any of cluster
+nodes, its kernels are distributed to all adjacent nodes in the hierarchy
+(including master node if applicable). To distribute the load evenly when the
+application is run on a subordinate node, each node maintains the weight of each
+adjacent node in the hierarchy. The weight equals to the number of nodes in the
+tree "behind" the adjacent node. For example, if the weight of the first
+adjacent node is 2, then round-robin load balancing algorithm distributes two
+kernels to the first node before moving to the next one.
To summarise, node discovery algorithm is
- designed to ease load balancing on the large number of cluster nodes,
