Балансировка нагрузки в распределенных системах

Авторы: А.И. Миков, Е.Б. Замятина

Источник: Интернет университет информационных технологий INTUIT.ru



Содержание

Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка нагрузки предполагает равномерную нагрузку вычислительных узлов (процессора многопроцессорной ЭВМ или компьютера в сети). При появлении новых заданий программное обеспечение, реализующее балансировку, должно принять решение о том, где (на каком вычислительном узле) следует выполнять вычисления, связанные с этим новым заданием. Кроме того, балансировка предполагает перенос (migration – миграция) части вычислений с наиболее загруженных вычислительных узлов на менее загруженные узлы.
Следует различать декомпозицию задач и проблему отображения задач на вычислительную среду. Декомпозиция задачи является этапом процесса создания параллельной программы. Декомпозиция предназначена для разделения приложения на модули (задачи). Задачи исполняются на отдельных процессорах. В результате декомпозиции распределенного приложения появляется набор задач, которые параллельно решают задачу. Эти задачи могут быть независимыми или связанными друг с другом посредством обмена данными. Отображение (или "распределение задач") является отдельным этапом, позволяющим распределить задания, полученные на этапе декомпозиции, между процессорами.
Итак, будем считать, что распределенное приложение представляет собой совокупность логических процессов, которые взаимодействуют друг с другом, посылая друг другу сообщения. Логические процессы распределяются по разным вычислительным узлам и могут функционировать параллельно. При распределении логических процессоров по вычислительным узлам их стараются распределять так, чтобы загрузка вычислительных узлов была равномерной.
Однако при выполнении распределенного приложения возникает конфликт между сбалансированным распределением объектов по процессорам и низкой скоростью обменов сообщениями между процессорами. Если логические процессы распределены между процессорами таким образом, что издержки на коммуникацию между ними сведены к нулю, то некоторые процессоры (компьютеры) могут простаивать, в то время как остальные будут перегружены. В другом случае, "хорошо сбалансированная" система потребует больших затрат на коммуникацию. Следовательно, стратегия балансировки должна быть таковой, чтобы вычислительные узлы были загружены достаточно равномерно, но и коммуникационная среда не должна быть перегружена.
Реализация распределённой системы имитации требует разработки алгоритмов синхронизации объектов (или процессов), функционирующих на различных узлах ВС. Алгоритмы синхронизации мы уже обсуждали ранее. Эффективность реализации этих алгоритмов, в свою очередь, зависит от равномерности распределения (балансировки) вычислительной нагрузки по узлам ВС во время функционирования распределённой программной системы, каковой является, в частности, распределённая система имитации.

Балансировка вычислительной нагрузки

Причины возникновения несбалансированной нагрузки

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

Статическая и динамическая балансировки

Следует различать статическую и динамическую балансировки.
Статическая балансировка выполняется до начала выполнения распределенного приложения. Очень часто при распределении логических процессов по процессорам используется опыт предыдущих выполнений, применяются генетические алгоритмы. Однако предварительное размещение логических процессов по процессорам (компьютерам) не даёт эффекта.
Это объясняется тем, что:
Так или иначе, выигрыш от распределения логических процессов по компьютерам с целью выполнения параллельной обработки становится неэффективным.
Динамическая балансировка предусматривает перераспределение вычислительной нагрузки на узлы во время выполнения приложения. Программное обеспечение, реализующее динамическую балансировку, определяет:
На основании собранных данных как о распределенном приложении, так и вычислительной среде) принимается решение о переносе логических процессов с одного узла на другой.

Постановка задачи динамической балансировки

Цель балансировки загрузки может быть сформулирована следующим образом:
Исходя из набора задач, включающих вычисления и передачу данных, и сети компьютеров определенной топологии, найти такое распределение задач по компьютерам, которое обеспечивает примерно равную вычислительную загрузку компьютеров и минимальные затраты на передачу данных между ними.
Представим распределенное приложение в виде графа. Пусть Gp = {V, E}, V –множество вершин (задачи распределенного приложения), E – множество дуг графа – связи между задачами распределенного приложения. Пусть TM – множество моделей распределенных приложений, Gp ϵ TM.
Задача балансировки ставится как задача отображения неизоморфных связных графов, B: TM -> NG, где TM – множество графов моделей, NG – множество графов – конфигураций компьютерной сети. Граф G ϵ NG, G = {C, Ed}, определяется множеством вычислительных узлов C и множеством ребер Ed, обозначающих линии связи. Можно рассматривать NG как суперграф, содержащий все возможные (допустимые) графы G в качестве подграфов.
Таким образом, множество графов задач должны быть оптимальным образом отображено на множество графов вычислительной системы.

