Введение
Набор методов для улучшения распределения рабочей нагрузки между множеством вычислительных ресурсов.
В вычислительной технике балансировка нагрузки – это процесс распределения набора задач по набору ресурсов (вычислительных единиц) с целью повышения эффективности их общей обработки. Балансировка нагрузки позволяет оптимизировать время отклика и избежать неравномерной перегрузки одних вычислительных узлов, в то время как другие остаются простаивать. Балансировка нагрузки является областью исследований в сфере параллельных вычислений. Существуют два основных подхода: статические алгоритмы, которые не учитывают состояние отдельных машин, и динамические алгоритмы, которые, как правило, более универсальны и эффективны, но требуют обмена информацией между различными вычислительными единицами, что может привести к снижению эффективности.
Обзор проблемы
Алгоритм балансировки нагрузки всегда стремится решить определенную задачу. При этом необходимо учитывать природу задач, алгоритмическую сложность, аппаратную архитектуру, на которой будут выполняться алгоритмы, а также требуемый уровень допустимости ошибок. Следовательно, необходимо найти компромисс, который наилучшим образом соответствует специфическим требованиям приложения.
Характер задач
Эффективность алгоритмов балансировки нагрузки критически зависит от природы задач. Следовательно, чем больше информации о задачах доступно в момент принятия решения, тем выше потенциал для оптимизации.
Размер задач
Совершенное знание времени выполнения каждой из задач позволяет достичь оптимального распределения нагрузки (см. алгоритм вычисления префиксной суммы). К сожалению, это на практике идеализированный случай. Знание точного времени выполнения каждой задачи – крайне редкое явление. Поэтому существует несколько методов, позволяющих оценить различные времена выполнения. Прежде всего, в благоприятном сценарии, когда задачи имеют относительно однородный размер, можно предположить, что каждой из них потребуется приблизительно среднее время выполнения. Если же время выполнения сильно неравномерно, необходимо использовать более сложные техники. Один из таких методов – добавление метаданных к каждой задаче. На основе времени выполнения аналогичных метаданных в прошлом можно делать прогнозы для будущих задач, используя статистические данные.
Зависимые страны
В некоторых случаях задачи зависят друг от друга. Эти взаимозависимости можно проиллюстрировать ориентированным ациклическим графом. Интуитивно понятно, что некоторые задачи не могут быть начаты, пока другие не будут завершены. Если предположить, что время, необходимое для выполнения каждой задачи, известно заранее, то оптимальный порядок выполнения должен приводить к минимизации общего времени выполнения. Хотя это NP-трудная задача, и поэтому точное решение может быть сложным. Существуют алгоритмы, такие как планировщик задач, которые вычисляют оптимальное распределение задач, используя метаэвристические методы.
Разделение задач
Еще одной особенностью задач, критически важных для проектирования алгоритма балансировки нагрузки, является возможность их декомпозиции на подзадачи в процессе выполнения. Алгоритм "Tree Shaped Computation", представленный далее, в полной мере использует эту особенность.
Статика
Алгоритм балансировки нагрузки считается "статическим", если при распределении задач он не учитывает текущее состояние системы. Под состоянием системы понимаются такие показатели, как уровень загрузки (иногда даже перегрузки) отдельных процессоров. Вместо этого заранее делаются предположения об общей системе, например, о времени поступления и потребностях в ресурсах входящих задач. Также известно количество процессоров, их производительность и скорость обмена данными. Таким образом, статическая балансировка нагрузки стремится сопоставить известный набор задач с доступными процессорами для минимизации определенной функции производительности. Ключевым моментом является выбор этой функции производительности. Методы статической балансировки нагрузки обычно централизованы вокруг маршрутизатора или главного узла, который распределяет задачи и оптимизирует функцию производительности. Эта минимизация может учитывать информацию о задачах, подлежащих распределению, и на ее основе вычислять ожидаемое время выполнения. Преимущество статических алгоритмов заключается в простоте настройки и высокой эффективности при работе с достаточно однородными задачами (например, обработкой HTTP-запросов с веб-сайта). Однако при распределении задач все равно сохраняется некоторая статистическая изменчивость, которая может привести к перегрузке отдельных вычислительных узлов.
Динамическая
В отличие от статических алгоритмов распределения нагрузки, динамические алгоритмы учитывают текущую нагрузку каждого из вычислительных блоков (также называемых узлами) в системе. При таком подходе задачи могут динамически перемещаться с перегруженного узла на недогруженный для ускорения обработки. Хотя разработка этих алгоритмов значительно сложнее, они способны демонстрировать отличные результаты, особенно когда время выполнения задач существенно различается. Архитектура динамической балансировки нагрузки может быть более модульной, поскольку не требует выделения конкретного узла для распределения работы. Если задачи однозначно назначаются процессору в зависимости от их состояния в текущий момент времени, это называется однозначным назначением. Если же задачи могут постоянно перераспределяться в соответствии с состоянием системы и её изменениями, это называется динамическим назначением. Очевидно, что алгоритм балансировки нагрузки, требующий избыточных коммуникаций для принятия решений, рискует замедлить решение общей задачи.
Гетерогенные машины
Параллельные вычислительные инфраструктуры часто состоят из узлов с разной вычислительной мощностью, что необходимо учитывать при распределении нагрузки. Например, узлы с меньшей мощностью могут получать запросы, требующие меньшего объема вычислений, или, в случае однородных или неизвестных размеров запросов, обрабатывать меньше запросов, чем узлы большей мощности.
Общая и распределенная память
Параллельные компьютеры часто разделяют на две широкие категории: компьютеры, в которых все процессоры используют единую общую память для параллельного чтения и записи данных (модель PRAM), и компьютеры, в которых каждый вычислительный узел имеет собственную память (модель распределенной памяти), а обмен информацией осуществляется посредством сообщений. В компьютерах с общей памятью управление конфликтами записи существенно замедляет скорость индивидуального выполнения каждого вычислительного узла. Однако они способны эффективно работать параллельно. В то же время, в случае обмена сообщениями каждый процессор может работать на максимальной скорости. С другой стороны, при коллективном обмене сообщениями все процессоры вынуждены ждать, пока самые медленные процессоры не начнут фазу коммуникации. В реальности, немногие системы полностью соответствуют одной из этих категорий. Как правило, каждый процессор имеет внутреннюю память для хранения данных, необходимых для последующих вычислений, и процессоры организованы в иерархические кластеры. Часто координация этих вычислительных элементов осуществляется посредством распределенной памяти и передачи сообщений. Следовательно, алгоритм балансировки нагрузки должен быть специально адаптирован к параллельной архитектуре. В противном случае существует риск значительного снижения эффективности параллельного решения задач.
Иерархия
Приспосабливаясь к описанным выше аппаратным структурам, можно выделить две основные категории алгоритмов балансировки нагрузки. С одной стороны, это схема, в которой задачи назначаются "мастером" и выполняются "рабочими", которые информируют "мастера" о ходе выполнения, позволяя ему при динамическом алгоритме назначать или перераспределять нагрузку. В литературе это называется архитектурой "мастер-рабочий". С другой стороны, управление может быть распределено между различными узлами. В этом случае алгоритм балансировки нагрузки выполняется на каждом узле, а ответственность за назначение задач (а также их перераспределение и разделение, при необходимости) распределяется между ними. Последняя категория подразумевает использование динамического алгоритма балансировки нагрузки. Поскольку каждый алгоритм балансировки нагрузки имеет уникальную конструкцию, необходимо уточнить предыдущее различие. Таким образом, возможны и промежуточные стратегии, например, "мастер-узлы" для каждого подкластера, которые, в свою очередь, подчиняются глобальному "мастеру". Существуют также многоуровневые организации, сочетающие в себе стратегии "мастер-подчиненный" и распределенного управления. Последние стратегии быстро усложняются и встречаются редко. Разработчики предпочитают алгоритмы, которыми легче управлять.
Адаптация к более крупным архитектурам (масштабируемость)
В контексте алгоритмов, работающих в течение очень длительного времени (серверы, облачные вычисления), компьютерная архитектура со временем меняется. Однако предпочтительнее не разрабатывать новый алгоритм каждый раз. Поэтому крайне важным параметром алгоритма балансировки нагрузки является его способность адаптироваться к масштабируемой аппаратной архитектуре. Это называется масштабируемостью алгоритма. Алгоритм считается масштабируемым для заданного входного параметра, если его производительность остаётся относительно независимой от величины этого параметра. Если алгоритм способен адаптироваться к различному количеству вычислительных узлов, но их количество должно быть зафиксировано перед началом выполнения, он называется адаптируемым (moldable). Если же алгоритм способен работать с изменяющимся количеством процессоров в процессе выполнения, то он считается гибким (malleable). Большинство алгоритмов балансировки нагрузки, по крайней мере, являются адаптируемыми.
Допустимость неисправности
Особенно в крупномасштабных вычислительных кластерах недопустимо выполнять параллельный алгоритм, не способный выдержать отказ одного единственного компонента. Поэтому разрабатываются отказоустойчивые алгоритмы, которые могут обнаруживать выход из строя процессоров и восстанавливать вычисления.
Статическое распределение с полным знанием задач: префикс сумма
Если задачи независимы друг от друга и допускают разделение на подзадачи, существует простой и оптимальный алгоритм. Разделив задачи таким образом, чтобы каждому процессору был выделен одинаковый объем вычислений, останется лишь собрать результаты воедино. С помощью алгоритма вычисления префиксных сумм такое разделение можно вычислить за логарифмическое время относительно числа процессоров. Однако, если задачи нельзя разделить (то есть они являются атомарными), хотя оптимизация распределения задач – сложная проблема, все же можно добиться приблизительно справедливого распределения, при условии, что размер каждой задачи значительно меньше общего объема вычислений, выполняемого каждым узлом.
Схема "Мастер-работник"
Схемы Master Worker относятся к числу самых простых алгоритмов динамического балансирования нагрузки. Главный узел распределяет рабочую нагрузку между всеми рабочими (иногда называемыми "подчинёнными"). Изначально все рабочие простаивают и сообщают об этом главному узлу. Главный узел отвечает на запросы рабочих и распределяет задачи между ними. Когда у него не остаётся задач, он уведомляет рабочих, чтобы они прекратили запрашивать новые задачи. Преимущество этой системы заключается в очень справедливом распределении нагрузки. Фактически, если не учитывать время, необходимое для назначения задач, время выполнения будет сопоставимо с суммой префиксов, рассмотренной выше. Проблема этого алгоритма в том, что ему сложно адаптироваться к большому числу процессоров из-за большого объёма необходимых коммуникаций. Это отсутствие масштабируемости быстро делает его неприменимым на очень больших серверах или очень больших параллельных компьютерах. Главный узел становится узким местом. Однако качество алгоритма можно значительно улучшить, заменив главный узел списком задач, к которому могут обращаться различные процессоры. Хотя этот алгоритм немного сложнее в реализации, он обещает гораздо лучшую масштабируемость, хотя её всё ещё недостаточно для очень крупных вычислительных центров.
Неиерархическая архитектура, без знания системы: кража работы
Еще один метод преодоления проблем масштабируемости, когда время, необходимое для завершения задачи, неизвестно, — это перераспределение задач. Подход заключается в назначении каждому процессору определенного количества задач случайным или предопределенным образом, а затем в предоставлении неактивным процессорам возможности "перехватывать" работу у активных или перегруженных процессоров. Существует несколько реализаций этой концепции, определяемых моделью разделения задач и правилами, регулирующими обмен между процессорами. Хотя эта техника может быть особенно эффективной, ее сложно реализовать, поскольку необходимо обеспечить, чтобы коммуникация не стала основной деятельностью процессоров, отвлекая их от решения задачи. В случае атомных задач можно выделить две основные стратегии: когда процессоры с низкой загрузкой предлагают свои вычислительные ресурсы тем, у кого самая высокая загрузка, и когда наиболее загруженные процессоры стремятся уменьшить свою рабочую нагрузку. Было показано, что при высокой загруженности сети более эффективно, если наименее загруженные процессоры предлагают свою доступность, а при низкой загруженности сети именно перегруженные процессоры нуждаются в поддержке со стороны наиболее неактивных. Это эмпирическое правило ограничивает количество обмениваемых сообщений. В случае, когда исходной является одна большая задача, которую нельзя разделить ниже атомного уровня, существует очень эффективный алгоритм "вычисления в форме дерева", при котором родительская задача распределяется по рабочему дереву.
Принцип
Первоначально большинство процессоров имеют пустую задачу, за исключением одного, который работает над ней последовательно. Процессоры, находящиеся в режиме простоя, случайным образом отправляют запросы другим процессорам (не обязательно активным). Если принимающий процессор способен разделить задачу, над которой он работает, он делает это, отправляя часть работы узлу, отправившему запрос. В противном случае он возвращает пустую задачу. Это приводит к формированию древовидной структуры. Затем необходимо отправить сигнал завершения родительскому процессору, когда подзадача будет выполнена, чтобы тот, в свою очередь, отправил сообщение своему родителю, пока оно не достигнет корня дерева. Когда первый процессор, то есть корневой, завершит работу, можно широковещательно отправить глобальное сообщение о завершении. В конечном итоге необходимо собрать результаты, пройдя по дереву снизу вверх.
Эффективность
Эффективность такого алгоритма приближается к эффективности вычисления префиксной суммы, когда время разделения задач и время обмена данными не слишком велико по сравнению с объемом выполняемой работы. Чтобы избежать чрезмерных затрат на связь, можно представить список задач, хранящийся в общей памяти. Следовательно, запрос представляет собой просто чтение из определенной позиции в этой общей памяти по запросу главного процессора.
Случаи использования
В дополнение к эффективному решению задач посредством параллельных вычислений, алгоритмы балансировки нагрузки широко применяются в управлении HTTP-запросами, когда сайту с большой аудиторией необходимо обрабатывать значительное количество запросов в секунду.
Интернет-услуги
Одним из наиболее часто используемых применений балансировки нагрузки является предоставление единой интернет-услуги с нескольких серверов, иногда называемых серверной фермой. К обычно балансируемым системам относятся популярные веб-сайты, крупные сети интернет-релейного чата (IRC), сайты протокола передачи файлов (FTP) с высокой пропускной способностью, серверы протокола передачи новостей (NNTP), серверы системы доменных имен (DNS) и базы данных.
Раунд-робин DNS
Round robin DNS — это альтернативный метод балансировки нагрузки, который не требует выделенного программного или аппаратного узла. В этой технике несколько IP-адресов ассоциируются с одним доменным именем, а клиентам IP-адреса выдаются поочередно. IP-адрес назначается клиентам с коротким временем жизни (TTL), поэтому при следующем обращении клиент, скорее всего, получит другой IP-адрес для запрашиваемой интернет-услуги.
Случайная балансировка нагрузки со стороны клиента
Другой подход к балансировке нагрузки заключается в предоставлении клиенту списка IP-адресов серверов, после чего клиент случайным образом выбирает IP-адрес из этого списка при каждом подключении. Этот метод в значительной степени опирается на то, что все клиенты создают схожую нагрузку, и на закон больших чисел. Некоторые приложения запрограммированы так, чтобы быть устойчивыми к этой проблеме, смещая точку балансировки нагрузки на различные платформы обмена данными за пределы определенной сети. Последовательные алгоритмы, используемые в этих функциях, определяются гибкими параметрами, уникальными для конкретной базы данных.
Алгоритмы планирования
Многочисленные алгоритмы планирования, также называемые методами балансировки нагрузки, используются балансировщиками нагрузки для определения, на какой сервер-бэкенд отправить запрос. Простые алгоритмы включают случайный выбор, метод "round robin" (циклический перебор) или наименьшее количество соединений. Более сложные балансировщики нагрузки могут учитывать дополнительные факторы, такие как сообщаемая сервером нагрузка, минимальное время отклика, статус доступности (определяемый посредством мониторинга), количество активных соединений, географическое положение, возможности сервера или объем трафика, назначенный ему в последнее время.
Настойчивость
Важным вопросом при эксплуатации сервиса с балансировкой нагрузки является то, как обрабатывать информацию, которую необходимо сохранять между несколькими запросами в сессии пользователя. Если эта информация хранится локально на одном из серверных узлов, то последующие запросы, направленные на другие серверные узлы, не смогут ее найти. Это может быть кэшированная информация, которую можно пересчитать, в этом случае балансировка нагрузки запроса на другой серверный узел лишь приводит к снижению производительности. Концепция Rbridges была впервые предложена Институту инженеров электротехники и электроники в 2004 году, который в 2005 году отклонил то, что впоследствии стало известно как TRILL, а в период с 2006 по 2012 год разработал несовместимую вариацию, известную как Shortest Path Bridging. IEEE одобрил стандарт IEEE 802.1aq в мае 2012 года, также известный как Shortest Path Bridging (SPB). SPB позволяет использовать все каналы связи по нескольким равноценным путям, обеспечивает более быстрое время сходимости для сокращения времени простоя и упрощает использование балансировки нагрузки в топологиях сети с ячеистой структурой (частично или полностью соединенных), позволяя трафику распределять нагрузку по всем путям сети. SPB разработан для практически полного исключения человеческого фактора при настройке и сохранения принципа Plug and Play, благодаря которому Ethernet стал де-факто протоколом второго уровня.
Маршрутизация 1
Многие телекоммуникационные компании имеют несколько маршрутов в своих сетях или для соединения с внешними сетями. Они используют сложное распределение нагрузки для перенаправления трафика с одного пути на другой, чтобы избежать перегрузки сети на отдельных каналах связи, а также для минимизации стоимости транзита через внешние сети или повышения надежности сети. Распределение нагрузки также может применяться в задачах мониторинга сети. Балансировщики нагрузки позволяют разделять большие потоки данных на несколько подпотоков и использовать несколько сетевых анализаторов, каждый из которых обрабатывает часть исходных данных. Это особенно полезно для мониторинга высокоскоростных сетей, таких как 10GbE или STM64, где сложная обработка данных в реальном времени может быть невозможна.
Сети центров обработки данных
Балансировка нагрузки широко используется в сетях центров обработки данных для распределения трафика по множеству существующих путей между любыми двумя серверами. Это позволяет более эффективно использовать пропускную способность сети и снижает затраты на выделение ресурсов. В общем случае, балансировку нагрузки в сетях центров обработки данных можно классифицировать как статическую или динамическую. Статическая балансировка нагрузки распределяет трафик, вычисляя хеш-функцию от адресов источника и назначения, а также номеров портов трафика, и используя ее для определения, как потоки назначаются одному из существующих путей. Динамическая балансировка нагрузки назначает потоки трафика путям, отслеживая использование пропускной способности на различных путях. Динамическое назначение может быть как проактивным, так и реактивным. В первом случае назначение фиксируется после его выполнения, а во втором сетевая логика непрерывно отслеживает доступные пути и перераспределяет потоки между ними по мере изменения загрузки сети (при появлении новых потоков или завершении существующих). Доступен всесторонний обзор балансировки нагрузки в сетях центров обработки данных.