commit 76494c64a0f35f00553f0d52dc07bf01e134f8b3
parent b064f8b584fedd9546cf39b01e6cfd87415573c9
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 6 Feb 2017 16:53:09 +0300
Sync tree hiearchy.
Diffstat:
| phd-diss-ru.org | | | 83 | ++++++++++++++++++++++++++++++++++++++----------------------------------------- |
| phd-diss.org | | | 68 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 108 insertions(+), 43 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2488,36 +2488,34 @@ IP-адреса: замена отображения IP-адресов на чт
- полностью основан на событиях, а значит не нагружает сеть периодической
отправкой сообщений.
-
**** Построение древовидной иерархии.
-Субординация на множестве $\mathcal{N}$ узлов одной подсети определяется как
+Отношение строго порядка на множестве $\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))),
+ \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$ --- отображение узла на его ранг, а $<$ --- оператор, определяющий
+отношение строго порядка на множестве $\mathcal{R}^n$. Функция $f$ присваивает
+узлу порядковый номер, а оператор $<$ делает этот номер уникальным.
Простейшее отображение $f$ ставит в соответствие каждому узлу подсети позицию
его IP-адреса в диапазоне всех адресов подсети. Без преобразования к древовидной
-структуре (когда в подсети выбирается только один лидер) рабочий узел, адрес
-которого занимает наименьшую позицию в диапазоне, становится главным. Если адрес
-узла занимает первую позицию в диапазоне, то для него невозможно выбрать лидера,
-и он будет находится на вершине иерархии вплоть до выхода из строя. Несмотря на
-то что идентификацию узлов на основе их IP-адресов легко реализовать в
-программе, такой подход устанавливает искусственную зависимость роли главного
-узла от IP-адреса. Тем не менее, этот подход полезен для первичного объединения
-узлов в кластер, когда более сложные методы идентификации узлов неприменимы.
-
-Для того чтобы алгоритм субординации масштабировался на большое количество
-узлов, структуру диапазона адресов подсети необходимо сделать древовидной. В
-древовидной иерархии каждый узел идентифицируется уровнем $l$ иерархии, на
-котором он находится и отступом $o$, который равен порядковому номеру узла на
-его уровне. Значения уровня и отступа определяются из следующей задачи
-оптимизации.
+иерархии (когда в подсети выбирается только один лидер) рабочий узел, адрес
+которого занимает наименьшую позицию в диапазоне, становится руководящим. Если
+адрес узла занимает первую позицию в диапазоне, то для него невозможно выбрать
+лидера, и он будет находится на вершине иерархии вплоть до выхода из строя.
+Несмотря на то что идентификацию узлов на основе их IP-адресов легко реализовать
+в программе, такой подход устанавливает искусственную зависимость роли
+руководителя от IP-адреса узла. Тем не менее, этот подход полезен для первичного
+объединения узлов в кластер, когда более сложные отображения неприменимы.
+
+Для того чтобы алгоритм обнаружения масштабировался на большое количество узлов,
+диапазона IP адресов подсети отображается на древовидную иерархию. В такой
+иерархии каждый узел определяется уровнем \(l\) иерархии, на котором он
+находится, и отступом \(o\), который равен порядковому номеру узла на его
+уровне. Значения уровня и отступа определяются из следующей задачи оптимизации.
\begin{equation*}
n = \sum\limits_{i=0}^{l(n)} p^i + o(n), \quad
l \rightarrow \min, \quad
@@ -2527,7 +2525,7 @@ IP-адреса: замена отображения IP-адресов на чт
\end{equation*}
где $n$ --- позиция IP-адреса узла в диапазоне IP-адресов подсети и $p$ ---
значение ветвления (максимальное количество подчиненных, которых может иметь
-узел). Лидер узла на уровне $l$ с отступом $o$ будет иметь уровень $l-1$ и
+узел). Руководитель узла на уровне $l$ с отступом $o$ имеет уровень $l-1$ и
отступ $\lfloor{o/p}\rfloor$. Расстояние между любыми двумя узлами в иерархии,
адреса которых занимают позиции $i$ и $j$ в диапазоне определяется как
\begin{align*}
@@ -2541,24 +2539,23 @@ IP-адреса: замена отображения IP-адресов на чт
l_1 - l_2 & \quad \text{if } l_1 < l_2.
\end{cases}
\end{align*}
-Расстояние имеет составную запись, чтобы при определении близости двух узлов
-уровень иерархии учитывался в первую очередь.
-
-Для выбора лидера каждый узел ранжирует все узлы подсети в соответствии с
-$\langle{l(n),o(n)}\rangle$ и, используя формулу для определения расстояния,
-выбирает ближайший к потенциальному лидеру узел, имеющий наименьший ранг. Это
-позволяет пропустить IP-адреса выключенных и просто несуществующих узлов, но для
-разреженных сетей, в которых некоторые IP-адреса из середины списка не
-закреплены за работающими узлами, сбалансированность дерева не гарантируется.
-
-Поскольку узлу для выбора лидера нужно соединиться только с узлом, адрес
-которого известен заранее, то алгоритм субординации хорошо масштабируется на
-большое количество узлов. Соединение с другими узлами из ранжированного списка
-происходит только в том случае, если соединение с узлом из начала списка
-прерывается. Таким образом, если адреса рабочих узлов расположены плотно в
-диапазоне адресов подсети, каждый узел устанавливает соединение только со своим
-узлом-лидером, и ресурсоемкого и неэффективного сканирования всей сети каждым
-узлом не происходит.
+Расстояние является составным, чтобы уровень иерархии учитывался в первую
+очередь.
+
+Для выбора руководителя каждый узел ранжирует все узлы подсети в соответствии с
+их позицией $\langle{l(n),o(n)}\rangle$ и, используя формулу для определения
+расстояния, выбирает ближайший к потенциальному руководителю узел, имеющий
+наименьший ранг. Это позволяет пропустить IP-адреса выключенных узлов, однако,
+для разреженных сетей (в которых узлы занимают непоследовательные IP-адреса)
+сбалансированность дерева не гарантируется.
+
+Поскольку узлу для выбора руководителя нужно соединиться с узлом, адрес которого
+известен заранее, то алгоритм обнаружения масштабируется на большое количество
+узлов. Соединение с другими узлами из ранжированного списка происходит только в
+том случае, если текущим узел-руководитель выходит из строя. Таким образом, если
+адреса узлов кластера расположены плотно в диапазоне адресов подсети, каждый
+узел устанавливает соединение только со своим руководителем, и
+неэффективного сканирования всей сети каждым узлом не происходит.
**** Результаты тестирования.
Платформа, на которой осуществлялось тестирование, состоит из одного
diff --git a/phd-diss.org b/phd-diss.org
@@ -2333,6 +2333,74 @@ To summarise, node discovery algorithm is
- fully event-based which means it does not load the network by periodically
sending messages.
+**** Building a tree hierarchy.
+Strict total order on the set $\mathcal{N}$ of cluster nodes connected to a
+network is defined as
+\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*}
+where $f$ maps a node to its rank and operator $<$ defines strict total order on
+$\mathcal{R}^n$. Function $f$ defines node's sequential number, and $<$ makes
+this number unique.
+
+The simpliest function $f$ maps each node to its Internet address position in
+network IP address range. Without conversion to a tree (when only \emph{one}
+leader is allowed in the network) a node with the lowest position in this range
+becomes the principal. 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 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.
+\begin{align*}
+ 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{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 offset
+$\lfloor{o/p}\rfloor$. The distance between any two nodes in the tree with
+network positions $i$ and $j$ is computed as
+\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*}
+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
+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.
+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.
+
+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.
+
*** Fail over algorithm
**** Introduction.
Fault tolerance of data processing pipelines is one of the top concerns in
