Сервис по реверсу MD5

Оценим минимальный размер возможного индекса. При любом способе индексации ключ должен вывести нас на 4 байта значения. Для хранения самих значений необходимо 16 ГБайт. Учитывая, что в индексе значения расположены в порядке следования ключей то можно считать их набором случайных данных с полным использованием всех возможных бит. Без потерь сжать такие данные не способен ни один алгоритм.

И так, минимальный индекс составляет 16 ГБайт. Но искать по ним пока не возможно, так как нужен способ быстро найти нужную ячейку этого массива. Учитывая, что MD5 дает хорошее распределение, и обладает большим лавинным эффектом, можно утверждать, что первые 4 байта хеша почти однозначно должны приводить нас к 4 байтам значения. В то же время вычисление функции MD5 на таком небольшом объеме происходит очень быстро. значит нам для поиска достаточно найти от 0 до N значений подходящих для данных 4х первых байт хеша и вычислить их MD5 для окончательной сверки. Причем значение N очень мало.

Предлагаю использовать следующую структуру индекса: создаем 2 файла. В первом (16 Гб) лежат значения отсортированные в порядке первых 4-х байт их хеша, назовем его словарь. Во втором, в порядке ключей лежат 20 байтные блоки, по одному на каждые 16 ключей, в каждом из которых храниться 4 байта - номер стартового элемента в словаре и 16 байт - количество элементов в списке значений для каждого ключа (в предположении что на один ключ не может быть более 255 значений в словаре). Данный файл назовем индекс. При таком подходе размер индексного файла составит 5 гигабайт.

Для поиска берем первые 4 байта хеша (ключ), сбрасываем 4 младшие бита, умножаем полученное значение на 20 и по полученному смещению считываем 20 байт из индекса. Берем младшие 4 бита ключа (k) и убеждаемся, что k элемент в списке длин не 0 (нет такого хеша). После этого к базовому смещению из начала блока добавляем по очереди с 0 по k-1 элемент списка длин (до 16 операций сложения). По полученному смещению (номер элемента*4) получаем список значений в количестве k. Для каждого значения вычисляем MD5 и сравниваем с искомым.

Если по статистике на один ключ приходится не более 15 значений индекс можно еще сократить, храня по 4 бита в списке длин. Тогда объем индексного файла составит 3 Гбайта. Возможно его можно еще сократить, уменьшив длину хранимого базового смещения до 3х, а может даже до 2х байт (храня не номер элемента, а его относительную позицию (со знаком), относительно "идеальной" (если бы на каждый ключ было бы строго 1 значение. Сокращать сильнее список длин смысла не вижу, выиграем еще максимум 1 байт но битовые преобразования значительно усложняться. Так же можно пересмотреть количество ключей, индексируемых одним блоком индекса. Это несколько сократит хранимый объем, но увеличит количество потенциальных операций сложения при поиске элемента.

При предложенном способе поиска хранить в оперативной памяти какие либо индексы не обязательно. Для поиска нам понадобится выполнить 2 операции ввода-вывода (получить с диска блок индекса и блок словаря) и провести немного вычислений: пара сдвигов и and/or, до 16 сложений и N операций MD5, где N обычно не превышает 10.

Для уменьшения объема индекса или уменьшения объема необходимых расчётов мы можем выбрать другую длину ключа, отличную от 4х байт. Уменьшение длины ключа на 1 бит даст 2х кратное уменьшение объема индекса (но в какой то момент придется увеличивать размер ячеек под количества), но в то же время потребует в среднем в 2 раза больше операций MD5 при поиске. При дальнейшем увеличении длины ключа довольно скоро мы придем к ситуации, что на каждый ключ у нас будет приходится не более 1 значения, в этом случае нам фактически будет не нужно делать отдельно словарь и индекс и можно будет держать значения по определенным ключом смещениям в индексе. Необходимый объем памяти для этого подхода надо прикинуть, собрав более детальную статистику и поняв необходимую длину ключа для достижения эффекта однозначного соответствия

Дополнение: способ номер 2

Индекс вообще не нужен !!! Нам нужен только 16 Гб словарь, в котором будут лежать значения, отсортированные в порядке следования их MD5-хешей. При поиске мы на основе первых N бит хеша прикидываем примерный регион файла, в котором должно находиться искомое значение. Учитывая почти однозначное соответствие даже 32 битных ключей это даст достаточно точное попадание. Далее мы вычисляем MD5 от найденного значения и сверяем с искомым. И двигаемся прыжками в том или ином направлении по региону словаря, фактически двоичным поиском, но не по хранимым данным, а по вычисляемым на лету MD5 суммам. Так же можно комбинировать первый и второй способ, сделав небольшой индекс указывающий искомый регион, для ограничения двоичного поиска сразу в нем и сильного уменьшения количества необходимых "прыжков"

Один из вариантов: Храним файлы каталогах со следующей структурой: (первые 3 символа hex(md5))/(следующие 2 символа hex(md5)).db Таким образом папок будет 4096, файлов в папках по 256. Всего 1048576 нод. При таких параметрах файловая система тормозить не будет. Файл будет содержать в среднем 4096 хеша. Сами файл - записи из 16 байт хеша + 4 байта - искомые, расположеные друг за другом. При первоначальной генерации файлы просто дополняются записями, потом записи в каждом файле нужно будет отсортировать по хешу. Таким образом можно будет за минимальное время дойти до нужного файла и выполнить бинарный поиск, занимающий не больше чем 12 итераций открытия файла и чтения 20 байт по смещению.

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

В соответствии с идеей Mike берем у каждого хеша первые 2 байта - и именно в таком виде записываем в файл. Файл можно организовать двухуровневым способом: в начале файла таблица из 65 536 ячеек (каждая ячейка соответствует некоторой комбинации первых двух байт), в каждой ячейке - смещение по которому записаны данные и количество попаданий в эту ячейку. Если брать по 8 байт на каждое значение - то всего эта таблица займет будет 1 МБ, что довольно немного.

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

Во второй части файла будут записаны все данные хеши которых привели в эту ячейку. Их будет в сумме 16 ГБ.

Ну а с поиском все просто: берем первые два байта хеша, по ним определяем список возможных кандидатов. И по этому списку проходим обычным линейным поиском, заново вычисляя все хеши в поисках точного совпадения.

Кстати, на 64х-битной системе можно использовать отображенный на память файл для ускорения работы. Но в 32х-битных системах преимущество такого подхода теряется: вы не сможете отобразить файл в память целиком.