Tag Archives: утилиты

Поиск дублирующихся файлов

На днях мной была написана простенькая консольная утилита fdf (сборка под Windows x86-64, для запуска требуется Microsoft Visual C++ 2013 runtime).

Цели разработки

  • Получить минималистичную утилиту для поиска файлов-дубликатов или уникальных файлов в заданных директориях;
  • потренироваться в решении подобных задач;
  • опробовать SHA3 (Keccak).

Цель получить код, отвечающий каким-то специальным критериям (краткость, дидактическая ценность, высокая эффективность), не ставилась. Тем не менее, предполагается, что он может служить вспомогательным примером при изучении, например, многопоточного программирования на C++: вспомогательные компоненты LockedQueue, LockedLog и ThreadGroup вынесены в отдельные заголовочные файлы и являются довольно примитивными.

Исходники выложены на bitbucket. Для самостоятельной сборки требуется скачать референсную реализацию Keccak и (удобно при использовании Visual C++) распаковать её в папку проекта, так, чтобы папка KeccakReferenceAndOptimized была рядом с файлами исходного кода. За подключение нужных .c файлов отвечает файл FileHasher.cpp, связь кода fdf с Keccak обеспечивается файлом FileHasher.hpp. Оказалось, что использовать референсную оптимизированную (жаль только, что SIMD под Windows/x64 не используется) реализацию весьма просто, спасибо авторам!

Параметры командной строки

  • /? ? -help —help выводит краткую справку;
  • -tN задаёт количество рабочих потоков (всего параллельных потоков будет N+1), по умолчанию выбирается N = max(1, количество логических ядер / 2);
  • -u меняет поведение программы на противоположное: вместо дубликатов будут перечислены найденные уникальные (в заданной области поиска) файлы;
  • -size включает вывод размеров файлов (один размер на группу дубликатов);
  • -loN включает фильтр по размеру файла: рассматриваются только файлы размера не менее N мегабайт, при этом если N=0, fdf будет игнорировать пустые файлы;
  • -timing включает вывод в конце затраченного времени (в секундах);
  • другие параметры расцениваются как указания мест поиска файлов (пути директорий), они формируют общую область поиска (объединение), если ни один путь не указан, то поиск производится в текущей директории.

Результаты работы

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

Принцип работы

Для обхода директорий используется библиотека boost::filesystem. Процесс работы разбит на три стадии:

  1. составление первичного списка файлов;
  2. объединение результатов первой стадии;
  3. проверка на дубликаты побайтовым сравнением найденных кандидатов в дубликаты.

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

На первой стадии основной поток раздаёт пути файлов, выполняя обход переданных директорий поиском в ширину (это приводит к большему расходу памяти, чем традиционный обход поиском в глубину, но позволяет паралелльно нагрузить произвольное число носителей данных), в то время как рабочие потоки вычисляют хэши файлов (целиком для файлов меньше 16 Мб и для выборки в 16 Мб для остальных, размер в 16 Мб взят «с потолка»), и в конце сортируют свои наборы файлов (лексикографически: размер, хэш, имя).

На второй стадии основной поток выполняет восходящее слияние результатов работы рабочих потоков.

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

Замечание. Вместо трёх стадий и формирования отсортированного списка файлов можно было использовать какую-либо параллельную реализацию хэш-таблицы (аналог std::unordered_multiset). Впрочем, в моей практике с использованием HDD именно первая стадия занимает этак 98% времени работы, поэтому сложно надеяться на заметное ускорение при работе на HDD.

Реклама

Xprer

Недавно возникла забавная задачка. Предположим, некий софт накапливает данные в файле. Иногда происходят сбои, и данные начинают записываться повторно в конец файла так, что результирующую структуру файла можно представить в виде трёх участков alpha alpha beta, где alpha — дублирующаяся последовательность байт (префикс). Корректный файл выглядит как alpha beta. Итак, задача: отбросить максимальный дублирующийся префикс в заданном файле за приемлемое время (файл может быть размером в десяток гигабайт).

Для решения данной задачи я написал небольшую консольную утилиту xprer «maXimal PREfix Reduction» (сборка под Windows x86-64, Microsoft Visual C++ 2013 runtime), принимающую один или два параметра командной строки: имя исходного файла и необязательное имя результирующего файла. Если имя результирующего файла не задано, то результат записывается в файл xprer.out.имя исходного файла.

Реализация утилиты использует стандартную библиотеку C++. Исходный код доступен здесь. Для поиска совпадения префикса используется подход, аналогичный алгоритму поиска подстроки Рабина-Карпа. Используется кольцевой хэш на основе суммы и суммы сумм (похож на Adler32, но имеет длину 64 бита и вычисляется по модулю 232).

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