Дисциплины с распределителями нагрузки
Главную роль в Web-кластере, играет распределитель нагрузки, принимающий решение о дальнейшем движении каждого запроса. При этом весь Web-кластер представлен для внешнего наблюдателя только одним IP-адресом иртуальным IP (VIP). Кратко упомянем о механизмах маршрутизации пакетов внутри Web-кластера [1, 3, 4]:
Серийно выпускаемые устройства используют, как правило, простые дисциплины обслуживания, а в экспериментальных устройствах применяются методы моделирования. Однако в любом случае должны соблюдаться следующие требования: приемлемая вычислительная сложность; совместимость с протоколами и стандартами Web; доступность распределителю нагрузки всей необходимой для принятия решения информации.
Применяемые алгоритмы диспетчеризации можно разделить на статические и динамические. В последнем случае распределитель нагрузки осуществляет периодический мониторинг серверов, входящих в кластер и выбирает для направления запроса наилучший из них.
В статических алгоритмах состояние серверов не отслеживается. Выбор алгоритмов зависит от многих факторов. Повышенная нтеллектуальностьинамических алгоритмов влечет накладные расходы, связанные со сбором информации с хостов, однако выбор дисциплины обслуживания во многом зависит не только от характера трафика, но и от функциональности распределителя нагрузки. Принято классифицировать их на устройства уровня 4 и уровня 7 (рис. 2).
 |
