самый быстрый способ создания контрольной суммы для больших файлов в Python - PullRequest
6 голосов
/ 07 октября 2009

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

почему-то я не могу заставить zlib.crc32 и zlib.adler32 работать с файлами размером более 4 ГБ на 64-битной машине с Windows XP Pro. я подозреваю, что я достиг ограничения в 32 бита здесь? используя hashlib.md5 я мог бы получить результат, но проблема в скорости. создание файла md5 для файла 4.8 ГБ занимает около 5 минут. Диспетчер задач показывает, что процесс использует только одно ядро.

мои вопросы:

  1. есть ли способ заставить crc работать с большими файлами? я предпочитаю использовать crc, чем md5
  2. если нет, то есть ли способ ускорить md5.hexdigest () / md5.digest? или в этом случае любой hashlib hexdigest / digest? может быть, разделив его на многопоточный процесс? как мне это сделать?

PS: я работаю над чем-то похожим на систему управления активами, вроде svn, но ресурс состоит из больших сжатых файлов изображений. файлы имеют небольшие изменения. хеширование / контрольная сумма необходима для обнаружения изменений и обнаружения ошибок.

Ответы [ 6 ]

4 голосов
/ 07 октября 2009

Это проблема выбора алгоритма , а не проблема выбора библиотеки / языка!

Похоже, что нужно учитывать в первую очередь два момента:

  • на сколько дисковый ввод-вывод повлияет на общую производительность?
  • какова ожидаемая надежность обнаружения ошибки функция?

По-видимому, ответ на второй вопрос - что-то вроде ' допускается несколько ложных отрицательных значений ', поскольку надежность любого 32-битного хеша относительно сообщения 4 Гбит даже в умеренно шумный канал, не собирается быть практически абсолютным.

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

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

Примечание: Alder32 не ограничен размерами сообщений ниже определенного порога. Это может быть просто предел API zlib. (Кстати, ссылка, которую я нашел о zlib.adler32, использовала буфер, и хорошо ... такого подхода следует избегать в контексте наших огромных сообщений в пользу потоковых процессов: немного прочитать из файла, вычислить, повторить. .)

2 голосов
/ 07 октября 2009

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

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

Что касается самого алгоритма хеширования, основной компромисс между скоростью и отсутствием коллизий (два разных блока данных дают один и тот же хеш). CRC-32 работает быстро, но только с 2 ^ 32 уникальными значениями можно увидеть столкновения. MD5 намного медленнее, но имеет 2 ^ 128 уникальных значений, поэтому столкновения почти никогда не будут видны (но все еще теоретически возможны). Большие хэши (SHA1, SHA256, ...) имеют еще более уникальные значения, но все еще медленнее: я сомневаюсь, что они вам нужны: вы беспокоитесь о случайных коллизиях, в отличие от приложений цифровой подписи, где вы беспокоитесь о намеренно ( необычно) инженерные столкновения.

Похоже, вы пытаетесь сделать что-то очень похожее на то, что делает утилита rsync. Вы можете просто использовать rsync?

1 голос
/ 09 октября 2009

Возможно, вы устанавливаете ограничение на размер файлов в XP. 64-разрядная версия дает вам больше адресного пространства (удаляя 2 ГБ (или около того) адресного пространства на приложение), но, вероятно, ничего не делает для проблемы размера файла.

0 голосов
/ 07 октября 2009

Вы пробовали модуль crc-generator ?

0 голосов
/ 07 октября 2009

md5 не может работать параллельно. Однако вы можете md5 файл в разделах (параллельно) и взять md5 из списка хэшей.

Однако это предполагает, что хеширование не ограничено IO, что я подозреваю. Как предполагает Антон Гоголев - убедитесь, что вы читаете файл эффективно (большими блоками степени 2). После этого убедитесь, что файл не фрагментирован.

Также для новых проектов должен быть выбран хеш, такой как sha256, а не md5.

Контрольные суммы zlib намного быстрее, чем md5 для файлов 4Gb?

0 голосов
/ 07 октября 2009

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

Тот факт, что обработка большого файла занимает так много времени, может быть вызвана «небуферизованным» чтением. Попробуйте прочитать, скажем, 16 Кбайт за раз, а затем передать контент кусками в функцию хеширования.

...