Обзор алгоритмов content-defined chunking (CDC)

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

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

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

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