Тема: Исследование возможности сжатия хеш-значений при дедупликации данных

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

В данной работе была рассмотрена задача сжатия хеш-значений в процессе
дедупликации. В ходе решения данной задачи были произведены следующие работы:
Изучение литературы по алгоритмам хеширования и компрессии;
Разработка структуры данных для дедупликации, которая позволит хранить
хеш-таблицу к более компактному виду;
Разработка программного кода и проведение экспериментов на его основе;
Сравнение результатов для разных алгоритмов сжатия;
Результаты эксперимента (параграф 7) показывают, что уменьшение затрат на
хранение таких метаданных, как хеш-значения и идентификаторов блоков, действительно
возможно, и умеренно увеличивает время процесса дедупликации.
В качестве продолжения работы можно предложить реализацию, в которой при
переполнении имеющейся in-memory базы данных, часть хеш-значений отправляется во
вторичную память.
Купить