Результат интеллектуальной деятельности: СПОСОБ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ИСПОЛЬЗОВАНИЯ ВИРТУАЛЬНЫХ СЕТЕВЫХ РЕСУРСОВ ЦЕНТРОВ ОБРАБОТКИ ДАННЫХ

Изобретение относится к области планирования распределения виртуальных ресурсов центров обработки данных (ЦОД), облачных платформ и средств по организации управления ресурсами систем.

Качество работы планировщиков ресурсов в центрах обработки данных (ЦОД) определяет загрузку ресурсов ЦОД и возможность гарантированного обеспечения требуемого качества сервиса SLA (Service Level Agreement - соглашения об уровне услуг). Из уровня техники известны алгоритмы, используемые в платформе OpenStack [Pepple K. Deploying OpenStack. Sebastopol: O'Reilly, 2011] "назначение запроса на первый подходящий физический ресурс" или "выбор случайным образом физического ресурса из множества подходящих ресурсов" приемлемы по качеству получаемых отображений запросов на физические ресурсы ЦОД при их загрузке до 50%. При загрузке физических ресурсов больше 50% качество отображений, получаемых этими алгоритмами, значительно ухудшается.

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

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

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

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

Заявленное изобретение согласно еще одному варианту осуществления сочетает жадные стратегии и стратегии ограниченного перебора, который наиболее эффективен в случае, когда критическими ресурсами являются сетевые ресурсы. Алгоритм основан на "компактном" размещении в ЦОД запроса на создание виртуальной сети.

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

Алгоритм осуществляет работу по шагам, последовательно обрабатывая запросы. На каждом шаге производится попытка размещения одного запроса в ЦОД, если разместить запрос не удается, то алгоритм переходит к следующему и т.д., пока не исчерпаются все запросы. Перед тем как начать последовательно просматривать запросы, они сортируются по убыванию суммарного количества элементов, содержащихся в запросе.

Первым делом из обрабатываемого запроса выделяются виртуальные узлы, а именно: виртуальные машины и виртуальные хранилища данных. Обозначим множество этих элементов - U. Затем производятся следующие действия:

1. По первому жадному критерию, выбирается виртуальный элемент с максимальной взвешенной суммой его параметров, из множества U и помещается в очередь Q элементов, ожидающих назначение.

2. Из очереди выбирается очередной виртуальный элемент (в зависимости от свойств виртуального элемента сначала отработает шаг 3 или 4, потом 5).

3. Если для рассматриваемого виртуального элемента элементы, связанные с ним виртуальными каналами, еще не размещены в ЦОД или рассматриваемый элемент в принципе не связан виртуальными каналами ни с одним другим элементом, то сформировать множество физических узлов, на которых может разместиться рассматриваемый виртуальный элемент. Если множество физических узлов, на которые можно разместить рассматриваемый виртуальный элемент, не пусто, то выбрать из этого множества физический узел, используя второй жадный критерий, выбирается физический элемент с минимальной взвешенной суммой его параметров, и производят назначение виртуального элемента, перейти к шагу 5. Если данное множество пусто, то вызвать процедуру ограниченного перебора. При неуспешном завершении процедуры удалить ранее назначенные элементы текущего запроса и перейти к обработке следующего запроса. Если процедура вернула успех, перейти к шагу 5.

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

5. Поместить в очередь Q не назначенные виртуальные элементы, которые связаны с рассматриваемым виртуальным элементом. Удалить рассматриваемый элемент из очереди Q. Если очередь Q не пуста, то перейти к шагу 2. Если очередь пуста, а множество U не пусто, то перейти к шагу 1. В ситуации, когда U пусто - все элементы запроса назначены, перейти к обработке следующего запроса.

Сущность заявленного изобретения поясняется следующими чертежами.

На фиг. 1 приведена блок-схема алгоритма планирования ресурсов.

На фиг. 2 приведена диаграмма классов заявленного технического решения.

На фиг. 3 приведена архитектура заявленного технического решения.

На фиг. 4 приведены входные данные алгоритма планирования ресурсов.

На фиг. 5 приведена условная схема работы заявленного изобретения.

В заявляемом изобретении модель физических ресурсов ЦОД задается графом Н = (Р, М, K, L), где Р - множество вычислительных узлов, М - множество хранилищ данных, К - множество коммутационных элементов сети обмена ЦОД, L - множество физических каналов передачи данных. На множествах Р, М, K и L определены векторные функции скалярного аргумента, задающие соответственно характеристики вычислительных узлов, хранилищ данных, коммутационных элементов и каналов передачи данных:

ph(p) (ph(p), ph(p), …, ph(p)),

mh(m) (mh(m), mh(m), …, mh(m)),

kh(k) (kh(k), kh(k), …, khn₂(k)),

lh(l) (lh(l), lh(l), …, lhn₃(l)).

где p ∈ P, m ∈ M, k ∈ K, l ∈ L. Компоненты векторной функции могут принимать целочисленные и вещественные значения. Согласно предпочтительному варианту осуществления заявленного изобретения для коммутационных элементов и каналов передачи данных определяются одинаковые характеристики.

Ресурсный запрос задается графом G(W, S, Е), где W - множество виртуальных машин, используемых приложениями, S - множество виртуальных хранилищ данных (storage-элементов), Е - множество виртуальных каналов передачи данных между виртуальными машинами и storage-элементами запроса. На множествах W, S и Е определены векторные функции скалярного аргумента, задающие характеристики запрашиваемого виртуального элемента (требуемое качество сервиса (SLA)):

wg(w) (wg₁(w), wg₂(₁w), …, wg_n (w)),

Здесь w ∈ , s ∈ S, e ∈ E. Компоненты векторной функции также принимают целочисленные или вещественные значения. Характеристики SLA элемента запроса совпадают с характеристиками соответствующего ему физического ресурса.

Назначают ресурсный запрос, который представляет собой отображение А:G→Н={W→Р, S→М, Е→{K, L}}. Выделяют три типа отношений между характеристиками элементов запросов и соответствующих характеристик физических ресурсов. Обозначают через xi характеристику i-го элемента запроса, через у j - соответствующую ей характеристику j-го физического ресурса. Указанные отношения можно записать следующим образом.

1. Недопустимость перегрузки емкости физического ресурса:

Σi ∈ Rjx_i≤y_j, здесь R - множество элементов запросов, назначенных на выполнение на физическом ресурсе yj.

2. Соответствие типа запрашиваемого ресурса типу физического ресурса: x_i y_i.

3. Наличие требуемых характеристик у физического ресурса: x_i≤y_i.

Отображение А:G→Н={W→Р, S→М, Е→{K, L}} считается корректным, если для всех физических ресурсов и всех их характеристик выполняются отношения, указанные выше.

Остаточным графом доступных ресурсов называется граф Hres, для которого переопределены значения функций по характеристикам, которые должны удовлетворять отношению 1:

Здесь Wp - множество виртуальных машин, назначенных на выполнение на вычислительном узле р, El - множество виртуальных каналов, отображенных на физический канал l, Ek - множество виртуальных каналов, проходящих через коммутационный элемент k, Sm - множество storage-элементов, размещенных в хранилище данных m.

В качестве исходных данных задачи назначения ресурсных запросов на физические ресурсы заданы:

1) множество запросов Z={G_i}, поступивших планировщику;

