Отслеживание уникальных версий файлов с хешами

Question

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

Однако вот мой вопрос - Могу ли я избежать коллизий, если я хэширую файл двумя разными методами и сохраняю оба хэша (скажем, SHA1 и MD5) или если я выберу один более длинный хеш ( как SHA256) и полагаться только на это? Я знаю, что вариант 1 имеет 288 битов хеша, а вариант 2 имеет только 256, но предположим, что мои два варианта имеют одинаковую общую длину хеша.

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

Answer 1

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

Один урокЯ научился играть с огромным количеством файлов, и хэширование таково: добавление миллионов записей в базу данных PostgreSQL за один раз не очень быстро.Когда я писал программу для хеширования одного миллиона файлов и сохранения их в базе данных PostgreSQL, база данных часто была узким местом.Я не пробовал MySQL, но полагаю, он примерно такой же.SQLite, вероятно, намного быстрее, так как нет затрат на клиент / сервер.Я рекомендую сначала попробовать SQLite.Это может быть слишком медленно.

Кроме того, если вы храните миллион файлов с помощью хэша в каталоге и теряете индексный файл, найти что-то сложно:)

Answer 2

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

РЕДАКТИРОВАТЬ: вы применяете хэш в качестве оптимизации, чтобы избежать сравнения каждого нового файла с миллионами существующих файлов. Столкновения - не повод избегать использования быстрого хэша. Просто разберитесь со случаем коллизии (если он когда-либо случится), сохранив новую версию файла в любом случае. Обе схемы хеширования обеспечат оптимизацию. Зачем переоптимизировать что-то, что, вероятно, не произойдет. Что, если бы у вас был сверхбыстрый хеш, который столкнулся бы с 1 в 1000000. Это не было бы хорошо для криптографии, но было бы хорошо для контроля версий.

Даже при использовании GUID системы обнаруживают коллизии и обрабатывают их. Систему не нужно оптимизировать для чего-то, что статистически никогда не произойдет.