На правах рукописи

Калашников Евгений Игоревич

Адаптивные алгоритмы управления

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

системах

Специальность 05.13.15 - «Вычислительные машины,

комплексы и компьютерные сети»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Москва 2010 г.

Работа выполнена в Московском государственном институте электроники и математики на кафедре «Вычислительные системы и сети»

доктор технических наук, профессор

Научный руководитель:

Саксонов Евгений Александрович

Официальные оппоненты: доктор технических наук, профессор Фролов Евгений Борисович кандидат технических наук, доцент Будихин Анатолий Владимирович

Ведущая организация: ФГУ Государственный НИИ информационных технологий и телекоммуникаций «Информика»

Защита диссертации состоится « 21 » декабря 2010г. в 13:00 часов на заседании диссертационного совета Д 212.133.03 при Московском государственном институте электроники и математики (МИЭМ): 109028, Москва, Б. Трехсвятительский пер. дом 3.

С диссертацией можно ознакомиться в библиотеке МИЭМ.

Автореферат разослан «19» ноября 2010г.

Ученый секретарь диссертационного совета доктор технических наук, доцент Ю. Л. Леохин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования.

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

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

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

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

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

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

Для достижения указанной цели в работе поставлены и решены следующие задачи:

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

разработана система показателей качества балансировки в кластерах, которые позволяют количественно оценивать параметры кластерной системы в зависимости от результатов балансировки;

разработан комплекс математических моделей для расчета параметров кластерной системы при различных алгоритмах балансировки, учитывающих детерминированную и стохастическую природу потока запросов;

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

На защиту выносятся:

Модели для расчета характеристик кластерной системы с учетом параметров оборудования, потока запросов и алгоритмов балансировки и распределения нагрузки между серверами;

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

Комплекс имитационного моделирования для расчета параметров систем при различных алгоритмах балансировки.

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

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

Разработке рекомендаций администраторам систем по настройке оборудования в кластерных системах.

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

Достоверность и обоснованность результатов основаны на проведении предварительного анализа свойств исследуемых объектов и использовании его результатов при построении математических моделей, согласованности полученных результатов с известными результатами других авторов и данными о практическом применении при создании реальных систем.

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

Апробация работы. Основные положения диссертационной работы доказывались и обсуждались на научно-практических конференциях и семинарах, в том числе:

Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ (Москва 2007г. - 2009г.).

II Международная научно-практическая конференция «Современные информационные компьютерные технологии mcIT-2010» (Гродно, Беларусь, 2010г.).

Публикация. Основное содержание диссертационной работы отражено автором в 7 печатных работах (в том числе 1 публикация в издании, рекомендованном ВАК).

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, сформулированы цель и задачи исследования, показана научная новизна и практическая ценность полученных результатов.

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

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

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

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

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

В качестве критерия эффективности балансировки обычно принимают два показателя:

время пребывания заявки на сервере (waiting time);

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

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

Least Loaded (LL, Наименее загруженный) - выбор сервера по критерию наименьшей загрузки его ресурсов (процессор, память, диск, количество очередей сообщений);

Least Connected (LC, Наименьшее количество соединений) - выбор сервера по критерию наименьшего числа текущих открытых TCP/IPсоединений;

Fast Response (FR, Наиболее быстрый отклик) - выбор сервера по критерию самого быстрого ответа на тестовый запрос от распределителя нагрузки;

Weighted Round Robbin (WRR, Взвешенное круговое распределение) при циклическом переборе каждому серверу, в отличие от статической дисциплины RR, передается подряд не один запрос, а несколько, в соответствии с весом сервера, пропорциональным, скажем, его текущей загрузке.

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

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

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

а) распределение нагрузки между серверами;

б) определение требующейся производительности серверов.

Во второй главе проведен анализ современных средства оценки эффективности методов (алгоритмов) балансировки нагрузки и соответствующих математических моделей.

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

Соответственно, изменение нагрузки необходимо отслеживать и корректировать работу алгоритма балансировки, адаптируя его к меняющимся условиям.

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

• ожидание в очереди на обслуживание к серверу;

• простой сервера.

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

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

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

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

