автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы миграции данных в высокомасштабируемых облачных системах хранения

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)

Петров Дмитрий Леонидович

Алгоритмы миграции данных в высокомасштабируемых облачных системах

хранения

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 С ОКТ 2011

Санкт-Петербург — 2011

4857515

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» им. В.И. Ульянова (Ленина)

(СПбГЭТУ)

Кафедра математического обеспечения и применения ЭВМ (МО ЭВМ)

Научный руководитель: Официальные оппоненты:

к.т.н., доцент кафедры МО ЭВМ СПбГЭТУ Татаринов Юрий Станиславович д.т.и., профессор кафедры «Вычислительной техники» СПбГЭТУ Водяхо Александр Иванович

к.т.н., старший научный сотрудник «Центр перспективных исследований» Санкт-Петербургского государственного политехнического университета Писарев Андрей Сергеевич ОАО «Информационные телекоммуникационные технологии» (ОАО «Интелтех»)

Защита состоится «02» ноября 2011 г. в 15:00 на заседании совета по защите докторских и кандидатских диссертаций Д 212.238.01 СПбГЭТУ по адресу: 197376, Санкт-Петербург, ул. Профессора Попова, дом 5.

С диссертацией можно ознакомиться в библиотеке СПбГЭТУ.

Автореферат диссертации разослан «30» сентября 2011 г. Ученый секретарь совета ио защите докторских и кандидатских диссертаций

Д 212.238.01, к.т.н. Щеголева Н.Л.

Ведущая организация:

Общая характеристика работы

Актуальность работы

В последние годы произошло сильное изменение в практике и теории организации распределенных вычислительных систем связанное с появлением концепции cloud computing, или «облачных вычислений». Согласно этой концепции, вычислительные ресурсы арендуются по требованию через Интернет, а вычислительные системы лишь временно используют их для выполнения своих функций. Уже сегодня имеется возможность аренды вычислительных ресурсов с поминутной, и даже посекундной оплатой. Это позволяет создавать новые типы вычислительных систем с уникальными технико-экономическими характеристиками за счет гибкости в оплате и возможности арендовать потенциально бесконечное количество ресурсов.

Одними из самых востребованных современным бизнесом типов вычислительных систем являются системы хранения данных (СХД), которые представляют собой множество распределенных устройств хранения, объединенных вычислительной сетью и представленных пользователям в виде одного логического устройства большой емкости. Концепция облачных вычислений оказывает сильное влияние на современные СХД, что привело к появлению нового класса систем хранения - высокомасштабируемые облачные системы хранения данных (ВО-СХД, Scalable Storage Cloud). ВО-СХД, в отличие от традиционных СХД, используют в своем составе не фиксированное количество устройств хранения, а арендуют устройства по мере необходимости, или же высвобождают ряд устройств, когда необходимость в них отпадает. Для эффективного использования арендованных ресурсов ВО-СХД вынуждены регулярно производить процедуру масштабирования, т.е. изменения количества устройств хранения, входящих в систему.

Масштабирование выполняется операционной системой (ОС) ВО-СХД,

оно связано с переконфигурацией хранилища, т.е. с перемещением огромного количества элементов данных (блоков данных) между устройствами хранения. Масштабирование и переконфигурация неразрывно связаны с алгоритмами миграции данных, которые строят план миграции (перемещения элементов данных) на основе текущего и целевого распределения элементов данных по устройствам хранения. Выполнение миграции данных не должно приводить к снижению качества обслуживания клиентов системы хранения, для чего в алгоритмах необходимо учитывать пропускную способность сети и максимальный объем данных, который можно перёдавать в один момент времени с одного устройства хранения на другое.

Существующие алгоритмы миграции данных не учитывают особенности ВО-СХД, и высвобождение лишних устройств хранения (добавление новых устройств) возможно производить лишь после полного завершения процедуры переконфигурации. Во время выполнения этого длительного этапа лишние устройства остаются задействованными, а новые устройства - не до конца использованными. Разработка специализированных алгоритмов миграции данных для управления арендованными ресурсами в ВО-СХД, способных сократить время масштабирования, позволит повысить эффективность использования ресурсов и понизить затраты на аренду устройств хранения, что представляет собой важную научную задачу, имеющую большое практическое значение.

Целью диссертационной работы является разработка алгоритмов миграции данных в ВО-СХД, способных уменьшить время масштабирования, но сравнению с традиционными алгоритмами миграции. В соответствии с указанной целью, в работе сформулированы и решены следующие задачи:

1. анализ существующих моделей СХД и алгоритмов миграции данных;

2. анализ особенностей ВО-СХД;

3. разработка модели ВО-СХД;

4. разработка алгоритмов миграции данных для ОС ВО-СХД;

5. анализ свойств разработанных алгоритмов.

Методы исследования. В исследовании формализация моделей производилась с помощью методов теории вычислительных систем и теории графов. Для описания и анализа алгоритмов в работе были использованы методы теории графов и теории алгоритмов.

Научная новизна работы заключается в следующем:

1. предложена математическая модель задачи миграции данных ВО-СХД, способная менять состав устройств хранения, и на основе модели сформулирована задача миграции данных в ВО-СХД в виде многокритериальной оптимизационной задачи;

2. предложены переборный и полиномиальный аппроксимационный алгоритмы миграции данных для управления вычислительными ресурсами ОС ВО-СХД, позволяющие предельно быстро производить масштабирование ВО-СХД;

3. произведен анализ свойств разработанных алгоритмов: доказана оптимальность алгоритмов по основному критерию «время масштабирования»; доказана полиномиальность вычислительной сложности аппрок-симационного алгоритма; экспериментально показана эффективность алгоритмов, по сравнению с существующими.

Практическая значимость. Предложенные модель и алгоритмы могут быть использованы при разработке ОС промышленных ВО-СХД, что позволит улучшить такой технико-экономический показатель ВО-СХД, как затраты на аренду вычислительных ресурсов.

