Обзор алгоритмов similarity based chunking (SBC)

Системы хранения данных бывают разных типов, в частности, это могут быть хранилища резервных копий. Подобные хранилища отличаются высокой плотностью хранения данных за счет сжатия и дедупликации. Основная идея дедупликации заключается в том, что входной набор данных разделяется системой на блоки и для каждого блока вычисляется подпись. Блок с уникальной подписью сохраняется в базу данных. Если в системе уже имеется некоторая подпись, то новый блок с такой подписью не сохраняется. На таких подписях в similarity based chunking определяется метрика, позволяющая оценить похожесть блоков.

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

• выполнение обзора основных алгоритмов разделения данных на блоки и вычисления similarity hash;
• проведение сравнения рассмотренных алгоритмов по объему используемой памяти, скорости работы на одном ядре и коэффициенту дедупликации;
• исследование возможности оптимизации алгоритмов за счет применения векторизации и/или распараллеливания;
• разработка оптимизированного алгоритма и анализ его производительности.

Более подробная информация по проекту тут.