Сергей Каличев, старший разработчик, Angie Software

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

Сводная таблица

Сначала приведу сводную таблицу со списком балансировщиков, какие вообще есть в Angie и где конкретно они доступны. Колонка "OSS" - Open Source версия, "PRO" - Angie PRO, "ADC" - ADC Load Balancer в составе Angie ADC. В отдельных таблицах будут приведены дополнительные возможности, смежные с функциональностью балансировщиков. Знак "+" означает, что балансировщик присутствует в соответствующей версии. Дополнительные плюсы в ячейке таблицы - это расширенные возможности, относительно OSS версии.

Балансировка HTTP (L7):

Балансировщик/Версия	OSS	PRO	ADC
round_robin	+	+	+
hash	+	+	+
ip_hash	+	+	+
least_conn	+	+	+
random	+	+	+
feedback		+	+
least_time		+	+
least_bandwidth			+

Возможности/Версия	OSS	PRO	ADC
keepalive	+	+	+
sticky	+	++	++
zone	+	++	++
probe		+	+
queue		+	+
backup-сервера	+	++	+++

Балансировка TCP/UDP (L4):

Балансировщик/Версия	OSS	PRO	ADC
round_robin	+	+	+
hash	+	+	+
least_conn	+	+	+
random	+	+	+
feedback		+	+
least_time		+	+
least_bandwidth			+
least_packets			+

Возможности/Версия	OSS	PRO	ADC
sticky	+	++	++
zone	+	++	++
probe		+	+
backup-сервера	+	+	++

Далее каждый балансировщик будет описан более подробно. Про вспомогательные (смежные) модули и возможности рассказывалось в первой статье.

Балансировщики OSS

Алгоритм round_robin

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	детерминированный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	поддерживается
Backup-группы серверов	поддерживаются

Самый базовый алгоритм балансировки, используемый по умолчанию. Перебирает все сервера группы по кругу. Если заданы веса серверов, то они кратно увеличивают количество случаев выбора данного сервера, относительно сервера с весом равным "1". Хотя я и написал, что алгоритм перебирает сервера "по кругу", в буквальном смысле это верно только для случая, когда все сервера имеют вес "1". Внутри алгоритм чуть более хитрый. Ему ведь надо поддерживать веса. Кроме этого было бы печально, если, предположим, сервер, имеющий вес "5", выбирался 5 раз подряд, а затем по одному разу два других сервера, имеющих вес "1". Алгоритм "перемешивает" такие случаи, чтобы запросы поступали на сервера вперемешку и, соответственно, более равномерно, а не длинными непрерывными порциями сначала на один, а только потом на другой.

Некоторые другие балансировщики, например least_conn, могут "откатиться" к алгоритму round_robin, если сами не могут сделать обоснованный выбор. Предположим есть три upstream-сервера с одинаковым количеством установленных активных соединений, тогда least_conn не имеет достаточно данных, чтобы выбрать один из них и, соответственно, перепоручает выбор алгоритму round_robin, для которого нет тупиковых ситуаций.

Обратите внимание, что в конфигурационном файле не существует директивы для включение алгоритма "round_robin" - он включен, если не используются другие балансировщики. В документации также нет для него отдельного раздела, вместо этого алгоритм описан в разделе секции "upstream" для L4 и L7.

Если попытка соединиться с выбранным сервером закончилась неудачей, то балансировщик попробует использовать следующий в группе сервер. И так далее. Количество попыток соединиться со "следующим" сервером и максимальная длительность таких попыток могут быть ограничены настройками "proxy_next_upstream_tries", "proxy_next_upstream_timeout". Так же себя ведут и другие балансировщики в случае неудачной попытки соединения, не только round_robin.

Алгоритм hash

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	детерминированный
Межпроцессные rw-блокировки	отсутствуют
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	не поддерживается
Backup-группы серверов	не поддерживаются

Балансировщик хэширует значение ключа, заданного в аргументах директивы "hash". По этому хэшу он выбирает сервер на который отправить запрос. Ну и в общем тут, как хэш ляжет... Ключом может быть текст, переменные и их сочетание. Но применительно к реальной жизни можно сказать, что указание в качестве ключа фиксированного текста не имеет никакого практического смысла, т.к. хэш всегда будет один и тот же. А вот переменные или наборы переменных, которые меняются во времени или в зависимости от характеристик клиента - это другое дело.

