Балансировка нагрузки

Алгоритм балансировки нагрузки всегда решает определённую задачу. При этом необходимо учитывать, в частности, характер задач, алгоритмическую сложность, аппаратную архитектуру, на которой работают алгоритмы, а также требуемую степень отказоустойчивости. Поэтому приходится находить компромисс, чтобы наилучшим образом удовлетворить специфическим требованиям приложений.

Эффективность алгоритмов балансировки нагрузки критически зависит от характера задач. Чем больше информации о задачах известно в момент принятия решения, тем выше потенциал для оптимизации.

Совершенное знание времени выполнения каждой задачи позволяет достичь оптимального распределения нагрузки (см. алгоритм префиксной суммы)^[1]. К сожалению, такая ситуация встречается крайне редко. Точное знание времени выполнения каждой задачи является исключительным случаем.

Поэтому существуют различные техники для получения представления о временах выполнения. Прежде всего, если задачи относительно однородны по размеру, можно считать, что каждая из них займёт примерно среднее время выполнения. Если же время выполнения сильно варьируется, применяются более сложные методы, например добавление к каждой задаче метаданных. Ориентируясь на предыдущее время выполнения для похожих метаданных, можно делать статистические оценки для ожидаемых задач^[2].

В некоторых случаях задачи зависят друг от друга — их взаимозависимости можно изобразить в виде ориентированного ациклического графа. Некоторые задачи не могут начинаться до выполнения других.

Предполагая, что требуется заранее известное время для каждой задачи, оптимальный порядок выполнения минимизирует общее время обработки. Однако данная задача относится к классу NP-трудных, то есть решение в общем случае затруднено. Существуют алгоритмы, например планировщики заданий, которые рассчитывают оптимальное распределение задач, используя метаэвристические методы.

Важным свойством задач для проектирования алгоритма балансировки нагрузки является степень, в которой их можно разбивать на подзадачи во время выполнения. Описанный далее алгоритм «древовидных вычислений» эффективно использует это свойство.

Алгоритм балансировки нагрузки считается «статическим», если при распределении задач не учитывается состояние системы. Параметры состояния могут включать уровень нагрузки (и даже перегрузки) отдельных процессоров. Вместо этого заранее принимаются предположения о системе — например о времени поступления и ресурсных требованиях входящих задач, известно число процессоров, их производительность и скорость обмена. Таким образом, статическая балансировка заключается в сопоставлении известного набора задач доступным процессорам для минимизации функции эффективности. Особенность состоит в самом определении этой функции.

Типично статические схемы централизованы вокруг роутера или мастера, который распределяет задачи и оптимизирует функцию производительности, иногда с учётом параметров задач, рассчитывая ожидаемое время выполнения.

Преимущество статических алгоритмов — простота реализации и высокая эффективность при обработке однородных задач (например, при обработке HTTP-запросов веб-сайта). Однако сохраняется статистическая дисперсия в назначении задач, что может привести к перегрузке отдельных вычислительных единиц.

В отличие от статических алгоритмов, динамические схемы учитывают текущую загрузку каждого вычислительного узла (также называемого узлом или нодой). В этой парадигме возможно динамическое перемещение задач от перегруженного узла к менее загруженному для ускорения обработки. Хотя эти алгоритмы сложнее в разработке, они обеспечивают отличные результаты, особенно если время выполнения варьируется от задачи к задаче.

Архитектура динамической балансировки может быть более модульной, поскольку не требуется выделенного узла для распределения работ. Если задачи закрепляются за процессорами разово, это уникальное (единожды назначение); если задачи могут перераспределяться в зависимости от состояния и его изменений, это динамическое назначение^[3]. Очевидно, что алгоритм, требующий чрезмерных коммуникаций для принятия решений, рискует замедлить решение основной задачи.

Параллельные вычислительные системы часто состоят из разнородных по производительности узлов, что нужно учитывать при распределении нагрузки.

К примеру, менее мощные узлы могут получать задачи, требующие меньших вычислений, либо, при однородных или неизвестных размерах запросов, получать меньшее их количество по сравнению с более мощными элементами.

Параллельные компьютеры обычно делятся на системы с общей памятью (одна разделяемая память для всех процессоров, PRAM) и системы с распределённой памятью (каждый узел имеет собственную память, обмен информацией происходит через сообщения).