Внедрение результатов. Предложенные алгоритмы миграции данных в ВО-СХД, а также разработанная программная система, реализующая данные алгоритмы, использовались при выполнении НИОКР ЦНИТ-9/Мк «Cache algorithms with user demand prediction for cloud storages» (Алгоритмы кэширования с прогнозированием пользовательских требований для облачных хранилищ), проводимом в СПбГЭТУ. Срок выполнения: с 01.2010 до 12.2010. Источник финансирования - впебюджет.

На защиту выносятся следующие результаты и положения:

1. математическая модель миграции данных в ВО-СХД;

2. аппроксимационный алгоритм миграции данных для управления вычислительными ресурсами в ВО-СХД;

3. доказательство оптимальности предложенного алгоритма по первому критерию задачи миграции данных в ВО-СХД, а также доказательство его полиномиальности.

Апробация работы. Предлагаемые решения и результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях в 2008-2011 гг.

Публикации. Материалы диссертации опубликованы в 5 научных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК, 3 работы в научных трудах конференций, из которых одна работа на английском языке в трудах международной конференции сообщества IEEE.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 77 наименований. Основная часть работы изложена на 113 страницах машинописного текста. Работа содержит 23 рисунка, 5 таблиц и 4 приложения общим объемом 18 страниц.

Содержание работы

Во Введении обоснована актуальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту научные положения.

В первой главе анализируются основные подходы к организации СХД. Описываются архитектуры СХД и развитие архитектур, связанное с ростом потребностей бизнеса в данных. Описана концепция интеллектуальных СХД и различные типы интеллектуальных систем: устройства внешней памяти (DAS, Direct-attached Storage), сетевые системы хранения (NAS, Network Attached Storage) и сети хранения данных (SAN, Storage Area Network). Проанализированы основные подсистемы входящие в состав сетевой ОС распределенных хранилищ (рис. 1): коммуникационная подсистема (front-end), кэш и серверная подсистема (back-end).

Эффективность функционирования СХД зависит от отображения логической структуры на физическую. В главе исследуется процедура переконфигурации СХД, которая служит повышению эффективности отображения логической структуры на физическую организацию за счет перемещения элементов данных с высокозагруженных устройств хранения на менее

загруженные устройства. Эта процедура выполняется в компоненте переконфигурации серверной подсистемы СХД (рис. 2).

Рисунок 2. Серверная подсистема СХД

Выделяют три фазы процедуры переконфигурации в СХД: вычисление (псевдо-) оптимального плана распределения данных; вычисления (псевдо-) оптимального плана миграции данных, согласно текущему расположению данных и (псевдо) оптимальному плану распределения; выполнение процедуры миграции данных, согласно плану миграции.

Длительность процедуры переконфигурации определяется длительностью процедуры миграции данных, т.к. миграция связана с перемещением большого количества элементов данных между устройствами хранения, причем ее выполнение не должно приводить к снижению производительности СХД. Таким образом, было выявлено, что от эффективности вычисления плана миграции напрямую зависит время выполнения переконфигурации СХД, и, соответственно, эффективность работы СХД.

Во второй главе рассматривается концепция облачных вычислений, или «cloud computing», согласно которой вычислительные ресурсы не покупаются, а предоставляются в виде услуги, т.е. арендуются. Описана ис-

тория термина «облачные вычисления», связь концепции облачных вычислений с GRID системами. Описаны наиболее популярные сервисы, предоставляющие ресурсы, в соответствии с этой концепцией: Amazon Web Services1, Microsoft Azure2 и другие. Такие службы, являющиеся вычислительной инфраструктурой для других служб или сервисов, относятся к классу IaaS сервисов (Infrastructure As A Service).

С практической точки зрения, наиболее интересными устройствами, использующими арендованные ресурсы, являются ВО-СХД, которые способны масштабироваться, т.е. динамически менять состав устройств хранения во время функционирования (рис. 3). Произведен анализ существующих ВО-СХД и особенностей их реализации. Основной задачей ВО-СХД, кроме обеспечения должного качества обслуживания пользователей, является минимизация использования арендованых IaaS ресурсов.

Рисунок 3. Добавляемые (светло-серые) и удаляемые (темно-серые) устройства хранения

Масштабирование ВО-СХД, т.е изменение состава устройств хранения, производится во время процедуры переконфигурации. Минимизация использования арендованных ресурсов требует предельно быстрого выполнения процедуры масштабирования, для чего требуется минимизировать время мигра-

1 http://aw5.amazon.com

2 http://www.microsoft.com/windowsazure/

Новые 4 устройства

ВО-СХД

Лишние 4 устройства хранения

ции данных с учетом специфики ВО-СХД. В главе был сделан вывод о необходимости разработки новых алгоритмов миграции данных для ОС ВО-СХД, способных сократить время масштабирования до завершения полной процедуры миграции. Алгоритмы миграции данных в облачных хранилищах должны разделять процедуру миграции на две части: масштабирование СХД и остаточную миграцию (рис. 4). Основной целью алгоритмов должно являться сокращение времени масштабирования на некоторую величину Д, при возможной потере эффективности общего времени переконфигурирования СХД.

Миграция данных в СХД '

1

истатонная

*_Масштабирование ^ М1,.пя|.ия

|__

! Миграция данДых в ВО-СХД

Рисунок 4. Сокращение времени масштабирования в процедуре миграции данных (Д)

В третей главе анализируются существующие математические модели СХД и алгоритмы миграции данных. В главе показано, что входными данными задачи миграции данных являются выходные данные задачи распределения данных и текущая конфигурация СХД, т.е. новое(целевое) распределение данных по устройствам хранения и текущее распределение. Эти данные можно представить в виде ненаправленного мультиграфа в демонстрирующего требования по перемещению элементов данных между устройствами хранения. Мультиграф С является моделью задачи миграции данных (рис. 5). В результате чего, план миграции можно разбить на шаги.

О пределение 0.1. Модель задачи миграции данных - это граф (7 = {В,Е, И7}, в котором выполняются условия: \ZvjW £ =

0 если (у,и)) £ Е иУу,т € Б \¥(у,ги) = Ш(ии, у), где Б - устройства хранения, Е С £) х Б - операции перемещения данных, : Е N - весовая функция мультиграфа.