Предположим состав upstream-серверов в группе поменялся. Такое может произойти по резолвингу адресов или по API-командам от администратора в коммерческих версиях. Это спутает нам все карты. Запросы будут распределяться по-другому, нежели до изменений. Если всё-таки очень хочется, чтобы только минимальное число ключей сменило свои целевые upstream-сервера, а основная масса осталась как есть, то можно использовать специальный метод консистентного хэширования ketama, который позволяет это сделать и включается опцией "consistent".

Консистентное хэширование работает иначе, чем базовый вариант. Сервера, "помещаются" на некое "кольцо консистентного хэширования" в зависимости от значения хэша своего адреса. Подробности лучше почитать в тематической литературе, однако тут нужно отметить, что позиция сервера на кольце зависит от его адреса и никак не зависит от последовательности, в которой сервера добавлялись. С практической точки зрения это означает следующее. Предположим у нас есть список upstream-серверов. Если сервера в списке поменять местами, при этом состав серверов оставить прежним, то это повлияет на обычный алгоритм выбора сервера по хэшу. Клиентские запросы пойдут на другие сервера, нежели до внесения изменений. А в случае консистентного метода хэширования - ничего не изменится. Изменения также будут минимальны, если из списка исчезнет сервер. Перераспределяться на новые сервера будут только те запросы, которые ранее попадали на исчезнувший сервер. Для остальных запросов ничего не поменяется. Соответственно, при добавлении нового сервера, только незначительная часть запросов будет перераспределено на новый сервер. Основная масса будет направлена на прежние сервера, и именно на те, что и раньше.

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

Реализация консистентного хэширования в Angie имеет особенность, которую надо учитывать. Дело в том, что, если при конфигурировании upstream-сервер указан по имени, а не по IP-адресу, то он может порезолвиться в целый набор адресов и, соответственно, в целый набор серверов. У таких серверов есть имя, то, что задано при конфигурировании и адрес, один из тех в которые порезолвилось имя. Так вот на "кольцо консистентного хэширования" сервера помещаются в зависимости от хэш значения своего адреса, а не имени. Если имя одного сервера порезолвилось в один адрес, а имя второго - в три адреса, то второй сервер займёт на кольце в три раза больше "места" и, примерно, в три раза больше запросов будут распределяться на него. Что значит распределяться на него? Тут как раз и появляется неочевидная особенность реализации. Мы выбрали сервер вроде бы по адресу, но не факт, что для обработки будет использоваться именно он. Когда сервер выбран по хэшу, то берётся имя этого сервера. После этого находятся все сервера, чьи адреса порезолвлены из этого имени, и среди них выбирается один по принципу round_robin. Таким образом, запросы привязываются именно к именам серверов, а не к их адресам. А вот количество запросов, выбираемых для обработки на серверах с одним именем, зависит от количества таких серверов.

Если выбранный сервер недоступен, то пытаемся пересчитать хэш с учётом предыдущего значения, и новый хэш будет уже другой. На какой сервер мы попадём на этот раз - заранее непонятно. Не факт, что это будет живой сервер. Таких попыток может быть всего "20". Это прямо в коде написано. Если за 20 попыток нашли подходящий сервер - хорошо, значит следующий запрос с аналогичным ключом также попадёт на этот сервер. А если не нашли ничего, то откатываемся к алгоритму round_robin. Но в этом случае распределение запросов по серверам будет уже случайное, в том смысле, что совпадающий ключ больше не гарантирует обработку на одном сервере.

Дополнительные сведения по алгоритму балансировки "hash" можно найти в документации для L4 и L7.

Алгоритм ip_hash

Характеристика/Возможность	Значение
Уровень балансировки	L7
Способ выбора сервера	детерминированный
Межпроцессные rw-блокировки	отсутствуют
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	не поддерживается
Backup-группы серверов	не поддерживаются

Балансировщик хэширует IP-адрес клиента и по значению этого хэша выбирает upstream-сервер для обработки запроса. Ключом являются первые три октета IPv4-адреса, либо IPv6-адрес целиком. В итоге запрос конкретного клиента всегда попадает на один и тот же сервер, если, конечно, он работоспособен.

