commit e1727d168f6b3038d85333b522e67419f3b2bfe4
parent 075423c24ef031873c940f7dd2d9054d93e96378
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 6 Feb 2017 15:24:53 +0300
Translate p1*.
Diffstat:
| phd-diss-ru.org | | | 85 | ++++++++++++++++++++++++++++++++++++++++++++----------------------------------- |
| phd-diss.org | | | 31 | ++++++++++++++++--------------- |
2 files changed, 63 insertions(+), 53 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2377,17 +2377,17 @@ arma.plot_factory_vs_openmp_overlap(
*** Алгоритм обнаружения узлов кластера
**** Введение.
Многие распределенные системы построены по принципу /субординации/: в каждом
-кластере выбирается главный узел, который управляет очередью задач, планирует их
-запуск на подчиненных узлах и следит за их состоянием. Роль главного узла
-задается либо /статически/, путем выделения конкретного физического узла под
-нее, либо /динамически/, путем избрания какого-либо из узлов кластера главным. В
-первом случае отказоустойчивость обеспечивается посредством резервирования
-дополнительного свободного узла, который выполнит роль главного в случае отказа
-текущего. Во втором случае отказоустойчивость обеспечивается выбором нового
-главного узла из оставшихся. Несмотря на то что динамическое задание ролей
-требует наличия специализированного распределенного алгоритма, этот подход
-становится все более и более популярным, поскольку не требует наличия
-простаивающих резервных узлов на случай отказа главного узла.
+кластере выбирается главный (руководящий) узел, который управляет очередью
+задач, планирует их запуск на подчиненных узлах и следит за их состоянием. Роль
+главного узла задается либо /статически/, путем выделения конкретного
+физического узла под нее, либо /динамически/, путем избрания какого-либо из
+узлов кластера главным. В первом случае отказоустойчивость обеспечивается
+посредством резервирования дополнительного свободного узла, который выполнит
+роль главного в случае отказа текущего. Во втором случае отказоустойчивость
+обеспечивается выбором нового главного узла из оставшихся. Несмотря на то что
+динамическое задание ролей требует наличия специализированного распределенного
+алгоритма, этот подход становится все более и более популярным, поскольку не
+требует наличия простаивающих резервных узлов на случай отказа главного узла.
Алгоритмы выбора лидера (которые иногда называют алгоритмами /распределенного
консенсуса/) являются частными случаями волновых алгоритмов. В
@@ -2421,33 +2421,42 @@ cite:tel2000introduction Тель определяет их как алгори
роли главного узла от одного узла к другому, что сделает кластер неуправляемым.
Простейшей такой функцией является позиция IP-адреса узла в диапазоне всех
IP-адресов подсети.
-**** TODO Translate from English version
-В отличие от других алгоритмов выбора лидера
-cite:brunekreef1996design,aguilera2001stable,romano2014design, алгоритм
-субординации не предназначен для управления одновременным обновлением записей в
-распределенной базе данных несколькими параллельными процессами; вместо этого
-основной областью применения алгоритма служит распределение нагрузки на большое
-количество узлов кластера. Обычно, кластер управляет одним главным узлов (или
-1-2 узлами для обеспечения отказоустойчивости), который собирает данные
-мониторинга, ведет учет потребленных пользователями ресурсов, позволяет изменять
-настройки всего кластера и ставит задачи в очередь для запуска. Для больших
-кластеров одного главного узла может быть недостаточно, чтобы справиться с
-нагрузкой, и в этом случае введение подчиненных узлов, управляющих отдельными
-частями кластера, может решить эту проблему.
-
-Алгоритм субординации предполагает, что IP-адрес узла изменяется редко (при
-этом один и тот же IP-адрес необязательно должен быть закреплен за определенным
-узлом). Практика показывает, что это предположение выполняется для кластеров,
-однако это может стать проблемой для виртуальных кластеров, создаваемых на
-ресурсах облачных провайдеров: в таких кластерах IP-адрес может меняться
-произвольно с сохранением DNS-имени узла. Использование алгоритм субординации в
-такой среде может привести к постоянному переназначению ролей узлов кластера,
-что не позволит эффективно распределять нагрузку.
-
-Суммируя вышесказанное, алгоритм субординации не подходит для сред, в которых
-IP-адреса меняются часто, основной сферой применения алгоритма является
-распределение нагрузки на вычислительный кластер и алгоритм не требует
-какой-либо предварительной конфигурации.
+
+Следующие ключевые особенности отличают наш подход от некоторых предложенных
+ранее подходов cite:brunekreef1996design,aguilera2001stable,romano2014design.
+- *Многоуровневая иерархия.* Количество руководящих узлов в сети зависит от
+ значения ветвления. Если оно меньше количества IP-адресов в подсети, то в
+ кластере будет несколько руководящих узлов. Если оно больше или равно
+ количеству IP-адресов в подсети, то в кластере будет только один руководящий
+ узел. Когда какой-либо узел выходит из строя, многоуровневая иерархия
+ изменятся локально, только узлы, примыкающие к вышедшему из строя,
+ взаимодействуют друг с другом.
+- *Отображение IP-адресов.* Поскольку структура иерархии зависит только от
+ IP-адресов узлов, то в алгоритме отсутствует фаза выбора лидера. Чтобы сменить
+ руководителя, каждый узел отправляет сообщение только прежнему и новому
+ руководителю.
+- *Полностью основан на событиях.* Сообщения отправляются только при выходе из
+ строя узла, поэтому постоянной нагрузки на сеть нету. Поскольку алгоритм
+ допускает ошибку при отправке любого сообщения, то нет необходимости в
+ heartbeat-пакетах, являющихся индикацией нахождения узла в сети; вместо этого
+ все сообщения выполняют роль heartbeat-пакетов и настраивается время ожидания
+ отправки пакета.
+- *Отсутствие ручной конфигурации.* Узлу не требуется никаких предварительных
+ знаний, чтобы найти руководителя: он определяет сеть, узлом которой он
+ является, вычисляет IP-адрес потенциального руководителя и отправляет ему
+ сообщение. Если это не срабатывает, то процесс повторяется для следующего
+ потенциального руководителя. Таким образом, алгоритм подходит для начальной
+ загрузки кластера без ручной настройки, для этого требуется только запустить
+ соответствующий сервис на каждом узле.
+Суммируя вышесказанное, достоинством алгоритма является то, что он
+- масштабируется на большое количество узлов посредством иерархии с несколькими
+ руководящими узлами,
+- не нагружает сеть отправкой сообщений с текущим состоянием узлов и
+ heartbeat-пакетами,
+- не требует ручной настройки для первичной загрузки кластера.
+
+
+
**** Построение древовидной иерархии.
Субординация на множестве $\mathcal{N}$ узлов одной подсети определяется как
diff --git a/phd-diss.org b/phd-diss.org
@@ -2273,23 +2273,23 @@ 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.
-There are a few key points that distinguish this approach with respect to some
+The following key features distinguish this approach with respect to some
existing proposals
cite:brunekreef1996design,aguilera2001stable,romano2014design.
-- *Multiple hierarchy levels.* The number of principal nodes in a network depends
- on the fan-out value. If it is lesser than the number of nodes in the network,
- then there are multiple principle nodes in the cluster. If it is greater than
- the number of nodes in the network, then there is only one principal node.
- Multiple hierarchy levels allow changing hierarchy locally (when nodes fail),
- without every change affecting all nodes.
-- *IP-address mapping.* Since node hierarchy solely depends on the nodes' IP
- addresses, there is no election phase in the algorithm. To change the
+- *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 principle 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 tolerating failure of sending any message, there is no need
- in heart-beat messages; all messages play role of heart-beats and packet send
- time-out is adjusted instead.
+ there is no constant load on the network. Since the algorithm allows
+ tolerating 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
@@ -2297,8 +2297,9 @@ cite:brunekreef1996design,aguilera2001stable,romano2014design.
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 with multiple principals in the hierarchy,
-- does not constantly load the network with node state updates and heart-beat
+- 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.
