Миграция данных

Ключевые слова и синонимы

Перенос файлов; перемещение данных

Постановка задачи

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

Рисунок 1. Слева: примеры исходного и целевого расположения данных. Справа: соответствующие множества [math]\displaystyle{ S_i \; }[/math] и [math]\displaystyle{ D_i \; }[/math]

Определение задачи выглядит следующим образом. Предположим, что имеется N дисков и [math]\displaystyle{ \Delta \; }[/math] элементов данных и что заданы исходное и целевое расположения (см. пример на рис. 1а). Для каждого элемента i его диски-источники [math]\displaystyle{ S_i \; }[/math] определяются как подмножество дисков, содержащих элемент i в своем исходном расположении. Диски-назначения [math]\displaystyle{ D_i \; }[/math] представляют собой подмножество дисков, желающих получить элемент i. Иными словами, диски из [math]\displaystyle{ D_i \; }[/math] должны хранить элемент i в целевом расположении, но не в исходном. На рис. 1б представлены соответствующие множества [math]\displaystyle{ S_i \; }[/math] и [math]\displaystyle{ D_i \; }[/math]. Предполагается, что [math]\displaystyle{ S_i \ne \empty \; }[/math] и [math]\displaystyle{ D_i \ne \empty \; }[/math] для каждого элемента i. Миграция данных представляет собой перенос данных таким образом, чтобы все множества [math]\displaystyle{ D_i \; }[/math] получили элемент i, изначально находившийся в [math]\displaystyle{ S_i \; }[/math], а задача заключается в минимизации общего времени, необходимого для переносов.

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

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

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

Хуллер и др. [11] разработали 9,5-аппроксимацию для задачи миграции данных, коэффициент которой был впоследствии улучшен до 6.5 + o(1). Далее мы рассмотрим нижние границы задачи.

Нотация и нижние границы

1. Максимальная полустепень захода ( [math]\displaystyle{ \beta \; }[/math]): Пусть [math]\displaystyle{ \beta_j \; }[/math] – количество элементов данных, которые собирается получить диск j. Иными словами, [math]\displaystyle{ \beta_j = | \{i | j \in D_i\} | }[/math]. Тогда [math]\displaystyle{ \beta = max_j \beta_j \; }[/math] является нижней границей оптимума, поскольку диск может получить только один элемент данных в одном раунде.

2. Максимальное количество элементов, источником или назначением которых может быть диск [math]\displaystyle{ (\alpha \; }[/math]): Для каждого элемента i по меньшей мере один диск в [math]\displaystyle{ S_i \; }[/math] должен быть использован в качестве источника элемента, этот диск называется первичным источником. Уникальный первичный источник [math]\displaystyle{ s_i \in S_i \; }[/math] для каждого элемента i, минимизирующего значение [math]\displaystyle{ \alpha = max_{j = 1, ..., N} (| \{ i | j = s_i \} |) \; }[/math], может быть найден при помощи алгоритма вычисления потока в сети. Отметим, что [math]\displaystyle{ \alpha \ge \beta \; }[/math]; [math]\displaystyle{ \alpha \; }[/math] также является нижней границей оптимального решения.

3. Минимальное время, необходимое для клонирования (M): Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает [math]\displaystyle{ 2^{m - k} \; }[/math], поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее [math]\displaystyle{ |D_i| \; }[/math] копий элемента i, минимальное значение m, удовлетворяющее следующей линейной программе, задает нижнюю границу оптимального решения:

L(m):

Алгоритм миграции данных

9,5-аппроксимацию можно получить следующим образом.

Алгоритм вначале вычисляет множества представителей для каждого элемента и отправляет элемент в множество, которое, в свою очередь, пересылает элемент в оставшееся множество. Множества представителей вычисляются по-разному в зависимости от размера [math]\displaystyle{ D_i \; }[/math].

Представители для больших множеств

Для множеств размером не менее [math]\displaystyle{ \beta \; }[/math] непересекающаяся коллекция множеств представителей [math]\displaystyle{ R_i, i = l, ..., \Delta \; }[/math] должна удовлетворять следующим свойствам: (1) каждое множество [math]\displaystyle{ R_i \; }[/math] должно быть подмножеством [math]\displaystyle{ D_i \; }[/math], (2) [math]\displaystyle{ |R_i| = \lfloor| D_i | / \beta \rfloor \; }[/math]. Множества представителей могут быть найдены при помощи алгоритма вычисления потока в сети.