В архитектурах с общей памятью разрешение конфликтов записей значительно замедляет исполнение отдельных вычислительных единиц, хотя они могут работать параллельно. В системах с обменом сообщениями каждый процессор может работать на полной скорости до фазы коллективного обмена, после чего ожидание тормозится медленнейшими узлами.

Большинство реальных систем совмещают элементы обеих моделей: у каждого процессора есть собственная память, а между кластерами реализованы механизмы распределённой памяти и передачи сообщений. Алгоритм балансировки при этом должен быть специально адаптирован к конкретной параллельной архитектуре — иначе эффективность снижается.

С учётом структур аппаратных платформ выделяют две основные категории алгоритмов балансировки нагрузки. С одной стороны, задачи назначаются «мастером» и исполняются «воркерами», уведомляющими мастера о ходе выполнения — мастер может производить переназначение в случае динамического алгоритма. Такая организация называется архитектурой master-worker. С другой стороны, контроль может быть распределён между всеми узлами: алгоритм балансировки запускается на каждом из них, а ответственность за назначение (и при необходимости, перераспределение и декомпозицию задач) делится между ними.

Возможны и промежуточные стратегии — например, «мастера» для подкластеров, подчиняющиеся глобальному мастеру, или многоуровневые схемы, чередующие master-slave и распределённое управление. Однако такие схемы быстро усложняются и реже применяются на практике, уступая более управляемым алгоритмам.

Для алгоритмов, непрерывно работающих на протяжении долгого времени (серверы, облачные инфраструктуры и др.), аппаратная архитектура со временем меняется. Желательно, чтобы не приходилось проектировать новый алгоритм при каждом изменении.

Критическим свойством алгоритма балансировки выступает способность адаптироваться к масштабируемой архитектуре, или масштабируемость. Алгоритм считается масштабируемым для некоторого параметра, если его производительность мало зависит от размера этого параметра.

Если алгоритм способен работать с переменным числом вычислительных узлов, но их количество фиксируется до запуска, он называется формуемым (англ. moldable). Если число узлов может меняться по ходу работы, алгоритм маллеабелен (англ. malleable). Большинство алгоритмов балансировки хотя бы формуемы^[4].

Особенно в крупных вычислительных кластерах недопустимо запускать параллельный алгоритм, не способный выдержать отказ хотя бы одного компонента. Поэтому ведётся разработка отказоустойчивых алгоритмов, способных обнаруживать выход узлов из строя и восстанавливать вычисления^[5].

Если задачи независимы и их время выполнения известно, а также допускается разбивка задач — существует простой и оптимальный алгоритм.

Разделив работу так, чтобы каждый процессор получил равное количество вычислений, остаётся только собрать результаты. Используя алгоритм префиксных сумм, это разделение можно вычислить за логарифмическое время относительно числа процессоров.

Если же задачи неделимы (атомарны), задача распределения сложна, но, если размер отдельной задачи невелик по отношению к общей работе на каждом узле, возможно достаточно приближённое равномерное распределение^[1]

На практике время выполнения задачи обычно неизвестно, доступны лишь грубые оценки. Поэтому данный алгоритм хотя и эффективен, подходит не для всех ситуаций.

Даже когда время выполнения заранее неизвестно, возможно использовать статическое распределение.

В циклической (англ. round robin) схеме первый запрос направляется первому серверу, следующий — второму и так далее по кругу до последнего сервера. Затем цикл повторяется.

Данный подход может быть взвешен: более мощные узлы получают большее число запросов и раньше остальных.

Случайная статическая схема подразумевает случайное распределение задач между серверами. Эта стратегия работает достаточно хорошо. Если количество задач известно заранее, можно ещё более эффективно заранее вычислить случайную перестановку, чтобы снизить расходы на коммуникации — каждому процессору сразу известна его задача. Даже при неизвестном количестве задач удаётся снизить коммуникационные издержки с помощью общеизвестного псевдослучайного назначения, синхронизированного для всех процессоров.

Однако эффективность этой стратегии (по времени выполнения фиксированного набора задач) падает при увеличении максимального размера отдельной задачи.

Существуют и другие методы назначения:

• Наименьшая загрузка: больше задач тем серверам, которые справляются с ними быстрее (метод возможно взвешивать).
• Хеширование: распределение через хеш-таблицу.
• «Сила двух выборов» (англ. power of two choices): случайным образом выбираются два сервера, задача направляется наименьше загруженному из них.^[6].^[7]