Методология практического решения задачи балансировки

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

Оценка загрузки

На этом этапе осуществляется приблизительная оценка загрузки каждого процессора. Полученная информация о загрузке используется в качестве базы данных для процесса балансировки, во-первых, для определения возникновения дисбаланса, во-вторых, для определения нового распределения объектов имитационной модели путем вычисления объема работ, необходимого для перемещения объектов. Отсюда, качество работы балансировки загрузки напрямую зависит от точности и полноты информации в базе данных.
В основном такая база данных состоит из двух типов данных:
Очень важно владеть такой информацией как коммуникационная модель.
Коммуникационная модель содержит важную информацию для принятия решений о перемещении задач при балансировке загрузки. При необходимости переместить объект с перегруженного процессора A на недогруженный процессор B целесообразно выбрать для перемещения тот объект, который наиболее интенсивно сообщается с задачами, уже расположенными на B.
Необходимо учитывать два типа связей между объектами: двухточечные коммуникации и коллективные коммуникации.
При распределении задач между процессорами производится оценка коммуникаций. Затраты на двухточечную связь между двумя задачами могут быть определены через объем передаваемых данных (b – объём сообщений в байтах) и частоту коммуникации (n – количество сообщений за единицу времени). Используя величины затрат процессора на каждое сообщение и каждый байт, можно оценить общие затраты на коммуникацию между двумя задачами: α * n + β * b, где b – общий объем всех n сообщений.
Оценка загрузки процессора и объекта может быть произведена несколькими способами. Один из способов (аналитический), обычно используемый при статической балансировке загрузки и состоит в приблизительной оценке загрузки каждого объекта на основе знаний о приложении. К этим знаниям относятся:
Преимущество аналитического метода состоит в том, что он достаточно точно может оценить трудоёмкость задачи с часто меняющейся загрузкой. В частности, вместо того, чтобы сообщать об изменении загрузки лишь после его возникновения, он может предсказать предстоящее изменение загрузки и отреагировать на него. Недостаток же этого метода состоит в том, что он требует огромных усилий со стороны программиста, знающего алгоритмы, и в том, что он может быть довольно неточным в случае, если модель для оценки скорости выполнения приложений неточна.
Другой способ сбора данных о загрузке состоит в измерении загрузки процессоров и задач. Большинство современных машин снабжено счетчиками времени (с точностью до микросекунд), которые могут быть использованы для измерения времени выполнения каждой задачи. Также этот метод потенциально предоставляет автоматическое решение задачи оценки стоимости загрузки. Преимущество метода состоит в том, что он является точным и не требует больших усилий программиста. К недостаткам можно отнести следующее: стратегии балансировки, основанные на этом методе (измерение) учитывают прошлое распределение нагрузок. Если загрузка задач меняется непредсказуемым образом, то метод будет неточным.
Приведенные два метода сбора данных о загрузке можно сочетать, дополняя метод, основанный на измерении производительности предсказывающей способностью аналитического метода оценки.

Инициализация балансировки загрузки

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

Принятие решений в процессе балансировки

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

Перемещение объектов

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

Архитектура подсистемы балансировки

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

Балансировка загрузки распределенной имитационной модели

