Алгоритмы балансировки нагрузки. Часть 2

Уходим от “round robin”

Динамический взвешенный round robin, по-видимому, хорошо учитывает различия как в мощности сервера, так и в стоимости запросов. Но что, если можно добиться еще большего успеха с помощью более простого алгоритма?

Этот алгоритм называется балансировкой нагрузки по принципу «наименьшего количества подключений».

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

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

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

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

Оптимизация с учетом задержки

Чаще всего больше беспокоит задержка. Она измеряется в миллисекундах с момента создания запроса до момента его обработки. Когда обсуждают задержку в этом контексте, обычно говорят о разных «процентилях». Например, 50-й процентиль (также называемый «медианой») определяется как значение в миллисекундах, для которого 50% запросов ниже, а 50% — выше.

Было проведено 3 моделирования с одинаковыми параметрами в течение 60 секунд, где каждую секунду проводились различные измерения. Каждое моделирование отличалось только используемым алгоритмом балансировки нагрузки. Сравним медианы для каждого из 3-х симуляций:

У round robin наилучшая медиана задержки. Однако обратим внимание на 95-й и 99-й процентили.

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

Здесь видно, что round robin не работает должным образом при больших процентилях. Как может быть, что у круговой системы отличная медиана, но плохие 95-й и 99-й процентили?

При циклическом алгоритме не учитывается состояние каждого сервера, поэтому довольно много запросов, поступающих на простаивающие серверы. Именно так получается низкий 50-й процентиль. С другой стороны, запросы отправляются на перегруженные серверы, отсюда и плохие 95-й и 99-й процентили.

Просмотреть полные данные можно в виде гистограммы:

Для симуляций были подобраны такие параметры, чтобы избежать отбрасывания каких-либо запросов. Это гарантирует, что будет сравниваться одинаковое количество точек данных для всех трех алгоритмов. Запустим повторное моделирование, но с увеличенным значением RPS, чтобы все алгоритмы могли справиться с этим. Ниже приведен график общего количества запросов, которые были отклонены с течением времени.

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

И последний алгоритм…

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

Ниже приведено моделирование с использованием алгоритма под названием «пиковая экспоненциально взвешенная скользящая средняя» (или PEWMA).

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

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

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

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

Итак, как это соотносится? Посмотрим на 50-й, 95-й и 99-й процентили в сравнении с данными о наименьшем количестве подключений, полученными ранее.

Заметно улучшение по всем направлениям! Оно гораздо более выражено при более высоких процентилях, однако заметно и у медианы.

Что насчет пропущенных запросов?

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

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

Послесловие

Обязательное предупреждение: вы всегда должны оценивать свои собственные рабочие нагрузки, а не руководствоваться рекомендациями из Интернета. Приведенные здесь автором симуляции игнорируют некоторые ограничения из реальной жизни (медленный запуск сервера, задержка в сети) и настроены таким образом, чтобы отображать конкретные свойства каждого алгоритма. Это нереалистичные критерии, которые нельзя принимать за чистую монету.

^{Источник: samwho.dev}