Метод удаления дубликатов в деле

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

Создание бэкапов ваших данных
Что может быть проще, чем создание резервной копии данных? Обычно вы просто копируете ваши данные на какой-нибудь надежный и защищенный сервер — и готово. Но на следующий день вы делаете небольшое изменение в вашем документе или файле данных и хотите снова сделать бэкап. Ну что ж, можно просто перезаписать вашу копию, заменив все файлы. Но что тогда насчет предыдущей версии ваших данных? Вы ведь не хотите просто так потерять историю ваших данных. Вы можете сравнить ваши файлы, найти изменившиеся и таким образом поддерживать историю данных. Таким образом, все сводится к тому, как вы определяете изменения в ваших файлах и сравниваете их.

Как определить, что изменилось со времени прошлого бэкапа?
Побайтовое сравнение содержимого файлов работает слишком медленно, особенно при больших размерах файлов. Нам нужно что-то типа «отпечатка пальцев», чтобы мы могли быстро сказать, идентичны файлы или нет. Отпечаток пальцев (или идентификатор) обычно реализуется как хэш функция (md5, sha256 и др). Бэкап с исключением повторных файлов намного более эффективен, чем бэкап в виде простой копии. Но это по-прежнему слабый метод в случае, когда огромные файлы размером в несколько гигабайт претерпевают изменение в 1 байте. В этом случае мы обнаружим это изменение и с радостью забэкапим целиком новую версию. Есть ли способ улучшить этот метод?

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

Как работает метод удаления дубликатов
Блоки идентифицируются и сравниваются с помощью этих идентификаторов.

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

Случаи модификации данных
Так как же модифицируются данные? Существуют три основных вида модификации данных: вставка, обновление, удаление. Любая модификация данных может быть представлена как последовательность этих основных действий.

Обновление — это простейший вид модификации. Когда мы обрабатываем обновление и данные у нас разделены на блоки, то границы блока не изменяются. Поэтому мы можем легко обнаружить и заменить измененный блок данных.
Но если некоторый кусок данных был удален или добавлен в блок то границы блоков могут измениться и нам придется рассматривать все последующие блоки как измененные, в то время как на самом деле они совсем не изменились, а всего лишь немного сдвинулись. Как же обнаружить этот сдвиг?

Идея плавающего окна для определения границ блока
Все, что нам нужно для определения передвигающихся границ (сдвиг границ блока в результате операций удаления/вставки) — это попробовать идентифицировать блоки со всеми смещениями от 0 до размера блока (не включительно). Так мы найдем начало следующего блока, иначе, если попробуем все смещения из диапазона и ничего не найдем, это будет означать, что был вставлен целый новый блок.

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

Улучшение производительности использованием кольцевого хэширования
Производительность определения вставленных/удаленных данных с помощью плавающего окна основывается на производительности вычисления идентификатора для данного блока со смещением A и длиной N. В общем, мы имеем дело с вычислением хэш функции с O(N) операциями. Так как нам нужно посчитать идентификаторы для всех смещений с 0 до N, то производительность плавающего окна уменьшается до O(N^2), а это уже не практично для блоков большого размера. Все, что нам нужно — это каким-то образом получить преимущество подсчета хэш функции для смещения A + 1 за счет того, что мы уже посчитали хэш функцию для смещения A. К счастью, существует хэш функция кольцевого хэширования Adler32, которая нам в этом поможет. Таким образом, мы можем поддерживать плавающее окно с сложностью O(N) и блоки большого размера.

Коллизии
Давайте посчитаем вероятность коллизии. Предположим, что мы можем хранить N блоков в нашем хранилище, и используем B битов в хэшкоде. Вероятность коллизии в нашем хранилище — это вероятность единичной коллизии 1/2^B , умноженная на количество пар блоков N*(N-1)/2
P=N*(N-1)/2^(B+1)
Для 1Tb данных и блоков размером 32К у нас будет 2^40/2^15=2^25 блоков, то есть N=2^25
P=2^25(2^25-1)/2^257~1/2^207~10^-63
Мы потеряем 32Kb из 1TB с вероятностью 10^-69. Это чрезвычайно редкая ситуация. Получается, что если вы будете делать бэкапы 100 PB данных на протяжении миллиона лет, у вас не будет даже одного шанса на миллиард потерять что-нибудь из-за коллизии.

Удаление дубликатов против ZIP сжатия
Используя все вышеперечисленные идеи, я создал утилиту удаления дубликатов, которая удаляет дубликаты во всех файлах заданной папки и всех ее подпапках. Для анализа результатов удаления дубликатов я провел две серии тестов.
Я взял один наш проект со всеми исходниками, бинарными файлами и метаданными SCM (мы используем Mercurial). Удаление дубликатов было проведено для трёх снимков нашего проекта с перерывом в 1 месяц, и один раз для всех снимков вместе. Результаты были сравнены с ZIP сжатием с максимальными настройками сжатия. Сравнение приведено в таблице:

Эксперимент показывает, что использование технологии удаления дубликатов превосходит архивирование данных.
Надеюсь, этот пост будет полезным тем, кто собирается построить большое масштабируемое хранилище данных и задумывается насчет технологии удаления дубликатов.

---
Мы в твиттере @AtomM_CMS
Группа во вконтакте AtomM_CMS