Содержание к диссертации
Введение
Глава 1. Исследование задачи балансировки вычислительной нагрузки в глобально распределённых вычислительных комплексах 20
1.1. Исследование особенностей и задач реализации современных распределённых комплексов 20
1.1.1. Распределённые вычислительные комплексы и их классификация 21
1.1.2. Особенности архитектуры современных РВК 23
1.1.3. Концепция GRID Computing 27
1.1.4. Задача балансировки вычислительной нагрузки в РВК
1.2. Анализ существующих подходов к решению задачи балансировки нагрузки для распределённых комплексов 32
1.3. Анализ и классификация методов балансировки нагрузки узлов распределённого вычислительного комплекса 36
1.4 Алгоритмы балансировки нагрузки, применяемые в промышленных системах 40
1.5. Прогностический подход к балансировке нагрузки в распределённых вычислительных комплексах 45
Выводы по 1 главе 47
Глава 2. Разработка метода балансировки вычислительной нагрузки на основе прогнозных моделей 49
2.1. Постановка задачи балансировки узловой нагрузки 50
2.2. Применение метода квазилинеаризации для оценки загрузки узла 52
2.3. Нахождение прогнозных оценок загрузки узла РВК 54
Выводы по 2 главе 57
Глава 3. Экспериментальное исследование метода балансировки нагрузки для распределённыхвычислительных комплексов 58
3.1. Анализ влияния параметров модели на производительность распределённого вычислительного комплекса 59
3.2. Разработка имитационной модели исследуемого комплекса 61
3.3. Анализ полученных результатов
3.3.1. Расчёт индекса безразмерной ошибки прогнозирования и анализ производительности работы разработанного алгоритма 68
3.3.2. Анализ влияния структуры файловой системы 74
3.3.3. Анализ влияния протокола передачи данных 75
Выводы по 3 главе 78
Глава 4. Методы реализации программных средств балансировки вычислительной нагрузки дляраспределённых вычислительных комплексов 79
4.1. Концепция разработки сложных программных систем 79
4.2. Обоснование выбора программно-аппаратных средств реализации разрабатываемой программной системы 84
4.3. Организация программной системы балансировки вычислительной нагрузки в РВК 92
Выводы по 4 главе 98
Заключение 99
Список литературы
- Концепция GRID Computing
- Применение метода квазилинеаризации для оценки загрузки узла
- Разработка имитационной модели исследуемого комплекса
- Обоснование выбора программно-аппаратных средств реализации разрабатываемой программной системы
Концепция GRID Computing
Ранее [105] было показано, что «существенный прорыв в области построения пространственно-распределёных комплексов образовался благодаря развитию концепции GRID (Global Resource Information Distribution). Идея Grid Computing (распределенные сети, или "решетки" вычислительных ресурсов) на сегодняшний день представляет собой ведущую технологию создания РВК» [105]. Учитывая все недостатки первых систем, а именно невозможность реализации данных систем в гетерогенной среде, дальнейшие разработки был направлены на разрешение данной проблемы. «В 1998 году Фостер и Кельман опубликовали статью [29], в которой предложили концептуально новый подход к организации глобально распределённых комплексов и систем» [105]. Как следует из статьи, грид комплексы являются «программно-аппаратными структурами, обеспечивающими надёжный и недорогой доступ к высокопроизводительным вычислительным возможностям» [29]. Как было уже показано ранее [105], «грид-архитектура позволяет соединять между собой географически рассредоточенные вычислительные узлы, посредством сети Интернет, в некоторую абстрактную решётку (англ. GRID - решётка), в которой каждый узел предоставляет ресурсы для совместного использования в конкретной задаче». «Данная вычислительная модель комплекса позволяет объединять не только сосредоточенные кластеры, но и ПК обычных пользователей сети Интернет в некий единый виртуальный суперкомпьютер. Возможность использования данного подхода к организации территориально-распределенных комплексов стало возможным, благодаря развитию общей индустрии информационных технологий, а именно:
На рисунке 1.3 представлена одна из возможных структур Grid Computing. Коммуникационная сеть Управляющий сервер Рисунок 1.3 — Структура грид Среди значимых комплексов второго поколения, которые подробно рассмотрены в [105], можно выделить такие проекты как Globus [30], gLite [32], Legion [33], Unicore [34]. «Проект Globus с разработанным инструментарием Globus Toolkit, позволяет объединить множество территориально распределённых гетерогенных ресурсов в единую виртуальную систему. Инструментарий Globus Toolkit имеет открытый исходный код. Стоит понимать, что данный инструментарий не является готовым техническим решением для организации распределённых вычислений, а представляет собой лишь набор стандартов и инструментов [31]. Популярность такого инструментария обусловливается, прежде всего, отсутствием жёсткой модели программирования, в результате чего разработчик может использовать широкий набор средств, в соответствии с потребностью. Проект Globus был поддержан многими производителями программного обеспечения, такими как IBM, Sun, HP, Intel» [105].
«Проект Legion был разработан в университете Вирджиния и представляет собой программную среду для организации географически распределённой системы, в состав которой могут входить рабочие станции, векторные суперкомпьютеры и параллельные суперкомпьютеры [35]. Основное отличие от других комплексов подобного рода является поддержка объектно-ориентированной модели, в которой грид представлялся в виде «легиона» и все узлы системы являются компонентами «легиона». Однако многих исследователей отталкивала объектно-ориентированная модель, вследствие чего их внимание смещалось в сторону Globus, а проект был закрыт» [105].
Как показано ранее [105], «концепция грид-среды активно развивается и отечественными учёными». «К примеру, исследователями Лаборатории вычислительных систем Института физики полупроводников им. А.В. Ржанова СО РАН и Центром параллельных вычислительных технологий Сибирского государственного университета телекоммуникаций и информатики (СибГУТИ) создана масштабируемая грид-модель – пространственно-распределённая мультикластерная ВС. В состав комплеска входят вычислительные кластеры данных организаций. Операционная система комплекса построена на ядре Linux. Так же в состав комплекса входит инструментарий разработчика для разработки программных продуктов, включающий такие средства как GCC, ряд библиотек для организации параллельных вычислений (MPI, OpenMP) [36]» [105].
В работе [105] показано, что «дальнейшим развитием в области построения пространственно-распределённых систем явилась разработка третьего поколения grid. Основная задача построения данных комплексов направлена не на стандартизацию интерфейсов, а на решение вопросов самоорганизации и автоматизации процессов, происходящих в grid [37]. Стоит понимать, что исследования в области стандартизации интерфейсов не прекратились, а продолжают развиваться в таких концепциях, как SOA и SOC, что привело к созданию новых коммуникационных протоколов, в частности SOAP (Simple Object Access Protocol)».
Применение метода квазилинеаризации для оценки загрузки узла
Метод квазилинеаризации (квазиньютоновский метод) является одним из наиболее часто применяемых на практике методов идентификации динамических нелинейных объектов. На сегодняшний момент метод, разработанный Беллманом и Калабой, был обобщён на ряд задач. Метод квазилинеаризации представляет собой итерационный процесс решения нелинейной п-го порядка последовательности линейных дифференциальных уравнений.
Метод преобразования нелинейной задачи в линейную позволяет произвести идентификацию и оценивание параметров состояния системы, значения которых представлены в виде векторов параметров и вектора состояния системы. При этом, часть компонентов вектора параметров и вектора состояния может отсутствовать или же не поддаваться полностью измерению. Это особенно важно для задачи предсказания загрузки узлов РВК, так как здесь параметры модели обычно также неизвестны.
Рассмотрим модель загрузки узла РВК на интервале [tit2] в виде нелинейной системы, описываемой уравнением [106] x(t) = f[x(t),u(t),q], (2.1) где x(t) - вектор состояния размерности п; для определенности будем считать, что наблюдаемой величиной - загрузкой узла РВК является первая компонента вектора х, u(t) - вектор входных воздействий размерности т; под входными воздействиями модели понимаются внутренние задачи, выполняемые узлом в данный момент времени, q - вектор параметров системы размерности к, f - гладкая вектор-функция размерности п.
Как было показано ранее [106], модель (2.1) рассматривается в непрерывном времени, так как, хотя компьютер и является цифровым устройством (то есть, по определению, дискретным), элементарные кванты времени компьютера настолько малы (менее 1 нс) по сравнению с интервалами принятия решений о распределении нагрузки между узлами (не менее 10 мс).
Будем считать, что векторы u(t) и x(t) могут быть измерены, причем u(t) полностью измерим, а x(t) может измеряться частично (некоторые компоненты в некоторые моменты времени). Вид компонент вектор-функции f предполагается известным, причем из практических соображений компоненты этой функции удобно рассматривать в виде полиномов не выше третьего порядка [76]. Компоненты вектора q неизвестны и не изменяются во времени, то есть, q = 0. (2.2)
Обозначим через tk текущий момент времени. Так как наша задача заключается в нахождении прогнозных значений загрузки узла РВК х1 (tk+1), а измерениям поддается та же величина в предыдущие моменты времени х1 (tt),i к, при том, что вектор параметров q нам также неизвестен, то вводим новый вектор [106]
Как было показано ранее [106], метод квазилинеаризации основан на нахождении линеаризованного приближения относительно предыдущей итерации (собственно, поэтому метод и называется квазилинеаризация). Если найдена N-я итерация оценки нового вектора состояния (3) %N(t)(t), то, раскладывая уравнение (2.4) в степенной ряд относительно найденного приближения zN(t) и оставляя только члены первого порядка малости, получаем следующее (N+1J-е приближение оценки искомого вектора:
. Для получения менее громоздких формул в обозначениях к формуле (2.6) опущен аргумент времени для переменных, однако, надо помнить, что все указанные элементы являются функциями времени [106]. Уравнение (2.6) линейно относительно XN+ЛО и, следовательно, может быть переписано в следующем линейном виде: 2N+l(t) = AN (t)xN+l (t) + VN+l, (t) (2.7) где: 4v( ff Зж X(t)=xN{t) (0 = эч z(t)=zN(t) дх Z(t)=zN(t) 4V(0-4v(0i;v-(0 Уравнение (2.7) является линейным и нестационарным относительно переменной Хм+ЛО. Его решение в форме Коши имеет вид: t XN+l(t) = YN(tJQ)xN+l(tQ)+\YN(t,T)VN(i)dT, (2.8) to иначе, с учетом обозначений к (2.7), t ZN+I (0 = YN {t, t0 )ZN+1 M+j YN {t, T)WN (z)dT to t -JYN(t,T)AN(T)xN(T)dT, to где XN(t, т) - фундаментальная матрица уравнения (2.9) %N+l (t) = AN (t)xN+[ (t). (2.10) Как было показано ранее [106], для оценки прогнозных значений загрузки узла РВК xx(tk+x) следует найти вектор %N+\{t) размерности п+к, включающий в себя п компонент вектора состояния x(t) и к компонент оценки вектора параметров модели q. Для этого необходимо иметь п+к измерений. Как уже говорилось, измерению поддаются предыдущие значения первой компоненты вектора x(t) в t моменты времени. Тогда новый вектор состояния на N + 1 итерации %N+1(t0) удовлетворяет граничному условию X1 (tj ) = Y1,N (tj, t0 )xN+1 (t0 ) + p1,N (tj ), j = 1, n + k, (2.11) где p1,N(tj) = \ Y1,N(tj,T)VN(T)dr,j = 1,n + k. (2.12) t0
В уравнениях (2.11) и (2.12) Y1,N() представляет собой 1-ую строку фундаментальной матрицы YN(). Так как произведено п+к измерений, то уравнений (2.11) тоже п+к, и они представляют собой полную систему линейных алгебраических уравнений с п+к переменными. Решение этой системы дает п+к компонентов, составляющих вектор zN+1(t0), последние к компонент которого представляют собой оценку искомого вектора параметров q. По найденному значению ZN+1( 0) и фундаментальной матрице Y1,N() легко ищется прогнозное значение загрузки узла [106]: 1,v( +1) = [1 0 - 0]lN+1(tk+1), ZN+1(tk+1) = YN(tk+1J0)ZN+1(t0)+ j YN(tk+1,T)4 N(T)dT t k+1 j Уы(Ч+1,т)Аы(т)Хы(т? , (2.13)
Метод квазилинеаризации отличается квадратичной сходимостью [4], если только он вообще сходится. Для обеспечения сходимости алгоритма необходимо, чтобы начальное приближение было не очень далеко от истинного значения параметров. Для получения адекватного начального приближения имеет смысл использовать методы прогнозирования, основанные на фрактальных свойствах трафика [66,76].
Разработка имитационной модели исследуемого комплекса
Однако, для оценки качества прогнозирования методом квазилинеаризации, использование таких оценок как индекс безразмерной ошибки и среднеквадратичной ошибки модели в некоторых случаях бывает недостаточно. На практике, для этих целей, часто применяют совокупность расчёта стандартного отклонения и интервальную оценку для исследуемого прогнозного параметра. В отличие от точечной оценки параметра, метод построения доверительного интервала статистической величины нагрузки является хорошим способом проверки не только точности, но и надёжности (качества) прогнозирования разработанной модели, по сравнению с другими моделями, например ARIMA.
Для построения доверительных интервалов характерно использование больших доверительных вероятностей (порядка 0,9; 0,95;0,99). Для наших целей необходимо найти верхнюю и нижнюю границу доверительного интервала текущей нагрузки с вероятностью 90% . Так как для установления требуемых границ необходимо знать характеристики закона распределения, что не всегда возможно, то, в случае, если объём выборки маленький (порядка п 30), рекомендуют использовать распределение Стьюдента (t-распределение) [101]. Однако, на практике применение t-критерия для среднего возможно только для генеральной совокупности данных, которая имеет нормальное распределение, что на практике не всегда может быть достигнуто [102,103]. Варианты решения данной проблемы заключаются, либо в непосредственном моделировании расчета доверительного интервала [104], либо в увеличении выборки и применении асимптотически корректных методов [102]. Так как, полученные в ходе эксперимента данные можно с лёгкостью обрабатывать машинными методами, то второй подход является в данных условиях наиболее предпочтительным. Доверительный интервал для среднего по совокупности данных, закон распределения вероятностей которого описывается непрерывным нормальным распределением, рассчитывается по следующей формуле: x , = ju x + t /9т=, (3.5) UC І І ТІ ( « /ТІ где х - выборочное среднее арифметическое; t - квантиль распределения Стьюдента уровня ; s - несмещённое среднее квадратичное отклонение по выборке; п - размер выборки; ju - среднее по совокупности.
Формула (3.5) применяется для больших (стремящихся к бесконечности) совокупностей данных. Для того чтобы обеспечить возможность работы с относительно небольшими выборками, необходимо учесть поправку на конечность выборки [104]. Таким образом, формула 3.5 может быть переписана следующим образом: x =1-— u x+t =1- — , (3.6) a/24n\ N a/24n\ N N - объём генеральной совокупности. В формуле (3.6) значение t / =.1-- представляет собой точность интервальной оценки, которую можно обозначить через Є , соответственно, формула (3.6) может быть переписана следующим образом: х-є JLKX + Є (3.7) Формула (3.6) позволяет найти машинным методом, значения доверительного интервала для относительно малых выборок генеральной совокупности, которые на практике составляют порядка 10 N 200.
В общем виде алгоритм нахождения доверительного интервала прогнозной нагрузки для конкретного узла состоит из следующих шагов: 1. Установить объём генсовокупности N=50 и соответствующий объём выборки (число элементов не менее 5% от генсовокупности [см. 104]). 2. Проанализировать полученную генеральную выборку значений нагрузки по всем узлам за период наблюдения, с целью вычисления выборочного среднего для каждого узла. 3. По таблице квантилей распределения Стьюдента найти соответствующие значение t / при уровне =0,1 (Р=0,9) и числе степеней свободы т = п-1. Данная таблица может быть получена с помощью Excel функции «СТЬЮДРАСПОБР». В качестве значений квантиля распределения при вероятности 90 % примем t / =1,67. 4. Далее, подставляя полученные значения в формулу (3.6) , найдём границы доверительного интервала для каждого узла. 5. Отдельно вычислим точность интервальной оценки є = t , „ = Jl -— аП4п\ N Таким образом, возможно нахождение интервальных оценок для значений вычислительной нагрузки, что впоследствии, можно использовать в качестве критерия оценки качества прогнозирования. Например, полученные значения доверительного интервала для значений нагрузки при соответствующем уровне =0,1, говорят о том, что с 90% вероятностью, реальная загрузка узла системы должна лежать в тех границах, которые определяются формулой (3.6). Соответственно, выход реальной нагрузки из расчётного доверительного интервала говорит не только о качестве прогнозирования, но и позволяет оценить влияние различных факторов на ход работы вычислительной системы. Глубокий анализ влияния факторов позволяет выявить негативные тенденции, которые оказывают сильное влияние на систему в целом. В ходе проведённого эксперимента, количество выхода реальных нагрузок из доверительного интервала составило порядка 6,4% для метода экспоненциального сглаживания и 3,1% для метода прогнозирования на основе квазилинеаризации, что позволило говорить о высоком качестве прогнозирования вычислительной нагрузки данными методами.
Полученные значения коэффициента вариации по всем узлам, а также общее процентное соотношение количества выходов реальной нагрузки из предсказанного доверительного интервала, позволили выявить некоторое преимущество разработанного метода, по сравнению с методом экспоненциального сглаживания. В частности, разработанный метод лучше реагирует на возникающую нагрузку и обладает лучшей производительностью. Однако, для повышения адаптивности алгоритмов балансировки нагрузки к резким изменениям нагрузки в РВК, необходимо производить периодический мониторинг всей системы и корректировку параметров прогностических алгоритмов, в соответствии с предсказанными значениями. 3.3.2. Анализ влияния структуры файловой системы
В результате анализа экспериментальных данных было выявлено [114], что структура файловой системы оказывает существенное влияние на производительность алгоритмов балансировки нагрузки. Так, при загрузке системы, стремящейся к 1, резко (см. рисунок 3.4) ухудшалась работа системы, построенной на основе бездисковой модели структуры файловой системы. Разработанный прогностический алгоритм на основе метода квазилинеаризации, так же как и метод на основе экспоненциального сглаживания, показали наилучшие результаты (см. рисунок 3.3 и рисунок 3.4). Данный эффект можно объяснить тем, что при больших нагрузках, а именно при больших количествах операций ввода/вывода, общий файловый сервер становится «узким» местом всего вычислительного комплекса. Особо остро данный проблема встаёт на тех узлах, на которых используется файл подкачки (англ. paging).
Обоснование выбора программно-аппаратных средств реализации разрабатываемой программной системы
Стоит отметить, что существует и ряд других технологий, позволяющих осуществить вызов удалённых процедур для нашей задачи. Так как разработка системы ведётся на языке JAVA, то стоить упомянуть про RMI (англ. Remote Method Invocation). RMI представляет собой программный вызов удалённых процедур для программм на языке JAVA. Преимуществом RMI по сравнению с непосредственной реализацией взаимодействия с использованием сокетов, заключается в упрощении программирования взаимодействия между клиентом и сервером. При использовании RMI, разработчику совсем не обязательно следить за используемыми портами, протоколами передачи данных, а также форматировать сообщения между клиентом и сервером. По своей сути, технология RMI представляет собой дистанционный вызов удалённых процедур, реализованных на основе технологии Socket, представляющих разработчику набор готовых методов для работы. Таким образом, использование RMI позволяет значительно упростить процесс разработки.
Для хранения данных используется соответствующая система управления базами данных (СУБД). Так как в рамках данного проекта в качестве основной парадигмы программирования был выбран объектно-ориентированный подход, то возникла задача выбора СУБД, использующей в качестве основной модели данных объектную модель. Преимущество объектно-ориентированных баз данных заключается в том, что данные, которые хранятся в БД, моделируются в виде объектов, классов и методов, что, в свою очередь, позволяет тесно интегрировать и наиболее полно использовать все преимущества объектно-ориентированного подхода при создании сложных систем.
В результате анализа СУБД, реализующих объектно-ориентированную модель хранения данных, в качестве основной ООСУБД была выбрана db4o [100]. Отличительной особенностью db4o является открытость исходного кода и относительная легкость использования в случае знакомства с технологией объектно – реляционного отображения (ORM) для связи реляционных баз данных с концепцией объектно-ориентированного программирования (библиотека Hibernate).
Таким образом, для реализации системы координирования вычислительной нагрузки в РВК в качестве основного языка был выбран язык JAVA, на котором велась разработка в среде программирования Eclipse, а в качестве системы управления базой данных был выбран движок db4o.
Все алгоритмы, разработанные в предыдущих главах диссертационного исследования, были реализованы в едином программном комплексе. Основные фрагменты исходного кода системы представлены в Приложении_2. Используя принципы экстремального программирования и модульный подход к разработке, была разработана программная система. Стоит отметить, что платформа JAVA позволяет эффективно создавать приложения с динамически подключаемыми модулями (англ. pluggable application). На момент написания данной главы существует множество подходов к созданию модульных программных систем на языке JAVA, например [98, 99], каждый из которых имеет свои преимущества и недостатки. В данной работе, для обеспечения модульности разрабатываемого приложения, был применён фреймворк (англ. framework) Java Plug-in Framework (JPF). Использование JPF позволило создать приложение с подключаемыми «на лету» (динамическими) модулями, что привело к снижению использования оперативной памяти в целевой системе.
Как было отмечено выше, разрабатываемое приложение должно состоять из клиентского и серверного приложения. Основными задачами клиентского приложения являются сбор статистической информации о текущей нагрузке и ходе процесса обработки задания, а также, непосредственно, передача в расчёт поступившего задания