WebClub - Всероссийский Клуб Веб-разработчиков
WebClub.RU » Советы » Дисциплины с распределителями нагрузки

Дисциплины с распределителями нагрузки


Дата публикации: 12-02-2008

Главную роль в Web-кластере, играет распределитель нагрузки, принимающий решение о дальнейшем движении каждого запроса. При этом весь Web-кластер представлен для внешнего наблюдателя только одним IP-адресом иртуальным IP (VIP). Кратко упомянем о механизмах маршрутизации пакетов внутри Web-кластера [1, 3, 4]:

  • Однонаправленная маршрутизация (one-way routing). Распределитель нагрузки подменяет в пакетах собственный IP-адрес IP-адресом выбранного сервера. Ответ сервера возвращается клиенту напрямую, без участия распределителя нагрузки. Web-сервер заменяет свой IP-адрес на VIP, чтобы ответ исходил из адреса, на который был послан запрос. Это позволяет разгрузить распределитель нагрузки (выходной поток значительно превышает входной), но требует изменений в коде операционной системы сервера, поскольку подмена IP-адреса происходит на уровне TCP/IP.
  • Двунаправленная маршрутизация (two-way routing). Выходной поток от сервера идет через распределитель нагрузки, который в этом случае выполняет обе подстановки адреса. При таком подходе распределитель нагрузки становится узким местом сети.
  • Маршрутизация через распределитель нагрузки (packet forwarding by the dispatcher). Подход реализован в IBM Network Dispatcher [7]. Пересылка пакетов серверу происходит на уровне MAC-адреса, без изменения заголовка IP-пакета, для которого в данном случае не нужно перевычислять контрольные суммы. Распределитель нагрузки и серверы должны находиться в одном сетевом сегменте.

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

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

Распределитель нагрузки уровня 4 анализирует пакеты только на уровне TCP/IP, не доходя до уровня приложения, не принимая во внимание HTTP-запрос при перенаправлении пакета на сервер. Такой механизм называют лепым к содержаниюontent-blind) или емедленным связываниемmmediate binding). Распределитель нагрузки уровня 7 принимает решение о маршрутизации запроса только при получении HTTP-пакета. При этом, проведя анализ URL, такие устройства могут учесть тип запроса, оценить его трудоемкость и определить, на каком сервере находится нужный ресурс. Этот механизм называют утким к содержаниюontent-aware) или тложенным связываниемelayed binding) [8]; его поддерживают многие коммерческие продукты [3]. Разумеется, дисциплины второго типа следует отнести к динамическим. С другой стороны, применение уровня 7 оправданно, если его возможности используются дисциплиной обслуживания, поэтому вполне естественно, что статические дисциплины реализуют только распределители нагрузки уровня 4, а динамические ак те, так и другие.

К статическим дисциплинам относятся Random и Round Robbin. В Random сервер выбирается случайным образом с помощью равномерного распределения. Дисциплина Round Robbin реализует принцип циклического перебора, который в чистом виде выглядит так: i-ая по счету заявка поступает на сервер с номером, равным остатку от деления i на N, где N оличество серверов.

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

  • время пребывания заявки на сервере (waiting time);
  • замедление (slowdown), т.е. отношение времени пребывания к длине заявки (во сколько раз замедляется обслуживание запроса из-за наличия очереди).

Наиболее естественными динамическими дисциплинами являются:

  • Least Loaded (LL) - выбор сервера по критерию наименьшей загрузки его ресурсов (процессор, память, диск, количество очередей сообщений);
  • Least Connected (LC) - выбор сервера по критерию наименьшего числа текущих открытых TCP/IP-соединений;
  • Fast Response (FR) - выбор сервера по критерию самого быстрого ответа на тестовый запрос от распределителя нагрузки;
  • Weighted Round Robbin (WRR) - при циклическом переборе каждому серверу, в отличие от статической дисциплины RR, передается подряд не один запрос, а несколько, в соответствии с весом сервера, пропорциональным, скажем, его текущей загрузке [7].

Все эти дисциплины лепы к содержанию не требуют анализа 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) и разделили показатели качества работы системы на три класса.

  • Input - вычисляются локально в РН, например, количество соединений, установленных с сервером за последние t единиц времени.
  • Host - вычисляются на каждом сервере, например, загрузка сервера.
  • Forward - вычисляются путем сетевого взаимодействия распределителя нагрузки с сервером. Эти характеристики доставляют специальные скрипты-агенты, например, подача HTTP-запроса "GET /" и измерение времени ответа.

Далее, по вектору 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-запросов.

Популярное

Не так давно в сети появился новый сервис, под названием Dead Man Zero. Этот сервис сделал...
Рынок социальных площадок уже давно стал стабильным. Несмотря на то, что время от времени...
Artisteer 4 – единственный в своем роде продукт, позволяющий автоматизировать работу над созданием...
Октябрь 2018 (14)
Февраль 2017 (3)
Январь 2017 (1)
Август 2016 (1)
Май 2016 (2)
Ноябрь 2015 (1)

Карта сайта: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41

Друзья сайта



Случайная цитата

Неизвестный автор:

"Жизнь – как сидение в интернете: смысла нет, а уходить не хочется."

Опрос

Ваша ОС?

Windows XP
Windows 7
др. версия Windows
Linux
др. ОС