Миграция данных: различия между версиями

Обычно большой сервер, хранящий данные, состоит из нескольких дисков, соединенных в сеть, называемую ''сетью хранения данных''. Для удовлетворения высокого спроса, особенно в случае мультимедийных данных, обычно практикуется репликация объектов данных в рамках системы хранения. У дисков обычно имеются ограничения на объем хранимых данных, а также на количество клиентов, которые могут одновременно обращаться к данным с одного диска. Было разработано несколько алгоритмов аппроксимации для сопоставления известной потребности в данных с конкретной схемой расположения данных для максимально продуктивного их использования [под использованием понимается общее количество клиентов, которые могут быть назначены диску, содержащему нужные им данные] [4, 8, 14, 15]. Для этого они вычисляют не только количество копий каждого элемента, которые необходимо создать, но и схему расположения, определяющую точное подмножество элементов на каждом диске. Эта задача является NP-полной, однако для нее существуют схему аппроксимации с полиномиальным временем выполнения [4, 8, 14]. Если известен относительный спрос на данные, алгоритм вычисляет почти оптимальную схему.

Еще один открытый вопрос заключается в объединении задач размещения и миграции данных. Этот вопрос изучали Хуллер и др. [9]. Пусть даны изначальное расположение и новая модель спроса. Задача заключается в поиске серии перемещений данных, которая может быть выполнена за определенное число этапов и обеспечивает наилучшее возможное расположение для имеющейся модели спроса. Они показали, что даже одноэтапная миграция является NP-полной задачей, и предложили эвристический алгоритм для ее решения. Эксперименты показали, что последовательное многократное выполнение одноэтапной миграции дает высокий практический результат. В дальнейшем было бы любопытно получить нетривиальные алгоритмы аппроксимации для этой задачи.

Еще одно перспективное направление будущих исследований – миграция данных в гетерогенной системе хранения. Большинство исследований миграции данных были посвящены главным образом гомогенным системам хранения и предполагали, что все диски имеют одни и те же фиксированные свойства, а все сетевые соединения – одну и ту же фиксированную пропускную способность. Однако на практике крупные системы хранения могут быть гетерогенными. Например, диски могут иметь разные свойства, поскольку добавляются со временем из-за возросшего спроса на емкость памяти. Лу и др. [13] изучали случай с различной пропускной способностью дисков, связанной с разной нагрузкой. Они использовали подход на базе теории управления для генерации адаптивных коэффициентов миграции данных, обеспечивающих минимальное снижение качества предоставления услуги. Этот алгоритм значительно уменьшает время задержки для клиентов по сравнению с предыдущими схемами. Однако теоретических границ эффективности миграции данных представлено не было. Коффман и др. [2] изучали случай, в котором каждый диск i может одновременно обрабатывать <math>p_i \;</math> передач, и предложили алгоритмы аппроксимации. В некоторых статьях [2, 12] рассматривался случай с гетерогенной длиной элементов данных (однако сама система при этом была гомогенной) и были предложены алгоритмы аппроксимации для этой задачи.

Специальный случай задачи миграции данных изучали Андерсон и др. [1] и Холл и др. [5]. Они предположили, что имеется граф переносов данных, вершины которого соответствуют дискам, а ориентированные ребра – каждой обозначенной операции перемещения (создание новых копий элементов данных не допускается). Вычисление графика перемещения данных в точности соответствует задаче раскраски ребер графа переноса. Теперь можно применить алгоритмы раскраски ребер мультиграфов для расчета графика миграции, поскольку каждый класс цветов представляет сопоставление в графе, которое можно спланировать одновременно. Вычисление решения с минимальным количеством раундов является NP-полной задачей, однако для раскраски ребер разработано несколько эффективных алгоритмов аппроксимации. Задача становится сложнее при наличии ограничений на объем диска. Холл и др. [5] показали, что в предположении, что на каждом диске имеется один свободный элемент памяти, можно разработать очень эффективные аппроксимации с константным коэффициентом. Такие алгоритмы используют не более <math>4 \lceil \Delta / 4 \rceil \;</math> цветов и не более n/3 обходных вершин, либо не более <math>6 \lceil \Delta / 4 \rceil \;</math> цветов – без обходных вершин.