Архитектуры типа master-worker (или мастер-подчинённый) — одни из простейших динамических алгоритмов балансировки нагрузки. Мастер распределяет задачи между воркерами (реже — «слэйвами»). Все воркеры изначально бездействуют и сообщают об этом мастеру. Мастер отвечает на запросы воркеров, выдаёт им задачи и, завершив раздачу, оповещает об отсутствии работ.

Преимущество подхода — очень равномерное распределение нагрузки. Если не учитывать время, затрачиваемое на назначение задач, время выполнения приближается к результату префиксной суммы.

Недостаток — низкая масштабируемость вследствие большого числа коммуникаций; для очень крупных систем схема быстро становится неэффективной, так как мастер превращается в узкое место.

Качество алгоритма можно повысить, заменив мастера списком задач, к которому обращаются различные процессоры. При чуть более сложной реализации достигается лучшая масштабируемость, но всё ещё недостаточная для крупных вычислительных центров.

Ещё одна стратегия для решения проблем масштабирования при неизвестном времени завершения задач — ворк-стилинг (англ. work stealing).

Каждому процессору изначально назначается некоторое число задач (случайно или по заранее определённому принципу), затем свободные процессоры «воруют» задачи у занятых или перегруженных. Существуют различные реализации схемы, различающиеся по модели разделения задач и правилам обмена. Хотя метод может быть эффективным, его сложно реализовать — коммуникации не должны стать основной загрузкой процессоров.

При атомарных задачах существуют две ключевые стратегии: одни (малозагруженные) инициируют передачу им работы; другие — перегруженные — сами инициализируют запрос о помощи. Показано^[8], что при высокой загрузке сети эффективнее инициатива слабо загруженных узлов, при низкой — инициатива перегруженных. Это правило минимизирует количество сообщений.

Если имеется одна крупная неделимая задача, эффективен так называемый алгоритм «древовидных вычислений» (англ. tree-shaped computation)^[9], при котором родительская задача разбивается на подзадачи по иерархии дерева.

Изначально вычислить задачу должна только одна нода, остальные простаивают. Простаивающие процессоры случайным образом обращаются с запросом к другим процессорам. Если процессор может разбить собственную задачу, он делегирует часть запроса обратившемуся. В противном случае возвращает пустой ответ. Вся обработка строит древовидную структуру. После завершения подзадачи накануне передаётся сигнал завершения родителю, который по цепочке передаётся до корня дерева. Затем собираются итоговые результаты.

Эффективность приближается к алгоритму префиксной суммы, если стоимость деления задач и коммуникаций невелика. Для ограничения коммуникационных издержек можно реализовать общую очередь задач в общей памяти; тогда получение задачи — это всего лишь чтение определённой позиции памяти главным процессором.

Помимо эффективного распределения параллельных вычислений, алгоритмы балансировки часто используются для управления HTTP-запросами на сайтах с высокой аудиторией, где требуется обработка большого числа запросов в секунду.

Одна из самых популярных областей применения балансировки — предоставление единого интернет-сервиса через несколько серверов (так называемый серверный пул). Так работают популярные веб-сайты, крупные IRC-сети, мощные FTP- и NNTP-сервера, DNS-серверы, базы данных.

Круговой DNS — альтернативный способ балансировки, не требующий выделенного программного или аппаратного ускорителя. Нескольким IP-адресам ставится в соответствие одно доменное имя; клиентам поочерёдно назначаются IP-адреса с коротким TTL, чтобы вероятность получения другого адреса при новом подключении оставалась высокой.

Более продвинутый способ распределения трафика через DNS заключается в делегировании поддомена (например, www.example.org) в обслуживаемое несколькими серверами пространство имён. Хорошо подходит для распределённых по географии серверов. Например:

one.example.org A 192.0.2.1

two.example.org A 203.0.113.2

www.example.org NS one.example.org

www.example.org NS two.example.org

Причём зона www.example.org на каждом сервере содержит только IP-адрес самого себя^[10].

Так, если сервер недоступен, его DNS не отвечает, и трафик не поступает на него. Также, наиболее быстрый отклик получает клиент, географически ближайший к серверу, обеспечивая геочувствительную балансировку. Короткий TTL помогает быстро переключать трафик при отказе узла, однако стоит учитывать, что возможно переключение клиентов между разными серверами прямо в сессии.

