Самый быстрый алгоритм для обнаружения дубликатов файлов

Question

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

Так что обычный алгоритм работает следующим образом:

• создать отсортированный список всех файлов (путь, размер, идентификатор)
• групповые файлы с одинаковым размером
• вычислить хэш всех файловс одинаковым размером и сравните хэши
• имеет одинаковые средства идентичные файлы - найден дубликат

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

Поэтому у меня сложилось мнение, что эта схема разбита на два разных измерения:

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

Я нашел одно (Windows) приложение, которое заявляет, что оно быстрое, если не использовать это общее хешированиесхема.

Я совершенно не прав с моими идеями и мнением?

[Обновить]

Кажется, есть мнение, что хеширование может быть быстрее, чем сравнение.Но это, похоже, заблуждение из общего использования «хеш-таблиц ускоряет вещи».Но для создания хэша файла в первый раз файлы должны быть прочитаны полностью побайтно.Так что с одной стороны есть побайтовое сравнение, которое сравнивает только столько байтов каждой функции-дубликата-кандидата до первой отличающейся позиции.И есть хеш-функция, которая генерирует ID из такого количества байтов - скажем, первые 10 Кбайт терабайта или полный терабайт, если первые 10 Кб совпадают.Таким образом, в предположении, что у меня обычно нет готовой вычисляемой и автоматически обновляемой таблицы всех хэшей файлов, мне нужно вычислить хэш и прочитать каждый байт кандидатов-дубликатов.Для побитового сравнения не нужно этого делать.

[Обновление 2]

У меня есть первый ответ, который снова идет в направлении: "Хэши, как правило, являютсяхорошая идея "и из этого (не так уж и неправильно) думать, пытаясь рационализировать использование хэшей с (ИМХО) неправильными аргументами.«Хэши лучше или быстрее, потому что вы можете использовать их позже» - не вопрос.«Предполагая, что многие (скажем, n) файлы имеют одинаковый размер, чтобы найти дубликаты, вам нужно выполнить n * (n-1) / 2 сравнения, чтобы проверить их попарно все друг против друга. Используя сильные хэши,вам нужно будет хэшировать каждый из них только один раз, что даст вам n хешей. "перекошен в пользу хешей и неправильных (ИМХО) тоже.Почему я не могу просто прочитать блок из каждого файла одинакового размера и сравнить его в памяти?Если мне нужно сравнить 100 файлов, я открываю 100 файловых дескрипторов и считываю блок из каждого параллельно, а затем выполняю сравнение в памяти.Это выглядит намного быстрее, чем обновлять один или несколько сложных алгоритмов медленного хэширования с этими 100 файлами.

[Обновление 3]

Учитывая очень большой уклон в пользу "всегда следует использовать хеш-функции, потому что они очень хороши!" Я прочитал некоторые вопросы о качестве хеша, например этот: Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Он показывает, что обычные хеш-функции чаще вызывают коллизии, чем мы думаем, из-за плохого дизайна и дня рождения парадоксон . Тестовый набор содержал: «Список из 216 553 английских слов (в нижнем регистре), числа от «1» до «216553» (например, почтовые индексы и то, как плохой хэш уничтожил msn.com) и 216,553 «случайных» (т. е. типа 4 uuid) идентификаторов GUID ». Эти крошечные наборы данных производятся от 100 до почти 20 тыс. Столкновения. Поэтому тестирование миллионов файлов на (в) равенстве только на основе хэшей может быть не очень хорошей идеей.

Полагаю, мне нужно изменить 1 и заменить часть трубы md5 / sha1 на "cmp" и просто измерить время. Я держу вас в курсе.

[Обновление 3] Спасибо за все отзывы. Медленно мы конвертируем. Фон - это то, что я наблюдал, когда fslints findup работал на моей машине md5, используя сотни изображений. Это заняло довольно много времени, и жесткий диск вращался, как ад Так что я бродил: «Какого черта этот сумасшедший инструмент думает об уничтожении моего жесткого диска и тратит огромное количество времени на сравнение байтов»: 1) дешевле на байт, чем любой алгоритм хэша или контрольной суммы и 2) с побайтовое сравнение Я могу вернуться к первому различию раньше, поэтому я сэкономлю массу времени, не тратя пропускную способность и время жесткого диска, читая полные файлы и вычисляя хеш-значения для полных файлов. Я все еще думаю, что это правда - но: я думаю, я не уловил, что сравнение 1: 1 (если (file_a [i]! = File_b [i]) возвращает 1;) может быть дешевле, чем хеширование на байт. Но сложное хеширование с помощью O (n) может выиграть, когда нужно сравнить больше файлов. Я поставил эту проблему в своем списке и планирую либо заменить часть md5 fslint в findup на cmp, либо улучшить pythons filecmp.py сравнить библиотеку, которая сравнивает только 2 файла одновременно с опцией для нескольких файлов и, возможно, версией md5hash. Так что спасибо всем на данный момент. И вообще ситуация такая, как вы, ребята, говорите: лучший способ (TM) полностью зависит от обстоятельств: жесткий диск и твердотельный накопитель, вероятность файлов одинаковой длины, дубликаты файлов, типичный размер файлов, производительность ЦП в сравнении с памятью в сравнении с диском, одинарная против Multicore и так далее. И я узнал, что мне следует чаще рассматривать хэши, но я разработчик встраиваемых систем, у которого в большинстве случаев очень ограниченные ресурсы; -)

Спасибо за все ваши усилия! Marcel

Answer 1

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

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

Но ...

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

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

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

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

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

Answer 2

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

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

