Алгоритм эффективного разложения огромных файлов

Question

Я должен хранить два файла A и B, которые оба очень большие (например, 100 ГБ). Однако B, вероятно, будет в значительной степени похож на A, поэтому я мог бы хранить A и diff (A, B). У этой проблемы есть два интересных аспекта:

1. Файлы слишком велики, чтобы их можно было проанализировать с помощью любой библиотеки различий, которую я знаю, потому что они находятся в памяти
2. Мне на самом деле не нужен diff - diff обычно имеет вставки, редактирует и удаляет, потому что он предназначен для чтения людьми. Я могу получить меньше информации: мне нужны только «новый диапазон байтов» и «скопировать байты из старого файла с произвольным смещением».

В настоящее время я в растерянности от того, как вычислить дельту от A до B при этих условиях. Кто-нибудь знает алгоритм для этого?

Опять же, проблема проста: напишите алгоритм, который может хранить файлы A и B с как можно меньшим количеством байтов, учитывая тот факт, что оба они очень похожи.

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

Answer 1

Вы можете использовать rdiff, который очень хорошо работает с большими файлами.Здесь я создаю разность двух больших файлов A и B:

1. Создание подписи одного файла, например,

   rdiff signature A sig.txt
   

2. используя созданный файл подписи sig.txt и другой большой файл, создайте дельту:

   rdiff delta sig.txt B delta
   

3. сейчас delta содержит всю информацию, необходимую для воссоздания файла B когда у вас есть A и delta.Чтобы воссоздать B, запустите

   rdiff patch A delta B
   

В Ubuntu просто запустите sudo apt-get install rdiff, чтобы установить его.Это довольно быстро, я получаю около 40 МБ в секунду на моем компьютере.Я только что попробовал это на файле 8 ГБ, и память, используемая rsync, была около 1 МБ.

Answer 2

Взгляните на алгоритм RSYNC, поскольку он в значительной степени предназначен именно для этого и позволяет эффективно копировать дельты. И алгоритм, как я помню, довольно хорошо документирован.

Answer 3

Именно эта проблема известна как «дедупликация данных» . Наиболее часто используемый подход:

• Прочитать файлы в блоках:
  • Разделить данные так называемых "кусков". Наиболее часто используемый подход называется «Определение содержания по частям с использованием метода снятия отпечатков Рабина» ( Код ). Использование такого подхода к фрагментации приводит к лучшей дедупликации для большинства наборов данных, чем использование фрагментов статического размера (например, показано здесь ).
  • Отпечатайте отпечатки пальцев с помощью криптографического метода снятия отпечатков, например, SHA-256.
  • Сохранение отпечатков пальцев в индексе и поиск для каждого фрагмента, если отпечаток уже известен. Если отпечаток пальца известен, нет необходимости хранить фрагмент во второй раз. Только когда отпечаток пальца неизвестен, данные должны быть сохранены.

Такой алгоритм дедупликации данных не так точен, как, например, xdelta , но он быстрее и более масштабируем для больших наборов данных. Чанкинг и дактилоскопия выполняются со скоростью около 50 МБ / с на ядро ​​(Java). Размер индекса зависит от избыточности, размера чанка и размера данных. Для 200 ГБ он должен уместиться в памяти для блоков размером, например 16KB.

Bentleys и Mciloys подход сжатия очень похож (используется, например, Googles BigTable), однако мне не известны какие-либо готовые инструменты командной строки, использующие технику сжатия.

"fs-c" проект с открытым исходным кодом содержит большую часть необходимого кода. Однако сам fs-c пытается измерять избыточность и анализируемые файлы в памяти или с помощью кластера Hadoop .

Answer 4

вопрос в том, каков размер записи в ваших файлах, т. Е. Могут ли смещения изменяться побайтно или файлы состоят, скажем, из блоков 1024B. Предполагая, что данные ориентированы на байты, вы можете сделать следующее:

1. Создание массива суффиксов для файла A. Этот массив представляет собой перестановку всех значений индекса в файле A. Если A имеет 2 ^ 37 байтов, то массив индекса проще всего представить 64-разрядными целыми числами, поэтому каждый байт (смещение к файлу) соответствует 8 байтам в массиве индекса, поэтому тогда индексный массив будет иметь длину 2 ^ 40 байт. Например. 800 Гб, скажем. Вы также можете индексировать только каждое 1024-е место, скажем, чтобы уменьшить размер индексного массива. Это затем снижает качество упаковки в зависимости от того, как долго работают средние партии копируемых фрагментов.

2. Теперь, чтобы жадно упаковать файл B, вы начинаете с его начала со смещением o = 0, а затем используете массив индексов, чтобы найти самое длинное совпадение в A, которое соответствует данным, начинающимся с 'o'. Вы выводите пару в упакованном файле. В вашем случае это занимает без кодирования 16 байтов, поэтому, если пробег составляет <16 байтов, вы фактически теряете пространство. Это можно легко исправить, используя затем кодирование на уровне битов и используя битовый маркер, чтобы отметить, кодируете ли вы изолированный байт (маркер + 8 бит = 9 бит) или пару смещение / длина (маркер + 40 бит + 40 бит = 81 биты), скажем. После упаковки самого длинного фрагмента в o увеличьте o до следующего байта после фрагмента и повторяйте до конца файла. </p>

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

Answer 5

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

Если вам нужно произвольное выравнивание байтов и вы действительно заботитесь о производительности, посмотрите на алгоритм simhash и используйте его для поиска похожих, но не выровненных блоков.