Авторы: А. М. Бершадский, Л. С. Курилов, А. Г. Финогеев
Источник: Известия высших учебных заведений. Поволжский регион. Технические науки Выпуск № 4 / 2009 http://cyberleninka.ru/article/n/issledovanie-strategiy-balansirovki-nagruzki-v-sistemah-raspredelennoy-obrabotki-dannyh
Рассматриваются методы и средства балансировки нагрузки в системах распределенной обработки данных. Проведена систематизация стратегий балансировки нагрузки по основным признакам, выделены как особый класс прогностические стратегии распределения нагрузки, обладающие полезными для применения свойствами и расширяющие возможности потенциального увеличения производительности распределенных систем. Предложена неклассическая прогностическая модель, основанная на синергетическом подходе и использующая фрактальные методы описания динамики нагрузки, и синтетический обобщенный подход к составлению прогнозов изменения нагрузки, основанный на объединении классического и фрактального методов.
Ключевые слова: распределенные системы, балансировка нагрузки, классификация стратегий, прогностические стратегии.
Задача обеспечения оптимального использования распределенных ресурсов в гетерогенных вычислительных сетях по праву является одной из самых приоритетных. От успешного решения данной задачи в исключительной степени зависит общая эффективность распределенной среды, выражающаяся прежде всего в максимизации производительности вычислительных компонент, наращиваемости информационных компонент системы, оптимизации сетевого трафика [1, 2].
Множество методов, предлагаемых для достижения целей интеграции ресурсов в распределенных системах, как правило, основывается на классических традиционных подходах, которые, несомненно, обладают определенными достоинствами, достаточно хорошо изучены и успешно применяются на практике. К таким методам можно отнести методы математической статистики, линейного программирования, теории вероятности, теории графов и др. Адекватность моделей, в рамках которых работают эти методы, обеспечивается разработанностью матаппарата и обоснованностью соответствующих теорий.
Вместе с тем резервы по повышению эффективности внутрисистемного взаимодействия в распределенных средах еще не исчерпаны. Новые подходы, принципиально отличающиеся от традиционных, обещают улучшить характеристики существующих схем управления распределенными ресурсами.
Рассмотрим одну из актуальных задач, значение которой для области распределенной обработки данных трудно переоценить. Речь идет о процедуре балансировки нагрузки. Она оказывает решающее влияние на способность распределенной системы эффективно планировать и распределять сетевые ресурсы [3–7].
Введем базовую классификацию стратегий балансировки нагрузки. Здесь и далее рассматриваются автоматические стратегии, реализованные в составе специализированного программного обеспечения системного или промежуточного (middleware) уровня в составе инструментального комплекса либо непосредственно включенные в состав прикладных распределенных программных комплексов. Ручные и полуавтоматические способы балансировки нагрузки не представляют интереса, так как их можно отнести к сравнительно простым и зачастую примитивным формам генерации плана распределения.
По ряду существенных признаков можно условно выделить следующие основные классы стратегий:
В отличие от статических и полудинамических, динамические средства балансировки изначально ориентированы на меняющиеся условия функционирования, поэтому преимущества динамических стратегий проявляются в полной мере в системах, где заранее неизвестны некоторые параметры функционирования вычислительных процессов, что связано как с эндогенными, так и экзогенными факторами (структурой и алгоритмом межпроцессного взаимодействия, характером выделения ресурсов в системе и т.п.). Следует признать, что статические стратегии привлекают разработчиков своей простотой и высокой эффективностью на приложениях с предсказуемым ходом вычислений, а также при наличии некоей априорной информации о предстоящих вычислениях. Однако далеко не всегда их использование уместно в динамически меняющихся средах – сказываются присущие им ограничения. С динамическими стратегиями тесно связаны понятия миграции ресурсов, а именно миграция процессов и миграция данных. Специфика переноса нагрузки с узла на другие узлы в гетерогенных системах затрагивает вопросы совместимости, портируемости, интероперабельности, масштабируемости.
Дополним вышеприведенную классификацию, типизировав стратегии балансировки нагрузки по некоторым важным второстепенным (частным) признакам. В рассмотрение не включены многие признаки, которые несущественны для большинства областей применения (например, исключены классификации по степени гранулярности ресурсов, приоритезации вычислений,прозрачности и т.д.).
Как видно из классификации, наибольший интерес для крупномасштабных гетерогенных распределенных сетей представляет динамическая адаптивная стратегия балансировки с возможностью прогнозирования будущих изменений нагрузки в отдельных узлах, на отдельных участках сети и во всей системе в целом (рис. 1).
(рис. 1)
Прогностические модели применительно к средствам балансировки и распределения ресурсов до недавнего времени не были популярны и почти не рассматривались, а если и обсуждались, то в основном чисто теоретически. Тем не менее большой потенциал, который заключен в них в плане утилизации незадействованных ресурсов, открывает альтернативные пути повышения общей производительности сетевых распределенных систем. Широкое распространение идей распределенной гетерогенной обработки, подкрепленное прогрессом в сетевых технологиях, позволяет сделать вывод о несомненной актуальности исследований в области прогностических методов балансировки нагрузки.
В зависимости от конечных целей используют долгосрочные прогнозы (макропрогнозирование) и краткосрочные (микропрогнозирование). Первый тип прогнозов полезен, когда планируется нагрузка на достаточно большие периоды времени и важна оценка общих объемов ресурсов с учетом долговременно действующих факторов (особо это заметно по влиянию так называемых «сезонных» колебаний). Микропрогнозирование обычно выполняется на уровне квантифицируемых порций вычислений, критерием эффективности краткосрочных прогнозов можно считать получаемый выигрыш от прогноза с учетом вычислительных затрат на выполнение собственно прогнозирования.
Стратегии прогнозирования можно разделить на централизованные и децентрализованные. В первом случае прогноз составляется в одной активной точке на основе данных, собранных со всех узлов сети. Во втором случае каждый узел в отдельности независимо занимается прогнозированием изменения собственной нагрузки, и, таким образом, имеется множество активных точек. Заметим, что не следует соотносить централизованное и децентрализованное прогнозирование с централизованным и децентрализованным управлением (см. классификацию стратегий, приведенную ранее), поскольку, в принципе, результаты прогнозов, полученные с различных узлов в сети, может использовать в своей работе централизованный агент – планировщик.
Проиллюстрируем проблему разбалансировки на следующем примере. Предположим, что в распределенной системе с постоянно меняющейся загрузкой запущено несколько вычислительных процессов одного распределенного приложения. Для простоты будем считать, что каждый процесс работает на отдельном узле. Процессы выполняют полезную работу в фоновом режиме (отдавая приоритет выполнения процессам операционной системы и прикладным процессам пользователя узла). Работа процессов синхронизирована в определенных точках, и в течение шага синхронизации каждый процесс выполняет свою долю типовых расчетов, пропорциональную производительности своего узла. Если отмасштабировать нагрузку относительно временного интервала, то каждая доля расчетов должна быть произведена всеми процессами приблизительно за одно и то же время (рис. 2).
(рис. 2)
Однако в узлах возможны события, замедляющие локальный фоновый процесс и обусловленные активностью основных процессов. В результате целевые процессы заканчиваются позже запланированного времени, и может возникнуть ситуация, когда «семеро одного ждут», т.е. переработавшие процессы вызывают непроизводительный простой (потерю ресурсов), кратный количеству узлов, выполнивших работу вовремя:
(формула)
Следовательно, задача прогноза – минимизировать потери M за счет предсказания границ Tреальн(i) и, соответственно, перераспределения вычислительных долей (нагрузки) с учетом рассчитанного предсказания.
Введем прогностическую модель распределения вычислительной нагрузки с целью предсказания будущей производительности узла сети для динамической адаптации в условиях постоянного изменения показателя производительности. Функция изменения рабочей нагрузки узла распределенной системы может быть представлена в виде последовательности значений выборок, полученных на основе промежуточных измерений. Интегральной характеристикой для всей системы будет являться генеральная совокупность таких последовательностей для всех узлов сети.
Классический подход заключается в применении статистических методов, традиционных и распространенных для анализа временных рядов. Если представить процесс изменения нагрузки в виде дискретного набора точек, отображающих загруженность (или наоборот, свободные ресурсы) узла в конкретный момент, измеренную через интервалы времени, то полученный временной ряд легко подвергнуть статистической обработке. Понятно, что во многих случаях на совокупностях выборок определенного временного масштаба в силу природы информационных процессов в сети удается выделить детерминированную составляющую (периодическую и непериодическую), определяющую поведение загруженности и явно отличающуюся от случайной составляющей по критерию сигнал/шум (SNR). Выявленную зависимость можно использовать, в частности, для вероятностного прогноза будущей загруженности узлов с целью улучшения распределения нагрузки, например за счет экстраполяции.
При формировании значений временного ряда, которые подвергнутся дальнейшей обработке, следует особое внимание уделить процедуре дискретизации проводимых измерений. Интервал, выбранный для измерения загрузки, должен быть ни слишком малым, ни чрезмерно большим. При малых значениях шага дискретизации увеличиваются накладные непроизводительные расходы. Слишком большой шаг может привести к существенному увеличению простоев в случае неточности очередного прогноза. На выбор шага также влияет степень гранулярности распределения ресурсов, особенно вычислительных.
При обработке допускается масштабирование значений ряда посредством накопляющей децимации, когда несколько временных интервалов объединяются в один, более длинный, с соответствующим суммированием значений нагрузки. Иногда бывает целесообразно использовать неоднородную дискретизацию с варьирующимся размером интервала, причем закон изменения временных интервалов может носить, вообще говоря, нелинейный характер. Это полезно в тех случаях, когда в определенные периоды требуется более подробная картина изменения нагрузки в отдельных частях системы. Вместо численных значений, показывающих конкретные уровни нагруженности, могут применяться нормированные значения нагрузки [0, …, 1], фактически отражающие коэффициент использования оборудования в течение заданных интервалов времени (отношение текущей загрузки к максимально возможной). Анализ также можно проводить не по непосредственным значениям нагрузки, а по разнице между максимальной и минимальной измеренной нагрузкой за один масштабный период (рис. 3).
(рис. 3)
Для составления комплексной модели, отражающей динамику функционирования всей распределенной системы в целом, следует проводить многомерный анализ временных рядов – как совокупности значений, измеряемых во всех узлах сети параллельно и независимо. При этом с целью выявления закономерностей более высокого порядка можно привлекать обширный набор инструментов из арсенала матстатистики (например, вычисление кросскорреляции и т.д.).
Следует отметить, что несмотря на то, что рассматриваемые распределенные системы по своей природе являются детерминированными программируемыми системами, процесс их функционирования трудно предсказать с достаточно высокой точностью. Системы данного класса по своим свойствам можно отнести к сложным динамическим системам, и их функционирование уже рассматривать в рамках теории динамических систем с точки зрения синергетического подхода со всеми вытекающими отсюда последствиями.
Альтернативный подход к созданию прогностической стратегии основан на фрактальном принципе и связан с синергетическим представлением об информационных процессах в сложных системах. Здесь гипотеза о нелинейном характере изменения рабочей нагрузки опирается на фундаментальные положения теории детерминированного хаоса и теории динамических систем. Предполагается, что распределенная среда относится к классу нелинейных динамических систем, поведение которых соотносится с хаотическим квазислучайным движением с определенной степенью аутопойетической организации, что выражается в возникновении в информационной вычислительной среде стохастических флуктуаций под воздействием дестабилизирующих факторов. Этот феномен определяется Ч. Л. Сайерсом следующим образом: «Процесс характеризуется детерминированным хаосом, если он генерирован полностью детерминированной системой, возникающей как результат беспорядочно функционирующих рядов в стандартных временных диапазонах».
Взамен ортодоксальной классической модели предлагается фрактальная модель [8], по-видимому, обладающая свойствами, более адекватными реальности, поскольку линейные методы не достаточно хорошо описывают сложные нелинейные процессы. Фрактальный анализ динамики процессов изменения нагрузки сводится к выявлению во временных траекториях фрактальных структур с масштабной инвариантностью. Параллельно следует проанализировать изменение параметров распределенной среды с представлением динамики ее развития вероятностными траекториями в фазовом пространстве состояний, а также изучить поведение исследуемой системы вблизи аттракторов, непосредственно влияющих на изменение ее производительности. Обнаруженное фрактальное самоподобие вероятностных траекторий может быть использовано для прогнозирования динамики нагрузки и подбора оптимальных параметров балансировки информационного трафика в виртуальной распределенной среде. Для описания фракталов хорошо подходит IFS-метод на основе систем итерируемых функций. Процедура поиска фрактальных инвариантов во многом похожа на те, что используются в алгоритмах фрактального сжатия.
Рисунок 4 иллюстрирует простейший пример, в котором инвариант масштабирования обнаруживает фрактальные признаки внутри временного ряда, что позволяет использовать найденную зависимость при составлении прогноза на будущее развитие вычислительного процесса.
Резюмируя вышеизложенное, следует отметить, что целесообразно объединить классический и фрактально-синергетический подходы, определив области их применимости и эффективности, выработать единую комплексную стратегию для описания динамики нагрузки. В тех случаях, когда затраты на выявление фрактальных свойств динамики превысят разумные пределы, либо не дадут приемлемых результатов, нужно будет воспользоваться средствами, которые предлагают традиционные статистические методы.