commit 337b35a34dbe3e9e1b744f7ab409113e385baef6
parent 582152e5dd5b6a6e31d115c9e47d41c2fc2f1bde
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 25 Sep 2017 17:13:48 +0300
Update cluster node discovery algorithm description.
Diffstat:
| arma-thesis-ru.org | | | 228 | +++++++++++++++++++++++++++++++++++++++++++++++++------------------------------ |
| arma-thesis.org | | | 278 | +++++++++++++++++++++++++++++++++++++------------------------------------------ |
2 files changed, 274 insertions(+), 232 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -2530,9 +2530,9 @@ arma.plot_factory_vs_openmp_overlap(
посредством резервирования дополнительного свободного узла, который выполнит
роль главного в случае отказа текущего. Во втором случае отказоустойчивость
обеспечивается выбором нового главного узла из оставшихся. Несмотря на то что
-динамическое задание ролей требует наличия специализированного распределенного
-алгоритма, этот подход становится все более и более популярным, поскольку не
-требует наличия простаивающих резервных узлов на случай отказа главного узла.
+динамическое задание ролей требует наличия алгоритма выбора лидера, этот подход
+становится все более и более популярным, поскольку не требует наличия
+простаивающих резервных узлов на случай отказа главного узла.
Алгоритмы выбора лидера (которые иногда называют алгоритмами /распределенного
консенсуса/) являются частными случаями волновых алгоритмов.
@@ -2547,16 +2547,15 @@ arma.plot_factory_vs_openmp_overlap(
узлов, так что включение и выключение отдельных узлов не влияет на работу
алгоритма.
-Подход к динамическому выбору главного узла, исследованный в данной работе, не
-использует волновые алгоритмы, а значит не требует опроса всех узлов кластера
-для выбора лидера. Вместо этого каждый узел кластера нумерует все узлы подсети,
-в которой он находится, и преобразует список в /древовидную иерархию/ с заданным
-максимальным значением ветвления (максимальным количеством подчиненных вершин).
-Затем узел определяет свой уровень иерархии и пытается соединиться с
-вышестоящими узлами, чтобы стать их подчиненным. Сначала он проверяет близко
-расположенные к нему узлы, а потом все остальные узлы вплоть до вершины
-иерархии. Если вышестоящих узлов нет или с ними невозможно соединиться, то узел
-сам становится главой всей иерархии.
+Подход к поиску узлов кластера не использует волновые алгоритмы, а значит не
+требует опроса всех узлов кластера для выбора лидера. Вместо этого каждый узел
+кластера нумерует все узлы подсети, в которой он находится, и преобразует список
+в /древовидную иерархию/ с заданным максимальным значением ветвления
+(максимальным количеством подчиненных вершин). Затем узел определяет свой
+уровень иерархии и пытается соединиться с вышестоящими узлами, чтобы стать их
+подчиненным. Сначала он проверяет близко расположенные к нему узлы, а потом все
+остальные узлы вплоть до вершины иерархии. Если вышестоящих узлов нет или с ними
+невозможно соединиться, то узел сам становится главой всей иерархии.
Древовидная иерархия узлов подсети определяет отношение строгого порядка на
множестве всех узлов кластера. Несмотря на то что с технической точки зрения
@@ -2564,77 +2563,11 @@ arma.plot_factory_vs_openmp_overlap(
практике эта функция должна быть достаточно гладкой вдоль временной оси и иметь
лишь редкие скачки: быстрые изменения в структуре иерархии узлов (которые часто
являются следствием погрешности измерений) могут привести постоянной передаче
-роли главного узла от одного узла к другому, что сделает кластер неуправляемым.
-Простейшей такой функцией является позиция IP-адреса узла в диапазоне всех
-IP-адресов подсети.
+роли главного узла от одного узла к другому, что сделает иерархию непригодной
+для распределения нагрузки. Простейшей такой функцией является позиция IP-адреса
+узла в диапазоне всех IP-адресов подсети.
-Следующие ключевые особенности отличают наш подход от некоторых предложенных
-ранее подходов\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
-- *Многоуровневая иерархия.* Количество руководящих узлов в сети зависит от
- значения ветвления. Если оно меньше количества IP-адресов в подсети, то в
- кластере будет несколько руководящих узлов. Если оно больше или равно
- количеству IP-адресов в подсети, то в кластере будет только один руководящий
- узел. Когда какой-либо узел выходит из строя, многоуровневая иерархия
- изменятся локально, только узлы, примыкающие к вышедшему из строя,
- взаимодействуют друг с другом.
-- *Отображение IP-адресов.* Поскольку структура иерархии зависит только от
- IP-адресов узлов, то в алгоритме отсутствует фаза выбора лидера. Чтобы сменить
- руководителя, каждый узел отправляет сообщение только прежнему и новому
- руководителю.
-- *Полностью основан на событиях.* Сообщения отправляются только при выходе из
- строя узла, поэтому постоянной нагрузки на сеть нету. Поскольку алгоритм
- допускает ошибку при отправке любого сообщения, то нет необходимости в
- heartbeat-пакетах, являющихся индикацией нахождения узла в сети; вместо этого
- все сообщения выполняют роль heartbeat-пакетов и настраивается время ожидания
- отправки пакета.
-- *Отсутствие ручной конфигурации.* Узлу не требуется никаких предварительных
- знаний, чтобы найти руководителя: он определяет сеть, узлом которой он
- является, вычисляет IP-адрес потенциального руководителя и отправляет ему
- сообщение. Если это не срабатывает, то процесс повторяется для следующего
- потенциального руководителя. Таким образом, алгоритм подходит для начальной
- загрузки кластера без ручной настройки, для этого требуется только запустить
- соответствующий сервис на каждом узле.
-Суммируя вышесказанное, достоинством алгоритма является то, что он
-- масштабируется на большое количество узлов посредством иерархии с несколькими
- руководящими узлами,
-- не нагружает сеть отправкой сообщений с текущим состоянием узлов и
- heartbeat-пакетами,
-- не требует ручной настройки для первичной загрузки кластера.
-
-Недостатком алгоритма является то, что он требует редкого изменения IP-адресов.
-Он не подходит для облачной среды, в которой только DNS имя узла сохраняется, а
-IP-адрес может меняться со временем. Когда IP-адрес меняется, текущие соединения
-могут закрыться, сигнализируя о "выходе из строя" узла и перестраивая иерархию
-узлов. Таким образом, окружения, в которых узлы не идентифицируются IP-адресами,
-не подходят для алгоритма.
-
-Другим недостатком алгоритма является искусственная зависимость ранга узла от
-IP-адреса: замена отображения IP-адресов на что-то более совершенное (например,
-на отображение, которое использует загрузку текущего узла и сети для
-ранжирования узлов) представляет сложность, поскольку погрешность измерений
-может стать причиной неустойчивой иерархии, а полная событийность алгоритма
-будет нарушена.
-
-Алгоритм обнаружения узлов спроектирован для балансировки нагрузки на кластер
-вычислительных узлов, и его применение в других приложениях не рассматривается в
-данной работе. Когда распределенная или параллельная программа запускается на
-одном из узлов кластера, ее подзадачи распределяются между всеми примыкающими
-узлами иерархии (включая главный узел, если есть). Для того чтобы равномерно
-распределить нагрузку, когда программа запускается на подчиненном узле, каждый
-узел хранит вес каждого из примыкающих узлов иерархии. Вес равен количеству
-узлов дерева, находящегося "за" примыкающим узлом. Например, если вес первого
-примыкающего узла равен 2, то циклический алгоритм балансировки нагрузки
-распределит две подзадачи на первый узел перед тем как перейти к следующему
-узлу.
-
-Суммируя вышесказанное, алгоритм обнаружения узлов
-- спроектирован для облегчения распределения нагрузки на кластер,
-- полностью отказоустойчивый, состояние каждого узла можно вычислить заново в
- любой момент времени,
-- полностью основан на событиях, а значит не нагружает сеть периодической
- отправкой сообщений.
-
-**** Построение древовидной иерархии.
+**** Алгоритм обхода древовидной иерархии.
Отношение строго порядка на множестве \(\mathcal{N}\) узлов одной подсети
определяется как
\begin{equation*}
@@ -2695,13 +2628,70 @@ IP-адреса: замена отображения IP-адресов на чт
для разреженных сетей (в которых узлы занимают непоследовательные IP-адреса)
сбалансированность дерева не гарантируется.
+Алгоритм обхода древовидной иерархии определяет IP-адреса и порядок их опроса,
+который каждый узел кластера выполняет для поиска своего руководителя. Сначала
+базовый узел (узел, который ищет руководителя) вычисляет адрес своего
+потенциального руководителя и пытается установить соединение с ним. Если
+соединение не удается, базовый узел последовательно пытается соединиться с
+каждым узлом, находящимся на более высоком уровне иерархии, пока не достигнет
+вершины иерархии (корня дерева). Если ни одно из соединений не удается, базовый
+узел последовательно пытается соединиться с каждым узлом на своем уровне,
+имеющим более низкую позицию в диапазоне всех IP-адресов подсети. Если ни один
+из узлов не отвечает, базовый узел занимает вершину иерархии, а обход иерархии
+повторяется через заданный промежуток времени. Пример порядка обхода для
+кластера из 11 узлов и древовидной иерархии с ветвлением 2 показан на
+рис.\nbsp{}[[fig-tree-hierarchy-11]].
+
+#+name: fig-tree-hierarchy-11
+#+begin_src dot :exports results :file build/tree-hierarchy-11-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="10.0.0.1"]
+ m2 [label="10.0.0.2"]
+ m3 [label="10.0.0.3"]
+ m4 [label="10.0.0.4"]
+ m5 [label="10.0.0.5"]
+ m6 [label="10.0.0.6"]
+ m7 [label="10.0.0.7"]
+ m8 [label="10.0.0.8"]
+ m9 [label="10.0.0.9"]
+ m10 [label="10.0.0.10",fillcolor="#c0c0c0",style="filled,rounded"]
+ m11 [label="10.0.0.11",shape=Mrecord]
+
+ m2->m1
+ m3->m1
+ m4->m2
+ m5->m2
+ m6->m3
+ m7->m3
+ m8->m4
+ m9->m4
+ m10->m5
+ m11->m5
+
+ m5->m4->m6 [style="dashed,bold",color="#c00000",constraint=false]
+ {rank=same; m6->m7 [style="dashed,bold",color="#c00000"]}
+ m7->m2->m3->m1->m8->m9 [style="dashed,bold",color="#c00000",constraint=false]
+
+}
+#+end_src
+
+#+caption: Древовидная иерархия для кластера из 11 узлов со значением ветвления 2. Красными стрелками обозначен порядок обхода иерархии узлом с IP-адресом 10.0.0.10.
+#+name: fig-tree-hierarchy-11
+#+RESULTS: fig-tree-hierarchy-11
+[[file:build/tree-hierarchy-11-ru.pdf]]
+
Поскольку узлу для выбора руководителя нужно соединиться с узлом, адрес которого
известен заранее, то алгоритм обнаружения масштабируется на большое количество
узлов. Соединение с другими узлами из ранжированного списка происходит только в
том случае, если текущим узел-руководитель выходит из строя. Таким образом, если
адреса узлов кластера расположены плотно в диапазоне адресов подсети, каждый
-узел устанавливает соединение только со своим руководителем, и
-неэффективного сканирования всей сети каждым узлом не происходит.
+узел устанавливает соединение только со своим руководителем, и неэффективного
+сканирования всей сети каждым узлом не происходит.
**** Результаты тестирования.
Платформа, на которой осуществлялось тестирование, представляла собой несколько
@@ -2776,6 +2766,74 @@ digraph {
#+RESULTS: fig-tree-hierarchy-11
[[file:build/tree-hierarchy-11-ru.pdf]]
+**** Обсуждение.
+Следующие ключевые особенности отличают наш подход от некоторых предложенных
+ранее
+подходов\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
+- *Многоуровневая иерархия.* Количество руководящих узлов в сети зависит от
+ значения ветвления. Если оно меньше количества IP-адресов в подсети, то в
+ кластере будет несколько руководящих узлов. Если оно больше или равно
+ количеству IP-адресов в подсети, то в кластере будет только один руководящий
+ узел. Когда какой-либо узел выходит из строя, многоуровневая иерархия
+ изменятся локально, только узлы, примыкающие к вышедшему из строя,
+ взаимодействуют друг с другом.
+- *Отображение IP-адресов.* Поскольку структура иерархии зависит только от
+ IP-адресов узлов, то в алгоритме отсутствует фаза выбора лидера. Чтобы сменить
+ руководителя, каждый узел отправляет сообщение только прежнему и новому
+ руководителю.
+- *Полностью основан на событиях.* Сообщения отправляются только при выходе из
+ строя узла, поэтому постоянной нагрузки на сеть нету. Поскольку алгоритм
+ допускает ошибку при отправке любого сообщения, то нет необходимости в
+ heartbeat-пакетах, являющихся индикацией нахождения узла в сети; вместо этого
+ все сообщения выполняют роль heartbeat-пакетов и настраивается время ожидания
+ отправки пакета.
+- *Отсутствие ручной конфигурации.* Узлу не требуется никаких предварительных
+ знаний, чтобы найти руководителя: он определяет сеть, узлом которой он
+ является, вычисляет IP-адрес потенциального руководителя и отправляет ему
+ сообщение. Если это не срабатывает, то процесс повторяется для следующего
+ потенциального руководителя. Таким образом, алгоритм подходит для начальной
+ загрузки кластера без ручной настройки, для этого требуется только запустить
+ соответствующий сервис на каждом узле.
+Суммируя вышесказанное, достоинством алгоритма является то, что он
+- масштабируется на большое количество узлов посредством иерархии с несколькими
+ руководящими узлами,
+- не нагружает сеть отправкой сообщений с текущим состоянием узлов и
+ heartbeat-пакетами,
+- не требует ручной настройки для первичной загрузки кластера.
+
+Недостатком алгоритма является то, что он требует редкого изменения IP-адресов.
+Он не подходит для облачной среды, в которой только DNS имя узла сохраняется, а
+IP-адрес может меняться со временем. Когда IP-адрес меняется, текущие соединения
+могут закрыться, сигнализируя о "выходе из строя" узла и перестраивая иерархию
+узлов. Таким образом, окружения, в которых узлы не идентифицируются IP-адресами,
+не подходят для алгоритма.
+
+Другим недостатком алгоритма является искусственная зависимость ранга узла от
+IP-адреса: замена отображения IP-адресов на что-то более совершенное (например,
+на отображение, которое использует загрузку текущего узла и сети для
+ранжирования узлов) представляет сложность, поскольку погрешность измерений
+может стать причиной неустойчивой иерархии, а полная событийность алгоритма
+будет нарушена.
+
+Алгоритм обнаружения узлов спроектирован для балансировки нагрузки на кластер
+вычислительных узлов, и его применение в других приложениях не рассматривается в
+данной работе. Когда распределенная или параллельная программа запускается на
+одном из узлов кластера, ее подзадачи распределяются между всеми примыкающими
+узлами иерархии (включая главный узел, если есть). Для того чтобы равномерно
+распределить нагрузку, когда программа запускается на подчиненном узле, каждый
+узел хранит вес каждого из примыкающих узлов иерархии. Вес равен количеству
+узлов дерева, находящегося "за" примыкающим узлом. Например, если вес первого
+примыкающего узла равен 2, то циклический алгоритм балансировки нагрузки
+распределит две подзадачи на первый узел перед тем как перейти к следующему
+узлу.
+
+Суммируя вышесказанное, алгоритм обнаружения узлов
+- спроектирован для облегчения распределения нагрузки на кластер,
+- полностью отказоустойчивый, состояние каждого узла можно вычислить заново в
+ любой момент времени,
+- полностью основан на событиях, а значит не нагружает сеть периодической
+ отправкой сообщений.
+
*** Алгоритм восстановления после сбоев
**** Контрольные точки восстановления.
Сбои узлов распределенной системы можно разделить на два типа: сбой подчиненного
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -2737,13 +2737,13 @@ 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
-by an algorithm. 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
-specialised distributed algorithm, this approach becomes more and more popular
-as it does not require spare reserved nodes to recover from principal 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
failure\nbsp{}cite:hunt2010zookeeper,lakshman2010cassandra,divya2013elasticsearch
and generally leads to a symmetric system in which the same software stack with
the same configuration is installed on every
@@ -2760,10 +2760,10 @@ algorithm. For a distributed system this means that wave algorithms work for
computer clusters with dynamically changing number of nodes, and the algorithm
is unaffected by some nodes going on-line and off-line.
-The approach in the following work 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
+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). 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
@@ -2775,69 +2775,11 @@ 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 cluster unmanageable. The simplest
-such function is the position of an IP address in network IP address range.
+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.
-The following key features distinguish this approach with respect to some
-existing proposals\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
-- *Multi-level hierarchy.* The number of principal 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
- 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
- locally, only nodes adjacent to the failed one communicate.
-- *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.
-- *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 role of heartbeats and packet send time-out is adjusted.
-- *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
- 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
- principals,
-- does not constantly load the network with node state updates and heartbeat
- packets,
-- does not require manual configuration to bootstrap a cluster.
-
-The disadvantage of the algorithm is that it requires IP-address to change
-infrequently. It is not suitable for cloud environments in which node DNS name
-is preserved, but IP-address may change over time. When IP-address changes,
-current connections may close, thus triggering node "failure" and rebuilding
-node hierarchy. So, environments where nodes are not identified by IP-addresses,
-are not suitable for the algorithm.
-
-The other disadvantage is that the algorithm creates artificial dependence of
-node rank on IP-address: it is difficult to substitute IP-address mapping with a
-more sophisticated one (e.g.\nbsp{}a mapping which uses current node and network
-load to infer node ranks) because measurement errors may result in unstable
-hierarchy, and the algorithm cease to be fully event-based.
-
-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 subtasks 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 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 subtasks to the first node before moving to
-the next one.
-
-To summarise, node discovery algorithm is
-- designed to ease load balancing on the cluster,
-- fully fault-tolerant the state of every node can be recomputed at any time,
-- fully event-based which means it does not load the network by periodically
- sending messages.
-
-**** Building a tree hierarchy.
+**** Tree hierarchy traversal algorithm.
Strict total order on the set \(\mathcal{N}\) of cluster nodes connected to a
network is defined as
\begin{equation*}
@@ -2845,7 +2787,7 @@ network is defined as
\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*}
-where \(f\) maps a node to its rank and operator \(<\) defines strict total order on
+where \(f\) maps a node to its level and operator \(<\) defines strict total order on
\(\mathcal{R}^n\). Function \(f\) defines node's sequential number, and \(<\) makes
this number unique.
@@ -2859,11 +2801,11 @@ implement, it introduces artificial dependence of the principal 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 discovery algorithm scale to a large number of nodes, IP address range
-is mapped to a tree hierarchy. In this hierarchy each node is uniquely
-identified by its hierarchy level \(l\), which it occupies, and offset \(o\),
-which equals to the sequential number of node on its level. Values of level and
-offset are computed from the following optimisation problem.
+To make node discovery scale to a large number of nodes, IP address range is
+mapped to a tree hierarchy. In this hierarchy each node is uniquely identified
+by its hierarchy level \(l\), which it occupies, and offset \(o\), which equals
+to the sequential number of node on its level. Values of level and offset are
+computed from the following optimisation problem.
\begin{align*}
n = \sum\limits_{i=0}^{l(n)} p^i + o(n), \quad
l \rightarrow \min, \quad
@@ -2889,78 +2831,25 @@ 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 principal each node levels 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 rank.
+the node which is closest to potential principal 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.
-#+name: fig-tree-hierarchy-algo
-#+begin_src dot :exports results :file build/tree-hierarchy-algo.pdf
-digraph {
-
- node [fontsize=14,margin="0.055,0.055",shape=box,style=rounded,fontname="Old Standard"]
- graph [nodesep="0.15",ranksep="0.20",rankdir="BT"]
- edge [arrowsize=0.66,fontname="Fira Mono"]
-
- start [label="",shape=circle,style=filled,fillcolor=black,width=0.23]
- end [label="",shape=doublecircle,style=filled,fillcolor=black,width=0.23]
-
- initial [label="{Initial | }",shape=Mrecord]
- traverse_parent [label="{Traversing parent node | Traverse only parent node}",shape=Mrecord]
- traverse_upper_layers [label="{Traversing upper layers | Traverse all nodes\lfrom the parent layer\lto the top of the hierarchy}",shape=Mrecord]
- traverse_base_layer [label="{Traversing base layer | Traverse all nodes\lon the same layer\lpreceding the base one}",shape=Mrecord]
-
- start->initial
- initial->end [label="[base.is_root()]"]
- initial->traverse_parent [label="[!base.is_root()]"]
- traverse_parent->traverse_upper_layers
- traverse_upper_layers->traverse_base_layer [label="[current.is_root()]"]
- traverse_base_layer->end [label="[current==base]"]
-
-}
-#+end_src
-
-#+caption: State diagram for tree hierarchy traversal algorithm.
-#+name: fig-tree-hierarchy-algo
-#+RESULTS: fig-tree-hierarchy-algo
-[[file:build/tree-hierarchy-algo.pdf]]
-
-In order to determine its principal a node is required to communicate to a node
-address of which it knows beforehand, so discovery algorithm scales to a large
-number of nodes. Communication with other nodes in ranked list occurs only when
-the current principal node fails. So, if address of cluster nodes occupy
-contiguous addresses network IP address range, each node connects to its
-principal only, and inefficient scan of all network by each node does not occur.
-
-**** Evaluation results.
-Test platform consisted of several multi-core nodes, on top of which virtual
-clusters with varying number of nodes were deployed using Linux network
-namespaces. Similar approach is used
-in\nbsp{}cite:lantz2010network,handigol2012reproducible,heller2013reproducible
-where the authors reproduce various real-world experiments using virtual
-clusters and compare results to physical ones. The advantage of it is that the
-tests can be performed on a large virtual cluster using relatively small number
-of physical nodes. This approach was used to evaluate node discovery algorithm,
-because the algorithm has low requirement for system resources (processor time
-and network throughput).
-
-Performance of the algorithm was evaluated by measuring time needed to all nodes
-of the cluster to discover each other. Each change of the hierarchy (as seen by
-each node) was written to a file and after 30 seconds all the processes (each of
-which models cluster node) were forcibly terminated. Test runs showed that
-running more than 100 virtual nodes on one physical node simultaneously warp the
-results, thus additional physical nodes, each of which run 100 virtual nodes,
-were used for the experiment. The experiment showed that discovery of 100--400
-nodes each other takes 1.5 seconds on average, and the value increases only
-slightly with increase in the number of nodes (see
-fig.\nbsp{}[[fig-bootstrap-local]]). An example of tree hierarchy for 11 nodes with
-fan-out 2 is shown in fig.\nbsp{}[[fig-tree-hierarchy-11]].
-
-#+name: fig-bootstrap-local
-#+caption: Time to discover all nodes of the cluster in depending on number of nodes.
-[[file:graphics/discovery.eps]]
+Tree hierarchy traversal algorithm defines IP addresses and the order in which
+they are polled by each cluster node to find its principal. 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.[[fig-tree-hierarchy-11]].
#+name: fig-tree-hierarchy-11
#+begin_src dot :exports results :file build/tree-hierarchy-11.pdf
@@ -3000,11 +2889,106 @@ digraph {
}
#+end_src
-#+caption: Tree hierarchy for 11 nodes with fan-out equals 2. Read arrows denote tree hierarchy traversal order for 10.0.0.10.
+#+caption: Tree hierarchy for 11 nodes with fan-out equals 2. Red arrows denote hierarchy traversal order for a node with IP address 10.0.0.10.
#+name: fig-tree-hierarchy-11
#+RESULTS: fig-tree-hierarchy-11
[[file:build/tree-hierarchy-11.pdf]]
+In order to determine its principal, a node is required to communicate to a node
+address of which it knows beforehand, so node discovery scales to a large number
+of nodes. 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 to its principal only, and inefficient scan of
+the whole network by each node does not occur.
+
+**** Evaluation results.
+Test platform consisted of several multi-core nodes, on top of which virtual
+clusters with varying number of nodes were deployed using Linux network
+namespaces. Similar approach is used
+in\nbsp{}cite:lantz2010network,handigol2012reproducible,heller2013reproducible
+where the authors reproduce various real-world experiments using virtual
+clusters and compare results to physical ones. The advantage of it is that the
+tests can be performed on a large virtual cluster using relatively small number
+of physical nodes. This approach was used to evaluate node discovery algorithm,
+because the algorithm has low requirement for system resources (processor time
+and network throughput).
+
+Performance of the algorithm was evaluated by measuring time needed to all nodes
+of the cluster to discover each other. Each change of the hierarchy (as seen by
+each node) was written to a file and after 30 seconds all the processes (each of
+which models cluster node) were forcibly terminated. Test runs showed that
+running more than 100 virtual nodes on one physical node simultaneously warp the
+results, thus additional physical nodes, each of which run 100 virtual nodes,
+were used for the experiment. The experiment showed that discovery of 100--400
+nodes each other takes 1.5 seconds on average, and the value increases only
+slightly with increase in the number of nodes (see
+fig.\nbsp{}[[fig-bootstrap-local]]).
+
+#+name: fig-bootstrap-local
+#+caption: Time to discover all nodes of the cluster in depending on number of nodes.
+[[file:graphics/discovery.eps]]
+
+**** Discussion.
+The following key features distinguish this approach with respect to some
+existing
+proposals\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
+- *Multi-level hierarchy.* The number of principal 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
+ 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
+ locally, only nodes adjacent to the failed one communicate.
+- *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.
+- *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.
+- *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
+ 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
+ principals,
+- does not constantly load the network with node state updates and heartbeat
+ packets,
+- does not require manual configuration to bootstrap a cluster.
+
+The disadvantage of the algorithm is that it requires IP-address to change
+infrequently. It is not suitable for cloud environments in which node DNS name
+is preserved, but IP-address may change over time. When IP-address changes,
+current connections may close, thus triggering node "failure" and rebuilding
+node hierarchy. So, environments where nodes are not identified by IP-addresses,
+are not suitable for the algorithm.
+
+The other disadvantage is that the algorithm creates artificial dependence of
+node rank on IP-address: it is difficult to substitute IP-address mapping with a
+more sophisticated one (e.g.\nbsp{}a mapping which uses current node and network
+load to infer node ranks) because measurement errors may result in unstable
+hierarchy, and the algorithm cease to be fully event-based.
+
+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 subtasks 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 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 subtasks to the first node before moving to
+the next one.
+
+To summarise, node discovery algorithm is
+- designed to ease load balancing on the cluster,
+- fully fault-tolerant the state of every node can be recomputed at any time,
+- fully event-based which means it does not load the network by periodically
+ sending messages.
+
*** Fail over algorithm
**** Checkpoints.
Node failures in a distributed system are divided into two types: failure of a