Другой подход — передавать клиенту сразу список IP серверов, и чтобы клиент самостоятельно выбирал IP из списка случайным образом при каждом соединении^[11].^[12] Это предполагает равномерную нагрузку от всех клиентов и эффект закона больших чисел^[12]. Было отмечено, что случайная балансировка на стороне клиента обеспечит более равномерное распределение нагрузки по сравнению с круговым DNS из-за особенностей кэширования в DNS серверах^[12].

Список серверов может предоставляться через DNS без ротации или быть жёстко прописан в приложении. Если реализован «умный клиент», определяющий отказ сервера и повторяющий попытки, появляется дополнительная отказоустойчивость.

В интернет-сервисах балансировщик — это программа, принимающая внешние соединения на определённом порту, далее перенаправляющая запросы на один из внутренних «бэкенд»-серверов, а ответы от них возвращает клиенту. Такая схема скрывает устройство инфраструктуры, защищая бэкенды от некоторых видов атак.

Многие балансировщики поддерживают сценарии отказа всех серверов — например, переход к резервному узлу или отображение сообщения пользователю.

Важно, чтобы сам балансировщик не стал единственной точкой отказа. Обычно применяют высокодоступные пары устройств с репликацией состояния, если того требует приложение^[13]. Некоторые системы работают поверх динамических распределённых платформ хранения, увеличивая отказоустойчивость и масштабируемость^[14].

Существует множество алгоритмов планирования (или методов балансировки), используемых балансировщиком для выбора бэкенда. Простые — случайный выбор, циклический или по наименьшему числу соединений^[15]. Более сложные методы учитывают загрузку, скорость отклика, статус и количество активных соединений, географию, возможности или последнюю нагрузку.

В работе балансированных сервисов важен вопрос сохранения данных для повторных запросов пользователя (сессия). Если информация хранится только на одном сервере, а запросы попадают на разные — данные теряются, что приводит к ошибкам или снижению производительности^[15].

В идеале, серверы не должны быть привязаны к сессии: для этого используют общие базы данных или системы кэширования типа Memcached. Элементарное решение — «прилипание» (англ. persistence, англ. stickiness): все запросы сессии направляются на один и тот же сервер. Недостаток — потеря данных при сбое сервера, то есть отсутствие автоматического фейловера.

Прикрепление может определяться по имени пользователя, IP клиента или случайно, однако динамика адресов из-за DHCP, NAT, прокси делает этот способ ненадёжным. Для случайного назначения нужны средства хранения на балансировщике, что создаёт нагрузку. Возможна утрата данных при отказе хранилища или перегрузке.

Альтернатива — сохранение сессионных данных в базе, однако это может увеличить нагрузку на базу и снизить производительность. Для масштабируемости базу реплицируют, а сами запросы балансируют между репликами. Пример — Microsoft ASP.NET State Server.

Наиболее распространённое решение — хранить данные сессии непосредственно в клиентском браузере, чаще всего в виде HTTP cookie, с таймштампом и шифрованием; либо через переписывание адресов. Это позволяет отдавать запросы любому серверу, однако сессии большого объёма или специфическая бизнес-логика могут стать проблемой — не всегда возможно переносить логику сервера на клиент. К тому же переписывание URL чревато уязвимостями.

Ещё один вариант — распределённые хеш-таблицы, где блок данных хранится на одном из серверов согласно хешу.

Аппаратные и программные балансировщики могут иметь дополнительные функции. Базовая — распределение запросов множеству бэкенд-серверов по алгоритму планирования. Другие, часто зависящие от производителя:

Асимметричная загрузка

Администрируемое вручную неравномерное распределение запросов.

Приоритетная активизация

Включение резервных серверов при отказах или пиковых нагрузках.

TLS-ускорение

Перенос вычислений по шифрованию на специализированное оборудование.

Защита от DDoS

Поддержка SYN cookies и задержка передачи клиента серверу до окончания рукопожатия.

HTTP-сжатие

Использование gzip для сокращения трафика.

TCP-оффлоуд

Объединение нескольких HTTP-запросов в один TCP-поток для бэкенда.

Буферизация TCP

Буферизация от сервера и постепенная/ускоренная передача клиенту.

Прямой возврат ответа

Асимметричный маршрут — разные пути на запрос и ответ.

Проверка состояния