Чем этот балансировщик отличается от балансировщика "hash"? Да практически ничем. Просто исторически он появился раньше, чем "hash" и если его выкинуть, то нарушится совместимость и появятся вопросы. По сути балансировщик делает почти тоже самое что и "hash" с ключом "$remote_addr", только из IPv4-адреса надо выделить три первых октета. Это можно сделать с помощью механизма map и регулярных выражений.

Балансировщик простой и в нём, в отличие от балансировщика "hash", нет консистентного хэширования. Из-за этого, если состав upstream-серверов изменится, то вся привязка поедет. Поэтому если есть желание удалить из группы один из серверов, то лучше этого не делать, а приписать ему состояние "down". Тогда запросы на него отправляться больше не будут, но при этом хэш таблица останется прежней. И только лишь запросы, ранее привязанные к этому серверу, уйдут на другие backend-ы. Ну а если сервер появляется в группе, а не исчезает, то тут ничего не поделаешь, workaround-а нет, привязка поедет.

Так же, как и в случае с балансировщиком "hash", "ip_hash" откатывается к алгоритму round_robin после 20 неудачных попыток выбрать живой сервер с помощью хэша.

Дополнительные сведения по алгоритму балансировки "ip_hash" можно найти в документации.

Алгоритм least_conn

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	детерминированный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	поддерживается
Backup-группы серверов	поддерживаются

Балансировщик ищет upstream-сервер с наименьшим количеством установленных активных соединений. Ну т.е. эти соединения он сам и устанавливает для передачи клиентских запросов серверу. Но тут сразу надо кое-что пояснить. Важно, что речь идет именно об "активных" соединениях. Потому что если, предположим, включен модуль keepalive, то соединение с upstream-сервером, которое использовалось для передачи запроса и получения ответа, после завершения цикла не будет закрыто. Модуль keepalive прибережёт его для обработки будущих запросов. Однако это соединение уже не будет "активным". Активными считаются только те соединения, которые используются прямо сейчас.

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

Если количество активных соединений у двух или более upstream-серверов оказалось одинаковым, то используется алгоритм round_robin, выбирающий "победителя" только среди этих серверов (с минимальным и одинаковым значением количества соединений). Надо сказать, что, по факту, все балансировщики с детерминированным способом выбора сервера, откатываются на какой-либо вариант round_robin, если сами не могут выбрать.

Дополнительные сведения по алгоритму балансировки "least_conn" можно найти в документации для L4 и L7.

Алгоритм random

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	вероятностный
Межпроцессные rw-блокировки	отсутствуют
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	не поддерживается
Backup-группы серверов	не поддерживаются

Балансировщик "random" использует случайный выбор upstream-сервера, с учётом весов. Хоть идея выглядит слишком простецки, однако это не так плохо, как может показаться с первого взгляда. На больших числах, т.е. при большом числе запросов, они довольно равномерно размажутся по upstream-серверам. А, собственно, качественный балансировщик и нужен только тогда, когда запросов достаточно много.

Вот так "random" палит на угад, и если не попал, т.е. попал, но в неработоспособный сервер, то "стреляет" еще раз. У него всего 20 попыток. Теоретически, все 20 раз он может попасть в один и тот же мёртвый сервер. И если у него так ничего толкового не вышло, то используется, как всегда, выручающий всех, алгоритм round_robin.

Кроме этого, у балансировщика есть второй режим работы. Случайным образом берутся два upstream-сервера, а потом, уже среди них, выбирается тот, у которого меньше активных соединений. Т.е. на первом этапе случайный выбор, а на втором аналог балансировщика "least_conn". Такой метод выбора имеет собственное название, в переводе что-то вроде "сила двух вариантов", и описан в статье. Суть в том, что, когда балансировщик один, то он имеет, насколько это вообще возможно, полную информацию о состоянии upstream-серверов. Например он точно знает, сколько активных соединений установлено с конкретным сервером, и может обоснованно выбрать сервер с минимальным количеством соединений. И будет прав. А вот если балансировщиков два или более и все они работают одновременно и независимо друг от друга, то начинаются проблемы. Каждый из них не видит всей картины состояния upstream-серверов, только свой кусочек. Например он знает сколько соединений установлено с сервером, но ведь это только его собственные соединения. Из-за этого случаются ситуации, когда разные балансировщики, на основании только своих расчётов, начинают заливать запросами один и тот-же сервер, потому что в моменте он оказался наименее нагруженным. Если бы балансировщик был один, то отправив на сервер запрос, сразу бы понял, что серверу уже хватит. А не имея полной картины, разные балансировщики, не могут вовремя остановиться. В итоге нагрузка распределяется неравномерно, случаются всплески. Алгоритм "сила двух вариантов" рандомизирует выбор и тем самым сглаживает распределение. Использовать этот алгоритм, если балансировщик один - не имеет смысла. Он полезен только если балансировщиков много.

