Ответ 1
Взгляните на алгоритм RSYNCs, так как он разработан в значительной степени, чтобы сделать именно это, чтобы он мог эффективно копировать дельта. И, как я помню, алгоритм довольно хорошо документирован.
Мне нужно хранить два файла A и B, которые являются очень большими (например, 100 ГБ). Однако B скорее всего будет похож на большие части на A, чтобы я мог хранить A и diff (A, B). Есть два интересных аспекта этой проблемы:
В настоящее время я не понимаю, как вычислить дельта от А до В в этих условиях. Кто-нибудь знает об этом алгоритме?
Опять же, проблема проста: напишите алгоритм, который может хранить файлы A и B с максимально возможным количеством байтов, учитывая тот факт, что оба они очень похожи.
Дополнительная информация: Хотя большие части могут быть идентичными, они, вероятно, будут иметь разные смещения и быть не в порядке. Последний факт заключается в том, почему обычный diff может не сэкономить.
Взгляните на алгоритм RSYNCs, так как он разработан в значительной степени, чтобы сделать именно это, чтобы он мог эффективно копировать дельта. И, как я помню, алгоритм довольно хорошо документирован.
Вы можете использовать rdiff
, который отлично работает с большими файлами. Здесь я создаю diff двух больших файлов A
и B
:
Создайте подпись одного файла, например,
rdiff signature A sig.txt
используя сгенерированный файл подписи sig.txt
и другой большой файл, создайте delta:
rdiff delta sig.txt B delta
теперь delta
содержит всю информацию, необходимую для воссоздания файла B
, когда у вас есть как A
, так и delta
. Чтобы воссоздать B, запустите
rdiff patch A delta B
В Ubuntu просто запустите sudo apt-get install rdiff
, чтобы установить его. Это довольно быстро, я получаю около 40 МБ в секунду на моем ПК. Я только что попробовал его в файле размером 8 ГБ, а память, используемая rsync, была около 1 МБ.
Это точно проблема, называемая "дедупликация данных" . Наиболее часто используемый подход:
Такой алгоритм дедупликации данных не такой точный, как, например, xdelta, но он более быстрый и масштабируемый для больших наборов данных. Блокировка и отпечатки пальцев выполняются со скоростью около 50 МБ/с на ядро (Java). Размер индекса зависит от избыточности, размера блока и размера данных. Для 200 ГБ он должен соответствовать памяти для размеров блоков, например. 16KB.
Метод сжатия Bentleys и Mciloys очень схож (используется, например, Googles BigTable), однако я не знаю ни одного из box с помощью техники сжатия.
Проект "fs-c" с открытым исходным кодом содержит большую часть необходимого кода. Однако сам fs-c пытается только измерить избыточность и аналитические файлы в памяти или использовать кластер Hadoop.
возникает вопрос, каков размер записи в ваших файлах, т.е. могут ли смещения изменять байты по байтам или делать файлы, состоящие, например, из блоков 1024B. Предполагая, что данные байт-ориентированы, вы можете сделать следующее:
Создайте массив суффиксов для файла A. Этот массив является перестановкой всех значений индекса в файл A. Если A имеет 2 ^ 37 байт, тогда индексный массив проще всего представить в виде 64-битных целых чисел, поэтому каждый байт (смещение к файлу) соответствует 8 байтам в массиве индексов, поэтому тогда массив индексов будет 2 ^ 40 байтов. Например. 800 ГБ, скажем. Вы также можете индексировать только каждое 1024-е место, скажем, для уменьшения размера массива индексов. Это затем сглаживает качество упаковки в зависимости от того, как долго средние пробеги копируемых фрагментов.
Теперь, чтобы жадно упаковать файл B, вы начинаете с его начала со смещения o = 0, а затем используете массив индексов, чтобы найти самое длинное совпадение в A, которое соответствует данным, начинающимся с 'o'. Вы выводите пару в упакованном файле. Это занимает в вашем случае без кодирования 16 байтов, поэтому, если пробег равен < 16 байт вы фактически теряете пространство. Это можно легко исправить, используя затем кодирование на уровне бит и используя бит-маркер, чтобы указать, кодируете ли вы изолированный байт (маркер + 8 бит = 9 бит) или пар смещения/длины (маркер + 40 бит + 40 бит = 81 бит), скажем. После упаковки самого длинного фрагмента в точке o увеличьте o до следующего байта после фрагмента и повторите до конца файла.
Конструкция и использование массива суффиксов легки, и вы должны найти ссылки легко. В высокоскоростных приложениях вместо этого используются суффикс-деревья или суффикс-попытки, которые сложнее манипулировать, но обеспечивают быстрый поиск. В вашем случае у вас будет массив на вторичном хранилище, и если скорость выполнения фаз упаковки не является проблемой, массив суффиксов должен быть достаточным.
В зависимости от ваших требований к производительности вы можете избавиться от выборки фрагментов, которые вы отпечатываете, и выращивать их, когда они совпадают. Таким образом, вам не нужно запускать контрольную сумму для всего вашего большого файла.
Если вам нужны произвольные байтовые выравнивания, и вы действительно заботитесь о производительности, посмотрите simhash алгоритм, и используйте его для поиска похожих, но не выровненных блоков.