Проверка на наличие дубликатов файлов без сохранения их контрольных сумм

Question

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

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

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

ПРИМЕЧАНИЕ. Приложение использует плоские файлы в качестве базы данных. Пожалуйста, не предлагайте использовать rdbms или тому подобное. Сейчас это просто невозможно.

Как вы думаете, может быть другой способ проверить дубликаты файлов?

Answer 1

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

Или вы находитесь в ситуации, когда клиент может загрузить один и тот же файл несколько раз? Если это так, то вам придется каждый раз проводить полное сравнение.

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

Также: рассмотрим многоуровневую структуру каталогов. Например, файл foobar.txt будет сохранен с использованием пути /f/fo/foobar.txt. Это сведет к минимуму стоимость сканирования каталогов (линейная операция) для конкретного файла.

И если вы сохраните контрольные суммы, это можно использовать для наложения: /1/21/321/myfile.txt (с использованием наименее значимых цифр для структуры; контрольная сумма в этом случае может быть 87654321).

Answer 2

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

Итак, все сводится к тому, как более эффективно хранить файл.

Я бы рекомендовал оставить его для профессионального программного обеспечения, такого как berkleydb или memcached или voldemort или тому подобное.

Если вам нужно свернуть свои собственные, вы можете взглянуть на принципы бинарного поиска ( qsort , bsearch и т. Д.).

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

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

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

Answer 3

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

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

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

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

Answer 4

Как уже упоминалось, наличие другой структуры данных для хранения контрольных сумм - правильный путь. В любом случае, хотя вы упомянули, что не хотите идти по пути RDBMS, почему бы не попробовать sqlite? Вы можете использовать его как файл, и это молниеносно. Он также очень прост в использовании - большинство языков также имеет встроенную поддержку sqlite. Это займет менее 40 строк кода, скажем, на Python.

Answer 5

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

Таким образом, вам нужно проверить только один (или несколько) файлов.

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

[РЕДАКТИРОВАТЬ] Некоторые файловые системы перестают работать, когда у вас есть каталог с большим количеством записей (в данном случае: каталоги контрольной суммы). Если это проблема для вас, создайте второй слой, используя первые два символа контрольной суммы в качестве имени родительского каталога. Повторите при необходимости.

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

Answer 6

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

Допустим, хэш в алфавитно-цифровом формате pIqxc9WI. Этот хэш хранится в файле с именем pI_hashes.db (на основе первых двух символов).

Когда приходит новый файл, вычислите хеш, возьмите первые 2 символа и выполните поиск только в CHARS_hashes.db файле

Answer 7

Несмотря на то, что вы просите не использовать suggets и RDBMS, я все же предложу SQLite - если вы сохраните все контрольные суммы в одной таблице с индексом, поиск будет довольно быстрым, а интеграция с SQLite не станет проблемой.

Answer 8

Вы должны как минимум переместить файл контрольных сумм в правильный файл базы данных (при условии, что это еще не так) - хотя SQLExpress с его пределом в 4 ГБ здесь может быть недостаточно. Затем вместе с каждой контрольной суммой сохраните имя файла, размер файла и полученную дату, добавьте индексы к размеру файла и контрольной сумме и выполните свой запрос только для контрольных сумм файлов с одинаковым размером. Но, как говорит Уилл, ваш метод проверки на дубликаты в любом случае не гарантирован.

Answer 9

Я думаю, вам придется перепроектировать систему, если я правильно понимаю вашу ситуацию и требования.

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

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

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