Рисунок 5. Модель миграции данных (двумя черточками выделены ребра кратные двум)

Задача миграции данных заключается в составлении плана миграции элементов данных СХД, при котором каждое устройство хранения в один момент времени участвует не более, чем в одной операции перемещения данных. Т.о. задача миграции данных сводится к задаче раскраски ребер мульти-графа, т.е. к задаче поиска хроматического индекса мультиграфа -¡¿, которая принадлежит классу ЫР-полных задач. Задачу можно выразить более формально на основе модели миграции данных:

Определение 0.2. Задача миграции данных в СХД заключается в поиске реберной раскраски мультиграфа модели миграции данных (2 (определение 0.1), обладающей минимальным количестволг цветов.

В главе приводится описание ряда алгоритмов из теории графов, которые в дальнейшем используются для разработки алгоритма миграции данных в ВО-СХД.

Алгоритм 0.1 (Алгоритм Шеннона) Полиномиальный аппроксимаци-онный алгоритм Шеннона для раскраски ребер мультиграфа имеет вычислительную сложность 0{\Е\{х! +|£>|)), где Е - множество ребер мультиграфа, Б - множество вершин, х' - хроматический индекс графа.

Задача раскраски ребер двудольного мультиграфа является частным случаям задачи раскраски ребер мультиграфа, но она принадлежит классу

полиномиальных задач. Т.о. для ее решения существуют оптимальные алгоритмы с полиномиальной вычислительной сложностью.

Алгоритм 0.2 (Раскраска ребер двудольного мультиграфа) Полиномиальный, оптимальный (не аппроксимационный) алгоритм раскраски ребер двудольного мультиграфа имеет вычислительную сложностью 0(|i5| log |£|), где Е - множество ребер.

В четвертой главе предложена модель миграции данных ВО-

СХД (определение 0.3), которая построена на основе) модели миграции СХД (определение 0.1) путем выделения подмножества масштабируемых устройств хранения D$. Ds определяются как подмножество устройств хранения, которые необходимо вывести из строя или добавить к ВО-СХД в результате переконфигурации. Причем среди операций передачи данных не может быть операций передачи с одного масштабирующего устройства на другое.

Определение 0.3. Моделью миграции данных ВО-СХД будем называть модель миграции данных с явно выделенным масштабирующим подмножеством Ds: G = {D,E,W,Ds), в котором выполняется условия:

W, w € D, W(v, w) = 0 если (v, w) <£ Е - из модели миграции; \/v,w £ D => W(v, w) = W(w, v) - из модели миграции; (1)

\/v,w € £>5 С D W{v, w) = 0 - из определения Ds.

Основываясь на предложенной модели 0.3, сформулирована задача миграции данных в ВО-СХД в терминах теории графов. Для ее точной формулировки введены понятия: масштабирующий подграф Gsca¡ и остаточный подграф Gre3 модели миграции ВО-СХД. Для чего введено понятие подмножества смежных устройств хранения Dadj как подмножества устройств, смежных с устройствами из Ds. Первый подграф Gscai включает все элементы G

(устройства и операции передачи данных), имеющие отношение к масштабированию (т.е. все устройства Ds и Dadj и ребра их соединяющие), второй подграф Ores включает все остальные элементы графа G, не вошедшие в Gseal ■ На рисунке G изображена модель задачи миграции данных, разделенная на два подграфа Gscai и GTes. Черным цветом отмечены масштабируемые устройства Ds, серым - устройства D^. На основе предложенной модели сформулирована задача миграции данных в ВО-СХД в виде многокритериальной оптимизационной задачи.

G

Рисунок 6. Разбиение модули миграции ВО-СХД G на два подграфа: Gsca¡ и Gre3

Определение 0.4. Задача миграции данных в ВО-СХД G - это многокритериальная задача оптимизации плана миграции. Основным критерием задачи является план миграции в подграфе Gscai, а второй критерий - план миграции в подграфе Grcs.

Для решения сформулированной задачи предложен переборный алгоритм миграции данных в ВО-СХД, а также предложен полиномиальный аппроксимационный алгоритм.

Алгоритм 0.3 (Полиномиальная миграции данных)

1. Выделить подграф Gscai из графа G на основе подмножества Ds-

2. Выделить подграф Gres из G на основе подграфа Gscai.

13

3. ■ Использовать полиномиальный алгоритм раскраски двудольного мулъ-

тиграфа (алгоритм 0.2) для вычисления плана миграции в Gscai-

4. Использовать аппроксимационный полиномиальный алгоритм Шеннона (алгоритм 0.1) для вычисления плана миграции мулътиграфа Gre3.

5. Получить общий план миграции ВО-СХД путем последовательного объединения планов миграции подграфа Gsmi с планом подграфа Gre3.

Алгоритм 0.4 (Переборная миграция данных) Переборный алгоритм миграции аналогичен полиномиальному алгоритму. Единственным отличием является использование оптимального переборного алгоритма раскраки ребер мулътиграфа на шаге 4-

Алгоритмы используют свойство двудолыюсти подграфа Gsca¡, которое доказывается на основе его определения. С практической точки зрения, дву-дольность Gscai означает, что во время масштабирования устройства D$ не обмениваются данными между собой. Двудольность позволяет использовать существующие точные полиномиальные алгоритмы (а не аппроксимацион-ные) для получения оптимального длана миграции в подграфе Gscai-

Доказывается оптимальность алгоритмов по первому критерию задачи миграции данных в ВО-СХД, а также доказывается полиномиаль-ность аппроксимационного алгоритма (0.3).

Теорема 0.1 (Оптимальность алгоритмов 0.3 и 0.4) Предложенные алгоритмы 0.3 и 0-4 оптимальны по первому критерию задачи миграции данных в ВО-СХД (определение 0.4).