Опрос бэкендов и автоматическое исключение неработающих.

HTTP-кэширование

Кэширование статического контента на балансировщике.

Фильтрация

Модификация трафика на ходу.

HTTP-безопасность

Сокрытие внутренних ошибок, удаление идентификаторов серверов.

Приоритетное обслуживание

Различный приоритет для разного трафика.

Контентное переключение

Раздача запросов в зависимости от URL.

Аутентификация

Проверка пользователей до выдачи доступа сайту.

Программируемость

Поддержка пользовательских алгоритмов и скриптов.

Firewall

Блокировка прямых подключений к бэкендам.

IPS

Анализ данных на прикладном уровне.

Балансировка применяется и в приложениях с резервированием каналов связи. Например, в организации с несколькими интернет-каналами, для резервирования на случай отказа одного из них.

Динамическая балансировка позволяет использовать все соединения одновременно: устройство/программа отслеживает доступность линков и выбирает путь для отправки пакетов, увеличивая пропускную способность.

Технология TRILL (англ. Transparent Interconnection of Lots of Links) позволяет строить Ethernet-сети произвольной топологии и делить нагрузку на основе алгоритма Дейкстры, без ручного вмешательства. Разработка TRILL вызвана крупными сбоями в медицинском центре Beth Israel Deaconess Medical Center в 2002 году^[16].^[17] Концепция Rbridge была предложена IEEE в 2004 году^[18], а IEEE в 2006—2012 годах разработал несовместимый стандарт Shortest Path Bridging (SPB)^[19].

IEEE 802.1aq утверждён в мае 2012 года^[20]. SPB позволяет использовать все каналы связи, снижая время восстановления после сбоев и упрощая балансировку в топологиях сеток^[21].^[22] SPB сохраняет принцип «plug-and-play», положивший начало доминированию Ethernet на втором уровне OSI^[23].

Многие телекоммуникационные компании имеют несколько маршрутов для трафика и гибко балансируют загрузку по разным каналам, чтобы избежать загрузки или снизить расходы по внешним линиям, а также повысить надёжность.

Балансировщики полезны и в мониторинге сетей — разделяют огромные потоки данных между несколькими анализаторами для параллельного анализа, что необходимо в 10GbE/STM64, где весь поток обработать на интерфейсе невозможно^[24].

Балансировка нагрузки активно применяется в дрцентрах для распределения трафика между разными маршрутами^[25]. Это делает использование каналов более эффективным и снижает затраты. Статическая балансировка использует хеширование адресов и портов для назначения маршрута, динамическая — анализирует пропускную способность разных маршрутов и переносит потоки при изменениях загрузки.

Динамические стратегии могут быть проактивными (раз назначили поток, больше не меняют) или реактивными (потоки переносятся между маршрутами при изменении ситуации). Детальный обзор методов дан в работе^[25].

Балансировка часто применяется для обеспечения фейловера — продолжения работы сервиса при отказе одного или нескольких компонентов. Состояние компонентов отслеживается (например, путём запроса страниц веб-сервера); если компонент не отвечает, балансировщик выключает его из пула и возобновляет маршрутизацию после восстановления. Для этого требуется минимум один избыточный компонент (N+1 избыточность). Это дешевле, чем парная избыточность (двойная модульная избыточность). Системы RAID также могут использовать «горячие» резервы^[26].

Такой подход увеличивает отказоустойчивость, но может сделать балансировщик единственной точкой отказа.

Растущая область применения балансировки нагрузки — управление потоками данных для обучения и инференса искусственных интеллектов, так называемых «ИИ-фабрик». Эти среды требуют непрерывной обработки огромных объёмов структурированных и неструктурированных данных и, соответственно, больших вычислительных, сетевых и дисковых ресурсов^[27]. Для минимизации задержек и повышения пропускной способности применяют балансировщики с поддержкой оптимизации TCP, пулов соединений и адаптивного планирования, которые равномерно распределяют запросы, предохраняют системы от перегрузок и увеличивают эффективность использования ресурсов^[28].

В крупных ИИ-инфраструктурах балансировщики помогают обойти лимиты пропускной способности, локальную обработку конфиденциальных данных (без передачи в облако) и соответствуют нормативным требованиям. По мере роста объёма моделей (до миллиардов параметров и выше) грамотная балансировка данных становится ключом к стабильности, масштабируемости и экономичности ИИ-фабрик.