В одной из предыдущих лекций мы рассматривали вопросы реализации распределенных систем имитации. Балансировку необходимо выполнять и при проведении распределённого моделирования. Первоначальная цель параллельного дискретно-событийного имитационного моделирования – быстрое выполнение больших и сложных моделей. В частности, PDES (Parallel Discrete Event Simulation) пытается увеличить скорость выполнения путём распределения модели на нескольких процессорах, которые работают параллельно. Однако распределение объектов моделирования оказывает большое влияние на скорость выполнения имитационного эксперимента, поскольку некоторые процессоры (или компьютеры в сети) оказываются сильно загруженными, другие слабо или вообще могут простаивать. Перераспределение нагрузки на менее загруженные процессоры (компьютеры) является выходом в этом случае. Чаще всего в параллельном дискретно-событийном имитационном моделировании компоненты моделируемой системы представляют собой логические процессы (LPj, j = 1 ÷ n) которые могут функционировать параллельно. Логические процессы распределяются между физическими процессорами, взаимодействие процессов осуществляется путём посылки сообщений от одного процесса другому.
В большинстве случаев алгоритм балансировки разрабатывается для конкретного класса задач. В других случаях балансировка предполагает большие изменения в коде авторских программ. В SPEEDES алгоритм балансировки предполагает, что программные средства для моделирования охватывают самые разнообразные области знаний, а вносимые изменения в код программы пользователя тоже незначительны.
Алгоритм динамической балансировки в SPEEDES предполагает пересылку (перенос, миграцию) объектов с процессора на процессор во время моделирования.
В SPEEDES рассматривается универсальная балансировка, которую можно применить к задачам различных типов, причём требуется лишь незначительное изменение пользовательского кода.
SPEEDES - это объектно-ориентрованное программное обеспечение, реализующее дискретное моделирование, управляемое событиями. Поскольку данная система была разработана для распределённого моделирования, оно реализует три стратегии синхронизации (TIME WARP, Breathing Time Buckets и Breathing Time Warp). Стратегии синхронизации могут быть выбраны пользователем при выполнении имитационного прогона.
В SPEEDES пользователь полностью отвечает за отображение логических процессов на компьютеры. Поскольку пользователю предоставлена полная свобода в выборе отображения, он априори не знает, как решать данную задачу в конкретном случае. В общем случае, построение оптимального отображения достаточно сложная задача, поэтому автоматизированное решение системой данной задачи значительно бы увеличило ее привлекательность для пользователей
Статическая балансировка не может дать хороших результатов, поскольку характеристики моделирования могут периодически меняться (об этом уже говорилось ранее).

Динамическая балансировка и перенос нагрузки

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

RCL – cтратегия переноса нагрузки

Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
Будем в дальнейшем называть эти алгоритмы балансировки RCL-стратегией.
Алгоритм переноса объекта или процесса с одного компьютера достаточно сложен. Введение некоторых разумных допущений только незначительно снижает сложность этого алгоритма. Итак, сделаны следующие допущения:
RCL стратегия использует двухуровневый процесс принятия решений, который объединяет централизованный и децентрализованный подходы. Двухуровневый процесс принятия решений предполагает:
На первом уровне выбирается центральный координатор для того, чтобы среди всех рабочих станций именно он мог принимать решения. Во время процесса переноса нагрузки все рабочие станции приостанавливают свою работу на некоторый промежуток времени, пока центральный координатор собирает информацию о загрузке процессоров. Координатор анализирует информацию, которая включает сведения о загрузке компьютеров и о распределении нагрузки в системе. Координатор, на основании этой информации решает, следует ли предпринимать действия по переносу нагрузки с одного компьютера на другой. Если состояние системы таково, что перенос нагрузки необходим (состояние соответствует критерию переноса нагрузки), центральный координатор начинает процедуру перераспределения нагрузки, руководствуясь скоростью работы компьютеров.
Если в переносе нагрузки нет необходимости, компьютер должен разослать сообщение об этом всем другим компьютерам. В этом случае действия второго уровня игнорируются, и каждый компьютер продолжает обрабатывать свои локальные события. Если, находясь на втором уровне, посылающие данные рабочие станции получат от центрального координатора сигнал о необходимости миграции нагрузки, они начинают процесс выбора части нагрузки для переноса её на другой хост. При выборе используют RCL стратегию. После того, как части нагрузки выбраны на всех пересылающих данные рабочих станциях, начинается процесс миграции. Последовательность шагов, предпринимаемых при миграции нагрузки между двумя компьютерами, включает упаковку данных и их отправку с посылающего компьютера, и приём и распаковку на принимающем компьютере. В конце каждого шага миграции принимающий компьютер рассылает всем остальным сообщение о завершении процедуры миграции и о новом размещении данных. После этого каждый компьютер продолжает обработку. Рассмотрим более детально действия на каждом уровне.