Дополнительные сведения по алгоритму балансировки "random" можно найти в документации для L4 и L7.

Балансировщики PRO

Все балансировщики OSS доступны и в PRO.

Алгоритм feedback

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	вероятностный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	поддерживается
Backup-группы серверов	поддерживаются

Алгоритм балансировки "feedback" основан на обратной связи от upstream-сервера. Кто лучше всех может оценить, к примеру, степень загруженности сервера? Сам этот сервер! Предполагается, что upstream-сервера посылают балансировщику некие метрики, на основе которых "feedback" принимает решение, кому направлять новые запросы на обработку.

Что может служить метриками? Предположим, upstream-сервер имеет свою собственную очередь запросов, поступивших на обработку. В этом случае метрикой может быть количество свободных слотов в такой очереди. Чем больше слотов, тем больше значение метрики, и тем вероятнее будет отправка новых запросов именно на этот сервер. Хорошо, другой случай. Метрикой считаем среднюю загруженность процессорных ядер upstream-сервера. В этом случае, чем больше загруженность ядер, тем больше значение метрики, и тем меньше должна быть вероятность отправки новых запросов на сервер. Обратите внимание, тут уже началась инверсная логика - чем больше, тем хуже. Для таких случаев у балансировщика "feedback" есть опция "inverse", которая делает логику выбора инверсной. По умолчанию логика прямая, т.е. чем больше метрика, тем лучше.

Балансировщик "feedback" получает значение метрики через переменную. Какую переменную для этого использовать, задаётся параметром директивы "feedback". Каждый раз, при получения ответа от upstream-сервера, балансировщик берёт переменную и расчитывает среднее значение по формуле экспоненциально взвешенного скользящего среднего. Коэффициент для формулы можно задать опцией "factor". Он говорит о том, какой вклад в расчет среднего даст старое значение среднего, а сколько вновь полученная метрика. В итоге для каждого upstream-сервера существует среднее значение метрики, которое и используется при выборе сервера для обработки следующего запроса.

Как метрика upstream-сервера попадёт в переменную на балансировщике? Самый простой вариант - через заголовок (header) HTTP-ответа. Но как бы ни была реализована передача метрики на балансировщик и какую-бы информацию ни собирал upstream-сервер для её формирования, должен существовать "агент", который этим занимается. Что это за агент и как его сделать - каждый решает сам. Если на upstream-сервере также используется веб-сервер Angie, то агентом мог бы выступать модуль Angie, который предоставляет переменную с метрикой. Стандартными средствами значение этой переменной добавляется в произвольный HTTP-заголовок и передаётся вместе с HTTP-ответом на балансировщик. Вообще говоря, агент, передающий метрику, может слушать на другом порту или другом виртуальном хосте, нежели целевой сервис. Для получения метрик таким способом могут использоваться активные проверки, речь о которых пойдёт далее.

По умолчанию только ответы на клиентские запросы учитываются при расчёте среднего значения метрики. Ответы на активные проверки upstream_probe не учитываются. А если очень надо? Да пожалуйста! Директива "feedback" содержит опцию "account", которая определяет, какие ответы будут учитываться. Опция "account" указывает на переменную. Если переменная не пуста и не "0", то ответ используется для расчётов. Довольно стандартный приём - определить переменную через механизм map. Активные проверки именованы и в map можно не только определить, что ответ принадлежит активной проверке, но и какой из них именно. Вообще говоря, хотя механизм "account" изначально и был сделан для того, чтобы обеспечить возможность черпать информацию из активных проверок, однако ими не ограничивается. Любая доступная информация может использоваться в конструкции map и тем самым определять, использовать ли ответ сервера для расчётов среднего.

Дополнительные сведения по алгоритму балансировки "feedback" можно найти в документации для L4 и L7.

