Какие проблемы решает алгоритм FastCDC при дедупликации данных

FastCDC — это алгоритм разбиения данных на блоки переменной длины (Content Defined Chunking, CDC). В отличие от нарезки с фиксированной длиной блока, FastCDC решает проблему смещения границ (boundary-shift problem), которая возникает при вставке новых данных в файл. Например, если в начало файла добавить байт, то при использовании разбиения с фиксированной длиной все последующие блоки изменятся.

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

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

Основная идея FastCDC заключается в следующем: среди всех возможных последовательностей байтов (множество A) выделяется подмножество B. Когда в файле обнаруживается последовательность из множества B, алгоритм устанавливает границу блока (anchor) сразу после этой последовательности.

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

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

Добавление всего одного нового байта 0 сдвигает все предыдущие байты вправо, что приводит к изменению содержимого каждого блока:

Эксперт по разработке ПО отдела систем обработки данных в YADRO Ростислав Ефремов в статье подробно объяснил, что такое дедупликация данных, какую роль она играет в системах резервного копирования и как работает в СХД TATLIN.BACKUP