Несколько особенностей для рассмотрения:

1) Вы измерили и обнаружили, что сравнение внутри файловых групп было дорогой частью операции? При обходе жесткого диска объемом 2 ТБ вся файловая система может занять много времени сама по себе. Сколько операций хеширования было фактически выполнено? Насколько большими были файловые группы и т.д?

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

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

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

Answer 3

Самый быстрый алгоритм дедупликации будет зависеть от нескольких факторов:

1. как часто можно найти почти дубликаты? Если очень часто можно найти сотни файлов с одинаковым содержимым и разницей в один байт, это сделает сильное хеширование гораздо более привлекательным. Если крайне редко можно найти более пары файлов одинакового размера, но различного содержимого, хеширование может быть ненужным.
2. как быстро это читать с диска, и насколько большие файлы? Если чтение с диска очень медленное или файлы очень маленькие, то однопроходные хэши, хотя и криптографически стойкие, будут быстрее, чем небольшие пропуски со слабым хешем, а затем более сильный, только если совпадет слабый хеш.
3. сколько раз вы собираетесь запустить инструмент? Если вы собираетесь запускать его много раз (например, чтобы постоянно дублировать объекты), то создание индекса с указанием пути, размера и strong_hash для каждого файла может стоить того, поскольку не нужно перестраивать его при последующих запусках инструмента.
4. вы хотите обнаружить дубликаты папок? Если вы хотите сделать это, вы можете создать дерево Меркле (по существу, рекурсивный хэш содержимого папки + ее метаданных); и добавьте эти хеши в индекс тоже.
5. что вы делаете с правами доступа к файлам, датой изменения, списками ACL и другими метаданными файла, которые исключают фактическое содержимое? Это не связано напрямую со скоростью алгоритма, но добавляет дополнительные сложности при выборе способа обработки дубликатов.

Следовательно, нет единого способа ответить на первоначальный вопрос. Самый быстрый, когда?

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

Предполагая, что многие (скажем n) файлы имеют одинаковый размер, чтобы найти дубликаты, вам нужно будет сделать n * (n-1) / 2 сравнений, чтобы проверить их попарно друг против друга. Используя сильные хэши, вам нужно будет хэшировать каждый из них только один раз, в итоге вы получите n хешей. Даже если для хэширования требуется k раз больше, чем для сравнения байтов, хэширование лучше, когда k > (n-1)/2. Хэши могут давать ложноположительные результаты (хотя сильные хэши будут делать это только с астрономически низкой вероятностью), но тестирование этих побайтных байтов только увеличит k максимум на 1. С k=3 вы будете впереди, как только как n>=7; с более консервативным k=2 вы достигаете безубыточности с n=3. На практике я ожидал бы, что k будет очень близко к 1: чтение с диска, вероятно, будет стоить дороже, чем хэширование всего, что вы прочитали.

Вероятность того, что несколько файлов будут иметь одинаковые размеры, увеличивается с квадратом количества файлов (посмотрите парадокс дня рождения). Следовательно, можно ожидать, что хеширование будет очень хорошей идеей в общем случае. Это также значительное ускорение в случае, если вы когда-нибудь снова запустите инструмент, потому что он может повторно использовать существующий индекс вместо построения его заново. , Таким образом, можно ожидать, что сравнение 1 нового файла с 1M существующих, разных, проиндексированных файлов того же размера займет 1 просмотр хеша + 1 в индексе по сравнению с 1M сравнений в сценарии без хеширования, без индекса: примерно 1 миллион раз Быстрее!

Обратите внимание, что вы можете повторить тот же аргумент с многоуровневым хешем : если вы используете очень быстрый хеш с, скажем, 1-м, центральным и последним 1k байтами, это будет намного быстрее для хеширования, чем для сравнения файлов (k < 1 выше) - но вы будете ожидать коллизий и сделаете второй проход с сильным хешем и / или байтовым сравнением, когда найдете. Это компромисс: вы держите пари, что будут различия, которые сэкономят вам время полного хэша или полного сравнения. Я думаю, что в целом оно того стоит, но «лучший» ответ зависит от специфики машины и рабочей нагрузки .

[Update]

ОП, кажется, под впечатлением

• Хэши медленно вычисляются
• Быстрые хэши приводят к столкновениям
• Использование хэширования всегда требует считывания полного содержимого файла, и поэтому является чрезмерным для файлов, которые отличаются своими 1-ыми байтами.

Я добавил этот сегмент, чтобы противостоять этим аргументам:

• Сильный хэш (sha1) занимает около 5 циклов на байт для вычисления , или около 15 нс на байт на современном процессоре. Задержки диска для вращающегося жесткого диска или ssd составляют порядка 75k нс и 5M нс соответственно. Вы можете хэшировать 1 Кб данных за время, необходимое для начала чтения с SSD. Более быстрый, не криптографический хэш, meowhash , может хешировать со скоростью 1 байт за цикл. Задержки основной памяти составляют около 120 нс - легко выполнить 400 циклов за время, необходимое для выполнения одного запроса access-noncached-memory.
• В 2018 году единственное известное столкновение в SHA-1 произошло от разрушенного проекта 1074 *, который потребовал огромных ресурсов для вычислений. Другие сильные алгоритмы хеширования не намного медленнее и не сильнее (SHA-3).
• Вы можете всегда хешировать части файла вместо всего этого; и сохраняйте частичные хеши до тех пор, пока не столкнетесь с коллизиями, то есть когда вы будете вычислять все более крупные хэши, пока в случае истинного дубликата вы не хешируете все это. Это значительно ускоряет построение индекса.

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