Рис. 2. Различия в порядке обмена информацией между клиентом, распределителем нагрузки и Web-кластером для уровней 4 и 7 (SYN апрос на соединение, ACK одтверждение соединения) |
К статическим дисциплинам относятся Random и Round Robbin. В Random сервер выбирается случайным образом с помощью равномерного распределения. Дисциплина Round Robbin реализует принцип циклического перебора, который в чистом виде выглядит так: i-ая по счету заявка поступает на сервер с номером, равным остатку от деления i на N, где N оличество серверов.
Для любой динамической дисциплины возникает задача выбора управляющих параметров, которая не всегда может быть решена точно.
В качестве критерия эффективности обычно принимают два показателя:
Наиболее естественными динамическими дисциплинами являются:
Все эти дисциплины лепы к содержанию не требуют анализа HTTP-запроса. В сравнительном исследовании дисциплин WRR, LC и LL по среднему времени ответа и загрузке серверов лучше всего показала себя дисциплина LL. При низкой и средней загрузке WRR ведет себя гораздо хуже динамических дисциплин, а время ожидания для LC в среднем в 6 раз больше, чем для LL. С ростом нагрузки производительности сходятся, причем показатели LC стремятся к показателям LL гораздо быстрее, чем WRR. Неудивительно, что, раз LL оказалась лучше, то легче реализовать LC, поскольку для LL требуется более интенсивный обмен служебной информацией между распределителем нагрузки и серверами. Из этого анализа следует, что вопрос о том, какая из перечисленных динамических дисциплин наиболее эффективна, имеет скорее теоретическое значение. На практике же этот выбор не оказывает сколько-нибудь определяющего влияния на производительность Web-кластера.
Универсальный подход к использованию динамических дисциплин типа content-blind реализован в IBM Network Dispatcher [7]. Авторы ввели понятие ндекса загрузкиad Metrics Index (LMI) и разделили показатели качества работы системы на три класса.
Далее, по вектору LMI для каждого сервера вычисляются значения функции WCF (Weight Computation Function), и выбирается сервер с наибольшим значением. Программное обеспечение диспетчера состоит из трех компонентов visor, Manager и Executor. Первый компонент опрашивает серверы и собранную информацию передает на второй для вычисления WCF; третий производит маршрутизацию пакетов. Открытыми остаются вопросы динамического подстраивания весов для WCF, а также оптимального значения периодичности обновления LMI.
Параметр LMI весьма важен. Дело в том, что информация о состоянии серверов при интенсивном входном потоке может быстро устареть и оказаться не просто бесполезной, но и вредной для распределителя нагрузки. Известен так называемый ффект стадакогда аилучшемуа данный момент серверу подряд пересылается много запросов и он быстро становится худшим адолго до следующего сбора информации о состоянии, когда можно будет что-то изменить. Методам предотвращения такой ситуации посвящено немало работ. Некоторые из них пытаются учесть озрастнформации о загрузке серверов. Если информация свежая, следует использовать динамическую дисциплину, иначе татическую. Допустим, после опроса состояния N серверов упорядочены по возрастанию числа активных соединений, и сервер для поступающих запросов выбирается среди первых k случайным образом. Очевидно, что k=1 соответствует динамической дисциплине LC, k=N татической дисциплине Random. Период T между двумя последовательными опросами состояния делится на N интервалов, и на j-ом интервале нагрузка делится между первыми j серверами. По мере старения информации происходит постепенный переход от полностью динамической дисциплины к полностью статической.
Для всех рассмотренных дисциплин решение принимается только на основании информации от сервера, но и информация клиента тоже может учитываться. Это характерно при поддержке свойства client affinity, под которым понимается последовательное направление запросов от одного клиента одному и тому же серверу [3]. Такой прием во многих случаях позволяет повысить производительность и функциональность системы.
Перейдем теперь к рассмотрению дисциплин, относящихся к классу content-aware. Наиболее простой из них является Cache Affinity [3], в соответствии с которой файлы распределяются между серверами с помощью хэш-функции. Ту же функцию использует и распределитель нагрузки, обеспечивая адресность обращений. Однако во-первых, такая дисциплина пригодна лишь для статического содержимого, во-вторых, игнорирует балансировку загрузки.
Рассмотрим алгоритмы, так или иначе принимающие во внимание трудоемкость и ресурсоемкость запроса. При этом предположение о статистических свойствах длин поступающих запросов приводит к уточнению традиционных представлений о балансировке нагрузки. Некоторые исследователи отмечают, что стремление равномерно загрузить серверы не соответствует структуре потоков в Internet, и можно использовать дисциплину SITA-V (Size Interval Tasks Assignment-Variable), согласно которой егкиеадачи посылаются на хост с меньшей загрузкой, а яжелые большей. Так как при степенном распределении егкихадач больше, а яжелыхеньше, эффективность метода возрастает с уменьшением параметра a. Случается, что среднее замедление снижается более чем в 100 раз по сравнению с дисциплиной равномерной загрузки, однако среднее время ожидания при этом возрастает. Кроме того, вычисление точек разбиения длин заявок на интервалы, позволяющие отличить егкиеадачи от яжелыхносит оценочный характер.
Следующим шагом стала работа [6], где была рассмотрена дисциплина SITA-E (здесь E т equal). Ее отличие от SITA-V заключается в том, что в ней для точек разбиения предложена точная формула: если требуется разделить входной поток заявок между N серверами, N-1 точек находятся из интегрального соотношения, выражающего условие равенства интервалов длин заявок, взвешенных по вероятности в соответствии с плотностью распределения.
Заявки, длины которых лежат в пределах i-го интервала, направляются на i-ый сервер.
Оценка эффективности метода основывалась на сравнении дисциплин FCFS (ервым пришел ервым обслужени PS (азделение процессораВ FCFS обслуживается только одна заявка, а остальные ждут в очереди; в PS очереди как таковой нет, поскольку ресурс процессора делится на все присутствующие в системе заявки в режиме квантования времени. Математический анализ дисциплины PS значительно сложнее анализа FCFS, но насколько эти усилия оправданы? Авторы [6] приходят к интересному выводу: в случае применения в распределителе нагрузке алгоритма SITA-E, казалось бы, досконально изученная дисциплина FCFS вдвое превосходит PS по времени ответа и замедлению. Системы пакетной обработки всегда были эффективнее с точки зрения использования ресурсов, чем системы разделения времени: на переключение тратятся системные ресурсы.
В дальнейших исследованиях алгоритма SITA-E каждый сервер обрабатывал запросы в соответствии с FCFS, длина заявки предполагается известной распределителю нагрузки. Был проведен сравнительный анализ трех дисциплин: Round Robbin, Random и Dynamic Least Work Remaining (в последнем случае запрос передается серверу с минимальной остаточной работой, близко к LC) и сделан вывод: ни одна из дисциплин не является наилучшей во всех случаях. Когда дисперсия не очень велика, динамическая дисциплина лучше остальных, но ее эффективность падает с приближением дисперсии к данным реальных измерений трафика.
Еще более математически насыщенным стал алгоритм балансировки ETAQA, для которого распределение Парето было представлено в виде суммы экспоненциальных случайных величин (т.е. приближено гиперэкспоненциальным распределением с порядком k), и предложен метод расчета количества серверов, обслуживающих каждую экспоненциальную фазу.
Однако построенные модели и сделанные выводы оказались больше интересны для математиков, чем для практиков. Причина в том, что трудно заранее точно определить длину заявки. Если к статическим запросам эти модели еще можно как-то приложить, то к динамическим SITA-E вряд ли будет уместен.
В одной из работ авторы SITA-E предложили алгоритм TAGS (Task Assignment Based on Guessing Size), хорошо работающий для потоков заявок с большой дисперсией и неизвестной заранее длиной заявки, которая определяется динамически. Сначала она поступает на обслуживание на первый сервер. Если s1 единиц времени оказалось недостаточно для завершения обслуживания, процесс прерывается, и заявка ставится в очередь ко второму серверу, где ее обслуживание начинается с начала и т.д. TAGS, таким образом, достигает приблизительно тех же целей, что и SITA-E, но без априорной информации о длине заявки. Для реализации этой дисциплины не требуется анализа HTTP-заголовка и наличия распределителя нагрузки. Однако непонятно, сколько необходимо серверов, чтобы снизить среднее замедление до заданного уровня. Неясно и то, как оптимально выбрать последовательности si.
В ряде работ делается общий вывод: эффект от использования динамических алгоритмов сказывается лишь в том случае, когда время обработки большинства запросов на три или более порядков выше времени обработки простых запросов к HTML-страницам. Иначе, при быстродействии современных компьютеров разница в производительности почти не ощущается, и сложные алгоритмы, требующие накладных расходов на реализацию, не нужны.
В другом исследовании предложена дисциплина MC-RR (Multi Class Round Robbin) для устройств уровня 7. Ее цель лучшить разделение нагрузки для Web-кластеров, выполняющих статические и динамические запросы. Все возможные запросы разделены по ожидаемому влиянию на сеть, процессор и диск: статические и егкиеинамические; с высокой нагрузкой на диск; с высокой нагрузкой на процессор; с высокой нагрузкой на диск и процессор. Заявки первого класса характерны для систем Web-публикаций, остальные ля обработки Web-транзакций и мультимедийных Web-приложений. Внутри каждого класса заявки обслуживаются согласно дисциплине RR. Основная идея алгоритма состоит в том, что распределитель нагрузки хотя и не может точно вычислить длину заявки, но может определить ее класс.
С небольшими модификациями метод MC- RR известен также как CAP (Client-Aware Policy).
Существует и принципиально иной подход, не учитывающий ни длину заявки, ни загрузку серверов. Выбор сервера делается на основании домена клиента, а не текущей загрузки серверов, более того, попытка учесть в алгоритме серверную информацию часто ведет к ухудшению производительности. Поэтому домены делятся на классы по интенсивности потоков запросов из них, и к каждому классу отдельно применяется Round Robbin. Цель редотвратить концентрацию запросов из орячихоменов на одном сервере. Учитывается также число назначений каждому серверу из каждого домена, однако сбор характеристик с серверов может ухудшить производительность, поэтому предложено учитывать их состояние при реализации оменныхисциплин в усеченной форме, например, исключить из текущего рассмотрения серверы, приславшие сигнал о перегрузке. При получении же диспетчером сигнала о реактивации, сервер, пославший его, вновь включается в кластер.
Приведенный перечень дисциплин обслуживания, ориентированных на распределитель нагрузки, конечно, далек от полноты. Так, ничего не было сказано про использование кэша. Например, в ряде работ имеется обоснование применения кэша для хранения результатов CGI-запросов.