Для вычисления величины интегрального критерия качества системы используется формула:

штраф за простой запросом в очереди к серверу i в течение единицы времени, d - штраф за простой сервера i в течение единицы времени, N i количество серверов, i - интенсивность потока запросов на сервер i, bi среднее время обслуживания запроса (производительность сервера).

Считается, что распределение нагрузки на сервера задается с помощью системы коэффициентов ( 1, 2,.., N ) таких, что 1 i 0, (i = 1,2,...,N) и = 1. Таким образом, интенсивность потока запросов на сервер номер i i =1 i равна i = i, где - интенсивность общего потока запросов на кластер.

распределения нагрузки, получена следующая формула:

d (b ) = Поскольку в общем случае нежелательны простои серверов, то при отсутствии запросов возможно выполнение фоновых задач, что определяет производительность сервера, связанную с обработкой запросов (среднее время обработки запроса - b i для сервера номер i).

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

Для решения задачи при детерминированном потоке запросов использовался метод неопределенных множителей Лагранжа, применение которого сводится к решению системы уравнений:

..........

..........

Поскольку реальные задачи имеют большую размерность, предложено упростить решение, разбив задачу на два этапа. На первом этапе вычисляется оптимальное распределение входного потока между серверами i, i = 1, N, а на втором этапе вычисляется оптимальная величина производительности для каждого сервера bi, i = 1, N. Рассмотрены различные варианты применения предложенного подхода.

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

Для решения задачи поиска оптимального распределения входного потока с использованием процедуры Кифера-Вольфовица получено:

Исследованы свойства данного алгоритма балансировки. Показано, что увеличение штрафа за простой в очереди к серверу ведет к оттоку запросов от этого сервера, а увеличение штрафа за простой самого сервера ведет, наоборот, к притоку запросов на этот сервер. Также установлено, что увеличение производительности сервера (уменьшение времени обработки запроса на сервере) ведет к увеличению доли запросов на этот сервер по двум причинам: во-первых, возрастает штраф за простой сервера и это требует увеличения потока запросов на этот сервер для того, чтобы уменьшить вероятность простоя сервера; во-вторых, уменьшается время простоя в очереди к этому серверу, а значит и затраты, связанные с простоем.

Для вычисления оптимальной производительности сервера при заданном потоке запросов на сервер получено следующее соотношение:

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

- масштабирование величины производительности сервера на текущем шаге, при котором используется следующее значение величины производительности сервера - bi ' = ( i i +1 )bi ;

- усреднение (сглаживание) интенсивности входного потока, когда величина интенсивности входного потока измеряется несколько ( K ) раз и при расчетах используется среднее значение величины интенсивности входного потока - i = i, j.

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

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

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

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

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

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

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

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

ОБЩИЕ ВЫВОДЫ

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Калашников Е.И., Адаптивное распределение нагрузки в мультисервисных сетях.//Качество. Инновации. Образование. №9, Москва, 2010. – с. 48-51.

2. Калашников Е.И., Решение задачи балансировки нагрузки серверов.// Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. Москва. МИЭМ 2007. – с. 74-75.

3. Калашников Е.И., Статический алгоритм балансировки нагрузки серверов. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. Москва. МИЭМ. 2008. – с.

212.

4. Калашников Е.И., Применение метода градиентного спуска при решении задачи балансировки нагрузки серверов.// Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ.

Тезисы докладов. Москва. МИЭМ. 2009. – с. 171.

5. Калашников Е.И., Статический алгоритм балансировки нагрузки серверов.// Информационные, сетевые и телекоммуникационные технологии.

Сборник научных трудов. Москва. МИЭМ. 2008. – с. 131-135.

6. Калашников Е.И., Оптимизация параметров обслуживающей системы со стохастическим входным потоком запросов.// Межвузовский сборник вычислительных систем», РГРТУ, Рязань. – с. 124 – 129.

7. Калашников Е.И., Оптимизация параметров обслуживающей системы со стохастическим входным потоком запросов.// II Международная научнопрактическая конференция "Современные информационные компьютерные технологии". Тезисы докладов, Беларусь, Гродно. – с. 126-131.