Load balancing algorithm in a distributed programming system, built on the basis of the HDP protocol.pdf На сегодняшний день большинство программных систем подвергаются внушительным функциональным нагрузкам. Порой система развивается настолько молниеносно, что наращивание мощности аппаратного обеспечения не позволяет адекватно справляться с возрастающей нагрузкой. А в случае высоконагруженных программных систем одного физического узла попросту не хватит, чтобы корректно обработать все поступающие запросы. Поэтому такие системы строятся, как правило, из одинаковых копий узлов, каждый из которых выполняет одинаковые функции, что приводит к возникновению задач маршрутизации и равномерного распределения нагрузки между существующими однотипными узлами программной системы. Также остро стоит вопрос о возможности поддержки: ввод нового узла или вывод старого узла из эксплуатации без полного выключения системы. Все эти задачи ложатся на методы и алгоритмы балансировки, но большинство таких методов и алгоритмов при распределении нагрузки не учитывают реальную ситуацию в текущий момент времени: при изменении набора узлов в них вносятся изменения, а дальше система функционирует без стороннего вмешательства. Важнейшим фактором, приводящим к появлению копий одних и тех же узлов, является и потребность отсутствия единой точки отказа. Система должна быть устойчива к выходу из строя одного или нескольких узлов и продолжать корректно реагировать на поступающие запросы. Такие системы могут быть построены на основе протокола взаимодействия HDP, в котором реализован алгоритм балансировки нагрузки с учетом данных обратной связи, который позволяет в режиме реального времени менять нагрузку на тот или иной узел, чтобы поддерживать оптимальную нагрузку на программную систему в целом. 1. Алгоритмы распределения нагрузки в распределенных системах Балансировка нагрузки - это метод распределения запросов между несколькими одинаковыми узлами распределенной вычислительной системы с целью оптимизации использования всех узлов совместно. Существуют различные алгоритмы балансировки нагрузки, которые имеют разное применение в различных областях, их целью также является обеспечение отказоустойчивости системы в целом. Алгоритм round robin представляет из себя циклический перебор всех узлов по кругу, каждый следующий запрос отправляется на следующий в наборе узел. Главное достоинство - это простота алгоритма, что позволяет использовать его во многих системах, и архитектура таких систем остается максимально простой, так как эксплуатационные особенности системы не вносят дополнительного вклада в сложность архитектуры. Из недостатков алгоритма стоит выделить неравномерное распределение нагрузки, если узлы сети имеют разные технические характеристики. Технически более мощный узел будет лучше справляться с запросами, чем остальные, которые будут более нагружены. Также не решена проблема недоступного узла, т.е. узла, который во время эксплуатации системы внезапно вышел из строя. Алгоритм weighted round robin представляет собой модификацию алгоритма round robin, в которой каждому узлу вручную назначается некий вес - вероятность, с которой балансировщик нагрузки в следующий раз выберет именно этот узел. По сравнению с round robin в данном алгоритме удалось компенсировать возможные технические отличия узлов сети. Из недостатков алгоритма стоит выделить отсутствие решения всех задач отказоустойчивости, ведь если узел сети с высоким приоритетом перестает быть доступным, на него все равно отправляется большинство запросов. 2. Алгоритм распределения нагрузки feedback node в программной системе, использующей протокол HDP для взаимодействия узлов Протокол HDP представляет собой протокол для обмена гетерогенными данными в распределенной вычислительной среде. Протокол использует жестко структурированные данные в формате JSON со специальными служебными метками согласно спецификации протокола. Согласно спецификации протокола все взаимодействующие узлы в HDP делятся на два типа: клиент и поставщик. Клиент - узел, запрашивающий данные. Поставщик - узел, предоставляющий доступ к данным и функциям их обработки. В протоколе заложена возможность указания нескольких узлов: однотипных копий одних и тех же сервисов для того, чтобы была возможность балансировать нагрузку между копиями, выдающими одинаковые данные и предоставляющими одинаковые функции над данными. Предлагаемый автором алгоритм feedback node является алгоритмом распределения нагрузки в программной системе, построенной на основе протокола HDP. Он учитывает гетерогенные данные о текущей загрузке каждого узла и на основе этих данных распределяет между ними нагрузку. На отслеживаемый узел устанавливается агент, который передает серверу данные об общей загрузке, загрузке процессора и использовании памяти на данном узле. Балансировщик HDP на основе этих данных принимает решение о передаче запроса тому или иному узлу в зависимости от его загруженности в текущий момент времени. Среди выбранных отслеживаемых метрик используются: - LA (Load Average) - среднее значение загрузки системы за период в 1 минуту. Значение LA строится на основе процессов, стоящих в очереди ожидания ресурсов, поэтому данное значение трактуется в зависимости от количества ядер процессора: значением по данной метрике является отношение количества ожидающих процессов к общему количеству ядер; - CPU (CPU utilization) - загрузка процессора в текущий момент времени, выраженная в процентах; - MU (Memory usage) - использование памяти, выраженное в процентах относительно общего количеств. Стоит отметить, что алгоритм может подстраиваться к исключению указанных выше метрик или добавлению новых. В любой момент времени на сервере поддерживается в актуальном состоянии список приоритетных узлов, в котором перечислены адреса всех узлов в определенном порядке. Один и тот же узел может быть указан в списке многократно. Балансировщик нагрузки обходит этот список по кругу и передает каждый следующий запрос последовательно следующему узлу, указанному в списке. У этого списка есть предельное время жизни (в секундах), в течение которого список не обновляется и признается актуальным. Предельное время жизни определяется на предположении, что за определенный промежуток времени значения отслеживаемых метрик кардинальным образом не изменятся, поэтому не имеет смысла нагружать узлы лишним получением метрик, тем самым повышая нагрузку на узел. Алгоритм распределения нагрузки feedback node: 1. Присвоить N количество всех доступных однотипных узлов в программной системе. 2. Отправить запросы получения текущих значений LA, CPU, MU всем узлам с установленными агентами. 3.1. Сравнить значения параметра LA у всех узлов. 3.1.1. Если значение параметра LA хотя бы у 2 узлов отличается, то перейти к пункту 3.1.2., иначе перейти к пункту 3.2. 3.1.2. Вычислить SLA - сумму значений всех параметров: N SLA = £ LA,. i=1 3.1.3. Сформировать таблицу «Узел-Значение», где «Значение» вычислить по следующей формуле для каждого узла из списка: SLA SLAi = LA 100 3.1.4. Инвертировать столбец «Значение», перейти к пункту 4. 3.2. Сравнить значения параметра CPU у всех узлов. 3.2.1. Если значение параметра CPU хотя бы у 2 узлов отличается, то перейти к пункту 3.2.2., иначе перейти к пункту 3.3. 3.2.2. Вычислить SCPU- сумму значений всех параметров: N SCPU = 2 CPUi. i=1 3.2.3. Сформировать таблицу «Узел-Значение», где «Значение» вычислить по следующей формуле для каждого узла из списка: SCPU ACPU = CPU-. i i 100 3.2.4. Инвертировать столбец «Значение», перейти к пункту 4. 3.3. Сравнить значения параметра MU у всех узлов. 3.3.1. Если значение параметра MU хотя бы у 2 узлов отличается, то перейти к пункту 3.3.2., иначе составить таблицу «Узел-Значение», в которой каждому узлу поставить 1 в «Значение» и перейти к пункту 4. 3.3.2. Вычислить SMU - сумму значений всех параметров: N SMU = 2 MUt. i=1 3.3.3. Сформировать таблицу «Узел-Значение», где «Значение» вычислить по следующей формуле для каждого узла из списка: SMU AMU = MU-. ' ' 100 3.3.4. Инвертировать столбец «Значение», перейти к пункту 4. 4. Сформировать список приоритетных узлов на основе таблицы «Узел-Значение» следующим образом: обойти таблицу и внести в список один и тот же узел столько раз, сколько указано в столбце «Значение». 5. Первый входящий запрос Ri=\ передать первому узлу из списка. 6. Входящий запрос Ri передать узлу Ri из списка. 7. При получении запроса Rn+i проверить, превышено ли предельное время жизни списка приоритетных узлов. Если время жизни списка было превышено, перейти к пункту 1, иначе присвоить i = 1 и перейти к пункту 5. Заключение В данной работе был проведен анализ проблемы оптимального распределения нагрузки в гетерогенной программной системе, указаны достоинства и недостатки существующих алгоритмов, предложен алгоритм распределения нагрузки, учитывающий обратные данные о текущем состоянии узлов и меняющий вектор нагрузки в режиме реального времени. Данный алгоритм позволяет эффективно использовать имеющиеся аппаратные ресурсы в виде распределенных узлов, равномерная загрузка которых, в свою очередь, ведет к повышению отказоустойчивости системы в целом и уменьшению времени реагирования на поступающие входящие запросы. В будущем данный алгоритм достаточно гибко может подстраиваться под новые метрики и толерантен к включению или выключению учета отдельных метрик в произвольных системах. Это приводит к тому, что данный алгоритм можно применить в высо-конагруженных распределенных программных системах, где крайне важно избежать единой точки отказа, обеспечить отказоустойчивость и сбор метрик не является критичным фактором, способным значительно увеличить общую нагрузку на программную систему.

Скачать электронную версию публикации