К. т. н., доцент Угрин Д. І., к. ф.-м. н. Вершигора В. Г.

ПВНЗ «Буковинський університет», Україна

МАТЕМАТИЧНІ ПІДХОДИ РІШЕННЯ ЗАДАЧІ МІГРАЦІЇ ДАНИХ У МАСШТАБОВАНИХ ХМАРНИХ СХОВИЩАХ

У розподілених системах оптимізація обчислювальних ресурсів стандартним чином здійснюється за допомогою процедури збалансування навантажень [1], яка полягає в призначенні виникаючих завдань певним пристроям-оброблювачам, об’єднаним в кластер. Таким чином, будь-яке завдання може бути оброблене будь-яким з пристроїв у кластері. Нажаль, ця умова не виконується в розподілених сховищах даних. Кожний із засобів не може зберігати всі дані, які можуть бути необхідними, тому кожний елемент даних (блок даних, файл) зберігається тільки на обмеженому наборі пристроїв збереження. Процедура балансування навантаження в розподілених сховищах є відносно простою і полягає у виборі пристрою з цього обмеженого набору. Основна ж задача розподілених сховищ даних – регулярна переконфігурація, яка повинна здійснюватися кожен раз після змін виконаних з даними [2, 3, 4, 5, 7]. Переконфігурація полягає у оптимізації розподілення даних по пристроям збереження, що входять в склад сховища. Цей процес вимагає переміщення великих об’ємів даних і займає багато часу. Одночасне переміщення великих об’ємів даних призводить до різкого падіння продуктивності. Задача складання оптимального плану переміщення даних у сховищі називається задачею міграції даних [4]. Отриманий в результаті її рішення план міграції даних дозволяє виконати процедуру міграції умовно швидше, тобто оптимізація плану міграції призводить до оптимізації часу міграції. Доведено, що задача міграції даних NP-складна [4], тобто неможливо отримати оптимальне рішення за поліноміальний час. Існують апроксимаційні алгоритми її рішення [3, 4, 6]. Хмарні обчислення сильно змінюють погляди на технології [1, 7], зокрема також на технології сховищ даних [7]. Сховища вміщують фіксовану кількість засобів збереження, з’єднаних мережею. Хмарними сховищами називають сховища, що засновані на хмарній інфраструктурі (інфраструктура, яка надається за потребою IaaS – Infrastructure as a Service). IaaS-інфраструктура дозволяє у разі необхідності тимчасово орендувати додаткові пристрої, не обмежуючись фіксованою кількістю пристроїв збереження та вивільняти пристрої, якщо в них немає необхідності. Зміна складу пристроїв збереження називається масштабуванням. Саме можливість масштабуватися відрізняє хмарні сховища від традиційних [7]. Відповідно пристрої, що додаються або видаляються зі сховища називаються масштабованими. Додавання чи видалення пристроїв повинне проходити підчас переконфігурації сховища. Задача міграції даних у масштабованому сховищі є частковим випадком задачі міграції, яка була сформульована в [7], як задача багатокритеріальної оптимізації часу міграції. Перший критерій задачі характеризувався оптимізацією часу міграції на масштабованих пристроях збереження, тобто оптимізацією часу масштабування; другий – оптимізацією часу міграції на решті пристроїв. Ефективне вирішення такої задачі дає можливість достатньо швидко масштабувати сховища даних, цим самим знижуючи вартість на оренду пристроїв збереження даних.

Література:

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

2. Golubchik L., Khanna S., Khuller S., Thurimella R. and Zhu A. Approximation Algorithmsfor Data Placement on Parallel Disks // Proc. of ACM-SIAM SODA, 2000.

3. Golubchik L., Khuller S., Kim Y.A., Shargorodskaya S., Wan Y. Data Migration on Parallel Disks: Algorithms and Evaluation // Algorithmica. – 2006. – №45(1). – P. 137–158.

4. Hall J., Hartline J., Karlin A., Saia J., Wilkes J. On Algorithms for Efcient Data Migration // ACM Symposium on Discrete Algorithms. – 2001. – P. 620–629.

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

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

7. Petrov D.L., Tatarinov Y. Data migration in the scalable storage cloud // IEEE, International Conference on Ultra Modern Telecommunications, ICUMT, St. Petersburg, 2009.