автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Адаптивные алгоритмы управления распределением нагрузки в многосерверных системах

004617145

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

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

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

системах

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

- 9 ЛЕН 2010

АВТОРЕФЕРАТ

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

Москва 2010 г.

004617145

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

сети»

Научный руководитель: доктор технических наук, профессор

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

Официальные оппоненты: доктор технических наук, профессор

Фролов Евгений Борисович

кандидат технических наук, доцент Будихин Анатолий Владимирова

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

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

С диссертацией можно ознакомиться в библиотеке МИЭМ. Автореферат разослан «1^» ноября 2010г.

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

10. Л. Леохин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Исследованы различные методы балансировки и показано, что в зависимости от конкретного метода балансировки нагрузки (круговой DNS,

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

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

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

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

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

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

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

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

4. Least Connected (LC, Наименьшее количество соединений) - выбор сервера по критерию наименьшего числа текущих открытых ТСРЛР-соединений;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= + где а -

/=1 2(1 -л, 1

штраф за простой запросом в очереди к серверу /в течение единицы времени, d. - штраф за простой сервера i"b течение единицы времени, N -

количество серверов, Яг- - интенсивность потока запросов на сервер i, b- -

среднее время обслуживания запроса (производительность сервера).

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

системы коэффициентов {a{,a1,..,aN) таких, что 1>а, >0, (г = 1,2,...Д) и

N _ .

Та--1. Таким образом, интенсивность потока запросов на сервер номер i Ы 1

равна Я, = а, А., где Л - интенсивность общего потока запросов на кластер.

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

N aiaj2A2bi2 S.

S(a1,a2...aN ,bl,b2...bN)= £{—-—— + —-(1 - aiAbi)}, где

/=1 2(1 - a¡Abi) b.

d(b) = ~, b e (0;-Ц-).

b А

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

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

N а:а:2А2Ъ;2 5 min {S(.al;a2...ccN,b],b7...bN)= У { ' 1 + -Ц1-«гЛ6,-)}}

a.,b. г=1 2(1 — а; Ab-) о-

i' i ' ' 1

N i

при ограничениях у = i, а. ^0 и ¿, е (0;—).

1 1 ' Л

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

- в1а,Л2Ь',2(а,Л Ъх - 2)/(2(а1Ь1 - I)2 )- • Л 1 + х = О

- а2а 2А2Ъ22 (а 2А Ъ2 - 2)/{2 (а 2Л 6 2 - I)2)- 8Х - Л, + л: = О

- а„апА2Ьп2(а пАЬп - 2)/2 {а„АЪп -Л)2 - 5„ -Л + л = О • £ а, - 1 - О

- а,«,2Л26,(а1Л61 - 2) /(г Са 1А 61 - I)2 )+ <5,(1 + а,Л)/Ь2 = 0

- ага2 А2Ьг(а2АЬ2 - 2)/\2(а2ЛЬ2 - I)2 )+ 32( 1 + а2Л)Д22 = 0

- ала„2А2Ь„(апАЬ„ - 2)/г{апАЪп -I)2 + 5„(1 + а„Л)/Ь2 = О

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

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

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

п~У' , a, (al + 0,01 ■ п'У>)2 А2 Ъ2

al _ а]----!— +

