Итак, в текстовый файл мы записали фразу “deduplication technologies are becoming more an more important now.” и прогнали по ней два алгоритма дедупликации: один с фиксированным размером блока (для простоты взят размер в 8 символов), а другой с изменяющимся. Получаем такой расклад:
Ох ты, а в тексте-то ошибка. :( Надо срочно ее исправить и дописать букву "d" в слово "end". Однако, это приведет к тому, что весь последующий текст сдвинется на один символ. Соответственно, это приведет к изменению 4 блоков фиксированного размера.
А вот в случае динамически изменяющихся размеров, "пострадает" только 1 блок. Количество информации, которое необходимо записать на хранилище в этом случае значительно меньше. Сочетая такие алгоритмы с методом дедупликации на клиенте, мы, к тому же, заметно разгружаем сеть передачи данных.
EMC Avamar использует дедупликацию на клиенте блоками изменяющегося размера. Алгоритм называется “sticky byte factoring”. Размер блока динамически вычисляется по предетерменированным паттернам данных и может варьироваться от 1byte до 64Kbyte (в среднем 24Kbyte). Для вычисления хэш-сумм (их там несколько типов: атомарные для каждого блока, композитные для групп блоков и корневые для всего объекта) используется специальная катящаяся (rolling) хэш-функция. Не смотря на то, что на ее вход поступают данные различного размера, результат ее работы (хэш-сумма) всегда имеет фиксированную длину 20byte. В общем, лихо закручен сюжет, я в подробностях даже не пытался разобраться... может вы попробуете? ;) здесь кое-что есть для затравки...
Комментариев нет:
Отправить комментарий
Примечание. Отправлять комментарии могут только участники этого блога.