Передо мной встала задача - реверс md5 хеша 4 произвольных байт. То есть, другими словами, мне надо написать сервис из 1 метода - метод получает 16 байт хеша на входе и возвращает 4 байта на выходе.
Поскольку, насколько я помню, реверс хеша сам по себе неосуществим, я решил пойти другим путем и сгеренировать хеши для всех возможных значений. Я выделил сущность, назовем её запись
, которая состоит из 16 байт хеша (назовем ключ
) и 4 байт значения.
Поскольку значений 4 байт ~4млд, то у меня получается 4млд записей, каждая размером 20 байт - это 80 гигабайт данных.
В качестве первого приближения я сгенерировал 80гиг, разбитых на сортированные отрезки (каждый отрезок - отдельный файл) и реализовал слияние файлов по принципу сортировки слиянием. Таким образом в итоге я получу один большой 80 гиговый файл, где будет 4 млд записей, сортированных по ключу. Я планирую по такому большому файлу создать второй файл - индексный, который запросто влезет в оперативку. После этого поиск записи по ключу будет выглядеть как двоичный поиск в большом файле с небольшой помощью индексного файла. Время поиска в общем случае должно быть логарифмическим, ограниченным максимумом в 32 прыжка.
Плюсы такого решения:
- простота развертывания. Просто задеплоил сервис, дождался инициализации, и все работает.
Минусы:
- Генерирование файла занимает очень много времени. Время измеряется часами.
- Генерируемые данные занимают очень много места - 80 гиг
Исходя из минусов, у меня возникло несколько идей:
Первая, конечно, хранить данные в БД. Они там сразу индексирутся и сжимаются. Я пробовал MongoDB и SQL Server, однако скорость вставки и там и там была настолько низкая, что я устал ждать, и оно явно было медленней, чем простая генерация в файл. То есть я и так ради 1 сервиса БД ставить не хотел, и выходит, что это бы мне и не помогло особо.
Вторая - попробовать придумать, как лучше сжать данные. Если честно - сжатие хеша не кажется мне чем то элементарным, а сжать значения не получится так как там используется полный набор значений. Была мысль разделить на файлы большой файл по подобию trie - тогда каждый уровень trie экономил бы мне примерно по 4гига + опускать в значениях незначащие нули (но это бы сильно усложнило поиск)
Мне довольно сложно побрать максимально конкретный вопрос в моей ситуации, но я постараюсь: Если ли более общепринятые способы решения подобной задачи? У меня стойкое ощущение, что я делаю что то не так.
UPD Итак, подведу текущие итоги.
Было опробовано несколько подходов.
1. Первоначальный мой вариант был генерацией всех 16 байтных хешей в файл вместе c начальными айдишниками и после искать хеш по файлу.
Время генерации: примерно 3-4 часа. Скорость поиска: не тестировалось. Память - 80гб
2. Второй подход заключался в том факте, что даже если от 16 байтного хеша взять первые 4 байта, то коллизий будет немного. Таким образом, можно было сгенерировать один большой файл айдишников (сортированный по хешу) + небольшой индексный файл. Поиск выглядел так: получаем входящий хеш, берем от него первые 3 байта, по этому адресу в индексном файле (который можно и в память загрузить) находится начальное смещение в большом файле. По этому смещению считываем 400 айдишников - один из них и есть искомый. Считаем 400 хешей, находим нужный id, возвращаем результат.
Время генерации: примерно 2 часа (не делал пока никаких оптимизаций). Индексный файл - 70мб, файл с айдишниками - 16гб. Скорость поиска: около 75-100 запросов в секунду.
3. Третий подход - генерация цепочек хешей. Суть подхода в том, что можно цепочку хешей представить только начальным и конечным значением. Для моей задачи это выглядит так:
Берем 4 байтный id, генерируем от него хеш H
(берем первые 4 байта), получаем что то типа id->H
. Хеш 4 байтный, значит, где то есть такой id
, значит я могу возять хеш от хеша и построить цепочку типа id->H1->H2->Hn
. В файл можно писать только начало цепочки и конец. Начало нужно для восстановления цепочки, конец для поиска значения по хешу.
Сам поиск выглядит следующим образом: на входе имеем хеш h
. Ищем цепочку с концом h
- если находим, то восстанавливаем цепочку, она содержит искомый id
. Если нет такой цепочки, то берем хеш от нашего хеша h1
, и ищем также цепочку с концом h1
. И так повторяем, пока не найдется цепочка.
Подход свиду имеет несколько плюсов - вроде как можно представить данные набором длинных цепочек (храня в памяти только начало и конец). И первая проблема в слове "длинных". Поясню далее.
Итак, минусы:
- Очевидно, что если в цепочке попадется
id
, который уже есть в другой цепочке, то цепочки начнут дублировать информацию.
Выглядит это так:
id1->H1->H2->H3->H4
id2->H5->H1->H2->H3
как видно, идет дублирование информации, если держать длину цепочек постоянной (что увеличит время генерации файла).
- Чтобы избавиться от дублирования, я выделил в памяти 2^32 бит (~500 мб), и отмечал уже обработанные айдишники. Таким образом 1 айдишник был только в 1 цепочке. И тут всплыла проблема с длиной цепи. Суть в том, что чтобы цепочка была реально длинной и полезной, надо чтобы все сгенерированные хеши внутри неё равнялись тем айдишникам, которые ещё не обработаны. Когда начинаешь расчитывать эти цепочки (я считал цепочку до тех пор, пока не встречал уже обработанный
id
) имеют среднюю длину 200 узлов. Но это число очень быстро уменьшается.
Приведу пример: представим, что обработаны 10%
всех айдишников, и идет генерация новой цепочки. Предполагая, что хеш функция имеет равномерное распределение, шанс, что первый хеш будет таким id
, который ещё не обрабатывался - 0,9
. Шанс, что второй хеш будет таким - 0,9*0,9=0,81
, и тд, и шанс, что в цепочке будет хотя бы 10
элементов примено 0.35
. И это при обработынных 10%
. При обработанных 80%
шанс иметь хотя бы 2
элементы в цепи (не считая первый id
) - 0,64
. При обработанных 99%
- шансы на длинную цепь, можно сказать, отсутвуют, и типичная цепь будет состоять из начального id
и его хеша. Так поучилось и у меня.
Итого, время генерации - примерно час, размер файла - 16гб. Скорость поиска даже не пробвал тестировать.
4. Четвертый подход - радужные таблицы (спасибо @AlexanderPetrov за наводку).
Радужные таблицы, по сути, вариация цепочек хешей. Разница с цепочками в том, что тут применение хеш функции чередуется с применением разных функций (функций редукции). Приведу пример:
id -> H1=H(id) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
В примере видно, что хеш функция чередуется с разными функциями редукции. Плюс этого подхода в том, что даже если какое то значение будет одинаково в 2 цепочках, дублирование будет только в том случае, если значение это будет стоять тем же по счету от начала цепи, например
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H3=H(H7) -> H4=R2(H3) -> H5=H(H4)
Но если это значение будет в разных местах цепочек, то оно даст разный результат, так как обработается разными функциями редукции
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H2=H(H7) -> H8=R2(H2) -> H9=H(H8)
И вроде бы все прекрасно, можно генерировать цепочки произвольной длины. Так я думал, когда начинал генерировать цепи длины 3000 элементов. И я очень быстро посчитал 30%
всех значений. За терпимое время посчитал 50%
. Но тут вступают те же правила с теорией вероятности, что я описал в предыдущем примере. Представим, что я посчитал 95%
всех айдишников. Таким образом, новая цепочка из 3000
элементов, будет содержать 150
новых элементов и 2850
уже посчитанных. Таким образом скорость расчетов цепочек драматически падает, так в каждой новая цепочке вхолостую считаются 95%
элементов. Я ждал примерно 30 часов, и не вытерпел, прекратил это безумие - примерно 98%
всех Id заняли порядка 240
мегабайт. Но меня не устраивала точность 98%
, мне, конечно, надо 100%
.
Из за введения функции редукции, поиск id
по хешу немного отличается от поиска в предыдущем варианте. Если в предыдущем варианте я просто брал хеш от хеша, то тут на основе входящего хеша надо строить новую цепь. Пример:
Допустим, есть цепочка
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
И нам на вход пришел хеш H1
. Цепочек, которые бы оканчивались на H1
у нас нет, потому мы считаем:
H(H1) - нет совпадений
R2(H(H1)) - нет совпадений
H(R2(H(H1))) - нет совпадений
R1(H(R2(H(H1)))) - на этом этапе результат выражения будет равен H5 элементу цепочки.
После того, как цепочка найдена, восстанавливаем её и находим искомый id
. Из практики - я ждал, когда найдется хотя бы 1 id по хешу минут 10, не дождался. Но подозреваю, что дело не в алгоритме, а я просто рукожоп. Вполне допускаю, что если надо реверсить хеш с какой то погрешностью, то, в принципе, вариант рабочий.
Итого, время генерации - очень долго, 98% за 30 часов, причем 98й процент считался часов 5-6, размер файла - 240 мб. Скорость поиска N/A.
Как текущий итог, я пока остановился на варианте 2) - 16 гиговый файл + индекс. Подозреваю, что этот вариант будет самым быстрым. Но другие варианты тоже не буду пока списывать со счетов.
UPD 2 Выложил исходники моих мытарств. Второй подход полностью реализован, вся генерация занимает 25 минут, поиск по 1 ключу за раз - примерно 180 запросов в секунду, поиск пачки входящих реальных данных с реальной программы - ~1000 запросов в секунду (проверял на 75 тыс имеющихся хешей).
Всем спасибо за помощь!