АНАЛИЗ И ОЦЕНКА МИНИМАЛЬНОГО УРОВНЯ ПРЕФИКСНОГО
ДЕРЕВА В СИСТЕМЕ БЕСХЕШЕВОЙ ДЕДУПЛИКАЦИИ

Жуков Максим Андреевич, Афанасьев Дмитрий Борисович

doi:10.17586/2226-1494-2015-15-3-470-475

2015 , ТОМ 15, НОМЕР 3 ( май-июнь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2015-15-3-470-475

УДК 004.627

АНАЛИЗ И ОЦЕНКА МИНИМАЛЬНОГО УРОВНЯ ПРЕФИКСНОГО ДЕРЕВА В СИСТЕМЕ БЕСХЕШЕВОЙ ДЕДУПЛИКАЦИИ

Жуков М.А., Афанасьев Д.Б.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования: Жуков М.А., Афанасьев Д.Б. Анализ и оценка минимального уровня префиксного дерева в системе бесхешевой дедупликации // Научно-технический вестник информационных технологий, механики и оптики. 2015. Т. 15. № 3. С. 470–475.

Аннотация

Предмет исследования. Предложен метод ограничения минимального уровня префиксного дерева в системе бесхешевой дедупликации данных.

Метод. Сущность предлагаемого метода заключается в принудительном заполнении префиксного дерева до определенного минимального уровня. Использование предлагаемого метода позволяет снизить количество коллизий на нижних уровнях префиксного дерева. Максимальный теоретический прирост производительности соответствует доле коллизий от общего количества операций чтения данных с носителя. Применение метода ограничения минимального уровня префиксного дерева увеличивает объем метаданных на объем новых структур, содержащих один элемент. Основные результаты. Результаты работы подтверждены данными вычислительного эксперимента бесхешевой дедупликации на наборе данных объемом 528 ГБ. Анализ процесса показал, что 99% времени выполнения занимает позиционирование головок жестких дисков. Причиной этого является распределение блоков на носителе в случайном порядке. На экспериментальном наборе данных применение метода ограничения минимального уровня префиксного дерева может увеличить производительность на 16%, а возрастание объема метаданных составит 49%. Общий объем метаданных будет меньше на 34%, чем при применении метода хешевой дедупликации с использованием алгоритма MD5 и на 17% меньше, чем c использованием алгоритма Tiger192. Полученные результаты подтверждают эффективность предложенного метода. Практическая значимость. Предложенный метод позволяет увеличить производительность процесса за счет сокращения количества коллизий при построении префиксного дерева. Результаты представляют практическую значимость для специалистов, занимающихся разработкой системы бесхешевой дедупликации данных.

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

Список литературы

1. Щербинин А. Решения по дедупликации данных // Storage News. 2008. № 2 (35). С. 2–7.

2. Черняк Л. Просто о сложностях дедупликации // Открытые системы. СУБД. 2013. № 3. С. 54–55.

3. Meyer D.T, Bolosky W.J. A study of practical deduplication // ACM Transactions on Storage. 2012. V. 7. N 4. Art. 14. doi: 10.1145/2078861.2078864

4. Meister D. Advanced Data Deduplication Techniques and their Application, PhD dissertation. Mainz, Johannes Gutenberg University, 2013. 230 p.

5. Bhagwat D., Eshghi K., Long D.D.E., Lillibridge M. Extreme binning: scalable, parallel deduplication for chunk-based file backup // Proc. 17th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS). London, UK, 2009. P. 237–245. doi: 10.1109/MASCOT.2009.5366623

6. Казаков В.Г., Федосин С.А., Плотникова Н.П. Способ адаптивной дедупликации с применением многоуровневого индекса размещения копируемых блоков данных // Фундаментальные исследования. 2013. № 8–6. С. 1322–1325.

7. Maddodi S., Attigeri G.V., Karunakar A.K. Data deduplication techniques and analysis // Proc. 3rd Int. Conf. on Emerging Trends in Engineering and Technology (ICETET 2010). Goa, India, 2010. P. 664–668. doi: 10.1109/ICETET.2010.42

8. Orlando K., Bautista M.M., Mejia J.R.M., Langnor R.G. IBM ProtecTIER Implementation and Best Practices Guide. IBM Redbooks, 2014. 578 p.

9. Biplob D., Sudipta S., Jin L. ChunkStash: speeding up inline storage deduplication using flash memory // Proc. 2010 USENIX Annual Technical Conference. 2010. P. 16.

10. Osuna A., Balogh E., Galante de Carvalho R.A., Javier R.F., Mann Z. Implementing IBM Storage Data Deduplication Solutions. IBM Redbooks, 2011. 322 p.

11. Sheu R.-K., Yuan S.-M., Lo W.-T., Ku C.-I. Design and implementation of file deduplication framework on HDFS // International Journal of Distributed Sensor Networks. 2014. V. 2014. Art. 561340. doi: 10.1155/2014/561340

12. Srinivasan K., Bisson T., Goodson G., Voruganti K. iDedup: latency-aware, inline data deduplication for primary storage // Proc. 10th USENIX Conference on File and Storage Technologies (FAST 2012). San Jose, USA, 2012. P. 299–312.

13. Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск. 2 изд. М.: Вильямс, 2001. 824 с.

14. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2000. 382 с.

15. Жуков М.А., Афанасьев Д.Б. Верификация блоков данных в системе бесхешевой дедупликации // Сб. тезисов докладов II конгресса молодых ученых. Вып. 1. СПб.: НИУ ИТМО, 2013. С. 78.

16. Жуков М.А., Афанасьев Д.Б. Хранение метаданных блоков в структуре данных префиксного дерева // Сборник трудов молодых ученых и сотрудников кафедры ВТ. Вып. 5. СПб.: НИУ ИТМО, 2014. C. 12–15.

17. Жуков М.А., Афанасьев Д.Б. Порядок построения префиксного дерева в системе бесхешевой дедупликации // Труды XXI Всероссийской научно-методической конференции Телематика'2014. Санкт-Петербург, 2014. C. 89.

18. Жуков М.А. Настройка параметров дедупликации // Сборник тезисов докладов конгресса молодых ученых. Вып. 1. Санкт-Петербург, 2012. C. 58.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License