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

Задача миграции данных является NP-полной в силу редукции задачи раскраски ребер. Однако для этой задачи неизвестны доказательства неаппроксимируемости. На данный момент лучший коэффициент аппроксимации достаточно высок (6:5 + o(1)), и было бы любопытно сузить разрыв между гарантией аппроксимации и неаппроксимируемостью.

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