Действия первого уровня

В начале действий по переносу нагрузки информации все компьютеры прекращают свою работу, и каждый получает информацию о локальной нагрузке в текущий момент времени. Информация о локальной нагрузке включает:
Как только координатор получает информацию от всех компьютеров сети, он начинает анализировать общую информацию о нагрузке на компьютеры. Координатор вычисляет следующие характеристики:
Дисперсия коэффициенты загрузки компьютера может свидетельствовать о том, насколько они загружены. Действительно, если какие-либо компьютеры выполняют несколько приложений вместе с приложениями SPEEDES в то время, как другие простаивают, значение дисперсии может быть велико. Чем больше величина дисперсии использования компьютера, тем менее эффективно используются ресурсы процессоров.
Общее количество нагрузки, ожидающей обслуживания – это сумма всех невыполненных работ на каждом из компьютеров. Если их количество мало, то выигрыша от балансировки может и не быть, поскольку накладные расходы на перенос нагрузки могут превысить выигрыш от балансировки. Это особенно ярко выражено, если нагрузка невелика.
Дисперсия нагрузки, ожидающей обслуживания (VarWLd). Дисперсия нагрузки, ожидающей обслуживания вычисляется для каждого компьютера. Большое значение этого показателя свидетельствует об отсутствии равномерной нагрузки на компьютеры. Этот показатель используется в качестве вторичного критерия, если дисперсия общей нагрузки ниже порогового значения (T). Указанную метрику (VarWLd) используют в процедуре (назовём её Decide()), которая выполняется перед процедурой переноса (Migrate()). Метрика нужна для принятия решения о переносе нагрузки.
На первом шаге процедуры Decide() выполняют сравнение между общим количеством ожидающей обслуживания нагрузки(TotalWLd) и указанным пороговым значением (T). Если значение TotalWLd выше, то вычисляется коэффициент загруженности компьютера. Если дисперсия коэффициента загрузки выше соответствующего порога (VarCLd > TLd), то выполняется процедура (Migrate()). В противном случае Migrate() на этом шаге не выполняется. В конце выполнения процедуры Decide(), центральный координатор посылает сообщение всем компьютерам о том, что они могут продолжить обработку своих локальных нагрузок, если в процедуре Migrate()нет необходимости.
Если необходимость в процедуре Migrate() есть, центральный координатор посылает сообщение о том, что ожидается выполнение этой процедуры. Далее происходит определение посылающего и принимающего компьютеров (Csender и Сreceiver). Опираясь на показатель скорости обработки, (например, отношение количества нагрузки, обработанной на локальном компьютере к общему количеству обработанной нагрузки на всех процессорах со времени последнего переноса.) центральный координатор перераспределяет оставшуюся необработанную нагрузку. Например, если компьютер обрабатывал 10% общего количества нагрузки после последнего выполнения Migrate(), он возьмёт 10% процентов ещё необработанной нагрузки. Следовательно, те рабочие станции, которые обработали большее количество нагрузки, получат опять большее её количество. Если слишком большой нагрузки нет, и скорость работы компьютеров остаётся неизменной, все компьютеры законча т свою работу примерно в одно и то же время.
Центральный координатор отмечает отложенные действия компьютеров – посылка, получение или отсутствие действия. Получающий компьютер будет проинформирован о количестве нагрузки, которую ему передадут, и идентификаторы посылающих компьютеров.
И, наконец, центральный координатор выполняет подготовку к переносу объектов, если этот перенос необходим. Таким образом, процедуры второго уровня выполняются лишь при необходимости выполнения процедуры Migrate().

Действия второго уровня