Теорема 0.2 (Полиномиалыюсть алгоритма 0.3) Предложенный алгоритм миграции данных в ВО-СХД 0.3 имеет полиномиальную вычислительную сложность max{0(|.E|log|.E|),0(|.E|(x' + |£>|))}. Где Е - множе-

14

ство ребер, £> - множество вершин (устройств хранения), Д - максимальная степень вершин.

В пятой главе приводится описание реализации разработанных алгоритмов миграции данных в ВО-СХД. Разработана структура программы и интерфейсы взаимодействия различных модулей. Подробно описаны модули программы, реализующие алгоритм разделения модели миграции ВО-СХД и алгоритмы раскраски ребер мультиграфа. Программа реализована на языке программирования Python.

При помощи реализованного программного средства экспериментально проверяется доказанное выше свойство оптимальности времени масштабирования ВО-СХД, а также определяется выигрыш во времени, который будет получен при использовании предложенных алгоритмов. Используемая методика экспериментальной оценки эффективности алгоритма призвана ответить на следующие вопросы: на,сколько уменьшается время (количество шагов) масштабирования; на сколько увеличивается время полной процедуры миграции. Оценки времени производятся в процентах, относительно общего времени миграции с использованием традиционного алгоритма миграции данных. Используются следующие оценки (рис. 7):

. Р X'(G) - x'jGscal)

• "reí =-)¿(G)--относительный выигрыш от масштабирования, соответствующий сэкономленному времени по сравнению с традиционным алгоритмом;

. г x'(Gscal) + x'(Gres)

• Ьт-ei =-x'(G)--ЭТ° 0тп0снтельнь1й проигрыш времени

от разделения графа, соответствующий дополнительно затраченному времени на миграцию от общего времени миграции данных.

Эксперимент проводился на нескольких случайных графах различного размера (табл. 1). |D| - количество вершин графа, |£| - количество ребер,

Миграция данных в СХД

\ х Масштабирование ___

'1-!

Миграция данных в ВО-СХД

Рисунок 7. Оценка эффективности алгоритма миграции данных ВО-СХД Таблица 1. Результаты экспериментов

№ \Е\ \й \Овай\ Ры Т

1 14 12 3 40% 20% <0:01

2 30 20 5 50% 33% <0:01

3 37 22 6 57% 29% <0:01

4 39 25 6 33% 50% <0:01

5 46 28 7 43% 43% <0:01

6 103 37 16 50% 50% <0:01

7 719 12 6 23% 27% 0:13

8 1067 12 3 21% 8% 0:48

9 1176 25 6 16% 21% 4:24

10 2784 28 7 18% 34% 21:02

I АкаН - количество масштабируемых вершин, Т - время работы алгоритма.

Экспериментально показано, что предложенные алгоритмы способе-ны обеспечивать значительную экономию времени масштабирования Рте\ на 16-57%, по сравнению с существующими алгоритмами. При этом общее время миграции данных Ьп; может увеличиться на 8-50%. Также в главе описаны возможные способы сокращения общего времени миграции.

В Заключении представлены основные результаты и выводы по диссертационной работе.

Остатрчная миграция

Г X

Основные результаты работы

В диссертационной работе, согласно поставленным целям, были разработаны: математическая модель, алгоритмы и программное обеспечение, предназначенные для организации эффективного масштабирования ВО-СХД, имеющие важное научное и практическое значение. Результаты:

1. решена техническая задача уменьшения времени масштабирования ВО-СХД во время выполнения процедуры переконфигурации;

2. разработана модель миграции данных ВО-СХД, которая учитывает возможность изменения состава устройств хранения ВО-СХД;

3. на основе предложенной модели, сформулирована задача миграции данных в ВО-СХД в виде многокритериальной оптимизационной задачи, основной критерий - «время масштабирования» ;

4. разработаны переборный и аппроксимационный алгоритмы миграции данных для ОС ВО-СХД, способные производить масштабирование ВО-СХД за минимальное время;

5. математически доказана оптимальность предложенных алгоритмов по критерию минимума времени масштабирования ВО-СХД, также доказана полиномиалыюсть аппроксимациоиного алгоритма;

6. разработано программное средство, реализующее предложенные алгоритмы;

7. экспериментально показано, что предложенные алгоритмы способны обеспечивать экономию времени масштабирования на 16-57% (по сравнению с существующими алгоритмами), при этом общее время миграции данных может увеличиться на 8-50%.

Публикации в изданиях, рекомендованных ВАК России:

1. Петров Д. Л. Оптимальный алгоритм миграции данных в масштабируемых облачных хранилищах // Управление большими системами: сборник трудов (электроннь1й журнал). М. Институт проблем управления РАН. 2010. № 30. С. 180-197.

2. Петров Д. Л. Динамическая модель консолидированного облачного хранилища данных // Известия СПбГЭТУ «ЛЭТИ». СПб. 2010. № 4. С. 17-21.

I

Другие статьи и материалы конференций:

3. Petrov D. L., Tatarinov Y. Data migration in the scalable storage cloud (Миграция данных в масштабируемых облачных хранилищах) // IEEE International Conference on Ultra Modern Telecommunications. 2009. Pp. 1-4.

4. Петров Д. Л., Красюк В. Консолидация распределенных хранилищ данных: модели и алгоритмы // Материалы IX международной конференции-семинара. Высокопроизводительные параллельные вычисления на кластерных системах. 2009. С. 316-318.

5. Захаров А. С., Петров Д. Л. Реализация и экспериментальное исследование алгоритмов раскраски ребер мультиграфов // XVI международная открытая научная конференция. Современные проблемы информатизации в анализе и синтезе технологических и программно телекоммуника ционных систем. 2011. С. 320-324.

Подписано в печать 29.09.11. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 84.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

Введение

Глава 1. Особенности построения современных систем хранения данных.

1.1. Архитектуры современных систем хранения данных.

1.2. Особенности реализации облачных систем хранения данных

1.3. Выявление связи между процедурой миграции данных и масштабированием

1.4. Выводы.

Глава 2. Задача миграции данных в высокомасштабируемых облачных системах хранения данных.

2.1. Принципы организации высокомасштабируемых облачных систем хранения данных

2.2. Требования к задаче миграции данных в высокомасштабируемых облачных системах хранения.

2.3. Качественная постановка задачи.

2.4. Выводы.

Глава 3. Анализ известных моделей и алгоритмов миграции данных в системах хранения.

3.1. Обобщенная модель систем хранения данных.

3.2. Математическая модель миграции данных в системах хранения

3.3. Сведение задачи миграции данных к задаче раскраски ребер мультиграфа.

3.4. Выводы.

Глава 4. Разработка моделей и алгоритмов миграции данных в высокомасштабируемых облачных системах хранения

4.1. Модель миграции данных в высокомасштабируемых облачных системах хранения.

4.2. Алгоритмы миграции данных в высокомасштабируемых облачных системах хранения.

4.3. Доказательство свойств предложенных алгоритмов.

4.4. Выводы.

Глава 5. Экспериментальная оценка эффективности предложенных алгоритмов.

5.1. Методика проведения эксперимента.

5.2. Особенности реализации алгоритмов миграции данных.

5.3. Результаты эксперимента.

5.4. Выводы.

Актуальность работы

В последние годы произошло сильное изменение в практике и теории организации распределенных вычислительных систем связанное с появлением концепции cloud computing, или «облачных вычислений». Согласно этой концепции, вычислительные ресурсы арендуются по требованию через Интернет, а вычислительные системы лишь временно используют их для выполнения своих функций. Уже сегодня имеется возможность аренды вычислительных ресурсов с поминутной, и даже посекундной оплатой. Это позволяет создавать новые типы вычислительных систем-с уникальными технико-экономическими характеристиками- за счет гибкости в оплате и возможности арендовать потенциально бесконечное количество ресурсов.

Одними из самых востребованных современным бизнесом типов вычислительных систем являются системы хранения данных (СХД), которые представляют собой множество распределенных устройств хранения, объединенных вычислительной сетью и представленных пользователям в виде одного логического устройства большой емкости. Концепция облачных вычислений оказывает сильное влияние на современные СХД, что привело к появлению нового класса систем хранения - высокомасштабируемые облачные системы хранения данных (ВО-СХД, Scalable Storage Cloud). ВО-СХД, в отличие от традиционных СХД; используют в своем составе не фиксированное количество устройств хранения, а арендуют устройства по мере необходимости, или же высвобождают ряд устройств, когда необходимость в них отпадает. Для эффективного использования арендованных ресурсов ВО-СХД вынуждены регулярно производить процедуру масштабирования, т.е. изменения количества устройств хранения, входящих в систему.

Масштабирование выполняется операционной системой (ОС) ВО-СХД, оно связано с переконфигурацией хранилища, т.е. с перемещением огромного количества элементов данных (блоков данных) между устройствами хранения. Масштабирование и переконфигурация неразрывно связаны с алгоритмами миграции данных, которые строят план миграции (перемещения элементов данных) на основе текущего и целевого распределения элементов данных по устройствам хранения. Выполнение миграции данных не должно приводить к снижению качества обслуживания клиентов системы хранения, для чего в алгоритмах необходимо учитывать пропускную способность сети и максимальный объем данных, который можно передавать в один момент времени с одного устройства хранения на другое.

Существующие алгоритмы миграции данных не учитывают особенности ВО-СХД, и высвобождение лишних устройств хранения (добавление новых устройств) возможно производить лишь после полного завершения процедуры переконфигурации. Во время выполнения этого длительного этапа лишние устройства остаются задействованными, а новые устройства - не до конца использованными. Разработка специализированных алгоритмов миграции данных для управления арендованными ресурсами в ВО-СХД, способных сократить время масштабирования, позволит повысить эффективность использования ресурсов и понизить затраты на аренду устройств хранения, что представляет собой важную научную задачу, имеющую большое практическое значение.

Целью диссертационной работы является разработка алгоритмов миграции данных в ВО-СХД, способных уменьшить время масштабирования, по сравнению с традиционными алгоритмами миграции. В соответствии с указанной целью, в работе сформулированы и решены следующие задачи:

1. анализ существующих моделей СХД и алгоритмов миграции данных;

2. анализ особенностей ВО-СХД;

3. разработка модели ВО-СХД;

4. разработка алгоритмов миграции данных для ОС ВО-СХД;

5. анализ свойств разработанных алгоритмов.

Методы исследования. В исследовании формализация моделей производилась с помощью методов теории вычислительных систем и теории графов. Для описания и анализа алгоритмов в работе были использованы методы теории графов и теории алгоритмов.

Научная новизна работы заключается в следующем:

1. предложена математическая модель задачи миграции данных ВО-СХД, способная менять состав устройств хранения, и на основе модели сформулирована задача миграции данных в ВО-СХД в виде многокритериальной оптимизационной задачи;

2. предложены переборный и полиномиальный аппроксимационный алгоритмы миграции данных для управления вычислительными ресурсами ОС ВО-СХД, позволяющие предельно быстро производить масштабирование ВО-СХД;

3. произведен анализ свойств разработанных алгоритмов: доказана оптимальность алгоритмов по основному критерию «время масштабирования»; доказана полиномиальность вычислительной сложности аппрок-симационного алгоритма; экспериментально показана эффективность алгоритмов, по сравнению с существующими.

Практическая значимость. Предложенные модель и алгоритмы могут быть использованы при разработке ОС промышленных ВО-СХД, что позволит улучшить такой технико-экономический показатель ВО-СХД, как затраты на аренду вычислительных ресурсов.

На защиту выносятся следующие результаты и положения:

1. математическая модель миграции данных в ВО-СХД;

2. аппроксимационный алгоритм миграции данных для управления вычислительными ресурсами в ВО-СХД;

3. доказательство оптимальности предложенного алгоритма по первому критерию задачи миграции данных в ВО-СХД, а также доказательство его полиномиальности.

Апробация работы. Предлагаемые решения и результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях в 2008-2011 гг.

Публикации. Материалы диссертации опубликованы в 5 научных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК, 3 работы в научных трудах конференций, из которых одна работа на английском языке в трудах международной конференции сообщества IEEE.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 77 наименований. Основная часть работы изложена на 113 страницах машинописного текста. Работа содержит 23 рисунка, 5 таблиц и 4 приложения общим объемом 18 страниц.

5.4 Выводы В главе приводится описание реализации разработанного алгоритма миграции данных в ВО-СХД. Разработана структура программы и механизмы взаимодействия различных модулей. Подробно описаны модули программы, реализующие алгоритм разделения графа хранилища и алгоритм раскраски ребер мультиграфа. В частности, описан модуль, реализующий алгоритм раскраски ребер * двудольного мультиграфа, и модуль раскраски ребер произвольного мультиграфа алгоритмом Шеннона. Реализация алгоритма выполнена на языке программирования Python.

Разработанный и реализованный алгоритм миграции данных, специализированный под ВО-СХД, сравнивается с существющими алгоритмами миграции. Для оценки эффективности разработанного алгоритма используются критерии относительного выигрыша от масштабирования Prei и относительного проигрыша от остаточной миграции Lrei. Экспериментально показано, что предложенный алгоритм способен обеспечивать экономию времени масштабирования на 16-57%, по сравнению с существующими алгоритмами. При этом, общее время миграции данных может увеличиться на 8-50%. Также в главе предложены способы улучшения разработанного алгоритма.

Результаты пятой главы опубликованы в работе [77].

Заключение

Высокая консолидация вычислительных мощностей в современных ЦОД и высокие скорости обмена данными сети Интернет повышают доступность и снижают себестоимость вычислительных ресурсов. Концепция облачных вычислений, используя эти особености текущего состояния техники, позволяет создавать новые типы приложений и устройств на основе арендованных ресурсов, расположенных во внешних ЦОД. Это приводит к необходимости разработки научных основ для новых типов «облачных» приложений и устройств. Требуются новые модели построения устройств и приложений, новые алгоритмы управления ресурсами, новые методы взаимодействия приложений с пользователями.

Особый интерес представляют ВО-СХД, т.е. СХД, построенные на основе концепции облачных вычислений, арендующие внешние вычислительные устройства для хранения данных и предоставляющие ресурсы хранения для пользователей через Интернет. С технической и научной точки зрения, наибольший интерес представляют алгоритмы управления вычислительными ресурсами ОС ВО-СХД. Эффективное использование арендованных ресурсов требует регурлярного масштабирования системы, т.е. изменения состава устройств хранения. В разультате масштабирования система хранения должна адаптироваться к новым требованиям со стороны пользователей и высвобождать лишние устройства хранения, либо арендовать новые. Эти особености ВО-СХД требуют разработки принципиально новых алгоритмов управления вычислительными ресурсами, чему и посвящено данное диссертационное исследование.

ВО-СХД имеют сложную организацию и относятся к классу больших систем, что требует системного подхода к их проектированию. В работе производится разработка только первой стадии процесса проектирования сложных систем - макропроектирования, которое разбито на этапы анализа и синтеза. Результатом макропроектирования является модель системы и алгоритмы ее функционирования без учета специфики реализации системы и без детального описания ее подсистем.

Целью работы является разработка эффективных алгоритмов миграции данных для ОС ВО-СХД, сокращающих время масштабирования системы. На этапе анализа изучаются существующие СХД, технологии для их реализации, модели, а также алгоритмы миграции данных в системах хранения. Критерием оценки эффективности ВО-СХД является время масштабирования системы, т.е. время изменения состава устройств хранения, входящих в неё. В ходе анализа выявлена связь между масштабированием хранилища и оптимизационной задачей миграции данных, решаемой с целью оптимальной переконфигурации хранилища. Показано, что задачу масштабирования можно сформулировать в терминах задачи миграции данных, изменив критерий оптимизации. На основе проведенного анализа предложена модель ВО-СХД и сформулирована задача миграции данных как многокритериальная оптимизационная задача, основным критерием которой является время масштабирования.

На этапе синтеза были разработаны алгоритмы миграции данных ВО-СХД - переборный и аппроксимационный, которые, в отличие от существующих алгоритмов миграции, способны сократить время масштабирования хранилища и повысить за счет этого эффективность использования арендованных вычислительных ресурсов. Произведен анализ разработанных алгоритмов. Доказано, что разработанные алгоритмы дают оптимальный результат по основному критерию задачи миграции данных в ВО-СХД - времени масштабирования. Также доказана полиномиальность вычислительной сложности аппроксимационного алгоритма.

Предложенные алгоритмы реализованы и произведена экспериментальная оценка их эффективности по основному критерию сформулированной задачи миграции данных. Экспериментально показано, что предложенные алгоритмы способны обеспечивать экономию времени масштабирования на 16-57%, по сравнению с существующими алгоритмами. При этом общее время миграции данных может увеличиться на 8-50%. Описаны возможные способы улучшения разработанных алгоритмов.

По результатам работы опубликовано 2 статьи в изданиях перечня ВАК: «Управление большими системами» и «Известия СПбГЭТУ «ЛЭТИ». Основные положения и результаты работы докладывались и обсуждались на российских и международных конференциях: международная конференция сообщества IEEE «International Conference on Ultra Modern Telecommunication» 2009 (публикация на английском языке), IX международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» 2009, XVI международная открытая научная конференция «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем» 2011.

Дальнейшее развитие работы может быть направлено на стадию микропроектирования модуля переконфигурации ОС ВО-СХД способного сократить время масштабирования системы за счет внедрения разработанных алгоритмов миграции данных. Для этого необходим детальный анализ существующих технологий СХД, построение более детальной модели системы и проработка подсистем.

1. Farley М. Storage Networking Fundamentals: An 1.troduction to Storage Devices, Subsystems, Applications, Management, and File Systems. Cisco Press, 2005. P. 480.

2. Preston W. C. Using SANs and NAS. O'Reilly Media, 2002. P. 250.

3. Chirillo J., Blaul S. Storage Security: Protecting SANs, NAS and DAS. Indianapolis, USA: Wiley Publishing, 2003. P. 362.

4. Олифер H. А., Олифер В. Г. Сетевые операционные системы. СПб: Питер, 2008. С. 669.

5. Захаркина О. Как хранить данные: SAN, NAS или DAS // CNews. 2005. Т. 9.

6. Гук М. Энциклопедия Интерфейсы устройств хранения: ATA, SCSI и другие. СПб: Питер, 2006. С. 448.

7. Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. СПб: Питер, 2003. С. 877.

8. Ouchi N. К. System for recovering data stored in failed memory unit // U.S. patent 4,092,732. 1978. P. 1-13.

9. Patterson D. A., Gibson G., Katz R. A case for redundant arrays of inexpensive disks (RAID) // ACM, International Conference on Management of Data. 1988. P. 109-116.

10. Chen P., Lee E. Striping in a RAID level 5 disk array // ACM SIGMETRICS Performance Evaluation Review. 1995. Vol. 23, Issue 1. P. 136—145.

11. Somasundaram G., Shrivastava A. Information Storage and Management: Storing, Managing, and Protecting Digital Information. John Wiley & Sons, 2009. P. 476.

12. Kashyap S., Khuller S. Algorithms for Non-Uniform Size Data Placement on Parallel Disks // Conference on Foundations of Software technology and Theoretical Computer Science. 2003. P. 265-276.

13. Khuller S., Kim Y. A. Algorithms for Data Migration with Cloning // SIAM Journal on Computing. 2004. Vol. 2. P. 448-461.

14. Wolf J. The placement optimization program: a practical solution to the disk file assignment problem // ACM, SIGMETRICS Performance Evaluation Review. 1989. Vol. 17, Issue 1. P. 1-10.

15. Anderson E., Hobbs M., Keeton K. et al. Hippodrome: Running Circles Around Storage Administration // Conference On File And Storage Technologies. 2002. Vol. 13. P. 175-188.

16. Borowsky E., Golding R., Jacobson P. et al. Capacity Planning With Phased Workloads //In Proceedings of the First Workshop on Software and Performance (WOSP'98). 1998. Vol. 1. P. 199-207.

17. Sundaram V., Wood T., Shenoy P. Efficient Data Migration in Self-managing Storage Systems // IEEE International Conference on Autonomic Computing (ICAC). 2006. P. 297-300.

18. Golubchik L., Khanna S., Khuller S. et al. Approximation Algorithms for Data Placement on Parallel Disks // ACM-SIAM, SODA. 2000. P. 223-232.

19. Golubchik L., Khuller S., Kim Y. A. et al. Data Migration on Parallel Disks: Algorithms and Evaluation // Algorithmica. 2006. Vol. 45(1). P. 137-158.

20. Hall J., Hartline J., Karlin A. et al. On Algorithms for Efficient Data Migration // ACM-SIAM, SODA. 2001. P. 620-629.

21. Petrov D. L., Tatarinov Y. Data migration in the scalable storage cloud (Миграция данных в масштабируемых облачных хранилищах) // IEEE International Conference on Ultra Modern Telecommunications. 2009. P. 1—4.

22. Chenyang L., Guillermo A., Wilkes J. Aqueduct: Online Data Migration with Performance Guarantees // USENIX Conference on File and Storage Technologies. 2002. Vol. 1. P. 219-230.

23. Ghemawat S., Gobioff H., Leung S.-T. The Google File System // ACM 19th Symposium on Operating Systems Principles. 2003. Vol. 37, Issue 5. P. 29—43.

24. Ying Z. Research on Management of Data Flow in the Cloud Storage Node Based on Data Block // 3th International Conference on Information and Computing. 2010. Vol. 4. P. 333-335.

25. Catlett С. E., Smarr L. Metacomputing // Communications of the ACM. 1992. Vol. 35, Issue 6. P. 44-52.

26. Foster I. T. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // International Journal of High Performance Computing Applications. 2001. Vol. 15. Issue 3. P. 200-222.

27. Ferris C., Farrell J. What are Web services? // Communications of the ACM. 2003. Vol. 46, Issue 6. P. 1-31.

28. Huhns M. N., Singh M. P. Service-Oriented Computing: Key Concepts and Principles // IEEE Internet Computing. 2005. Vol. 9, Issue 1. P. 75-81.

29. Carr N. Does IT Matter? Information Technology and the Corrosion of Competitive Advantage. Harvard: Harvard Business Press, 2004.

30. Гофф М. К. Сетевые распределенные вычисления: достижения и проблемы. Москва: КУДИЦ-Образ, 2005. С. 320.

31. Воеводин В. В., Воеводин В. В. Паралельные вычисления. СПб: БХВ-Петербург, 2004. С. 608.

32. Пономаренко В. С., Листровой С. В., Минухин С. В., Знахур С. В. Методы и модели планирования ресурсов в GRID-системах. Москва: ИНЖЕК, 2008. С. 408.

33. Fouquet М., Niedermayer Н., Carle G. Cloud computing for the masses // ACM CoNEXT. 2009. P. 31-36.

34. Ньюкомер Э. Веб-сервисы: XML, WSDL, SOAP и UDDI. Спб: Питер, 2003. С. 256.

35. Tai S., Nimis J., Lenk A., Klems M. Cloud service engineering // International Conference on Software Engineerin. 2010. Vol. 2. P. 475-476.

36. Robison S. A Bright Future in the Cloud // Financial Times. 2008. Vol. 4.

37. Delic K. A., Walker M. A. Emergence of the academic computing clouds // ACM Ubiquity. 2008. Vol. 9, Iss. 31.

38. Chiu G. Z., Liu L. L. Adaptive Data Migration in Multi-tiered Storage Based Cloud Environment // 3rd International Conference on Cloud Computing (CLOUD), 2010. IEEE. 2010. P. 148-155.

39. Schwan K., Eisenhauer G., Gavrilovska A. et al. Managing large-scale utility cloud // IEEE International Symposium on Parallel &; Distributed Processing, Workshops and Phd Forum (IPDPSW). 2010. P. 1-1.

40. Xue W., Shi J., Yang B. X-RIME: Cloud-Based Large Scale Social Network Analysis // IEEE International Conference on Services Computing (SCC). 2010. Vol. 2010. P. 506-513.

41. Xu K., Song M., Zhang X., Song J. A Cloud Computing Platform Based on P2P // IEEE International Symposium on IT in Medicine & Education (ITIME). 2009. Vol. 1. P. 427-432.

42. Ying Z., Yong S. Cloud Storage Management Technology // IEEE ICIC. 2009. P. 309-311.

43. Gopisetty S., Butler E., Jaquet S., etc M. K. Automated planners for storage provisioning and disaster recovery // IBM Journal of Research and Development. 2008. Vol. 52, Iss. 4. P. 353-365.

44. Gupta K., Sarkar P., Mbogo L. MIRAGE: storage provisioning in large data centers using balanced component utilizations // ACM SIGOPS Operating Systems Review. 2008. Vol. 42, Iss. 1. P. 104-105.

45. Kamoun F. Virtualizing the Datacenter Without Compromising Server Performance // ACM Ubiquity. 2009. Vol. Aug.

46. Brynjolfsson E., Hofmann P., Jordan J. Cloud Computing and Electricity: Beyond the Utility Model // Communications of the ACM. 2010. Vol. 53, No. 5. P. 32-34.

47. Chang V., Bacigalupo D., Wills G., Roure D. D. A Categorisation of Cloud Computing Business Models // 10th IEEE/ACM CCGRID, International Conference on Cluster, Cloud and Grid Computing. 2010. P. 509—512.

48. Zuckerman B. Scalable storage in the cloud // Cloud Slam Conference. 2009.

49. McCullough J. С., Dunagan J., Wolman A., Snoeren A. C. Stout: an adaptive interface to scalable cloud storage // USENIXATC'10 Proceedings of the 2010 USENIX conference on USENIX annual technical conference. 2010. P. 4-4.

50. Bonvin N., Papaioannou T. G., Aberer K. A self-organized, fault-tolerant and scalable replication scheme for cloud storage // ACM SoCC '10 Proceedings of the 1st ACM symposium on Cloud computing. 2010. P. 205-216.

51. Shiflett C. HTTP Developer's Handbook. Sams, 2003. P. 312.

52. Смирнов С. H. XML и JDBC. Практическое введение. Москва: Гелиос АРВ, 2010. С. 188.

53. Ghandeharizadeh S., Ramos L., Asad Z., Qureshi W. Object Placement in Parallel Hypermedia Systems // Proceedings of the 17th International Conference on Very Large Data Bases. 1991. Vol. 03-06. P. 243-254.

54. Советов В., Яковлев С. Моделирование систем (4-е издание). Москва: Высшая школа, 2005. С. 343.

55. Бусленко Н. Моделирование сложных систем. Москва: Наука, 1988. С. 356.

56. Шеннон Р. Имитационное моделирование систем. Искусство и наука. Москва: Мир, 1978. С. 424.

57. Frieze А. М., Clarke R. В. Approximation algorithms for the m-dimensional knapsack problem: worst case and probabilistic analyses // European Journal of Operational Research. 1984. P. 100-109.

58. Chekuri C., Khanna S. On multidimensional packing problems // SODA. 1999. P. 185-194.

59. Евстигнеев В., Касьянов В. Графы в программировании: обработка, визуализация и применение. СПб: БХВ-Петербург, 2003. С. 1104.

60. Корман Т. X., Лейзерсон Ч. И., Ривест P. JL, Штайн К. Алгоритмы: построение и анализ. 2-ое издание. Перевод с англ. М.: Вильяме, 2007. С. 1296.

61. Goldberg М. К. Edge-coloring of multigraphs: Recoloring technique // Graph Theory. 1984. Vol. 8. P. 121-137.

62. Holyer I. The NP-completeness of Edge-Coloring // SIAM Journal on Computing. 1982. Vol. 11. P. 117-129.

63. Shannon С. E. A theorem on colouring lines of a network // Journal of Mathematics and Physics. 1949. Vol. 28. P. 148-151.

64. Hochbaum D. S., Nishizeki Т., Shmoys D. B. A better than "Best Possible" algorithm to edge color multigraphs // J. off Algorithms. 1986. Vol. 7. P. 79-104.

65. Hopcroft J., Karp R. An n. 5/2 algorithm for maximum matchings in bipartite graphs // SIAM Journal on Computing. 1973. Vol. 2. P. 225-231.

66. Cole R., Ost K., Schirra S. Edge-coloring bipartite multigraphs in 0(E log D) time // Combinatorica. 2001. Vol. 21. P. 5-12.

67. Alon N. A simple algorithm for edge-coloring bipartite multigraphs // Information Processing Letters. 2003. Vol. 85, Issue 6.

68. Визинг В. Хроматический класс мультиграфа // Кибернетика. 1965. Т. 3. С. 29-39.

69. Berger M., Bokhari S. Partitioning strategy for nonuniform problems on multiprocessors // IEEE Transactions on Computers. 1987. Vol. 36, Iss. 5. P. 570-580.

70. George A., Liu J. Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall Professional Technical Reference, 1981.

71. Петров Д. JI. Динамическая модель консолидированного облачного хранилища данных // Известия СПбГЭТУ "ЛЭТИ". №4. 2010. С. 17-21.

72. Петров Д. Л. Оптимальный алгоритм миграции данных в масштабируемых облачных хранилищах // Управление большими системами: сборник трудов (электронный журнал). №30. М. Институт проблем управления РАН. 2010. С. 180-197.

73. Бизли Д. М., ван Россум Г. Язык программирования Python. Справочник. Москва: ДиаСофт, 2000.

74. Сузи P. Python. Наиболее полное руководство. Санкт-Петербург: БХВ-Петербург, 2002.

75. Буч Г., Максимчук Р. А., Энгл М. У. и др. Объектно-ориентированный анализ и проектирование с примерами приложений. М.: Вильяме, 2008.

76. Орлов С. Технологии разработки программного обеспечения. СПб: Питер, 2002. С. 464.