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

Ответ 1

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

Ответ 2

Вы можете использовать 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 МБ.

Ответ 3

Это точно проблема, называемая "дедупликация данных" . Наиболее часто используемый подход:

• Прочитайте файлы в блоках:
  • Разделите данные так называемых "кусков". Наиболее часто используемый подход называется "Определенный контентом Chunking с использованием метода Fingerprinting Rabins" (Code). Использование этого подхода chunking приводит к лучшей дедупликации в большинстве наборов данных, а затем использует куски статического размера (например, показано здесь).
  • Отпечаток фрагментов с использованием криптографического метода отпечатка пальца, например. SHA-256.
  • Сохраните отпечатки пальцев в индексе и найдите каждый фрагмент, если отпечаток уже известен. Если отпечаток известен, нет необходимости хранить кусок второй раз. Данные, хранящиеся в памяти, должны сохраняться только тогда, когда отпечаток неизвестен.

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

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

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

Ответ 4

возникает вопрос, каков размер записи в ваших файлах, т.е. могут ли смещения изменять байты по байтам или делать файлы, состоящие, например, из блоков 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 до следующего байта после фрагмента и повторите до конца файла.

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

Ответ 5

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

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