■ " + 1 " 10 2(1 - (а 1 + 0,01 ■ п "/4 )A6j )

+ jL(1 _ (e , + 0,01 , И-*)Л*. «,(!-(« 4-0.01 ■п-Ху)2А2Ь2 + 1>1 1 2 (I — (1 — (я I + 0,01 • п )) Л Aj )

+ i_(1 _ (1 _ (в1 + 0,01 . - £■("'-0,01 -n-У^у-ь,

ъх • 1 2(1 - (а 1 - 0,01 • п~/')АЬ. )

_-£-(1 0.01 - -0.0'

1 2(1 - (1 - (а 1 + 0,01 ■ п'Л))КЬх) - —(1 - (1 - («1 - 0,01 • п'У<))АЪ.} 1

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

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

n X аА2(Ьп +0,01 -п X)2

b" + l = ~~ÎÔ~[2(1-A(l +0,01- n-У^У

V 1/ яЛ2 (£ - 0,01 .«-X)2

---—--г--(1 -К(Ъ +0,01 -n"/4))---V—-----

(Ь +0,01.«" >4) " 2(1-Л(0и -0,01. «^))

1 п ' '

_.-g _ -(1-Л(6я -0,01-н"^))]

(6 - 0,01 • п / 4 )

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

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

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

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

1 к ■

входного потока - Л, = — £Л .

К >1

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

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

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

1

1 145 -

1

г»:

I ^!

ог 1

а) б)

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

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

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

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

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

Врмм

2 I й

I „, *—----—.—.—~—_~—.—

Рис. 2. Результаты вычислений.

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

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

ОБЩИЕ ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 11.11.2010. Фермат 60x84/16. Бумага типографская № 2. Печать - ризография. Усп. печ. л. 1,2 Тираж ВО. экз. Заказ -1036.

Московский государственный институт электроники и математики 109028, Москва, Б.Трехсвятительский пер., 3.

Центр оперативной полиграфии (495) 91$-88-04, 916-89-25

Введение.

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

1.1 Введение.

1.2 Модель клиент-сервер.

1.2.1 Клиенты и серверы.

1.2.2 Трехзвенная клиент-серверная модель.

1.2.3 Варианты реализации архитектуры клиент-сервер.

1.2.4 Программное обеспечение в технологии клиент-сервер.

1.3 Проблема управления нагрузкой серверов.

1.4 Современные методы и средства балансировки нагрузки.

1.4.1 \УеЬ-сайты из нескольких серверов.

1.4.2 Схемы распределения нагрузки во многомашинной системе

1.5 Алгоритмы балансировки нагрузки в промышленных реализациях.

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

1.5.2 Алгоритмы, используемые в аппаратных балансировщиках нагрузки.

1.5.3 Алгоритмы, используемые в программных балансировщиках нагрузки.

2.2 Современные методы анализа и оптимизации производительности вычислительных систем.70

2.2.1 Оптимизация вычислительных систем и сетей с учетом поступающей информации.70

2.2.2 «Нечувствительная» балансировка.72

2.2.3 Стохастический анализ влияния случайных задержек.74

2.2.4 Математическая модель в асимметричной серверной ферме 76

2.3 Статистика использования реальных вычислительных систем

79

2.3.1 Официальный сайт Мурманского Государственного Технического Университета.80

2.3.2 КиноПоиск.ги.88

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

2.5 Заключение.99

Глава 3. Модели для анализа алгоритма управления.101

3.1 Введение.101

3.2 Описание системы.101

3.3 Характеристики и параметры системы.104

3.4 Анализ системы при статических параметрах потока запросов 108

3.4.1 Комплексная задача.108

3.4.2 Задача одновременного выбора параметров серверов и распределения входного потока.109

3.4.3 Задача распределения входного потока между серверами 114

3.4.4 Задача выбора производительности серверов.121

3.5 Анализ системы при стохастических параметрах потока запросов 125

3.5.1 Краткое описание процедуры Кифера-Вольфовица.126

3.5.2 Задача распределения входного потока между серверами 127

3.5.3 Задача выбора параметров серверов.134

3.6 Заключение.147

Глава 4. Моделирование алгоритма управления. Применение результатов 149

4.1 Введение.149

4.2 Моделирующий комплекс.151

4.3 Алгоритм работы моделирующего комплекса.153

4.3.1 Генерация входного потока.154

4.3.2 Изменение настраиваемого параметра системы.155

4.3.3 Сбор статистики.157

4.4 Результаты работы моделирующего комплекса.158

4.4.1 Задача выбора производительности сервера.159

4.4.2 Задача распределения входного потока.164

4.5 Сравнение адаптивного метода с существующими методами 167

4.6 Применение результатов для создания центра управления

СОДИ ТПП России.169

4.7 Заключение.176

Заключение.177

Список литературы.178

Приложение 1.186

Приложение 2.192

Приложение 3.198

Приложение 4.204

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ьт1п(1атЬс1а = 0,75)

Ьгтп (1атЬс1а = 5) — — Ьгшп(1атЬс)а = 10) л ни О X А с; <и

I-^ с£ о га сп О. х 2! о 0 а ?с: га х л с: га

5 з:

Ус О

1,4 1,2 1 0,8 0,6 0,4 б/а

Рис. 3.5.3.2.3. Зависимость оптимальной величины производительности от соотношения весовых коэффициентов

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

3.5.3.4 Результаты

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

Заключение

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

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

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

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

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

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

1. Александров А. Г. Оптимальные и адаптивные системы. М.: Высшая школа, 1989. 263с.

2. Андреев А., Кокорева О., Чекмарев А., Юрченко Л. Microsoft Windows ХР. Руководство администратора Серия: В подлиннике. -СБП:БХВ-Петербург, 2007. 848 с.

3. Бизли, Дэвид М. Язык программирования Python. Справочник. — К.: ДиаСофт, 2000. — 336с.

4. Борисова В. Н. 1С: Бухгалтерия 7.7. Компьютерный учет. Методические материалы М:ИКС Технологии 208с.

5. Вабищевич П.Н. Численные методы: Вычислительный практикум. Практическое применение численных методов при использовании алгоритмического языка Python. М.:Книжный дом "Либроком", 2010. -320с.

6. Вазан М. Стохастическая аппроксимация. М.:Мир, 1972. - 296с.

7. Гамильтон С. Управление цепочками поставок с Microsoft Axapta М:Альпина Бизнес Букс, 2005. - 352с.

8. Герасимов А.И. Аналитические методы исследования и оптимизации вычислительных систем и сетей на основе сетевых моделей массового обслуживания. М.: Радио и связь, 2001 240 с.

9. Герасимов А.И. Оптимизация и балансировка систем и сетей с учетом поступающей информации. Труды института конструкторского-технологической информатики РАН. М., 2005.

10. Гласс Г., Эйблс К. Unix для программистов и пользователей. -СПБ:БХВ-Петербург, 2004. 848 с.

11. Гнеденко Б.В., Даниэлян Э.А., Димитров Б.Н. и др. -Приоритетные системы обслуживания. М.: МГУ, 1973 448с.

12. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие для вузов.-М.:Сов. радио, 1980 272с.

13. Деревицкий Д. П., Фрадков А. Л. Прикладная теория дискретных адаптивных систем управления. М.: Наука, 1981. 216с.

14. Диттнер Р., Мейджорз К. и др. Виртуализация и Microsoft Virtual Server 2005.- М.:Бином-Пресс, 2008 432с.

15. Дорофеев А. Телевизионный контент в мультисервисных сетях. // Broadcasting. Телевидение и радиовещание. 2008. №4. - с. 80-81.

16. Егоров В. Ю. Microsoft Dynamics NAV 5. Руководство пользователя М:ЭКОМ Паблишерз, 2009. 1088с.

17. Журнал сетевых решений/Lan. Электронный ресурс. URL: http://www.osp.ru/lan/text/302/38041.html (Дата обращения 12.04.2007).

18. Ивента. Электронный ресурс. URL: http://www.rhd.ru/docs/manuals/enterprise/RHEL-AS-2 Л-Maniial/install-guide/ch-lvs-overview.html (Дата обращения 14.09.2009).

19. Информатизация общего среднего образования. Под. ред. Матроса Д. Ш. М.: Педагогическое общество России, 2004. 384с.

20. КиноПоиск.ги. Электронный ресурс. URL: http://www.kinopoisk.ru/ (Дата обращения 23.07.2008).

21. Клейнрок Л. Вычислительные системы с очередями. — М.:Мир, 1979.-600с.

22. Компания Яндекс. Электронный ресурс. URL: http://company.yandex.ru/facts/researches/ (Дата обращения 07.06.2010).

23. Куликовский Р. Оптимальные и адаптивные процессы в системах автоматического регулирования. Пер. с польск. М.: Наука, 1967. 380с.

24. Лутц М. Программирование на Python: Перевод с английского (+CD). — СПб.: Символ-Плюс, 2002. — 1136с.

25. Мирошник И. В., Никифоров В. О., Фрадков A. JI. Нелинейное и адаптивное управление сложными динамическими системами. СПб.: Наука, 2000. 550с.

26. Мишкин Э., Браун JI. Приспосабливающиеся автоматические системы. Пер. с англ. М.: ПИЛ, 1963. 672с.

27. Независимое аналитическое обозрение. Электронный ресурс. URL: http://www.polit.iinov.ru/2010/01/22/sociiiternet09/ (Дата обращения 05.06.2010).

28. Олифер В.Г., Олифер H.A. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд. СПб.: Питер, 2006. -958с.

29. Опыт информатизации образовательных учреждений Костромской области. Методический сборник. Лушина Е.А., Николаева Т.В., Ершов В.Н. М.: Бином, 2009. 260с.

30. Орлов Н. Triple play и конвергенция мультисервисных сетей. // Теле-Спутник. 2008. №4(150). с. 100-101.

31. Открытые системы. Электронный ресурс. URL: http://www.osp.ru/text/302/142985/ (Дата обращения 12.04.2007).

32. Официальный сайт корпорации Microsoft. Электронный ресурс. URL:http://www.microsoft.com/Riis/Business/Infrastructure/Unified/Scalability/LoadBa lance.mspx (Дата обращения 12.04.2007).

33. Официальный сайт министерства связи и массовых коммуникаций РФ. Электронный ресурс. URL: http://minkomsviaz.ru/monitoring-smi/xPages/entrY.8419.html (Дата обращения 10.06.2010).

34. Протасов С.С. , Белоусов С. М., Тормасов А. Г. Математическая модель и метод построения сервиса балансирования нагрузки междусерверами асимметричной фермы. Исследовательское подразделение компании SWsofí, Inc, USA.

35. Растригин JI. А. Адаптация сложных систем. Рига: Зинатне, 1981. -375с.

36. Рид Дж., Доан М. Настольная книга SAP-консультанта. Книга, которая расскажет, как добиться успеха в мире SAP СПБ: Эксперт РП, 2008. -288с.

37. Робачевский А., Немнюгин С., Стесик О. Операционная система UNIX. СБП:БХВ-Петербург, 2007. - 656с.

38. Роббинс A. Unix. Справочник. М:КУДИЦ-Пресс, 2007. - 864с.

39. Рязанцева Н., Рязанцев Д. 1С:Предприятие. Секреты программирования СПБ:БХВ-Петербург, 2005. - 352с.

40. Саммерфилд М. Программирование на Python 3. Подробное руководство. — Перевод с английского. — СПб.: Символ-Плюс, 2009. — 608с.

41. Саридис Дж. Самоорганизующиеся стохастические системы управления. М.: Наука, 1980. 400с.

42. Снайдер М., Стегер Дж. Microsoft Dynamics CRM 4.0 М: Эком, 2009. - 624с.

43. Спикльмайр С. и др. Zope. Разработка Web-приложений и управление контентом. — М.: ДМК., 2003. — 464с.

44. Срагович В. Г. Адаптивное управление. М.: Наука, 1981. 384 с.

45. Статистика Livelnternet.ru. Электронный ресурс. URL: http://www.liveinternet.ruystat/kinopoisk.ru/index.htm] (Дата обращения 05.06.2010).

46. Статистика Livelnternet.ru. Электронный ресурс. URL: http://www.livemternet.ru/stat/kinopoisk.ru/index.html?period=inonth (Дата обращения 05.06.2010).

47. Статистика Livelnternet.ru. Электронный ресурс. URL: http://www.liveinternet.m/stat/mstu/index.html?date~2Q 10-05-29&id=:0&id=8&show:=пepecтpoить+гpaфик&report=indcx■html%ЗFdate%ЗD20 10-05-29 (Дата обращения 05.06.2010).

48. Статистика Livelnternet.ru. Электронный ресурс. URL: http^/www.Hveinternet.ru/stat/mstu/mdex.htm^id^Ozid^Sidate^O 10-05-29:period=month (Дата обращения 05.06.2010).

49. Сузи Р. А. Язык программирования Python: Учебное пособие. — М.: ИНТУИТ, БИНОМ. Лаборатория знаний, 2006. — 328 с.

50. Сузи Р. А. Python. Наиболее полное руководство (+CD). — СПб.: БХВ-Петербург, 2002. — 768с.

51. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб. Литер, 2003. - 877с.

52. Тюкин И. Ю., Терехов В. А. Адаптация в нелинейных динамических системах М.: ЛКИ, 2008. 384 с.

53. Управление молекулярными и квантовыми системами. Перевод с английского И. А. Макарова. Под редакцией А. Л. Фрадкова и О. А. Якубовского. Сборник статей. Москва-Ижевск: Институт компьютерных исследований, 2003. 416 с.

54. Фомин В. Н., Фрадков А. Л., Якубович В. А. Адаптивное управление динамическими объектами. М.: Наука, 1981. 448 с.

55. Фрадков А. Л. Адаптивное управление в сложных системах: беспоисковые методы. М.: Наука, 1990. 296с.

56. Фрадков А. Л. Кибернетическая физика: принципы и примеры. С.-Петербург: Наука, 2003. 208с.

57. Цыпкин Я. 3. Адаптация и обучение в автоматических системах. М.: Наука, 1968. 400с.

58. Шапиро Д.Р., Бойс Д., Полихт М., Паттерсон Б., Лезерс С. Windows Server 2003. Библия пользователя. М:Вильямс, 2006. - 1216 с.

59. Шустикова Т. 1С: Зарплата и Управление персоналом. М:НТ Пресс, 2007. - 256с.

60. Abdallah С. Т., Alluri N., Birdwell J. D., Chiasson J., Chupryna V., Tang Z., and Wang T. A Linear Time Delay Model for Studying Load Balancing Instabilities in Parallel Computations. The International Journal of System Science, to appear, 2003.

61. Alanyali M., Hajek В., Analysis of simple algorithms for dynamic load balancing, Mathematics of Operations Research 22-4 (1997) 840-871.

62. Bonald Т., Jonckheere M. and Proutiere A. Insensitive Load Balancing. France Telecom R&D.

63. Bonald Т., Proutiere A. Insensitivity in processor-sharing networks, Performance Evaluation 49 (2002) 193-209.

64. Bonald Т., Proutiere A., Insensitive bandwidth sharing in data networks, Queueing Systems 44-1 (2003) 69-100.

65. Brown M.C. Python: The Complete Reference. McGraw-Hill Professional Publishing, 2001 г. - 1200p.

66. Chun W.J. Core Python Programming. Prentice Hall PTR, 2000 r. -816p.

67. CIT Forum. Электронный ресурс. URL: http://www.citforum.ru/cfin/alg ob web ser/ (Дата обращения 12.04.2009).

68. Daley D. J. and Vere-Jones D. An Introduction to the Theory of Point Processes. Springer-Verlag, New York, 1988.

69. David Beazley, Guido Van Rossum. Python: Essential Reference. -New Riders Publishing, 1999 г. 352p.

70. Dowling K. SAP Project System Handbook McGraw-Hill Osborne Media, 2008 r. - 298c.

71. Gerasimov A.I. On normalazing Constants in Multiclass Queueing Networks // Operation Research 1995. - Vol. 43, N 4. - P.704-711.

72. Gupta R. Making use of Python. Wiley, 2002 г. - 1136p.

73. Hamilton S. Managing Your Supply Chain Using Microsoft Axapta -McGraw-Hill, 2004 r. 272c.

74. Hayat M.M., Dhakal S., Abdallah C.T. Dynamic Time Delay Models for Load Balancing. Part II: A Stochastic Analysis of the Effect of Delay Uncertainty. University of Tennessee, Knoxville, TN 37996, USA

75. Jacobs F.R., Whybark D.C. Why ERP? A Primer on SAP Implementation McGraw-Hill/Irwin, 2000r. - 144c.

76. Lutz M. Programming Python (2nd Edition). O'Reilly & Associates, 2001 г. - 1296p.

77. Lutz M., Ascher D. Learning Python. O'Reilly, 1999 г. - 384p.

78. PC Magazine. Электронный ресурс. URL: 1 (Дата обращения 12.04.2009).

79. SOCIETYSTYLE Новости общества и образования. Электронный ресурс. URL: http://mysocietvstyle.blogspot.com/2010/04/pronilcnovenie-intemeta-v-rossii.html (Дата обращения 10.06.2010).

80. Python programming language. Электронный ресурс. URL: http://www.python.org/download/ (Дата обращения 15.03.2008).

81. WEB Optimizator. Электронный ресурс. URL: http://webo.in/articles/habrahabr/06-client-side-balancing/ (Дата обращения 12.04.2009).

82. Webmascon. Электронный ресурс. URL: http://webmascon.eom/topics/technolog:ies/4b.asp (Дата обращения 12.04.2007).

83. Webmascon. Электронный ресурс. URL: http://www.webmascon.com/topics/technologies/4e.asp (Дата обращения 14.04.2007).

84. Wikipedia. Электронный ресурс. URL: http://ru.wikipedia.org/wiki/KHHorioHCK (Дата обращения 05.06.2010).