К. т. н. Казаков В. Г., к. т. н. Федосин С. А.
Мордовский государственный университет имени Н. П. Огарева, г . Саранск, Российская Федерация
РАЗРАБОТКА СИСТЕМЫ ДЕДУПЛИКАЦИИ С ПРИМЕНЕНИЕМ ГРУППИРОВКИ ИНДЕКСА ДАННЫХ
Технология дедупликации служит для снижения объема хранимых данных посредством удаления избыточных элементов в различных копиях. Представленная работа посвящена разработке технологии организации дедупликации при копировании данных, нацеленной на совместное использование пофайловой и различных вариантов блочной дедупликации для нахождения эффективного баланса снижения вычислительной нагрузки при сохранении достаточно высокого уровня дедупликации. Постоянно увеличивающийся научный интерес к данной технологии обусловлен, прежде всего, беспрецедентным ростом данных, и, как следствие, необходимостью повышения эффективности процессов хранения, обработки и защиты информации.
В целях повышения производительности процесса дедупликации разработан специализированный алгоритм группировки индексов, основанный на принципе объединения файлов в классы. Так, индекс размещения данных разработанной системы разбивается по уровням: индекс файлов, классов подобия и индекс блоков данных (рис. 1) [2]. Для каждого файла в системе создается запись в индексе, хранящая значение хеш-функции, ссылку на индекс блоков данных, где в случае, когда используется блочная дедупликация, хранится информация об имеющихся блоках с указанием хеш-значений. При использовании файловой дедупликации данные хранятся в едином блоке для обеспечения унификации работы системы и индекса размещения данных.
Ключевым элементом построения индекса блоков данных является применяемый принцип разбиения множества обрабатываемых файлов на классы. Так, в случае, когда логическое разделение блоков по файлам известно, предлагается применение группировки блоков по классам подобных файлов. При этом для оценки степени подобия используется индекс Жаккарда и обобщение теоремы Бродера [4]. Так, если S 1 и S 2 – два множества блоков двух файлов, H ( S 1 ) и H ( S 2 ) – хеш блоков, тогда:
Данное выражение показывает, что вероятность совпадения минимальных хеш-элементов множеств S 1 и S 2 равна индексу Жаккарда. Для возможности определения подобных файлов, информация о минимальном хеш-элементе хранится в файловом индексе. Имеющиеся исследования [3] показывают, что использование описанного выше подхода может быть использовано с высокой точность без необходимости применения техники перебора. Пример, изображенный на рис. 1 иллюстрирует частный случай размещения класса подобных файлов. Так, при появлении нового файла F i +1 , относящегося к классу C k дополнительного элемента в индексе классов не создается. Вместо этого, различающиеся блоки ( B n +4 на рисунке) помещаются в хранилище, а в индексе блоков добавляются необходимые ссылки. Для повышения производительности индекс файлов постоянно располагается в оперативной памяти, в то же время индексы блоков данных в целях обеспечения экономии памяти загружаются и остаются в кэше в зависимости от потребности системы.
Объединение индексов блоков в группы, которые с высокой вероятностью будут затребованы вместе, последовательно или с небольшим интервалом также позволяет увеличить производительность. Так, при поиске идентификатора нового блока выполняется пои ск в гр уппе предыдущего совпадения. В отличие от известного подхода [3], предложена схема, где разбиение по блокам является опциональным. Это обобщение позволяет реализовать гибридный подход, где в одном ряду может быть использовано как файловая, так и блочная дедупликация, в зависимости от работы заданных параметров.
Описанный в работе подход позволяет применять технологию дедупликации не только с использованием выделенных вычислительных серверных мощностей на крупных предприятиях, но и в бытовых персональных компьютерах и даже на мобильных устройствах. Для возможности проведения комплексного анализа характеристик эффективности дедупликации и производительности разработан прототип программной системы, средствами которой можно проводить исследование разных аспектов процессов резервного копирования и восстановления как на моделируемых, так и на реальных данных. В системе реализовано полное, инкрементное, дифференциальное и другие основные виды резервного копирования, предусмотрены возможности архивирования резервных копий, автоматизированное восстановление [1]. Важнейшим направлением дальнейшей работы является детальное экспериментальное исследование количественных характеристик эффективности предложенного способа.
Список использованных источников:
1. Казаков В. Г. Исследование эффективности и отказоустойчивости резервного копирования цифровых данных / В. Г. Казаков, С. А. Федосин, Д. П. Сидоров // Инфокоммуникационные технологии. – 2010. – Т. 8, № 4. – С. 13–19.
2. Казаков В. Г. Способ адаптивной дедупликации с применением многоуровневого индекса размещения копируемых блоков данных / В. Г. Казаков, С. А. Федосин // Фундаментальные исследования. – 2013. – № 8 (Ч. 6). – C. 1322–1325.
3. Bhagwat D. Extreme binning: scalable, parallel deduplication for chunk-based file backup / D. Bhagwat, K. Eshghi, D. Long, M. Lillibridge // In Proc. 17th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2009.
4. Broder A. Z. On the resemblance and containment of documents / A. Z. Broder // SEQUENCES ’97: Proceedings of the Compression and Complexity of Sequences 1997. –1997. – Р. 21–29.