Алгоритм least_time

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	вероятностный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	не поддерживается
Медленный старт (slow_start)	не поддерживается
Backup-группы серверов	поддерживаются

В качестве критерия выбора балансировщик использует среднее время ответа от upstream-сервера. Чем быстрее сервер отвечает, т.е. чем меньше время ответа, тем больше вероятность того, что запросы будут отправлены на этот сервер.

А, собственно, что такое время ответа? Под временем ответа могут подразумеваться немного разные вещи. Для HTTP протокола:

header - время получения заголовка ответа;
last_byte - время получения полного ответа.

Для L4 (модуль "stream"):

connect - время соединения с upstream-сервером;
first_byte - время получения первого байта от upstream-сервера;
last_byte - время получения последнего байта от upstream-сервера.

Какое именно время ответа использовать задаётся опцией в директиве "least_time".

Так же, как и алгоритм "feedback", "least_time" использует формулу экспоненциально взвешенного скользящего среднего, коэффициент для которой можно задать опцией. Можно также определить какие ответы будут использоваться для расчета среднего времени ответа. Об этом (опция "account") было подробно рассказано в разделе про балансировщик "feedback".

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

Дополнительные сведения по алгоритму балансировки "least_time" можно найти в документации для L4 и L7.

Балансировщики ADC

Все балансировщики OSS и PRO доступны в составе ADC.

Алгоритм least_bandwidth

Характеристика/Возможность	Значение
Уровень балансировки	L4, L7
Способ выбора сервера	вероятностный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	поддерживается
Backup-группы серверов	поддерживаются

Хочется написать, что балансировщик использует показатель пропускной способности для выбора upstream-сервера, но такая формулировки только запутает дело. Кажется, что в данном случае английское слово "bandwidth" лучше отражает смысл происходящего, нежели русское словосочетание "пропускная способность". Под пропускной способностью обычно понимают ширину канала, т.е. сколько данных мы можем по нему прокачать в единицу времени. А тут же немного другой смысл. Важно не сколько трафика можно прокачать, а сколько реально прокачали в единицу времени. Наиболее подходящий вариант перевода - "метод наименьшего текущего трафика". Т.е. много ли данных мы отправляем на upstream-сервер или получаем от него. Соответственно, чем меньше трафика, тем сервер считается менее загруженным и тем больше запросов будет на него отправляться.

А что за трафик мы считаем? Тут есть выбор. Можно считать трафик от клиентов к серверу, т.е. "upstream", можно от сервера по направлению к клиенту, т.е. "downstream", а можно и то и другое сразу, т.е. "both". Где-то однажды прочитал, как легко запомнить что-же такое "upstream" и "downstream", кто из них "вверх", а кто "вниз". Так вот надо мысленно представить картинку, где сервер находится на горе. Клиенты приходят к подножию и просят мудрости. Тогда сервер, с барского плеча, отсыпает им немного данных. Вот этот основной поток льётся с горы вниз "downstream". А просили клиенты стоя внизу, т.е. кричали наверх "upstream". Мне когда-то помогло запомнить.

Так же, как и алгоритм "feedback", "least_bandwidth" использует формулу экспоненциально взвешенного скользящего среднего, коэффициент для которой можно задать опцией. Среднее значение для всех upstream-серверов перерассчитывается каждый раз, когда надо выбрать сервер для обработки нового запроса.

Дополнительные сведения по алгоритму балансировки "least_bandwidth" можно найти в документации для L4, а для L7 пока документация не готова, т.к. модуль новый, но там по настройкам всё тоже самое, что и в L4.

Алгоритм least_packets

Характеристика/Возможность	Значение
Уровень балансировки	L4
Способ выбора сервера	вероятностный
Межпроцессные rw-блокировки	используются
Вес (weight) серверов	поддерживается
Медленный старт (slow_start)	поддерживается
Backup-группы серверов	поддерживаются

Балансировщик считает используемую полосу пропускания, но не в байтах, а в пакетах. Все, что написано про балансировщик "least_bandwidth" применимо и к "least_packets", только единица измерения - сетевой IP-пакет.

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

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

Дополнительные сведения по алгоритму балансировки "least_packets" можно найти в документации.

Спасибо за внимание!

Балансировка в Angie: Алгоритмы