Данная статья является продолжением моей предудущей статьи,где была представлена и разьяснена технология дедупликации. В отличии от предыдущей статья, задачей данной работы является экспериментальное исследование зависимости параметров процесса дедупликации (от используемых хэш-функций и размера блока данных) . 

Основными целями работы являются:

1. исследование зависимости коэффициента дедупликации от размера блока дедуплицируемых данных;
2. исследование зависимости времени процесса дедупликации от используемых хеш-функций и размера блока данных;
3. обнаружение коллизий в процессе дудупликации и способы уменьшения вероятности их возникновения.

Следует отметить, что параметры дедупликации задаются опираясь на эмпирические предположения, по причине отсутствия вырабатанной методологии по этой технологии.

Средства исследования :

Для экспериментального исследования было написано приложение для анализа эффективности использования дедупликации.

Принцип работы приложения:

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

Для процесса хеширования мною были использованны хэш-функции использующие алгоритмы MD5, SHA-256, SHA-512, SHA-1. 
Для уменьшения вероятности возникновения коллизии были использованы помимо одиночных алгоритмов, комбинации алгоритмов хеширования.
При использовании комбинаций алгоритмов, мы можем отловить коллизию в случае если результаты на запрос о наличие\отсутствии хеша в базе будут отличаться у двух функций используемых в данной комбинации хэш-функций. Полностью мы не избавляемся от возникновения коллизий, но таким образом мы снижаем вероятность возникновения коллизии.

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

В качестве хранилища хешей используется хранение в памяти посредством структуры данных Java - ConcurrentHashMap

Оценка производительности по времени осуществляется посредством вычисления времени выполнения начиная с создания и выполнения потоков процесса дедупликации (чтение очередного блока данных,вычисление хеша(хешей), запись хеша в место хранения) до их завершения. 

В качестве минимального размера блока был выбран размер сектора (512 байт), ввиду того, что операции чтения\записи происходят именно секторами. В качестве верхней границы был выбран 1 мегабайт, из предположения о достаточно низком коэффициенте дедупликации на таких, относительно больших, размерах блока.

Исходные данные :

Так как дедупликация является технологией находящее все более и более широкое и повседневное применение, в качестве набора исходных данных был взят набор образов трех виртуальных машин с развернутыми на них службами и данными ( в частности на одном из них живет drupal ).
 

Совокупный объем данных представляемый 3 образами ~ 17.2Gb (точный размер 17631364 байт)

Нужно выявить информацию, которая будет являться важной в рамках данного исследования:

• объем входных данных
• объем выходных данных
• Размер блока данных
• Наличие ошибок при хешировании
• Время выполнения

Ниже приведена таблица результатов полученная на данном наборе данных
 

Условные обозначения
BS - BlockSize - размер блока данных
HA - HashAlgoritm - алгоритм( алгоритмы) хеширования
BR - BlocksRead - количество считанных блоков
BD - BlocksDedupl - количество уникальных блоков
TR - TimeRead - время чтения данных
TD - TimeDedup - время дедупликации
TA - TimeAll - общее время выполнени
SO - SizeOutput - количество дедуплицированных данных
K - Коэффицент дедупликации

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

Сводная таблица полученных данных :

По данному графику можно увидеть две важные зависимости : зависимость коэффицента дедупликации от размера блока и время выполнения дедупликации от размера блока.

Мы можем наблюдать уменьшение коэффицента дедупликации с увеличением размера блока. Данная зависимость достаточно очевидна.
По графику времени выполнения от размера блока видно, что в момент скачка ( размер блока 8 кб) настает момент когда время вычисления хеш-функции  увеличивается быстрее, чем уменьшается количество блоков. 

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

Причина проседания графика времени выполнения обьяснена выше.
 

Выводы :

Наиболее благоприятный интервал выбора блока : 512 байт — 2 килобайта . Данный интервал выбран ввиду наиболее благоприятного отношения коэффицента дедупликации и времени выполнения процесса, обеспечивающего эффективную экономию свободного пространства за приемлемое время.