Содержание к диссертации
Введение
1 Технологии хранения и обработки больших данных 7
1.1 Методы и технологии работы с большими данными 7
1.2 Методы оптимизации размещения больших данных 24
1.3 Методы планирования высокопроизводительных вычислений с интенсивной обработкой больших данных 30
1.4 Выводы к главе 1 36
2 Технология исполнения композитных приложений с совмещенными методами оптимизации 38
2.1 Интеграция технологий высокопроизводительных вычислений и технологий работы с большими данными 38
2.2 Концепция ipse и платформа clavire 41
2.3 Модели процессов в распределенной вычислительной среде 46
2.4 Выводы к главе 2 59
3 Алгоритмы оптимизации размещения сложных структур больших данных в стационарных условиях 61
3.1 Формальное описание задачи оптимизации размещения сложных структур в стационарных условиях 61
3.2 Описание стационарных методов оптимизации размещения больших данных 63
3.3 Экспериментальные исследования стационарных методов оптимизации размещения больших данных 76
3.4 Выводы к главе 3 85
4 Алгоритмы оптимизации размещения сложных структур больших данных в нестационарных условиях 86
4.1 Формальное описание задачи оптимизации размещения сложных структур в нестационарных условиях 86
4.2 Описание нестационарных методов оптимизации размещения больших данных 89
4.3 Экспериментальные исследования нестационарных методов оптимизации размещения больших данных 97
4.4 Выводы к главе 4 103
5 Алгоритмы планирования распределенных вычислений с использованием оптимизации размещения сложных структур 105
5.1 Формальное описание задачи планирования вычислений с использованием сложных структур в нестационарных условиях 105
5.2 Описание методов планирования вычислений с использованием сложных структур 107
5.3 Экспериментальные исследования нестационарных методов оптимизации размещения больших данных 125
5.4 Выводы к главе 5 132
Заключение 133
Список сокращений и условных обозначений 135
Список литературы 137
- Методы планирования высокопроизводительных вычислений с интенсивной обработкой больших данных
- Концепция ipse и платформа clavire
- Экспериментальные исследования стационарных методов оптимизации размещения больших данных
- Экспериментальные исследования нестационарных методов оптимизации размещения больших данных
Введение к работе
Актуальность темы исследования обусловлена интенсивным развитием технологий электронной науки (eScience), предназначенных для поддержки выполнения сложных расчетов с использованием больших объемов данных, размещенных в распределенной вычислительной среде. В России данное направление представлено в работах научных школ А.П.Афанасьева, В.П.Иванникова, В.А.Ильина, В.В. Коренькова и других исследователей. В отличие от классических суперкомпьютерных технологий, особенности работы с большими объемами данных заключаются в том, что эти данные размещаются на распределенных вычислительных узлах не равномерно по объему, а соответственно сложной структуре, диктуемой особенностями предметной области. Изменение структуры данных во времени приводит к необходимости их перераспределения для достижения наибольшей эффективности использования вычислительной инфраструктуры. Как следствие, выполнение расчетов над большими данными требует максимизации использования процессорного времени и повышения скорости работы с операциями ввода/вывода за счет использования многоуровневого хранения данных на различных по скорости работы и внутреннему объему устройствах памяти. На сегодняшний день отсутствуют методы и технологии оптимизации работы со сложными структурами больших данных в распределенной среде, которые совокупно учитывали бы особенности организации хранения и доступа к данным, а также оптимизацию самих вычислительных процессов, что делает актуальной тему диссертационной работы.
Предметом исследования являются алгоритмы оптимизации размещения больших объемов данных в распределенной вычислительной среде, а также алгоритмы планирования вычислительно-интенсивных задач в распределенных средах на их основе.
Целью исследования является разработка математического, алгоритмического и программного обеспечения для оптимизации работы со сложными структурами больших данных при выполнении расчетов в распределенных вычислительных средах.
Задачи исследования:
анализ существующих решений управления большими данными и оптимизацией их размещения, включая алгоритмы планирования, с целью определения требований к объектам исследования и разработки;
формализация постановки задачи оптимизации размещения данных и планирования на основе параметрических моделей композитных приложений и распределенной вычислительной среды;
разработка и программная реализация алгоритмов перераспределения больших данных, совмещенных с алгоритмами планирования интенсивно-вычислительных задач в стационарных и нестационарных условиях работы вычислительной среды;
- экспериментальное исследование разработанных алгоритмов для оценки их
работоспособности, эффективности и сравнения с существующими
аналогами.
Методы исследования включают в себя методы теории алгоритмов, дискретной математики, эволюционных вычислений, теории вероятностей и математической статистики, имитационного моделирования, инженерии программного обеспечения и анализа программного обеспечения.
Научная новизна исследования обусловлена тем, что в работе впервые предложено и обосновано семейство алгоритмов распределения сложноструктурированных данных в вычислительной среде, позволяющее обеспечивать их оптимальное размещение на вычислительных узлах с использованием ретроспективы эксплуатации системы, как в стационарных, так и в нестационарных условиях. На основе указанных алгоритмов разработаны алгоритмы динамического коэволюционного планирования композитных приложений на динамически реконфигурируемых вычислительных ресурсах. По сравнению с аналогами разработанные и программно реализованные алгоритмы позволили повысить эффективность использования вычислительных ресурсов и снизить время обработки больших данных в 1,2-3 раза.
Практическую значимость исследования определяет программная реализация разработанных алгоритмов оптимизации сложных структур больших данных, интегрированная в подсистему хранения данных CLAVIRE/DCStorage и обеспечивающая эффективное функционирование облачной платформы CLAVIRE.
На защиту выносятся:
семейство алгоритмов перераспределения сложноструктурированных данных на основе ретроспективы эксплуатации вычислительной среды в стационарных и нестационарных условиях;
семейство алгоритмов динамического коэволюционного планирования композитных приложений на динамически реконфигурируемых вычислительных ресурсах, учитывающих специфику обработки больших сложноструктурированных данных.
Достоверность научных результатов и выводов обусловлена: корректностью формальной постановки задач планирования перераспределения данных и выполняемых на них вычислительно-интенсивных задач; использованием параметрических моделей для оценки экспериментальных данных; результатами экспериментальных исследований на различных конфигурациях распределенной вычислительной среды, сравнений с адаптированными существующими подходами.
Внедрение результатов работы. Результаты работы использованы при выполнении проектов: «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы», шифр 2010-218-01-209 по договору от 07 сентября 2010 г. № 13.G25.31.0029, в рамках конкурса субсидий в соответствии с постановлением Правительства Российской Федерации № 218; «Распределенные экстренные вычисления для
поддержки принятия решений в критических ситуациях», дог. № 11.G34.31.0019 от 02.12.2010 г. с дополнительным соглашением № 02 от 01.03.2013 г.; «Информационная технология обеспечения жизненного цикла систем поддержки принятия решений нового поколения для задач персонифицированной медицины» № 715788 от 31.03.2015 г.; «Суперкомпьютерное моделирование критических явлений в сложных социальных системах», соглашение № 14-21-00137 от 15.08.2014 г.; «Исследования и разработка быстродействующей кластерной системы хранения и обработки сверхбольших объемов данных», соглашение о предоставлении субсидии от 24 ноября 2014 г. № 14.578.21.0077. В диссертацию включены результаты, полученные при поддержке Министерства образования и науки РФ в рамках договора № 14.Z50.31.0024.
Апробация работы. Основные результаты были представлены на следующих международных научных и научно-практических конференциях: International Conference on Computational Science (Барселона, Испания,2013); International Conference on Computational Science (Кэрнс, Австралия, 2014); The 14th International Multidisciplinary Scientific GeoConference & EXPO SGEM 2014 (Албена, Болгария, 2014); International Conference on Application of Information and Communication Technologies (Астана, Казахстан, 2014); The 9th International Conference on Soft Computing Models in Industrial and Environmental Applications (Билбао, Испания, 2014); 6th International Conference on Evolutionary Computation Theory and Applications (Рим, Италия, 2014); International Conference on Computational Science (Рейкьявик, Исландия, 2015); The 15th International Multidisciplinary Scientific GeoConference & EXPO SGEM 2015 (Албена, Болгария, 2015); 7th International Conference on Evolutionary Computation Theory and Applications (Лиссабон, Португалия, 2015); Young Science Conference (молодежная конференция, Афины, Греция, 2015); International Conference on Computational Science (Сан-Диего, 2016).
Публикации. По материалам диссертации опубликована 21 печатная работа в изданиях, рекомендуемых ВАК и индексируемых системами Scopus и Web of Science. Получено 4 свидетельства о регистрации программы для ЭВМ.
Личный вклад автора в работах, выполненных в соавторстве, заключается в обосновании требований к планированию оптимизации размещения данных и вычислении; разработке методов планирования с использованием коэволюционного подхода в условиях стационарной и нестационарной среды; разработке алгоритмов оптимизации размещения данных с учетом неоднородности ресурсов хранения по объему и скорости доступа; проработке архитектуры в целом и модулей, в частности, платформ запуска высокоинтенсивных задач на больших данных; проведении экспериментальных исследований и интерпретации их результатов.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы (181 источник). Содержит 154 страницы текста, включая 44 рисунка и 16 таблиц.
Методы планирования высокопроизводительных вычислений с интенсивной обработкой больших данных
Изучением вопроса организации и эффективной обработки больших данных активно занимаются научные группы под руководством ведущих мировых ученых: Я. Фостера[13], Е. Дилман [14], Д. Тейна[15], Я. Гордон, Р. Буйя[12], Т. Хей, Р. Продан[16], Ильин В.А.[17]. Такие работы также проводятся в исследовательских центрах крупных промышленных ИКТ-компаний, включая Google, Microsoft, Amazon и др. Для выявления существующих направлений стоит проанализировать возникающие при современных расчетах на больших данных [19, 20] проблемы и тенденции: - создание новых алгоритмов, которые способны масштабироваться при поиске и обработке больших массивов данных; - создание новых масштабируемых технологий управления метаданными сложных, гетерогенных и распределенных источников данных; - создание новых подходов в области высокопроизводительных вычислительных платформ для обеспечения равномерного высокоскоростного доступа к мультитерабайтным структурам данных; - создание специализированных коммуникационных гибридных архитектур для фильтрации и обработки потоков мультигигабайтных данных, происходящих от высокоскоростных сетей передачи данных, научных измерительных систем и систем моделирования в режиме реального времени; - разработка высоконадежных высокопроизводительных распределенных файловых систем, ориентированных на обслуживание петабайтных массивов данных; - создание новых алгоритмов для обеспечения мобильности расчетов на узлах, стоимость передачи данных с которых на другой узел слишком высока; - появление гибких и упрощенных технологий, обеспечивающих интеграцию новых плагинов и программных компонентов, работающих на разных вычислительных платформах; - развитие методов генерации подписей для данных с целью уменьшения размерности и увеличения скорости их обработки.
На сегодняшний день существует ряд подходов (парадигм), которые были разработаны для успешного решения задач обработки больших данных. Прежде всего, следует выделить два принципиально различных режима обработки: пакетный и режим реального времени (потоковый). Пакетный режим предполагает обработку статических данных и обычно не накладывает ограничений на время выполнения расчетов, ориентируясь в основном на результат обработки. Рассмотрим наиболее известные подходы к обеспечению этого режима.
Подход на основе абстракции Грид. Представителем классической концепции обработки больших данных через Грид технологии [19,20] является система, построенная в CERN – Gfarm (Grid Datafarm) [21]. В основе Gfarm лежат несколько базовых компонентов: распределенная файловая система (parallel file system), узлы ресурсов (nodes) и система выполнения расчетов. Распределенная файловая система, состоящая из расчетных узлов и сервисов метаданных, предоставляет огромный объем дискового пространства (измеряемый в петабайтах) и включает в себя возможности масштабирования пропускной способности на основные операции чтения–записи, а также функциональность по обеспечению отказоустойчивости.
Системы, основанные на этой парадигме, используют в качестве базы принцип Codeo-Data и выполняют запуск вычислительных расчетов непосредственно на узлах данных, тем самым, идеологически не отделяя их от вычислительного типа узлов. Плюсы: масштабируемость, позволяющая работать на уровне петабайтов; возможность планирования с учетом стоимости (в том числе и по времени) передачи данных для расчета и запуска любых пакетов внутри Грид; отказоустойчивость. Минусы: жесткая привязка к инфраструктурным особенностям Грид; отсутствие поддержки современных технологических решений (например, вычислительных облаков).
Попытки развития данного подхода были предприняты рядом научных групп, в том числе известных в сфере высокопроизводительных вычислений: группой создателя Grid Computing – Яна Фостера [22, 23], группой Ильина Вячеслава Анатольевича совместно с ведущим научным центром по физике высоких энергий ЦЕРН [17,24,25] и другие однако поскольку популярность Грид продолжает стремительно падать, уступая место современным технологиям, подход можно считать малоперспективным (однако работы по оптимизации расчетов data-intensive с использованием различных техник планирования развиваются и сейчас [26]).
Подход на основе абстракции WMS. На смену традиционному механизму решения задач в Грид пришла концепция, поднявшая распределенные вычисления еще на один уровень абстракции. Речь идет об организации расчетов через систему управления цепочками задач (workflow) – Workflow Management Systems, WMS [27]. WMS отделяет абстрактное описание задачи от конкретного ресурса вычислительной среды, сама среда выходит за рамки конкретной системы организации инфраструктуры и использует Грид как один из возможных вычислителей, тем самым позволяя избегать необходимости изучения его внутренней структуры и отдавая право выполнения расчетов непосредственно ему. Несмотря на то что концепция, основанная на цепочках задач, изначально была создана для Грид [28], на текущий момент она с успехом применяется как в облачных вычислениях, так и в гетерогенных средах.
Традиционно цепочка задач (workflow, WF) представляет собой направленный ацикличный граф (directed acyclic graph, DAG) [29], однако многие системы управления потоками заданий (СУПЗ) допускают наличие циклов, равно как и условных переходов между узлами. WF состоит из узлов и связей между ними. Узлом является конкретное задание, обычно представленное расчетным пакетом, моделью или просто программным обеспечением с возможностью запуска из командной строки. Связи между узлами образованы зависимостями по данным – выходные данные одного расчетного пакета являются входными другого.
Каждая СУПЗ имеет внутренние механизмы работы с вычислительными ресурсами, на которых установлены или потенциально могут быть развернуты пакеты. Принимая на выполнение очередной WF, СУПЗ с помощью алгоритмов планирования соотносит каждый его шаг c имеющимся работоспособным ресурсом так, чтобы удовлетворить выбранному критерию оптимизации. В случае учета критерия оптимизации по передаче данных можно получить эффективное решение для обработки больших данных.
Концепция ipse и платформа clavire
Однако на создание тех или иных подходов во многом повлияли факторы, которые необходимо учитывать при проектировании и реализации подобных систем [30]. оптимизация вычисления шагов при выполнении WF с целью минимизации объема передаваемых входных и выходных данных. Часто выгоднее (по времени и стоимости) выполнить очередные [14] расчеты непосредственно на узле размещения данных, а не на высокопроизводительном ресурсе с неизбежными потерями при копировании данных; оптимизация планирования задач WF с учетом специфики расчетов на сверхбольших данных и минимизацией времени на передачу данных от одного шага WF к другому (речь идет об учете накладных затрат при передаче данных между шагами WF наравне со временем выполнения самих расчетов); оптимизация локализации выполнения расчетов в ходе планирования - следование принципу Codeo-Data для шагов WF там, где это выгоднее копирования входных данных на удаленный вычислительный ресурс; - необходимость учета физического пространства как во временной, так и в постоянной памяти для выполнения самих расчетов и генерируемых результатов. При работе с большими объемами данных может не хватить вычислительных ресурсов на узле - этого необходимо избегать путем оценки и учета текущей нагрузки и состояния ресурсов; - необходимость взаимодействия модулей планирования WF и сервисов асихронного размещения данных. Подобная кооперация позволяет снизить общее время выполнения путем подготовки данных на вычислительных узлах с опережением; оптимизация передачи данных в гетерогенной среде с разными интерфейсами взаимодействия, борьба с возникающими ошибками. В той или иной степени, проблемы при использовании различных протоколов передачи данных и разных источников хранилища замедляют время расчета, что порождает также задачи оптимизации выполнения; оптимизация работы с виртуальными объектами. Часто для работы с определенными данными необходимо выполнить их предобработку, таким образом могут одновременно выполняться несколько WF, тем самым затрачивая время на одну и ту же операцию. Возможность доступа к общим виртуальным объектам могла бы решить это проблему. Получили распространение решения, основанные на каком-либо СУПЗ и имплементации MapReduce. Одна из первых реализаций – схема интеграции системы управления потоками заданий Kepler и Hadoop [170]. В основу Kepler заложен механизм взаимодействия атомарных и композитных акторов. Под актором можно понимать независимую программную сущность с определенными интерфейсами взаимодействия, либо набор других акторов, связанных друг с другом (sub-workflow). Авторы предлагают реализовать MapReduce как композитный актор, в котором реализованы внутренние атомарные акторы, описывающие отдельно операции Map и Reduce. Операция Map, по аналогии с модельным представлением самой парадигмы, определена также внутренними (на уровне sub-workflow) акторами с входными данными k1 (ключ), v1 (значение) и выходными данными – сгенерированным списком list(k2, v2). На уровне самой операции Map необходимо указать параметры inputPath (путь к входным данным), outputPath (путь к выходным данным) и Result (результат расчета), это позволяет использовать данные файловой системы HDFS, динамически сгенерированные при выполнении предшествующих акторов. Операция Reduce по такому же принципу получает на вход внутренних акторов k2, list(v2) и возвращает list(v2). Такой подход позволяет использовать функциональные возможности Hadoop как акторы, т.е. отделяемые сущности, способные работать с другими акторами в совершенно разных WF. Однако подобная унификация приводит к ощутимой потере производительности в сравнении с простой реализацией на Java.
В работе [168] M. Baranowski представлена схожая идея, основанная на системе управления потоками заданий WS-VLAM, позволяющая расширять функциональные возможности за счет модульной системы. Авторы, учитывая недостатки решения Kepler и Hadoop, предлагают использовать готовые модули Reduce, крайне редко модифицируемые для разных задач, но оказывающие весомое влияние на производительность, а менее эффективные операции Map реализовывать, используя метапрограммирование. Таким образом, MapReduce в WS-VLAM преобразуется в два шага при построении WF, первый – имплементация Map-операции; второй – выбор операции Reduce из уже интегрированных реализаций. Это позволило получить показатели затрачевоемого времени до 71 % ниже, чем у реализации только с использованием Java, в то время как решение, основанное на интеграции Kepler и Hadoop, потребовало в 6–7 раз больше времени.
Другая не менее интересная идея представлена в фреймворке Cascading [171]. Технически он реализует API для планирования и выполнения задач, возникающих при обработке сверхбольших данных, основной формой представления которой является data-processing workflow (DPW). DPW ориентированы на сложные задачи обработки данных только поверх платформы Hadoop. Используя в качестве основы парадигму source-pipe-sink , Cascading явно отделяет источники данных (source) от методов самой обработки (pipe) и от результатов, сохраняемых в выходные файлы (sink). Связки source и sink образуют потоки (flow), которые могут объединяться в каскады (cascade). Это позволяет модулю планирования легко отслеживать корректность и своевременность выполнения элементов потока, так как поток не пойдет дальше, пока все его зависимости не выполнятся. Подобная организация является важным элементом системы, так как допускает многократное использование элементов обработки pipe, да и потоков в целом, поскольку, меняя порядок выполняемых шагов, отдельные элементы потока, можно с минимумом усилий решать различные задачи. Важные аспекты Cascading: отсутствие необходимости изучения MapReduce; реализация кода на любом языке, интерпретируемом на JVM (Java Virtual Machine).
Аналогом Cascading в каком-то отношении является программное решение Oozie [172], специализирующееся на планировании WF, воспроизводящих задачи (jobs), выполняемые в Hadoop и Pig (платформа над Hadoop для анализа сверхбольших данных). Само Oozie является веб-приложением, развернутым в JSC (Java Servlet-Container). Для представления связей задач в WF используется принцип “control dependency”, основая суть которого – ожидание выполнения текущей операции (Map или Reduce) до завершения всех предшествующих шагов, связанных с этой операцией. Oozie workflow состоит из узлов двух типов: control и action. Для выполнения задач и отслеживания их состояния используются операции, которые формируют взаимодействия удаленной системы (Hadoop, Pig) и Oozie. Это могут быть операции MapReduce, Hadoop, Pig, SSH, HTTP, eMail, а также другие sub-workflow. По завершении каждой операции генерируется сообщение, которое позволяет Oozie запустить продолжение процесса выполнения WF. Control-узлы отвечают за начало и конец WF, а также сам процесс выполнения (узлы принятия решения, ветвления и т.д.).
Экспериментальные исследования стационарных методов оптимизации размещения больших данных
Обобщенная схема. Представим обобщенную последовательность действий алгоритма оптимизации размещения данных при многоуровневом хранении на основе генетического алгоритма: а) инициализировать популяцию хромосом, где каждая представляет собой случайное размещение данных по узлам хранения и уровням на них; б) произвести операции мутации в соответствии с заданными параметрами вероятности их осуществления; в) произвести операции кроссовера в соответствии с параметрами вероятности их осуществления; г) произвести вычисление значения функции приспособленности для каждой хромосомы в популяции; д) произвести селекцию, в результате которой часть хромосом в соответствии с выбранным оператором селекции удалить из популяции и на их место клонировать лучшие из оставшихся; е) проверить, что количество поколений не превысило лимит; если лимит не превышен, вернуться к шагу 2, в противном случае осуществить выход из алгоритма с запоминанием хромосомы с лучшим значением функции приспособленности. Таким образом, для повышения эффективности реализации стандартной схемы генетического алгоритма необходима интеграция принципов гравитации и категоризации файлов.
В данном параграфе описаны условия выполнения экспериментальных исследований, а также результаты, полученные путем подбора наиболее оптимальных параметров, для разных алгоритмов.
Для экспериментального исследования были разработаны программные модули алгоритмов оптимизации размещения на основе жадного и генетического алгоритмов для многоуровневой среды хранения данных. Разработка выполнена на языке Java. Выполнена интеграция программных модулей разработанных алгоритмов в симулятор платформы CLAVIRE для выполнения исследований эффективности их работы.
Простые сценарии исследования алгоритмов. Экспериментальные исследования эффективности работы разработанного алгоритма проводились на начальной конфигурации экспериментального стенда, которая включала в себя: 17 070 файлов; 8 узлов; 1 реплика, все файлы имели одинаковый размер 200 МБ, максимальный размер пространства для хранения на узле 1,8 TБ.
Для оценки работы алгоритма было проведено несколько экспериментов. Первый (сценарий I) заключался в оптимизации размещения двух задач размером 96 и 24 файла. Между собой задачи имели пересечения в 16 совместно используемых файлов. Во втором (сценарий II) четыре задачи были распределены по 12 узлам. Две из них превышали емкость любого из узлов, две другие задачи в сумме были меньше любой из первых двух задач и меньше емкости двух узлов. Далее исследование алгоритма осуществлялось по сценарию III – путем добавления уровней хранения данных с различными характеристиками скорости чтения и записи и сравнения распределения, полученного случайным образом, и распределения, выработанного программным алгоритмом на основе жадного алгоритма.
Исследование эффективности алгоритмов на реальных сценариях. В ходе экспериментального исследования было изучено поведение разработанных алгоритмов GA (реализация базовой схемы генетики с гравитацией), CGA (реализация схемы GA с использованием категоризации) [92] и финальной версии TCGA, реализующего описанные в параграфе 2.2.4 формализованные компоненты алгоритма. Условия проведения экспериментальных исследований совпадают с описанными для предыдущего эксперимента. Исследование программного алгоритма оптимизации размещения данных на основе генетического алгоритма включало три основных этапа: исследование чувствительности разработанного алгоритма, нахождение оптимального набора коэффициентов, сравнение эффективности полученных решений.
В качестве прикладных задач, на основе которых была собрана информация по запускам и использованию определенных данных, в рамках расчета для проведения экспериментов были использованы задачи (таблица 3.1), возникающие в вычислительной системе при моделировании экстремальных гидрометеорологических явлений в рамках системы оперативного прогнозирования и ретроспективного воспроизведения климатических характеристик.
Начальные условия экспериментов основного сценария IV, представленные в таблице 3.2, были построены по статистике задач таблицы 3.1. По строкам и столбцам заданы задачи, в пересечении строк и столбцов указан коэффициент пересечения файлов между задачами. По главной диагонали указано пересечение задач самих с собой, что всегда равно 100 %. Критерий С является коэффициентом «важности» задачи, который определяет, насколько задача значима на фоне остальных задача, выполняемых в системе (обычно важность определяется через частоту запуска и числа используемых файлов).
Экспериментальные исследования нестационарных методов оптимизации размещения больших данных
Вычислительная нагрузка состоит из нескольких композитных приложений, которые должны быть распределены по вычислительным узлам и запущены на них: W = {wi} = { Ai,Ei }. (5.1) Каждое композитное приложение Wj представлено в виде графа двумя множествами: А± -множество элементарных задач или исполняемых файлов АІ = {ау}. (5.2) Множество Et определяет зависимости между этими задачами. Каждое ребро графа представляет собой кортеж из родительской и дочерней задач, а также объема передачи данных между ними dj к: Et = {е)к} = { (а),а[),d)ik }. (5.3)
Для упрощения можно использовать глобальную индексацию всех задач. В этом случае все указанные выше выражения переопределяются без индексации по і . Таким образом, все композитные приложения объединены в одно, которое содержит все задачи и зависимости между ними: W = { {at},{ejik} }.. (5.4) Вычислительная среда определяется двумя множествами. Множество R представляет собой физические вычислительные ресурсы, которые в общем виде могут включать в себя также узлы 106 хранения данных и сетевые коммутаторы. Каждый ресурс rt может быть определен как набор различных характеристик - число ядер процессора, оперативная память, видеопамять и т.д.: R = {ц\(срщ,гатидрщ,...) Є rj. (5.5) Вторым является множество сетевых маршрутов В между ресурсами: В = {Щ\{гк} Є Щ]. (5.6)
Каждый ресурс из R полностью виртуализируется и разделяется на несколько виртуальных машин или контейнеров. Все виртуальные ресурсы составляют множество вычислительных узлов N. В процессе планирования все задачи и приложения назначаются на виртуальные узлы из множества N вместо физических. Каждый вычислительный узел щ наследует часть характеристик от родительского ресурса N = {щ \щ Є гк; (срщ,...) (срик,...)}. (5.7) Для упрощения определен набор виртуальных сетей В, который представляет собой матрицу смежности между всеми узлами из множества узлов N. B = {btJ\i,jEl...\N\}. (5.8) Сформулируем задачу планирования. Расписание S представляет собой назначение задач на вычислительные узлы: Б = {(аипк)}. (5.9)
Основная цель планирования - найти оптимальное расписание Sopt. Производительность задачи щ на определенном узле пк оценивается с помощью модели производительности, которая может быть получена аналитически или статистически и представляет собой функцию от задачи и вычислительного узла: р(аипк). (5.10) При постановке задачи планирования используется набор оптимизационных критериев и ограничений G: G = {gi(S)}. (5.11) Предполагается, что все критерии , (5) максимизируются. В случае минимизации значение критерия может быть отрицательным —gi(S). Помимо критериев оптимизации постановка задачи включает в себя различные ограничения С: 107 C = {Ci(S)} (5.12) Найденные решения S должны удовлетворять определенным ограничениям С. В противном случае решение либо может считаться недействительным, либо при оценке решения будут наложены штрафы, в зависимости от значимости того или иного ограничения. Принимая во внимания все критерии оптимизации и ограничения, можно определить постановку задачи. Цель задачи планирования - найти такое оптимальное расписание Sopt, что: (gi(Sovt) gi(s ),vgiEG (5.13) 3S0Vt: VS gt Sovt: \ ) P opt opt C/(5opt) Cj(S ),VCj Є С Другими словами, оптимальное решение должно максимизировать критерии оптимизации и удовлетворять всем ограничениям. Однако в действительности такое решение не может существовать. Поэтому определенное выше выражение больше применимо для случая многокритериальной оптимизации.
Для упрощения такое представление может быть свернуто к однокритериальной задаче оптимизации с двумя наборами коэффициентов и , используемых для определения значимости того или иного критерия или ограничения. Таким образом, можно переписать выражение в виде однокритериальной задачи для оценки найденных в ходе работы алгоритмов решений.
Данный параграф посвящен исследованию применимости коэволюционных методов для оптимизации размещения данных в распределенных хранилищах. Принцип коэволюции как совместного развития и взаимовлияния нескольких видов был описан еще Чарльзом Дарвином в фундаментальном труде «Эволюция видов» в 1859 г. [184]. Однако в задачах оптимизации он стал использоваться сравнительно недавно [185]. Ключевым достоинством коэволюционных алгоритмов является расширение пространства поиска наилучшего решения за счет использования нескольких популяций в процессе эволюции. Ниже рассмотрены ключевые принципы коэволюции применительно к оптимизации выполнения задачи и размещения данных, описан коэволюционный алгоритм оптимизации размещения данных в распределенной инфраструктуре, а также приведены результаты его экспериментального исследования.
В основе коэволюционных алгоритмов лежит принцип совместного изменения нескольких популяций с целью расширения пространства поиска алгоритма благодаря стохастичности работы эволюционных алгоритмов. В коэволюционном процессе могут принимать участие две и более популяции, которые, изменяясь внутри себя посредством операций кроссовера и мутации, также оказывают влияние друг на друга через различные процедуры, такие как объединение или взаимообмен.
Существует несколько основных подходов к коэволюционному планированию. Первый класс алгоритмов используют инверсную коэволюцию для нахождения оптимального решения. В основе этих алгоритмов, как и многих других метаэвристических алгоритмов, лежит взаимодействие носителей и паразитов в живой природе [186]. Основной принцип таких алгоритмов заключается в создании нескольких популяций одного вида (распределение задач на ресурсах, распределение данных на узлах) и сравнении их хромосом с помощью фитнес-функции по принципу «все со всеми», что приводит к исключению из популяций тех хромосом, чьи значения фитнес-функции меньше, чем у определенного числа хромосом другой (других) популяции [187].