2) остаточный граф доступных ресурсов H_res (Р М K, L).

Требуется: из множества Z разместить на выполнение в ЦОД максимальное число запросов, таких, что отображение А является корректным.

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

Репликацией называется отображение R:Н→Н, дублирующее данные некоторого m ∈ М, создающее виртуальный канал поддержки консистентности данных ki ∈ K, li ∈ L, m' ∈ М, m' - реплика хранилища m (m', l1, k1, …, kn 1, ln, m).

Если storage-элемент является репликацией некоторого виртуального хранилища данных s, то в граф запрашиваемых ресурсов G добавляется вершина s'. В граф G также добавляется виртуальный канал между вершинами s и s', пропускная способность которого определяется исходя из требования обеспечения консистентности репликации и базы данных.

Входом алгоритма назначения запросов на физические ресурсы являются остаточный граф доступных ресурсов Н res и множество ресурсных запросов {Gi}. Множество {Gi} формирует диспетчер задач. В него кроме вновь поступивших запросов могут входить и запросы, которые выполняются и для которых допустима миграция. Диспетчер задач также определяет время запуска планировщика.

Выходом алгоритма назначения запросов на физические ресурсы является множество назначений ресурсных запросов на физические ресурсы {A_i:G_i→H,i=1,n} и множество репликаций {R_i}, i 0, 1, …

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

Шаг 1. Если множество ресурсных запросов {G_i} не пусто, то выбирают очередной запрос G_i в соответствии с жадным критерием K_G, в противном случае - завершают работу алгоритма.

Шаг 2. Формируют из элементов запроса G_i множество U {W S).

Шаг 3. Выбрать очередной элемент е ∈ U в соответствии с жадным критерием Kƒ, поместить е в очередь Q элементов, ожидающих назначения.

Шаг 4. Выбрать из Q элемент е в соответствии с жадным критерием K_Q, выполнить следующие действия:

4а) сформировать множество физических ресурсов Ph, на которые может быть назначен данный элемент е, т.е. для которого выполнены отношения корректности отображения в случае назначения запроса е на физический ресурс. Если данное множество пусто, то вызвать процедуру ограниченного перебора. При неуспешном завершении процедуры удалить ранее назначенные элементы запроса Gi и переопределить значения характеристик физических ресурсов в соответствии с функциями, удалить запрос из множества {Gi}, перейти к шагу 1;