Действия второго уровня охватывают все рабочие станции распределённой системы. Конкретной количество нагрузки посылается с одной рабочей станции на другую. Основные действия связаны с выбором нагрузки, её упаковкой, инициализацией переноса, переносом нагрузки, распаковкой, изменением глобальной информации. Каждый логический процесс в SPEEDES состоит из количества объектов моделирования (N) и очереди событий (ei, i = 1 ÷ n). События помещаются в очередь событий в неубывающем порядке их временных меток.
Нагрузка определяется как вся работа, которая должна быть выполнена для обработки запланированных событий, находящихся в очереди. Поскольку SPEEDES должна модифицировать нагрузку для переноса её части, каждому типу событий назначается коэффициент сложности (ki) в интервале от 1 до 10. Пользователь должен назначить коэффициент сложности для каждого определённого им события. Чем ближе коэффициент сложности к 10, тем больше времени требуется на обработку события. Нагрузка, ожидающая обслуживания, вычисляется исходя из количества событий, находящихся в очереди и их коэффициентов сложности (LocalWLD = Σei*ki, i = 1 ÷ n).
К примеру, предположим, что моделируемый объект содержит два события типа 1 и два события типа 2 в очереди событий. Если коэффициент сложности равен 4 для события типа 1 и 8 для события типа 2, то нагрузка может быть определена следующим образом: (2*4)+(3*8)= 32. Перенос нагрузки предполагает перенос объектов с одного компьютера на другой. Для выбора объектов, которые следует перенести на другой компьютер, используют один из трёх алгоритмов. Это случайный алгоритм, основанный на коммуникациях и основанный на вычислении нагрузки.

Случайный алгоритм

Случайный алгоритм (R) заключается в случайном выборе объектов моделирования на посылающем компьютере (Csender). Выбор продолжается до тех пор, пока количество выбранных объектов не будет соответствовать заданному числу.
К преимуществам использования случайного алгоритма следует отнести: лёгкость реализации, небольшие накладные расходы и сравнительно небольшое время выбор объектов для переноса.

Алгоритм, основанный на коммуникациях

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

Алгоритм, основанный на вычислении нагрузки

Алгоритм, основанный на вычислении нагрузки, пытается минимизировать количество выбранных для миграции объектов. Во время миграции объекты моделирования сортируются в зависимости от их нагрузки (количество событий каждого типа, умноженное на коэффициент их сложности). Первым выбирают объект с максимальной нагрузкой.
Алгоритм, основанный на вычислении нагрузки, предпочтительнее алгоритма, основанного на коммуникациях, поскольку требует меньших временных затрат.
Итак, перед тем, как начать имитационный эксперимент, пользователь выбирает один из алгоритмов переноса нагрузки. По окончании шага выбора объектов, посылающий компьютер уже имеет список объектов для пересылки.
Реализация
Стратегия динамического переноса нагрузки RCL была разработана для SPEEDES с целью повышения её производительности. Были проведены эксперименты для выявления конкретных параметров, которые влияют на скорость выполнения имитационного эксперимента. В качестве такого параметра может быть рассмотрен интервал между переносами нагрузки (между процедурами Migrate()). SPEEDES поддерживает несколько синхронизирующих алгоритмов для выполнения распределённого моделирования: Breathing Time Warp (BTW), который совмещает черты алгоритма деформации времени Time Warp и протокола Breathing Time Buckets.
В результате исследований было обнаружено, что процедуру Migrate() следует выполнять в конце цикла GVT (Global Virtual Time). Действительно, события удаляются из системы во время вычисления GVT. Поэтому нет опасности, что возникнет необходимость в откате, который затронет только что перенесённую нагрузку. Более того, необходимо перенести только события и переменные мигрирующих объектов, а данные, связанные с откатом, не надо переносить, поскольку очередь откатов очищается в конце цикла GVT.
Каждый из алгоритмов был протестирован на трёх наборах входных данных. При этом варьировалась внешняя нагрузка. Результаты экспериментов показали, что процедуры миграции могут дать положительный эффект в различных условиях моделирования – при различных нагрузках.
Результаты можно интерпретировать следующим образом:

Мультиагентный подход к решению задачи балансировки

Распределенные веб-сервисы

