Содержание к диссертации
Введение
Глава 1. Проблемы управления нагрузкой серверов в распределенных системах 11
1.1 Введение 11
1.2 Модель клиент-сервер 12
1.2.1 Клиенты и серверы 12
1.2.2 Трехзвенная клиент-серверная модель 14
1.2.3 Варианты реализации архитектуры клиент-сервер 20
1.2.4 Программное обеспечение в технологии клиент-сервер 24
1.3 Проблема управления нагрузкой серверов 29
1.4 Современные методы и средства балансировки нагрузки 29
1.4.1 Web-сайты из нескольких серверов 31
1.4.2 Схемы распределения нагрузки во многомашинной системе 35
1.5 Алгоритмы балансировки нагрузки в промышленных реализациях 53
1.5.1 Общие сведения об алгоритмах, используемых в балансировщиках нагрузки 53
1.5.2 Алгоритмы, используемые в аппаратных балансировщиках нагрузки. 62
1.5.3 Алгоритмы, используемые в программных балансировщиках нагрузки 65
1.6 Заключение 68
Глава 2. Обзор математических моделей балансировки нагрузки 70
2.1 Введение 70
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
Приложение 186
- Варианты реализации архитектуры клиент-сервер
- Алгоритмы балансировки нагрузки в промышленных реализациях
- Официальный сайт Мурманского Государственного Технического Университета
- Задача одновременного выбора параметров серверов и распределения входного потока
Введение к работе
Актуальность исследования.
Развитие и внедрение в повседневную жизнь населения информационных систем обусловило резкое увеличение числа запросов на обработку, увеличение нагрузки на обрабатывающее оборудование (серверы).
Использование высоконагруженных систем, услугами которых пользуется большое количество пользователей, требует применения в качестве аппаратной платформы серверных групп или кластеров. Кластер состоит из нескольких компьютеров, объединенных высокоскоростным соединением. Для пользователей кластер выглядит как один компьютер, а внутри он является разновидностью сети, которая может быть распределенной или локальной.
Важное звено кластера сосредоточено в устройстве или программном обеспечении, распределяющем нагрузку (поток запросов) между компьютерами кластера. Это устройство (программное обеспечение) называется балансировщиком нагрузки. Основной проблемой, связанной с балансировкой, является вопрос о том, как распределять нагрузку наиболее эффективно. Для этого нужно формализировать методику оценки качества работы балансировщика, которая зависит от параметров системы и параметров входного потока запросов.
Поскольку нагрузка на информационные системы будет постоянно расти, задачи балансировки будут приобретать все более важное значение для повышения эффективности информационных систем.
В связи с этим актуальным является проведение исследований, направленных на повышение качества балансировки, путем выявления и устранения недостатков, присущих известным алгоритмам балансировки.
Целью работы является разработка и анализ методов адаптивной балансировки позволяющих повысить качество балансировки нагрузки в многосерверных кластерных системах и эффективность работы таких систем.
Для достижения указанной цели в работе поставлены и решены следующие задачи:
проведен обзор современных методов и средств балансировки трафика и методов анализа и оптимизации современных кластерных систем, позволивший выявить особенности балансировки нагрузки, закономерности и связи между параметрами оборудования и параметрами потока запросов при балансировке, что дало возможность с формул ирвоать задачи работы;
разработана система показателей качества балансировки в кластерах, которые позволяют количественно оценивать параметры кластерной системы в зависимости от результатов балансировки;
разработан комплекс математических моделей для расчета параметров кластерной системы при различных алгоритмах балансировки, учитывающих детерминированную и стохастическую природу потока запросов;
разработан комплекс имитационных моделей для исследования алгоритмов балансировки в случаях, когда построение и применение математических моделей либо невозможно, либо требует существенных упрощений при их построении. Проведено сравнение результатов аналитического и имитационного моделирования, показавшее достаточную точность предложенных методов.
На защиту выносятся:
Модели для расчета характеристик кластерной системы с учетом параметров оборудования, потока запросов и алгоритмов балансировки и распределения нагрузки между серверами;
Методы применения алгоритмов стохастической аппроксимации для решения задач балансировки, учитываюшие специфику работы серверов, как систем массового обслуживания, связанную с необходимостью выполнения условий, обеспечивающих существование стационарного режима работы.
Комплекс имитационного моделирования для расчета параметров систем при различных алгоритмах балансировки.
Научная новизна заключается в том, что выявлены особенности балансировки при стохастической природе входного потока запросов,
позволившие выбрать адаптивный алгоритм и модель для его анализа, основанную на процедуре стохастической аппроксимации, а также в разработке математических моделей для анализа работы многосерверной системы обеспечивающих возможность численно вычислить значения показателей качества работы системы, оптимизировать заданные показатели качества и параметры серверов.
Практическая значимость результатов диссертации состоит в создании комплекса моделей, позволяющих проводить балансировку при случайных изменениях параметров потока запросов, программной реализации адаптивного алгоритма балансировки нагрузки, которая произведена в разработанном для этого моделирующем комплексе. Разработке рекомендаций администраторам систем по настройке оборудования в кластерных системах.
Полученное математическое и программное обеспечение позволяет решать задачи балансировки с учетом реальных свойств входного потока запросов, что повышает практическую значимость результатов.
Достоверность и обоснованность результатов основаны на проведении предварительного анализа свойств исследуемых объектов и использовании его результатов при построении математических моделей, согласованности полученных результатов с известными результатами других авторов и данными о практическом применении при создании реальных систем.
Методы исследования. Для решения поставленных задач использованы методы общей теории систем, теории массового обслуживания, стохастической аппроксимации, теории управления.
Апробация работы. Основные положения диссертационной работы доказывались и обсуждались на научно-практических конференциях и семинарах, в том числе:
Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ (Москва 2007г. - 2009г.).
II Международная научно-практическая конференция «Современные информационные компьютерные технологии mcIT-2010» (Гродно, Беларусь, 2010г.).
Публикация. Основное содержание диссертационной работы отражено автором в 7 печатных работах (в том числе 1 публикация в издании, рекомендованном ВАК).
Структура диссертации. Диссертация состоит из введения, четырех глав, заключения, приложений и списка литературы. Объем диссертации составляет 179 страниц.
Варианты реализации архитектуры клиент-сервер
Один из подходов к организации клиентов и серверов — это распределение программ, находящихся на уровне приложений, описанном в предыдущем пункте, по различным машинам, как показано на рис. 1.2.3.1.1. В качестве первого шага мы рассмотрим разделение на два типа машин: на клиенты и на серверы, что приведет нас к физически двухзвенной архитектуре (physically twoiered architecture).
Один из возможных вариантов организации — поместить на клиентскую сторону только терминальную часть пользовательского интерфейса, как показано нарис. 1.2.3.1.1, а, позволив приложению удаленно контролировать представление данных. Альтернативой этому подходу будет передача клиенту всей работы с пользовательским интерфейсом (рис. 1.2.3.1.1, б). В обоих случаях мы отделяем от приложения графический внешний интерфейс, связанный с остальной частью приложения (находящейся на сервере) посредством специфичного для данного приложения протокола. В подобной модели внешний интерфейс делает только то, что необходимо для предоставления интерфейса приложения. 1.2.3.1.1.
Продолжим линию наших рассуждений. Мы можем перенести во внешний интерфейс часть нашего приложения, как показано на рис. 1.2.3.1.1, в. Примером может быть вариант, когда приложение создает форму непосредственно перед ее заполнением. Внешний интерфейс затем проверяет правильность и полноту заполнения формы и при необходимости взаимодействует с пользователем. Другим примером организации системы по образцу, представленному на рис. 1.2.3.1.1, в, может служить текстовый процессор, в котором базовые функции редактирования осуществляются на стороне клиента с локально каптируемыми или находящимися в памяти данными, а специальная обработка, такая как проверка орфографии или грамматики, выполняется на стороне сервера.
Во многих системах клиент-сервер популярна организация, представленная на рис. 1.2.3.1.1, гид. Эти типы организации применяются в том случае, когда клиентская машина — персональный компьютер или рабочая станция — соединена сетью с распределенной файловой системой или базой данных. Большая часть приложения работает на клиентской машине, а все операции с файлами или базой данных передаются на сервер. Рис. 1.2.3.1.1, д отражает ситуацию, когда часть данных содержится на локальном диске клиента. Так, например, при работе в Интернете клиент может постепенно создать на локальном диске огромный кэш наиболее часто посещаемых web-страниц.
Рассматривая только клиенты и серверы, мы упускаем тот момент, что серверу иногда может понадобиться работать в качестве клиента. Такая ситуация, отраженная на рис. 1.2.3Л.2., приводит нас к физически трехзвенной архитектуре (physically threeiered architecture)
В подобной архитектуре программы, составляющие часть уровня обработки, выносятся на отдельный сервер, но дополнительно могут частично находиться и на машинах клиентов и серверов. Типичный пример трехзвенной архитектуры — обработка транзакций. В этом случае отдельный процесс — монитор транзакций — координирует все транзакции, возможно, на нескольких серверах данных.
Многозвенные архитектуры клиент-сервер являются прямым продолжением разделения приложений на уровни пользовательского интерфейса, компонентов обработки и данных. Различные звенья взаимодействуют в соответствии с логической организацией приложения. Во множестве бизнес-приложений распределенная обработка эквивалентна организации многозвенной архитектуры приложений клиент-сервер. Мы будем называть такой тип распределения вертикальным распределением (vertical distribution). Характеристической особенностью вертикального распределения является то, что оно достигается размещением логически различных компонентов на разных машинах. Это понятие связано с концепцией вертикального разбиения (vertical fragmentation), используемой в распределенных реляционных базах данных, где под этим термином понимается разбиение по столбцам таблиц для их хранения на различных машинах.
Однако вертикальное распределение — это лишь один из возможных способов организации приложений клиент-сервер, причем во многих случаях наименее интересный. В современных архитектурах распределение на клиенты и серверы происходит способом, известным как горизонтальное распределение (horizontal distribution). При таком типе распределения клиент или сервер может содержать физически разделенные части логически однородного модуля, причем работа с каждой из частей может происходить независимо. Это делается для выравнивания загрузки.
В качестве распространенного примера горизонтального распределения рассмотрим web-сервер, реплицированный на несколько машин локальной сети, как показано на рис. 1.2.3.2.3. На каждом из серверов содержится один и тот же набор web-страниц, и всякий раз, когда одна из web-страниц обновляется, ее копии незамедлительно рассылаются на все серверы. Сервер, которому будет передан приходящий запрос, выбирается по правилу «карусели» (round-robin). Эта форма горизонтального распределения весьма успешно используется для выравнивания нагрузки на серверы популярных web-сайтов. Таким же образом, хотя и менее очевидно, могут быть распределены и клиенты. Для несложного приложения, предназначенного для коллективной работы, мы можем не иметь сервера вообще. В этом случае мы обычно говорим об одноранговом распределении (peero-peer distribution). Подобное происходит, например, если пользователь хочет связаться с другим пользователем. Оба они должны запустить одно и то же приложение, чтобы начать сеанс. Третий клиент может общаться с одним из них или обоими, для чего ему нужно запустить то же самое приложение.
Алгоритмы балансировки нагрузки в промышленных реализациях
Главную роль в Web-кластере, играет распределитель нагрузки, принимающий решение о дальнейшем движении каждого запроса [67]. При этом весь Web-кластер представлен для внешнего наблюдателя только одним ІР-адресом — виртуальным IP (VIP). Кратко упомянем о механизмах маршрутизации пакетов внутри Web-кластера: 1. Однонаправленная маршрутизация (one-way routing). Распределитель нагрузки подменяет в пакетах собственный IP-адрес ІР-адресом выбранного сервера. Ответ сервера возвращается клиенту напрямую, без участия распределителя нагрузки. Web-сервер заменяет свой IP-адрес на VIP, чтобы ответ исходил из адреса, на который был послан запрос. Это позволяет разгрузить распределитель нагрузки (выходной поток значительно превышает входной), но требует изменений в коде операционной системы сервера, поскольку подмена IP-адреса происходит на уровне TCP/IP. 2. Двунаправленная маршрутизация (two-way routing). Выходной поток от сервера идет через распределитель нагрузки, который в этом случае выполняет обе подстановки адреса. При таком подходе распределитель нагрузки становится узким местом сети. 3. Маршрутизация через распределитель нагрузки (packet forwarding by the dispatcher). Подход реализован в IBM Network Dispatcher. Пересылка пакетов серверу происходит на уровне МАС-адреса, без изменения заголовка IP-пакета, для которого в данном случае не нужно перевычислять контрольные суммы. Распределитель нагрузки и серверы должны находиться в одном сетевом сегменте.
Серийно выпускаемые устройства используют, как правило, простые дисциплины обслуживания, а в экспериментальных устройствах применяются методы моделирования. Однако в любом случае должны соблюдаться следующие требования: приемлемая вычислительная сложность; совместимость с протоколами и стандартами Web; доступность распределителю нагрузки всей необходимой для принятия решения информации.
Применяемые алгоритмы диспетчеризации можно разделить на статические и динамические. В последнем случае распределитель нагрузки осуществляет периодический мониторинг серверов, входящих в кластер и выбирает для направления запроса наилучший из них. В статических алгоритмах состояние серверов не отслеживается. Выбор алгоритмов зависит от многих факторов. Повышенная «интеллектуальность» динамических алгоритмов влечет накладные расходы, связанные со сбором информации с хостов, однако выбор дисциплины обслуживания во многом зависит не только от характера трафика, но и от функциональности распределителя нагрузки.
К статическим дисциплинам относятся Random и Round Robbin. В Random сервер выбирается случайным образом с помощью равномерного распределения. Дисциплина Round Robbin реализует принцип циклического перебора, который в чистом виде выглядит так: і-ая по счету заявка поступает на сервер с номером, равным остатку от деления і на N, где N — количество серверов.
Для любой динамической дисциплины возникает задача выбора управляющих параметров, которая не всегда может быть решена точно. В качестве критерия эффективности обычно принимают два показателя: 1. время пребывания заявки на сервере (waiting time); 2. замедление (slowdown), т.е. отношение времени пребывания к длине заявки (во сколько раз замедляется обслуживание запроса из-за наличия очереди).
Наиболее естественными динамическими дисциплинами являются: 1. Least Loaded (LL, Наименее загруженный) - выбор сервера по критерию наименьшей загрузки его ресурсов (процессор, память, диск, количество очередей сообщений); 2. Least Connected (LC, Наименьшее количество соединений) - выбор сервера по критерию наименьшего числа текущих открытых TCP/IP-соединений; 3. Fast Response (FR, Наиболее быстрый отклик) - выбор сервера по критерию самого быстрого ответа на тестовый запрос от распределителя нагрузки; 4. Weighted Round Robbin (WRR, Взвешенное круговое распределение) - при циклическом переборе каждому серверу, в отличие от статической дисциплины RR, передается подряд не один запрос, а несколько, в соответствии с весом сервера, пропорциональным, скажем, его текущей загрузке.
Все эти дисциплины «слепы к содержанию» и не требуют анализа HTTP-запроса. В сравнительном исследовании дисциплин WRR, LC и LL по среднему времени ответа и загрузке серверов лучше всего показывает себя дисциплина LL. При низкой и средней загрузке WRR ведет себя гораздо хуже динамических дисциплин, а время ожидания для LC в среднем в 6 раз больше, чем для LL. С ростом нагрузки производительности сходятся, причем показатели LC стремятся к показателям LL гораздо быстрее, чем WRR. Неудивительно, что, раз LL оказалась лучше, то легче реализовать LC, поскольку для LL требуется более интенсивный обмен служебной информацией между распределителем нагрузки и серверами. Из этого анализа следует, что вопрос о том, какая из перечисленных динамических дисциплин наиболее эффективна, имеет скорее теоретическое значение.
Официальный сайт Мурманского Государственного Технического Университета
Далее рассмотрена статистика использования сайта Мурманского Государственного Технического Университета (МГТУ), собираемая популярным в русскоязычном интернете сервисом сбора статистики Liveintemet.ru. Была выбрана статистика именно этого сайта, так как она является общедоступной. То есть владелец статистики (МГТУ) включил возможность просмотра статистики для неавторизованных пользователей. Кроме того это сайт с достаточно большой посещаемостью, которая, например, в мае составила около 1400 человек в день [47]:
Как видно из графика зависимости количества посетителей от даты, количество посетителей каждый день не одно и то же. Так как сайт не является развлекательным, то основной наплыв посетителей приходится на рабочие дни. Среднее количество посетителей в рабочие дни составляет около 1600 человек в день, а в выходные - 1100 человек в день.
Рассмотрим усредненную помесячную статистику прихода уникальных посетителей за два года с мая 2008г. по май 2010г. [48]:
Как видно из графика спады посещаемости приходятся на август месяц, что отражает реальную картину профессиональной деятельности среднестатического ВУЗа. Август это месяц, когда заканчивается весенний семестр и приемная кампания, но еще не начался осенний семестр. Общий тренд роста количества посетителей сайта можно объяснить двумя факторами.
Первым фактором является то, что сайт является официальным сайтом ВУЗа и время оказывает положительное влияние на посещаемость. Приходят как новые посетители, так как те, кто уже был раньше. При этом это не только студенты и работники ВУЗа, но и выпускники. За время существования сайта ВУЗ успевает выпускать несколько потоков выпускников. Часть выпускников пользовалась сайтом во время обучения, а часть тех кто пользовался сайтом ранее, заходит на сайт и после выпуска для того чтобы узнать новости из жизни ВУЗа, возможно, узнать информацию о проведении юбилея ВУЗа.
Вторым фактором, оказывающим положительное влияние на рост посещаемости сайта, является общий тренд, связанный с ростом количества пользователей русскоязычного интернета. Рост русскоязычного сегмента интернета отмечают многие источники, как негосударственные [27, 80], так и государственное Министерство связи и массовых коммуникаций Российской Федерации [33]. То есть, даже если среднее количество студентов МГТУ и не изменилось за два года, то доля студентов, пользующихся официальным сайтом своего ВУЗа, растет.
Рассмотрим теперь, как работают посетители сайта МГТУ, то есть количество запросов к сайту и как оно зависит от дня и от времени суток. Под запросом здесь понимается запрошенная страница на сайте. Естественно, что запрос страницы на сайте чаще всего подразумевает несколько запросов - запрос самой страницы, файла со стилями на странице, файл с Java-скриптами, выполняемыми на стороне пользователя, файлов картинок, составляющих оформление страницы и т.п. Наконец, в запрашиваемой странице встроен код счетчика, на основе которого построена эта статистика. При отрисовке страницы в браузере пользователя выполняется код счетчика, в процессе чего браузер пользователя запрашивает изображение счетчика. На основе запросов изображений счетчика с сайта статистики строится статистика использования сайта. Ниже приведен график среднесуточного количества запросов к сайту МГТУ в мае 2010 года [47]:
Задача одновременного выбора параметров серверов и распределения входного потока
Рассмотрим задачу минимизации критерия качества, если количество серверов задано. Выразим интенсивность потока запросов на сервер: где аг- - доля входного потока запросов, отправляемая на сервер /. Весь входной поток запросов отправляется на сервера, поэтому сумма долей входного потока запросов на все сервера равна единице: Доля потока на каждый сервер не отрицательная величина: Зависимость штрафа за простой сервера от производительности сервера d(b) должна быть обратной - чем больше время обработки запроса, отражающее производительность сервера, тем дешевле должен быть сервер и тем меньше должен быть штраф за простой такого сервера.
Примем следующее выражение для вычисления величины штрафа за простой сервера: Где д - некий постоянный для данного сервера поправочный коэффициент. Естественным ограничением области допустимых значений производительности сервера является: Задача оптимизации системы серверов, связанная одновременно с распределением входного потока и выбора производительности серверов является задачей математического программирования с ограничениями, которую аналитически или численно можно решить, используя метод множителей Лагранжа. Для решения этой задачи методом множителей Лагранжа введем обозначения: Решение этой системы уравнений позволит вычислить оптимальное распределение входного потока запросов при оптимальных параметрах производительности серверов, а так же сами эти параметры. Однако данная задача является многомерной. Решения многомерных задач всегда очень сложны, поэтому для простоты изложения предлагается упростить это решение, разбив задачу на два этапа. На первом этапе вычисляется 113 оптимальное распределение входного потока между серверами аіг i = \,N, а на втором этапе вычисляется оптимальная величина производительности для каждого сервера bi,i = l,N при условии, что величина входного потока на этот сервер определяется соотношением (3.4.2.1). Далее рассмотрены обе эти задачи.
С учетом, что величины производительности серверов постоянные величины для решения задачи нахождения оптимального распределения входного потока между серверами необходимо решить задачу минимизации: при ограничениях т.е. сумма долей входного потока на все сервера равна общему потоку заявок поступивших на вход системы, а доля запросов на каждый сервер неотрицательная величина. Данная задача является задачей математического программирования. Для решения данной задачи применим метод множителей Лагранжа. Для этого введем обозначения: В аналитическом виде решить эти уравнения сложно. Воспользуемся для решения задачи минимизации критерия качества (3.4.1.1) численными методами. Для этого был написан скрипт на скриптовом языке Python 2.6,
Похожие диссертации на Адаптивные алгоритмы управления распределением нагрузки в многосерверных системах
