Адаптивные алгоритмы управления распределением нагрузки в многосерверных системах тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Калашников, Евгений Игоревич

• Калашников, Евгений Игоревич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Калашников, Евгений Игоревич

Введение.

Глава 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. Разработан программный моделирующий комплекс, который может применяться для оценки качества теоретических результатов и анализа систем с непуассоновскими входными потоками, что расширяет область применения предложенного метода балансировки.

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

Список литературы диссертационного исследования кандидат технических наук Калашников, Евгений Игоревич, 2010 год

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).