Содержание к диссертации
Введение
Глава 1. Особенности построения современных систем хранения данных 8
1.1. Архитектуры современных систем хранения данных 8
1.2. Особенности реализации облачных систем хранения данных . 22
1.3. Выявление связи между процедурой миграции данных и масштабированием 29
1.4. Выводы 32
Глава 2 . Задача миграции данных в высокомасштабируемых облачных системах хранения данных 34
2.1. Принципы организации высокомасштабируемых облачных систем хранения данных 34
2.2. Требования к задаче миграции данных в высокомасштабируемых облачных системах храпения 39
2.3. Качественная постановка задачи 44
2.4. Выводы 50
Глава 3- Анализ известных моделей и алгоритмов миграции данных в системах хранения 52
3.1. Обобщенная модель систем хранения данных 52
3.2. Математическая модель миграции данных в системах хранения 59
3.3. Сведение задачи миграции данных к задаче раскраски ребер мультиграфа 60
3.4. Выводы 66
Глава 4. Разработка моделей и алгоритмов миграции данных в высокомасштабируемых облачных системах хранения 69
4.1. Модель миграции данных в высокомасштабируемых облачных системах хранения 69
4.2. Алгоритмы миграции данных в высокомасштабируемых облачных системах хранения 78
4.3. Доказательство свойств предложенных алгоритмов 81
4.4. Выводы 82
Глава 5. Экспериментальная оценка эффективности предложенных алгоритмов 86
5.1. Методика проведения эксперимента 86
5.2. Особенности реализации алгоритмов миграции данных 95
5.3. Результаты эксперимента 99
5.4. Выводы 101
Заключение 103
Литература 106
Приложение А. Акт внедрения 114
Приложение Б Исходный код алгоритма 115
Приложение В. Исходный код модуля bipart .119
Приложение Г Исходный код модуля shannon 129
- Особенности реализации облачных систем хранения данных
- Требования к задаче миграции данных в высокомасштабируемых облачных системах храпения
- Математическая модель миграции данных в системах хранения
- Алгоритмы миграции данных в высокомасштабируемых облачных системах хранения
Введение к работе
Актуальность работы
В последние годы произошло сильное изменение в практике и теории организации распределенных вычислительных систем связанное с появлением концепции cloud computing, или «облачных вычислений». Согласно этой концепции, вычислительные ресурсы арендуются по требованию через Интернет, а вычислительные системы лишь временно используют их для выполнения своих функций. Уже сегодня имеется возможность аренды вычислительных ресурсов с поминутной, и даже посекундной оплатой. Это позволяет создавать новые типы вычислительных систем с уникальными технико-экономическими характеристиками за счет гибкости в оплате и возможности арендовать потенциально бесконечное количество ресурсов.
Одними из самых востребованных современным бизнесом типов вычислительных систем являются системы хранения данных (СХД), которые представляют собой множество распределенных устройств хранения, объединенных вычислительной сетью и представленных пользователям в виде одного логического устройства большой емкости. Концепция облачных вычислений оказывает сильное влияние на современные СХД, что привело к появлению нового класса систем хранения - высокомасштабируемые облачные системы хранения данных (ВО-СХД, Scalable Storage Cloud). ВО-СХД, в отличие от традиционных СХД, используют в своем составе не фиксированное количество устройств хранения, а арендуют устройства по мере необходимости, или же высвобождают ряд устройств, когда необходимость в них отпадает. Для эффективного использования арендованных ресурсов ВО-СХД вынуждены регулярно производить процедуру масштабирования, т.е. изменения количества устройств хранения, входящих в систему.
Масштабирование выполняется операционной системой (ОС) ВО-СХД,
оно связано с переконфигурацией хранилища, т.е. с перемещением огромного количества элементов данных (блоков данных) между устройствами хранения. Масштабирование и переконфигурация неразрывно связаны с алгоритмами миграции данных, которые строят план миграции (перемещения элементов данных) на основе текущего и целевого распределения элементов данных по устройствам хранения. Выполнение миграции данных не должно приводить к снижению качества обслуживания клиентов системы хранения, для чего в алгоритмах необходимо учитывать пропускную способность сети и максимальный объем данных, который можно передавать в один момент времени с одного устройства хранения на другое.
Существующие алгоритмы миграции данных не учитывают особенности ВО-СХД, и высвобождение лишних устройств хранения (добавление новых устройств) возможно производить лишь после полного завершения процедуры переконфигурации. Во время выполнения этого длительного этапа лишние устройства остаются задействованными, а новые устройства - не до конца использованными. Разработка специализированных алгоритмов миграции данных для управления арендованными ресурсами в ВО-СХД, способных сократить время масштабирования, позволит повысить эффективность использования ресурсов и понизить затраты на аренду устройств хранения, что представляет собой важную научную задачу, имеющую большое практическое значение.
Целью диссертационной работы является разработка алгоритмов миграции данных в ВО-СХД, способных уменьшить время масштабирования, по сравнению с традиционными алгоритмами миграции. В соответствии с указанной целью, в работе сформулированы и решены следующие задачи:
анализ существующих моделей СХД и алгоритмов миграции данных;
анализ особенностей ВО-СХД;
разработка модели ВО-СХД;
разработка алгоритмов миграции данных для ОС ВО-СХД;
анализ свойств разработанных алгоритмов.
Методы исследования. В исследовании формализация моделей производилась с помощью методов теории вычислительных систем и теории графов. Для описания и анализа алгоритмов в работе были использованы методы теории графов и теории алгоритмов.
Научная новизна работы заключается в следующем:
предложена математическая модель задачи миграции данных ВО-СХД, способная менять состав устройств хранения, и на основе модели сформулирована задача миграции данных в ВО-СХД в виде многокритериальной оптимизационной задачи;
предложены переборный и полиномиальный аппроксимационный алгоритмы миграции данных для управления вычислительными ресурсами ОС ВО-СХД, позволяющие предельно быстро производить масштабирование ВО-СХД;
произведен анализ свойств разработанных алгоритмов: доказана оптимальность алгоритмов по основному критерию «время масштабирования»; доказана полиномиальность вычислительной сложности аппрок-симационного алгоритма; экспериментально показана эффективность алгоритмов, по сравнению с существующими.
Практическая значимость. Предложенные модель и алгоритмы могут быть использованы при разработке ОС промышленных ВО-СХД, что позволит улучшить такой технико-экономический показатель ВО-СХД, как затраты на аренду вычислительных ресурсов.
Внедрение результатов. Предложенные алгоритмы миграции данных в ВО-СХД, а также разработанная программная система, реализующая данные алгоритмы, использовались при выполнении НИОКР ЦНИТ-9/Мк «Cache algorithms with user demand prediction for cloud storages» (Алгоритмы кэширования с прогнозированием пользовательских требований для облачных хранилищ), проводимом в СПбГЭТУ. Срок выполнения: с 01.2010 до 12.2010. Источник финансирования - внебюджет.
На защиту выносятся следующие результаты и положения:
математическая модель миграции данных в ВО-СХД;
аппроксимационный алгоритм миграции данных для управления вычислительными ресурсами в ВО-СХД;
доказательство оптимальности предложенного алгоритма по первому критерию задачи миграции данных в ВО-СХД, а также доказательство его полиномиальности.
Апробация работы. Предлагаемые решения и результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях в 2008-2011 гг.
Публикации. Материалы диссертации опубликованы в 5 научных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК, 3 работы в научных трудах конференций, из которых одна работа на английском языке в трудах международной конференции сообщества IEEE.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 77 наименований. Основная часть работы изложена на 113 страницах машинописного текста. Работа содержит 23 рисунка, 5 таблиц и 4 приложения общим объемом 18 страниц.
Особенности реализации облачных систем хранения данных
Облачные вычисления (computingcloud, англ.) -это концепция, согласно которой.вычислительные ресурсы находятся на удаленных серверах и арендуются по требованию. Приложения лишь временно используют эти ресурсы для выполнения своих функций. Концепцию трудно назвать новой. Еще в i960 году создатель языка программирования LISP и автор термина «искусственный интеллект» Джон Маккарти высказал предположение о необходимости совместного использования компьютерных мощностей в виде услуги, проводя аналогию с электросетями и водоснабжением. Технологии тех лет были слишком примитивны для подобных решений. В некоторой мере эта концепция была реализована позже в майнфреймах, в которых пользователи одной организации имели доступ через терминал к общему компьютеру.
Появление grid технологий в 90-х годах создало технологическую базу для компьютерных мощностей предоставляемых в виде услуги [25, 26]. Эта технологическая база оформилась в виде стандартов веб-служб (web-services), которые унифицировали интерфейсы взаимодействия между службами [27т 28]. Полноценное развитие концепция облачных вычислений получила только в начале XXI века. Ее развитию способствовало повсеместное распространение сети Интернет как телекоммуникационной основы и стандартов веб-служб (web-services) как технологической базы.
Термин computing cloud впервые использовал Nicholas G. Carr в книге "Does IT Matter? Information Technology and the Corrosion of Competitive Advantage" [29], опубликованной в 2004 году. В книге автор критикует компании, которые поддавшись веяниям моды инвестируют огромные средства в информационную инфраструктуру. Развивая этот тезис, он низводит ИТ до уровня базовых технологий, и ставит их в один ряд с электричеством или кондиционированием воздуха, при этом развивая идею о совместном использовании инфраструктуры несколькими компаниями, и предлагает создание «облаков» вычислительных ресурсов. В дальнейшем этот термин начали активно использовать компании, предоставляющие информационную инфраструктуру по требованию.
Основной предпосылкой появления и широкого распространения облачных вычислений были GRID технологии, или грид вычисления. GRID вычисления - это форма распределённых вычислений, в которой компьютер представлен в виде кластера соединённых с помощью сети слабосвязанных компьютеров, работающих вместе для выполнения огромного количества за даний [ЗО] - Часто вместо термина GRID используют термин «метакомпью-тинг» [25, 31]. GRID системы чаще используются в академических кругах для решения научных, математических задач, требующих для решения значительных вычислительных ресурсов [32].
Основное отличие облачных вычислений от GRID систем заключается в их открытости и простоте. GRID это специализированные системы, построенные для решения определенного набора задач, используемые узким кругом специалистов. В отличие от них, системы, построенные в соответствии с концепцией облачных вычислений, предоставляют универсальные интерфейсы широкому кругу пользователей. Именно доступность и открытость позволила облачным вычислениям стать столь популярной концепцией.
С широким распространением облачных вычислений появилась необходимость в классификации облачных систем и сервисов [33]. Одной из самых первых и самых простых классификаций является классификация по уровню, который виртуализируется облачным сервисом. Выделяют следующие уровни:
Infrastructure as a Service (laaS) - это предоставление компьютерной инфраструктуры как услуги. IaaS включает в себя: аппаратные средства, ОС и системное ПО,
Platform as a Service (PaaS) - это предоставление интегрированной платформы для разработки, тестирования, развертывания и поддержки приложений как услуги.
Software as a Service (SaaS) - это предоставление приложений для конечных пользователей в виде услуги, обычно в виде веб приложения.
Часто этот термин используют для обозначения бизнес-модели продажи программного обеспечения по подписке.
На сегодня это, пожалуй, единственная широкораспространенная классификация облачных сервисов, несмотря на ее неоднозначность и слабую связь с потребительскими свойствами облачных сервисов.
Облачные сервисы и программное обеспечение для их создания предо-ставляют многие компании: Amazon, Microsoft, EMC, VMWare (часть EMC), Oracle, Sun Microsystems (часть Oracle), IBM и д.р. Первыми популярными облачными сервисами стали сервисы компании Amazon, объединенные под торговой маркой Amazon Web Services1. Amazon первая представила широкому кругу пользователей ресурсы по требованию, которые можно было использовать в любом количестве, арендуя мощности через программные интерфейсы. Если раньше для аренды ресурсов требовалось пройти длительную стадию заключения контракта с компанией-провайдером, то в Amazon достаточно пройти простую процедуру регистрации на сайте и оставить данные кредитной карты. По аналогичной схеме сегодня предоставляются вычислительные ресурсы многими другими компаниями. Облачные вычисления превращают вычислительные ресурсы в товар массового потребления.
Требования к задаче миграции данных в высокомасштабируемых облачных системах храпения
Основная техническая задача решаемая в работе - это повышение эффективности использования вычислительных ресурсов ВО-СХД. Такая многогранная задача может решаться на различных уровнях: от организационного (разграничение прав использования системы, заключение контрактов на выгодных условиях об аренде и настройке оборудования) до технического (оптимизация работы оборудования, разработка оптимальных алгоритмов управления ресурсами). В настоящей работе рассматривается лишь технический уровень и, в частности, разработка оптимальных алгоритмов управления ресурсами.
Повышение эффективности использования ресурсов системы хранения за счет использования арендованных ресурсов требует решения технической задачи масштабирования ВО-СХД. Как было показано при анализе СХД, масштабирование тесно связано с задачей миграции данных, решение кото-рой, в свою очередь, требует разработки новых моделей миграции данных СХД, способных учитывать особенности ВО-СХД. В данной главе рассмотрим особенности ВО-СХД, значимые для моделей миграции, предложим модель миграции данных в ВО-СХД и на основе предложенной модели разработаем новый алгоритм миграции данных в ВО-СХД. Графическое изображение решаемых задач, используемых PI разрабатываемых моделей и алгоритмов показано на рисунке 4.4 в выводах по данной главе.
Возможность ВО-СХД использовать внешние арендованные устройства хранения, как уже было сказано, обеспечивается сервис-провайдерами вычислительных ресурсов, такими как службы Amazon Web Services, Microsoft Azure и др. Возможность использования внешних устройств приводит к изменению структуры серверной подсистемы (back-end) ВО-СХД в отличие от серверной подсистемы СХД. Модуль доступа к устройствам хранения, очевидно, должен учитывать специфику арендуемых вычислительных ресурсов и обеспечивать работу с ними в соответствии с протоколами, определяемыми сервис-провайдером.
Использование ресурсов сервис-провайдера требует согласование этой деятельности со специализированной службой сервис-провайдера - менеджером вычислительных ресурсов. Взаимодействие с менеджером вычислительных ресурсов становится возможным после регистрации у сервис провайдера, которая заключается в принятии соглашения между поставщиком вычислительных ресурсов (сервис-провайдер) и потребителем ресурсов (владельцем ВО-СХД). Современные поставщики вычислительных ресурсов допускают заключение соглашений как с юридическими организациями, так и с частными лицами. Во втором случае регистрация у сервис-провайдера заключается в предоставлении авторизационных данных на веб-сервисе провайдера услуг, а также данных кредитной карты физического лица. После чего предоставляется доступ к службе - менеджеру вычислительных ресурсов (через веб-интерфейс или программный интерфейс). Таким образом, модуль доступа к устройствам хранения должен обеспечивать работу как с устройствами хранения (рис. 2.4), так и со службой менеджера вычислительных ресурсов.
Динамические особености арендованных устройств хранения данных, а точнее, способность ВО-СХД менять состав устройств хранения, сказываются на алгоритмах управления ресурсами системы и соответствующих модулях системы: модуль распределения данных, модуль миграции данных. Компонент переконфигурации должен иметь доступ к информации о текущем составе устройств хранения и о возможностях по изменению состава устройств. Такую информацию можно представить в виде множества масштабируемых устройств хранения. Знание этой информации позволит ВО-СХД адаптироваться под меняющиеся требования к системе со стороны пользователя. рации, масштабируемым подмножеством устройств хранения ВО-СХД или просто масштабируемым подмножеством будем называть множество состоящее из устройств хранения ВО-СХД которые должны быть отключении от ВО-СХД в результате выполнения текущей переконфигурации, или наоборот - подключении к системе.
Входными данными алгоритма миграции данных (модуля миграции данных) в ВО-СХД должны являться не только текущая и новая конфигурации (расположение элементов данных по устройствам хранения), но и явно указанное множество масштабируемых устройств. Такая особеность ВО-СХД требует вычисления множества масштабируемых устройств при каждой
переконфигурации хранилища. Модуль распределения данных в множестве масштабируемых устройств должен различать удаляемые устройства PI добавляемые устройства, поскольку это важно для алгоритма распределения данных. В отличие от него, эти различия несущественны для модуля миграции данных, поскольку задача предельно быстрого маштабирования (основной частью которой является алгоритм миграции данных) не делает разницы между масштабированием с уменьшением размера и масштабированием с увеличением размера. Таким образом, множество масштабируемых устройств хранения является симметрической разницей множества устройств хранения из текущей конфигурации и новой конфигурации,
Масштабируемые устройства хранения добавляются или удаляются к/из системы. Очевидно, что все элементы данных с удаляемых устройств хра-пения должны быть перенесены на другие устройства (вероятно, не часто используемые), причем они уже должны находится в системе. Также, на все новые, подключаемые устройства хранения должны быть переданы элементы данных, находящиеся на работающих устройствах (вероятно, это устройства перегруженные запросами). Можно принять ограничение, что элементы данных не передаются между масштабируемыми устройствами. А, поскольку, одновременное подключение и отключение устройств является не типичным случаем для масштабирования ВО-СХД, т.е. передача данных с масштабируемого отключаемого устройства на масштабируемое подключаемое устройство нетипичный случай, то и введение ограничение-не нарушается.
Особенности ВО-СХД не отражаются на коммуникационной подсистеме, которая может реализовывать те же самые протоколы доступа к данным, как и обычные, не высокомасштабируемые СХД. При этом, реализация подсистемы кэша и алгоритмов кэширования могут заметно отличаться, т.к. временные характеристики доступа к данным ВО-СХД могут быть иными, нежели временные характеристики доступа к данным СХД.
Математическая модель миграции данных в системах хранения
Задача распределения данных была впервые сформулирована в статье [53] в виде задачи распределения объектов в распределенной системе. Более формальное описание приведено в работе [18]. В ней же произведено разделение проблемы миграции данных на задачу в гомогенной системе (Homogeneous Data Placement, HDP), в которой все диски для хранения данных идентичны, а также задачу распределения данных в гетерогенной системе (Uniform Ratio Data Placement, URDP), в которой присутствуют ограничения на каждое из устройств хранения. Ограничения на устройства хранения L, С, введенные в предыдущем параграфе, типичны для гетерогенных систем хранения. Сформулируем задачу более формально.
Определение 3-3. Задача распределения данных в хранилище S (из определения 3.2) - это задача поиска нового опт ималъного распределения элементов данных по устройствам хранения Р , исходя из новых пользовательских требований к элементам данных В!.
Задача распределения данных имеет сходства с классической задачей о многомерном ранце [57, 58]. Ио она имеет дополнительные ограничения, которые не позволяют адаптировать известные подходы к решению задачи о многомерном ранце к задаче о распределении данных [18].
Известно, что задача является NP-сложной [18]. Следовательно, оптимальное решение можно получить лишь путем полного перебора всех возможных вариантов решения [59, 60]. Выполнение полного перебора невозможно при большом количестве элементов данных, характерном для реальных хранилищ. Однако, разработаны полиномиальные аппроксимационные алгоритмы ее решения [12, 18] Вычислив новое распределение данных Р и имея старое распределение Р, можно построить направленный мультиграф без ЦИКЛОВ C tfemanrfj ДЄМОН стрирующий перемещение элементов данных из старой конфигурации в новую. Этот граф является моделью задачи миграции данных. Другое название модели миграции - граф требований [20[.
Следует заметить, что направление передачи данных в хранилище не имеет значения, с точки зрения задачи миграции [20]. Устройство считается занятым, независимо от того, принимает оно данные или передает. Исходя из этого, модель можно представить в виде ненаправленного мультиграфа.
Задача миграции данных в хранилище 3.2 с ограничением на размер устройств хранения заключается в составлении плана перемещения данных между устройствами хранения, согласно модели (3.4), за минимальное число шагов. Т.о. задача миграции данных сводится к задаче раскраски ребер мультиграфа, т.е. к задаче поиска хроматического индекса мультиграфа, которая принадлежит классу NP-иолных задач. Задачу можно выразить более формально на основе модели:
Определение 3.5. Задача миграции данных в СХД 3.2 заключается в поиске реберной раскраски мультиграфа модели миграции Gdemand (3.4). обладающей минимальным количеством цветов.
Существуют и другие разновидности этой задачи. В статье [13] допускается копирование (клонирование) элементов данных на другие устройства с целью ускорения процедуры миграции за счет использования копий. С практической точки зрения, это дает выигрыш, когда в модели миграции один элемент данных должен быть мигрирован на множество устройств хранения.
Более простой разновидностью задачи миграции является задача с отсутствием ограничений на размер устройств хранения. С практической точки зрения, это не сильное ограничение, поскольку емкость устройств хранения учитывается в задаче распределения данных, т.е. в начале процедуры миграции и по ее завершению емкость устройств хранения не будет превышена. На протяжении процедуры миграции превышения емкости не могут быть существенными. В данной работе в качестве задачи миграции данных мы будем использовать задачу без ограничения на емкость устройств хранения.
Определение 3.6, Задача миграции данных в хранилище 3.2 (без ограничений на размер устройств хранения) заключается в составлении плана перемещения данных меоіеду устройствами хранения, согласно мо дели (3.4), за минимальное число шагов без учета ограничений емкости устройств хранения С ,
Задача миграции данных с ограничением на размер устройств хранения (3.5) имеет сходства с задачей раскраски дуг мультиграфа. Основное отличие заключается в ограничении на максимальный размер устройств хранения, В таком виде она не сводится к задаче раскраски дуг. Известно, что задача является NP-сложной [13, 19т 20].
Задача миграции данных без ограничений на размер устройств хранения явно сводится к задаче раскраски дуг мультиграфа требований (3.4). Дугами графа является операция передачи данных между устройствами. Дуги3 покрашенные в один цвет - это все операции передачи данных, которые можно выполнить в один момент времени, не задействовав одно и то же устройство более одного раза. Минимальное количество цветов раскраски - это минимальное количество шагов в плане миграции. Решение задачи миграции дан иых - это оптимальная раскраска ребер модели. Известно, что задача, как и предыдущие задачи, является NP-сложной [61].
Поскольку задача раскраски дуг мультиграфа играет важную роль в данной работе, рассмотрим ее и ее вариации в следующем разделе, Для моделирования современных распределенных систем, какими являются СХД, часто используются теоретико-графовые алгоритмы. На основе теории графов решаются многие задачи эффективного использования ресурсов вычислительных систем (оптимизация использования памяти, регистров, уменьшение обменов между оперативной и внешней памятью), повышение эффективности многопроцессорных и многомашинных систем {распределе-ние загрузки процессоров, обмен сообщениями между процессорами, конфигурация сетей связи между процессорами).
СХД состоят из множества устройств хранения и элементов данных расположенных на этих устройствах. В настоящей работе исследуются вопросы перекоифигурации, т.е. перемещения элементов данных между устройствами. Взамосвязи между множеством объектов удобно представлять в виде графового описания.
Теория графов - это раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G = (К, Е)7 где V есть подмножество любого счетного множества, а Е - подмножество V V.
С точки зрения решаемой задачи, легко представить СХД в виде графа, вершинами которого являются устройства хранения, а дугами (или ребрами) являются операции передачи данных между устройствами. В такой модели задачу распределения данных молено свести к задаче раскраски вершин муль-тиграфа [53], а задачу миграции данных можно свести к графовой задаче раскраски ребер мультиграфа [20]. Рассмотрим эти задачи подробнее.
Определение 3.7. Задача раскраски ребер мультиграфа заключается в поиске минимального числа цветов, которые потребуются для раскраска ребер графа, при условии, что любые два смежных ребра (т.е. два ребра, имеющие общую вершину) не могут быть окрашены в один цвет.
Алгоритмы миграции данных в высокомасштабируемых облачных системах хранения
Опишем очевидный переборный алгоритм миграции данных в ВО-СХД, дающий оптимальный результат по первому критерию - оптимальность плана масштабирования. Для решения задачи будем использовать метод уступок. Выделив два критерия оптимизации, будем оптимизировать алгоритм по первому критерию, для чего потребуется поступиться эффективностью по второму критерию. Первый частный критерий - время масштабирования, т.е. миграция данных на масштабирующем подграфе GaCat- Второй критерий - время миграции на остальных устройствах, т.е. миграция данных на подграфе Gres Алгоритм 4.1 (Переборная миграция данных) Опишем алгоритм в виде последовательности шагов, описанных выше.
Выделить подграф Gscai из графа G па основе известного подмножества Ds . Выделить подграф Gre$ из G на основе подграфа GSCai 3. Использовать оптимальный полиномиальный алгоритм 3.3 для расчета плана миграции двудольного мультиграфа Gscai 4- Использовать переборный алгоритм 3.1 для расчета плана миграции мультиграфа GTes.
Получить общий план миграции ВО-СХДС путем последовательного объединения планов миграции мультиграфа Gsca.i с планом миграции teres Очевидно, что приведенный алгоритм имеет экспоненциальную вычислительную сложность от размера дуг графа, поскольку он содержит шаг 4 имеющий экспоненциальную сложность.
Прежде чем описывать полиномиальный аппроксимационный алгоритм миграции данных, докажем, что масштабирующий подграф Gsca[ является двудольным мультиграфом, для которого существуют оптимальные полиномиальные алгоритмы раскраски ребер.
Доказательство: Исходя из определения масштабирующего подграфа (4.6), ои состоит из множества вершин Ds и вершин ?оф" смежных с )$. Докажем, что множества вершин Ds и Раф- разбивают граф G$mi на две доли, т.е. в графе нет дуг, идущих из Ds в Ds или же из Пщ в Da$.
Вершины из множества Da y не имеют общих дуг, поскольку это противоречит определению масштабирующего подмножества (4.3), входящего в состав ВО-СХД (определение 4.4). Также из определения 4.6 следует, что любое его ребро соединяет вершины из D$ только с вершинами из Dadj. Следовательно, вершины из Dadj также не могут иметь общих ребер. Таким образом, множества вершин Ds и D j составляют две доли двудольного мультиграфа GScal- І
Опишем полиномиальный алгоритм миграции данных в ВО-СХД, заменив в предыдущем алгоритме 4.1 шаги 4 имеющий экспоненциальную сложность, на шаг с полиномиальной вычислительной сложностью.
Алгоритм 4.2 (Полиномиальная миграции данных) Шагщ аналогичные алгоритму 4-і- Но ма шаге 4 используется полиномиальный алгоритм Шеннона 3.2 вместо переборного алгоритма ЗЛ.
1. Выделить подграф Gscai из графа G на основе известного подмнооїсе-ства Ds 2. Выделить подграф Gres из G на основе подграфа Gscai.
3. Использовать оптимальный полиномиальный алгоритм 3.3 для расчета плана миграции двудольного мультиграфа Gscai
4- Использовать аппроксимационный полиномиальный алгоритм 3.2 для расчета плана миграции мультиграфа Gres 5. Получить общий план миграции ВО-СХД G путем последовательного объединения планов миграции мультиграфа Gscai с планом миграции
Использование разработгшых алгоритмов в практике построения про-мышленых СХД требует большой производительности алгоритмов и гарантированной эффективности получаемого ими результата. Для гарантии эффективности получаемого результата докажем оптимальность алгоритмов по критерию задачи миграции данных в ВО-СХД. Очевидно, что переборный алгоритм 4.1 не может эффективно пременяться в промышленных СХД, поскольку перебор всех возможных вариантов не способен обеспечить прием-лимой производительности даже на небольших объемах данных. Необходимо доказать полиномиальность, а следовательно и применимость на практике, аппроксимационного алгоритма 4.2.
Теорема 4Л (Оптимальность алгоритмов 4.1 и 4.2) Предложенные ал горитмы (1 u Jh2 оптимальны по первому критерию задачи миграции данных в масштабируемом облачном хранилище, сформулированной в определении 4-8.
Доказательство: Рассмотрим сначала алгоритм 4.2. В соответствии с доказанной леммой 4.1, подграф GSCai является двудольным мульти J графом, и для нахождения оптимальной раскраски дуг GSCai в алгоритме используется полиномиальный алгоритм 3.3, который дает оптимальное время миграции подграфа Gscai- Исходя из постановки задачи, сформулированной в определении 4.8, оптимальность алгоритма по первому критерию обеспечивается, благодаря оптимальности времени миграции подграфа GSCai (шаг 3 алгоритма). Т.е. алгоритм 4.2 является оптимальным по первому критерию. Переборный алгоритм 4.2 также является оптимальным по первому критерию, поскольку шаг 3 алгоритма также дает оптимальный результат за счет использования переборного алгоритма раскраски дуг мультиграфа, Теорема 4.2 (Полиномиальность алгоритма 4.2) Предлооюепиый алгоритм 4-% имеет полиномиальную вычислительную слооюностъ max{0(SlogjE),0([S(x + jD))}- ГдеЕ - множество ребер, D - мноо&е-сгпво вершин (устройств хранения), х хроматический индекс мультигра-фа, S - некоторая константа.
Доказательство: Очевидно, что шаги 1 и 2 алгоритма 4.2 являются полиномиальными, поскольку вычисление вершин Da4j смежных с S - задача тривиальная, а выделение подграфов Gscat и GreS} состоящих из заданных вершин, имеет линейную сложность от количества вершин 0(_D). Шаги 3 и 4 также являются полиномиальными, их вычислительная сложность равна 0(7 log \Е\) и ?([Sj( -f-ji?})-, в соответствии с алгоритмом 3.2 и алгоритмом 3.3 Результат выполнения шагов 3 и 4 - два плана миграции, состоящие из последовательности операций перемещения данных (ребер подграфов), а шаг 5 состоит из простой операции последовательного объединения двух планов миграции. Очевидно, что шаг 5 имеет линейное время выполнения 0(25), зависящее от числа ребер графа G.
Поскольку алгоритм 4.2 является последовательным объединением шагов 1-5, его вычислительная сложность равна сложности наиболее затратного шага, т.е. m {0{\D\),O{\E\\og\E\),0{\E\{xr + \D\)),0{\E\)} что соответствует max{0(ilogi?),0(i?(x + ))}. Из этого следует, что алгоритм имеет полиномиальную сложность max{0(-? log ?), 0{? (х +1- 1))}- I
