arma-thesis

git clone https://git.igankevich.com/arma-thesis.git
Log | Files | Refs | LICENSE

commit eb02a9ff6b9f11137997d3e6536def96630ebfa0
parent edc03d2a68f910f274c68d5daadcadd757482fde
Author: Ivan Gankevich <igankevich@ya.ru>
Date:   Thu, 16 Nov 2017 12:18:34 +0300

Edit X.

Diffstat:
arma-thesis-ru.org | 104++++++++++++++++++++++++++++++++++++++++---------------------------------------
arma-thesis.org | 45+++++++++++++++++++++++----------------------
2 files changed, 76 insertions(+), 73 deletions(-)

diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org @@ -2383,7 +2383,7 @@ OpenGL увеличивает производительность путем и **** Физический уровень. Состоит из узлов и прямых/маршрутизируемых физических сетевых соединений. На этом уровне предполагается полная сетевая связность, т.е.\nbsp{}возможность -отправить сетевой пакет между любой парой узлов кластера. +отправлять сетевые пакеты между любой парой узлов кластера. **** Уровень резидентных процессов. :PROPERTIES: @@ -2395,28 +2395,28 @@ OpenGL увеличивает производительность путем и процесс, поэтому эти понятия взаимозаменяемы в данной работе. Роль главного и подчиненного назначается резидентным процессам динамически, т.е.\nbsp{}любой физический узел может стать главным или подчиненным, или быть и тем, и другим -одновременно. Динамический выбор ролей использует алгоритм выбора лидера, не -требующий периодической отправки широковещательных сообщений всем узлам -кластера, вместо этого роль определяется IP-адресом узла. Подробное описание -алгоритма приведено в разделе\nbsp{}[[#sec-node-discovery]]. Его сильными сторонами -являются масштабируемость на большое количество узлов и низкие накладные -расходы, что делает его пригодным для высокопроизводительных вычислений; его -слабой стороной является искусственная зависимость места, занимаемого узлом в -иерархии, от его IP-адреса, что делает его непригодным для виртуальных сред, где -IP-адрес узла может динамически меняться. +одновременно. Для динамического назначения ролей используется алгоритм выбора +лидера, не требующий периодической отправки широковещательных сообщений всем +узлам кластера, вместо этого роль определяется IP-адресом узла. Подробное +описание алгоритма приведено в разделе\nbsp{}[[#sec-node-discovery]]. Его сильными +сторонами являются масштабируемость на большое количество узлов и низкие +накладные расходы, что делает его пригодным для высокопроизводительных +вычислений; его слабой стороной является искусственная зависимость места, +занимаемого узлом в иерархии, от его IP-адреса, что делает его непригодным для +виртуальных сред, где IP-адрес узла может динамически меняться. Единственное предназначение древовидной иерархии состоит в балансировке нагрузки между узлами кластера. Нагрузка распределяется от текущего узла к его соседям в иерархии путем простой итерации по ним. Когда в иерархии появляются новые связи или меняются старые (из-за того что новый узел присоединяется к кластеру или -работающий узел выходит из строя), резидентные процессы обмениваются -сообщениями, передавая друг другу количество узлов, находящихся /за/ -соответствующей связью в иерархии. Эта информация используется для равномерного -распределения нагрузки, даже если распределенная программа запускается на -подчиненном узле. Кроме того, иерархия уменьшает количество одновременных -сетевых соединений между узлами: на каждую связь в иерархии устанавливается и -поддерживается только одно соединение\nbsp{}--- что уменьшает вероятность -возникновения перегрузки сети при большом количестве узлов в кластере. +работающий узел выходит из строя), резидентные процессы сообщают друг другу +количество узлов, находящихся /за/ соответствующей связью в иерархии. Эта +информация используется для равномерного распределения нагрузки, даже если +распределенная программа запускается на подчиненном узле. Кроме того, иерархия +уменьшает количество одновременных сетевых соединений между узлами: на каждую +связь в иерархии устанавливается и поддерживается только одно +соединение,\nbsp{}--- что уменьшает вероятность возникновения перегрузки сети +при большом количестве узлов в кластере. Балансировка нагрузки реализована следующим образом. Когда узел \(A\) пытается стать подчиненным узлу \(B\), он отправляет сообщение на соответствующий @@ -2436,23 +2436,24 @@ IP-адрес, передавая, сколько узлов уже связан находящимся внизу иерархии, ее управляющие объекты распределяются равномерно между всеми узлами кластера. -Предложенный подход может быть расширен, включив сложную логику в алгоритм -распределения нагрузки. Вместе с количеством узлов, находящихся за связью в -иерархии, может быть отправлена любая метрика, которая необходима для реализации -этой логики. Однако, если эта метрика обновляется чаще, чем изменяется иерархия, -или периодически, то и сообщения с изменениями будут отправляться чаще. Для того -чтобы эти пересылки не повлияли на производительность программ, для них можно -использовать отдельную физическую сеть. Также, когда происходит изменение -иерархии, управляющие объекты, которые уже отправлены на узлы до этого -изменения, не учитываются при распределении нагрузки, из-за чего частые -изменения иерархии могут стать причиной неравномерной загруженности узлов -кластера (которая, однако, станет равномерной со временем). +Предложенный подход может быть расширен путем включения сложной логики в +алгоритм распределения нагрузки. Вместе с количеством узлов, находящихся за +связью в иерархии, может быть отправлена любая метрика, которая необходима для +реализации этой логики. Однако, если эта метрика обновляется чаще, чем +изменяется иерархия, или периодически, то и сообщения о текущем состоянии будут +отправляться чаще. Для того чтобы эти пересылки не повлияли на +производительность программ, для них можно использовать отдельную физическую +сеть. Также, когда происходит изменение иерархии, управляющие объекты, которые +уже отправлены на узлы до этого изменения, не учитываются при распределении +нагрузки, из-за чего частые изменения иерархии могут стать причиной +неравномерной загрузке узлов кластера (которая, однако, станет равномерной со +временем). Динамическое назначение ролей главного и подчиненного узла вместе с распределением управляющих объектов делает архитектуру системы однородной в рамках одного кластера. На каждом узле запущен один и тот же резидентный процесс, и никакой предварительной конфигурации не требуется, чтобы объединить -процессы на разных узлах в иерархию. +процессы, запущенные на разных узлах, в иерархию. **** Уровень управляющих объектов. :PROPERTIES: @@ -2465,23 +2466,23 @@ IP-адрес, передавая, сколько узлов уже связан руководящая задача становится ответственной за перезапуск подчиненной, завершившейся неудачно, на оставшихся узлах кластера. Для того чтобы иметь возможность перезапустить задачу, у которой нету главенствующей над ней задачи, -создается копия, и отправляется на другой узел +создается ее копия, и отправляется на другой узел (см.\nbsp{}разд.\nbsp{}[[#sec-fail-over]]). Существует несколько систем, которые способны выполнять направленные ациклические графы задач параллельно\nbsp{}cite:acun2014charmpp,islam2012oozie, однако, графы не подходят для определения связей руководитель-подчиненный между задачами, поскольку -вершина графа может иметь несколько входящих ребер, а значит несколько -руководящих узлов. +вершина графа может иметь несколько входящих ребер (а значит несколько +руководящих узлов). Основное назначение предлагаемого подхода состоит в упрощении разработки распределенных приложений, работающих в пакетном режиме, и промежуточного -программного обеспечения, а идея состоит в обеспечении отказоустойчивости на -самом низком из возможных уровней. Реализация разделена на два слоя: нижний слой +программного обеспечения. Идея состоит в обеспечении отказоустойчивости на самом +низком из возможных уровней. Реализация разделена на два слоя: нижний слой состоит из подпрограмм и классов для приложений, работающих на одном узле (без взаимодействия по сети), а верхний слой предназначен для приложений, работающих -на произвольном количестве узлов. Предполагается наличие двух типов сильно -связанных сущностей\nbsp{}--- это /управляющие объекты/ (или /объекты/ для -краткости) и /конвейеры/,\nbsp{}--- которые составляют основу программы. +на произвольном количестве узлов. Имеется два типа сильно связанных +сущностей\nbsp{}--- это /управляющие объекты/ (или /объекты/ для краткости) и +/конвейеры/,\nbsp{}--- которые составляют основу программы. Управляющие объекты реализуют логику (порядок выполнения) программы в методах ~act~ и ~react~ и хранят состояние текущей ветки исполнения. Как логика, так и @@ -3194,7 +3195,7 @@ bscheduler.plot_discovery( Если это не срабатывает, то процесс повторяется для следующего потенциального главного узла. Таким образом, алгоритм подходит для начальной загрузки кластера без ручной настройки, для этого требуется только запустить - соответствующий сервис на каждом узле. + соответствующий резидентный процесс на каждом узле. Суммируя вышесказанное, достоинством алгоритма является то, что он - масштабируется на большое количество узлов посредством иерархии с несколькими главными узлами, @@ -3372,18 +3373,19 @@ Keepalived\nbsp{}cite:cassen2002keepalived. /руководитель-подчиненный/. Если связь установлена между двумя управляющими объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо /родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни -один управляющий объект не может иметь связь с сервисом, и наоборот. Поскольку -иерархия сервисом используется для распределения нагрузки на узлы кластера, -иерархия управляющих объектов отображается на нее, и это отображение может быть -произвольным: обычна ситуация, когда руководящий управляющий объект находится на -подчиненном узле, а его подчиненные управляющие объекты распределены равномерно -между всеми узлами кластера (включая узел, где находится руководящий объект). -Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются -предпочтительными для высоко параллельных программ, так как в них меньше -количество промежуточных узлов, через которые должны пройти управляющие объекты -при распределении между узлами кластера. Поскольку существует однозначное -соответствие между резидентными процессами и узлами кластера, в данной работе -они используются как взаимозаменяемые термины. +один управляющий объект не может иметь связь с резидентным процессом, и +наоборот. Поскольку иерархия резидентных процессов используется для +распределения нагрузки на узлы кластера, иерархия управляющих объектов +отображается на нее, и это отображение может быть произвольным: обычна ситуация, +когда руководящий управляющий объект находится на подчиненном узле, а его +подчиненные управляющие объекты распределены равномерно между всеми узлами +кластера (включая узел, где находится руководящий объект). Обе иерархии может +быть сколь угодно глубокими, но "неглубокие" являются предпочтительными для +высоко параллельных программ, так как в них меньше количество промежуточных +узлов, через которые должны пройти управляющие объекты при распределении между +узлами кластера. Поскольку существует однозначное соответствие между +резидентными процессами и узлами кластера, в данной работе они используются как +взаимозаменяемые термины. **** Обработка выхода узлов из строя. Основной стратегией при выходе из строя подчиненного узла является перезапуск diff --git a/arma-thesis.org b/arma-thesis.org @@ -2304,11 +2304,12 @@ execution time. If such formula did not exist or did not have all integrals as Fourier transforms, velocity potential field computation would consume much more time. +#+LATEX: \pagebreak ** Fault-tolerant batch job scheduler *** System architecture **** Physical layer. Consists of nodes and direct/routed physical network links. On this layer full -network connectivity, i.e.\nbsp{}an ability to send network packet between any +network connectivity, i.e.\nbsp{}an ability to send network packets between any pair of cluster nodes. **** Daemon process layer. @@ -2321,7 +2322,7 @@ Consists of daemon processes running on cluster nodes and hierarchical per node, so these terms are use interchangeably in this work. Master and slave roles are dynamically assigned to daemon processes, i.e.\nbsp{}any physical cluster node may become a master or a slave, or both simultaneously. Dynamic -reassignment uses leader election algorithm that does not require periodic +role assignment uses leader election algorithm that does not require periodic broadcasting of messages to all cluster nodes, instead the role is determined by node's IP address. Detailed explanation of the algorithm is provided in\nbsp{}[[#sec-node-discovery]]. Its strengths are scalability to a large number of @@ -2334,20 +2335,20 @@ The only purpose of tree hierarchy is to balance the load between cluster nodes. The load is distributed from the current node to its neighbours in the hierarchy by simply iterating over them. When new links appear in the hierarchy or old links change (due to new node joining the cluster or due to node failure), -daemons exchange messages telling each other how many daemons are /behind/ the +daemon processes communicate each other the number of processes /behind/ the corresponding link in the hierarchy. This information is used to distribute the -load evenly, even if a distributed programme is launched on a slave node. In +load evenly, even if distributed programme is launched on slave node. In addition, this hierarchy reduces the number of simultaneous network connections between nodes: only one network connection is established and maintained for each hierarchical link\nbsp{}--- this decreases probability of network -congestion when there are large number of nodes in the cluster. +congestion when there is a large number of nodes in the cluster. Load balancing is implemented as follows. When node \(A\) tries to become a subordinate of node \(B\), it sends a message to a corresponding IP address -telling how many daemons are already linked to it in the hierarchy (including -itself). After all hierarchical links are established, every node has enough -information to tell, how many nodes exist behind each link. If the link is -between a slave and a master, and the slave wants to know, how many nodes are +telling how many daemon processes are already linked to it in the hierarchy +(including itself). After all hierarchical links are established, every node has +enough information to tell, how many nodes exist behind each link. If the link +is between a slave and a master, and the slave wants to know, how many nodes are behind the link to the master, then it subtracts the total number of nodes behind all of its slave nodes from the total number of nodes behind the master to get the correct amount. To distribute kernels @@ -2362,7 +2363,7 @@ The proposed approach can be extended to include sophisticated logic into load distribution algorithm. Along with the number of nodes behind the hierarchical link, any metric, that is required to implement this logic, can be sent. However, if an update of the metric happens more frequently, than a change in -the hierarchy occurs, or it changes periodically, then update messages will be +the hierarchy occurs, or it changes periodically, then status messages will be also sent more frequently. To ensure that this transfers do not affect programmes' performance, a separate physical network may be used to transmit the messages. The other disadvantage is that when reconfiguration of the hierarchy @@ -2371,9 +2372,9 @@ account in the load distribution, so frequent hierarchy changes may cause uneven load on cluster nodes (which, however, balances over time). Dynamic master/slave role assignment coupled with kernel distribution makes -overall system architecture homogeneous within single cluster. On every node the -same daemon is run, and no prior configuration is needed to construct a -hierarchy of daemons processes. +overall system architecture homogeneous within the framework of single cluster. +On every node the same daemon is run, and no prior configuration is needed to +construct a hierarchy of daemons processes running on different nodes. **** Control flow objects layer. :PROPERTIES: @@ -2389,17 +2390,17 @@ sent to a different node (see\nbsp{}sec.\nbsp{}[[#sec-fail-over]]). There exists number of systems that are capable of executing directed acyclic graphs of tasks in parallel\nbsp{}cite:acun2014charmpp,islam2012oozie, but graphs are not suitable to determine principal-subordinate relationship between tasks, because -a node in the graph may have multiple incoming edges (multiple principal nodes). +a node in the graph may have multiple incoming edges (and hence multiple +principal nodes). The main purpose of the proposed approach is to simplify development of -distributed batch processing applications and middleware. The main focus is to -make application resilient to failures, i.e. make it fault tolerant on the -lowest possible level. The implementation is divided into two layers: the lower -layer consists of routines and classes for single node applications (with no -network interactions), and the upper layer for applications that run on an -arbitrary number of nodes. There are two kinds of tightly coupled -entities\nbsp{}--- /control flow objects/ (or /kernels/ for short) and -/pipelines/\nbsp{}--- which compose a programme base. +distributed batch processing applications and middleware. The idea is to provide +resilience to failures on the lowest possible level. The implementation is +divided into two layers: the lower layer consists of routines and classes for +single node applications (with no network interactions), and the upper layer for +applications that run on an arbitrary number of nodes. There are two kinds of +tightly coupled entities\nbsp{}--- /control flow objects/ (or /kernels/ for +short) and /pipelines/\nbsp{}--- which form a basis of the programme. Kernels implement control flow logic in theirs ~act~ and ~react~ methods and store the state of the current control flow branch. Both logic and state are