Представители для маленьких множеств

Для каждого элемента i положим [math]\displaystyle{ \gamma_i = | D_i | \; mod \; k }[/math]. Необходимо вычислить вторичного представителя [math]\displaystyle{ r_i в D_i \; }[/math] для элементов с [math]\displaystyle{ \gamma_i \ne 0 \; }[/math]. Диск j может быть вторичным представителем [math]\displaystyle{ r_i \; }[/math] для нескольких элементов, если [math]\displaystyle{ \sum_{i \in I_j} \gamma_i \le 2 \beta + 1 \; }[/math], где [math]\displaystyle{ I_j \; }[/math] – множество элементов, для которых j является вторичным представителем. Это можно сделать при помощи алгоритма Шмойса-Тардош [17] для обобщенной задачи о назначениях.

Планирование миграций

Если имеются представители для всех элементов данных, миграцию можно выполнить в три этапа следующим образом:

1. Миграция в [math]\displaystyle{ R_i \; }[/math]: каждый элемент данных вначале отправляется в множество [math]\displaystyle{ R_i \; }[/math]. Преобразуя дробное решение, приведенное в L(M), можно найти график миграции из [math]\displaystyle{ s_i \; }[/math] в [math]\displaystyle{ R_i \; }[/math], требующий не более [math]\displaystyle{ 2M + \alpha \; }[/math] раундов.

2. Миграция в [math]\displaystyle{ r_i \; }[/math]: элемент i отправляется из первичного источника [math]\displaystyle{ s_i \; }[/math] в [math]\displaystyle{ r_i \; }[/math]. Эту миграцию можно выполнить за [math]\displaystyle{ 1,5 \alpha \; }[/math] раундов при помощи раскраски ребер [16].

3. Миграция на оставшиеся диски: Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в [math]\displaystyle{ R_i \; }[/math] к [math]\displaystyle{ (\beta - 1) \lfloor \frac{|D_i|}{\beta} \rfloor \; }[/math] дисков в [math]\displaystyle{ D_i \backslash R_i \; }[/math], такие, что полустепень выхода каждой вершины в [math]\displaystyle{ R_i \; }[/math] не превышает [math]\displaystyle{ \beta - 1 \; }[/math], а полустепень входа каждой вершины в [math]\displaystyle{ D_i \backslash \R_i \; }[/math] из [math]\displaystyle{ R_i \; }[/math] равна 1. Также добавляется ориентированное ребро от вторичного представителя [math]\displaystyle{ r_i \; }[/math] элемента i к оставшимся дискам в [math]\displaystyle{ D_i \; }[/math], не имеющим входящих ребер из [math]\displaystyle{ R_i \; }[/math]. Было показано, что максимальная степень графа переносов не превышает [math]\displaystyle{ 4 \beta - 5 \; }[/math], а кратность равна [math]\displaystyle{ \beta + 2 \; }[/math]. Следовательно, миграцию из графа переносов можно выполнить за [math]\displaystyle{ 5 \beta - 3 \; }[/math] раундов при помощи алгоритма раскраски ребер мультиграфа [18].

Анализ

Заметим, что общее количество раундов, необходимых для выполнения вышеописанного алгоритма, не превышает [math]\displaystyle{ 2M + 2,5 \alpha + 5 \beta - 3 \; }[/math]. Поскольку [math]\displaystyle{ \alpha \; }[/math], [math]\displaystyle{ \beta \; }[/math] и M являются нижними границами оптимального количества раундов, этот алгоритм дает 9,5-аппроксимацию.

Теорема 1 ([11]). Существует алгоритм 9,5-аппроксимации для задачи миграции данных. Хуллер и др. [10] позднее улучшили его, получив (6,5 + o(1))-аппроксимацию.

Теорема 2 ([10]). Существует алгоритм (6.5 + o(1))-аппроксимации для задачи миграции данных.

Применение

Миграция данных в системах хранения