В настоящее время веб-сервисы находят все более широкое применение. Они используются в самых разных случаях в Интернет. Быстрое увеличение числа веб-сервисов и пользователей этих сервисов требует высокопроизводительных веб-серверов для реализации быстрых ответов на запросы, которые могут появиться в любой момент времени. Необходимо добиваться еще и того, чтобы веб-серверы были достаточно надежны.
Для реализации высокопроизводительных и надежных веб-серверов используют распределенные веб-серверы. Распределенные веб-серверы представляют собой набор веб-серверов – это продублированные ресурсы для одновременного предоставления сервисов многим клиентам. Входящие запросы могут быть распределены по серверам согласно определенным стратегиям распределения загрузки и поэтому эти запросы могут быть быстро обработаны. Распределенные веб-серверы могут быть организованны различным образом:
Распределенные веб-серверы обладают высокой степенью масштабируемости. Количество их может быть увеличено простым добавлением в нового сервера в локальную сеть.

Балансировка загрузки распределенных веб-сереров

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

Использование мобильных агентов

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

Различные подходы к балансировке, основанные на технологии клиент-сервер

Рассмотрим различные подходы к балансировке нагрузки. Выделяют следующие категории:
Клиентский подход реализует выбор сервера на стороне клиента. Клиенты могут выбрать один из веб-серверов случайным образом или выбрать наиболее подходящий сервер, используя механизмы интеллектуального выбора. Браузер Netscape Navigator использует клиентский подход при доступе к своим сайтам. Когда пользователь просматривает домашнюю страницу Netscape, Navigator случайным образом выбирает один из серверов и направляет ему запрос пользователя. Случайный выбор не может гарантировать балансировку загрузки и доступность сервера. Интеллектуальный выбор сервера может быть реализован с использованием Java апплетов, запущенных на стороне клиента для определения состояния серверов и задержек в сети. В этом случае может быть выбран наиболее подходящий сервер и запрос отправлен именно ему. Недостаток данного подхода состоит в большой временной задержке, вызванной определением состояний серверов.
Подход, основанный на DNS – это решение на стороне системы. Сервер служба имен доменов – это механизм маршрутизации для распределенных веб-серверов. Он может выбрать один из веб-серверов для обработки запроса путем отображения унифицированного указателя информационного ресурса (URL УУИР) на IP адрес веб-сервера. Однако DNS-сервер может стать узким местом в процессе маршрутизации. Существуют программные продукты для распределения нагрузки между многими географически рассредоточенными серверами, в которых DNS-сервер определяет и доступность серверов, и временную задержку в сети для выбора подходящего сервера, использующего технологию клиент-сервер.
Чтобы получить полный контроль над маршрутизацией клиентских запросов диспетчерский подход выполняет отображение адресов на уровне IP. Он определяет группу веб-серверов с одиночным виртуальным IP адресом, которым является IP адрес диспетчера. Диспетчер в свою очередь действует в качестве центрального планировщика и имеет полный контроль над маршрутизацией запросов. Диспетчер идентифицирует каждый сервер с частным адресом и, если нужно, перенаправляет клиент-серверный пакет, переписав IP адрес. В основе лежит механизм на основе TCP-маршрутизатора, TCP- маршрутизатор играет роль диспетчера. Основным недостатком подхода с переписыванием пакета является накладные расходы на изменение адреса.
Другая схема: перенаправления пакетов – перенаправление на уровне HTTP. Здесь диспетчер распределяет входящие запросы по серверам через механизмы перенаправления, предоставляемые HTTP. Диспетчер может перенаправить запрос посылкой ответа клиента, при этом в заголовке ответа указан адрес сервера. В этом случае клиент еще раз отправляет запрос, но уже напрямую на сервер.
Серверный подход использует механизм двухуровневой диспетчеризации. DNS сервер первоначально определяет сервер, на который идет клиентский запрос. После этого каждый сервер может переопределить запрос к другому серверу. Это децентрализованная стратегия перераспределения загрузки, в которой всем серверам разрешено участие в процессе балансировки загрузки. Существует реализация этого подхода на основе веб-сервера Apache. Эта реализация позволяет произвести однородное перераспределение HTTP запросов от перегруженных серверов к малоиспользуемым. Запрос передается по цепочке функций принятия решений, называемых функциями-кандидатами. Каждая функция-кандидат переупорядочивает набор доступных серверов и выбирает метод перераспределения запроса (HTTP перенаправление или через HTTP-прокси), основываясь на информации о ресурсах.

Мультиагентный подход к балансировке

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

Проект Traveller

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

Проект Messengers

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

Проект Flash

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