Регулярное резервное копирование является обычной практикой для защиты от аппаратных сбоев и ошибок пользователей. Сжатие данных перед передачей может помочь существенно увеличить пропускную способность[1]. Действенным методом для эффективного уменьшения передаваемых данных является дедупликация[2].
Дедупликация - это метод сжатия массива данных, при котором находятся и удаляются дубликаты данных. Сначала данные разбиваются на блоки, по которым считаются хеш-значения, а затем эти хеш-значения сравниваются, и только при совпадении уже сравниваются сами блоки данных.
В процессе дедупликации генерируется большой массив хеш-значений. Например, для блоков по 4 Кб на 4 Тб данных потребуется 8 Гб памяти только для хеш-значений (если брать алгоритм, в котором 1 хеш занимает 8 байт). Кроме того, требуется память для хранения идентификаторов блоков и других метаданных.
Одной из стадий дедупликации является сравнение полученных хеш-значений с теми, которые уже хранятся в базе данных. Для ускорения процесса сравнения можно хранить список хешей в in-memory базе данных. Но такой способ подходит не для всех хранилищ, т.к. размер in-memory баз данных намного меньше обычных. Поэтому для расширения границ ее использования можно применить сжатие к хеш-значениям перед хранением.
В данной работе была рассмотрена задача сжатия хеш-значений в процессе дедупликации. В ходе решения данной задачи были произведены следующие работы:
• Изучение литературы по алгоритмам хеширования и компрессии;
• Разработка структуры данных для дедупликации, которая позволит хранить хеш-таблицу к более компактному виду;
• Разработка программного кода и проведение экспериментов на его основе;
• Сравнение результатов для разных алгоритмов сжатия;
Результаты эксперимента (параграф 7) показывают, что уменьшение затрат на хранение таких метаданных, как хеш-значения и идентификаторов блоков, действительно возможно, и умеренно увеличивает время процесса дедупликации.
В качестве продолжения работы можно предложить реализацию, в которой при переполнении имеющейся in-memory базы данных, часть хеш-значений отправляется во вторичную память.