4b) выбрать физический ресурс ph ∈ Ph в соответствии с жадным критерием K ph;

4с) сформировать пути между ph и физическими ресурсами, на которые назначены элементы запроса, связанные виртуальными каналами с элементом е, в случае неуспеха удалить ph из Ph, перейти к шагу 4b;

4d) назначить е на ph и переопределить значения характеристик физических ресурсов в соответствии с функциями (1.1);

4е) удалить е из Q и U;

4f) добавить в Q множество элементов запроса {e_t}, связанных виртуальными каналами с элементом е, e_t ∈ U.

Шаг 5. Если Q не пусто, то перейти к шагу 4.

Шаг 6. Если U не пусто, то перейти к шагу 3, в противном случае перейти к шагу 1.

Процедура ограниченного перебора вызывается при отсутствии возможности назначить очередной элемент запроса е ни на один физический ресурс ph. Процедура ограниченного перебора выполняет поиск среди множества А уже назначенных элементов запросов такого подмножества Am ⊆ A, что элемент может быть назначен после переназначения элементов из Am. Перебор ограничивается числом m, задающим максимальное количество физических элементов, для которых возможно переназначение. При переборе рассматриваются только такие множества из m ресурсов, которые в сумме имеют достаточное количество остаточных ресурсов для назначения текущего элемента.

Общая схема процедуры ограниченного перебора.

1. Для заданного m сформировать все множества Am ⊆ A из m физических ресурсов.

2. Если для некоторого множества Am суммарная остаточная емкость ресурсов достаточна для назначения текущего элемента:

2.1) произвести снятие элементов, которые назначены на физические ресурсы из множества Am и для которых разрешена миграция;

2.2) произвести снятие всех виртуальных каналов, связанных с элементами из множества Am;

2.3) произвести попытку переназначить элементы множества Am и назначить элемент е, а также всех связанных с ними виртуальных каналов. Возможны три варианта:

i) назначить элемент е, а затем все элементы множества Am с использованием жадной схемы (шаги 2-4 основной схемы алгоритма без вызова процедуры ограниченного перебора);

ii) назначить элементы множества Am ∪ {е} с использованием жадной схемы (шаги 2-4 основной схемы алгоритма без вызова процедуры ограниченного перебора);

iii) назначить элементы множества Am ∪ {е} с использованием полного перебора;

2.4) в случае успешного назначения всех элементов вернуть успех, в противном случае восстановить исходные назначения элементов из Am.

Если после перебора всех сформированных множеств элемент е назначить не удается, вернуть неуспех. Указанная схема при фиксированном m может позволить за полиномиальное время произвести переназначение с возможностью назначения элемента е.

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

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

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

Минимальная остаточная величина пропускной способности физического элемента. При этом увеличивается утилизация сетевых ресурсов при возможно более компактном размещении запросов. Применение этого критерия повышает точность алгоритма в ЦОД с топологией fat-tree и другими аналогичными топологиями с дополнительными каналами обеспечения доступности.

Качество работы алгоритма существенно зависит от выбора жадных критериев. Критерии задаются для выбора очередного запроса K_G, очередного элемента запроса K_ƒ и для выбора физического ресурса для назначения этого элемента K_ph.

Критерий K_ƒ основан на функции стоимости r(е) назначения элемента е. Элемент характеризуется вектором значений требуемых характеристик ресурса (r_e, 1, r_e, 2, …, r_e, n).

Данная величина вычисляется как частное, в котором числитель - разница между общим значением требуемой характеристики ресурса по всем запросам и значением имеющихся физических ресурсов по данной характеристике. Знаменателем является общая сумма требуемых ресурсов по данной характеристике. В случае, если имеющихся ресурсов достаточно для назначения запроса, дефицит d(i) может принимать отрицательные значения.

В качестве критерия K_ƒ предлагается выбирать элемент, для которого физические ресурсы в текущий момент времени имеют наибольший дефицит. Таким образом, среди элементов запроса выбирается такой элемент е, стоимость r(e) которого максимальна.

Для выбора физического ресурса ph ∈ Ph для назначения очередного элемента запроса е предлагается критерий K_h, при котором выбирается элемент ph с минимальной суммарной длиной путей до всех элементов, на которых размещены назначенные элементы запроса, связанные виртуальными каналами с назначаемым элементом е. Длина пути измеряется в количестве дуг физической сети обмена входящих в путь.

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

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

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

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

Процедура репликации возможна в случае, если одним из элементов запроса, соединяемым виртуальным каналом e(w, s), является storage-элемент s ∈ S, для которого доступна репликация. Процедура заключается в поиске хранилища данных m ∈ М, которое имеет достаточно ресурсов для назначения реплики (реплика требует столько же ресурсов, сколько и данный storage-элемент s). Кандидаты рассматриваются в порядке возрастания суммарной длины маршрутов всех виртуальных каналов e(w, s) (включающих данный storage-элемент s) к данной реплике m в соответствии с критерием Kph. Кроме того, необходимо проложить канал 1 для поддержания консистентности между репликой и исходным storage-элементом (требуемая пропускная способность канала 1 определяется интенсивностью потока данных, необходимых для поддержания консистентности). В случае невозможности прокладки канала 1 с требуемой пропускной способностью процедура переходит к рассмотрению следующего кандидата на размещение.

При успешном выполнении процедуры репликации последующее назначение виртуальных каналов, включающих данный storage-элемент s, можно производить или на данную реплику m, или storage-элемент s ∈ S. Если не удается найти хранилище данных m ∈ М с достаточным количеством ресурсов или не удается провести канал поддержания консистентности данных 1, то процедура возвращает неуспех.

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

Изобретение промышленно применимо, поскольку использует промышленно изготовленные и промышленно применимые ресурсы.

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