Мгновенный поиск в 75 гигабайтах

Речь пойдет о том, как был реализован быстрый поиск по большим объемам данных на этой страничке. Там можно искать пароль по хешу, для игрового сервера PvPGN, и генерировать эти же хеши.
Поиск написан на чистом PHP, без использования модулей и сторонней БД. В принципе, таким образом можно наращивать объемы до многих терабайт, было бы место — скорость от этого не сильно пострадает.

Далее от начала до конца описан весь процесс, который включает в себя брутфорс, создание хеш таблицы, её сортировка и, собственно, поиск.




Bruteforce



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

Я приведу простейший пример брутфорса на C#, перебирающий пароли для поиска MD5 хеша. А генерация несортированной таблицы сводится к простому складыванию сгенерированных данных в файл вида CSV.

    class Program
    {
        static bool _isFound = false;
        static string _findHash;
        static string _symbols;
        static int _pass_lenght;

        static void Main(string[] args)
        {
            _findHash = args[0]; // искомый хеш
            _pass_lenght = int.Parse(args[1]); // длина взламываемого пароля
            _symbols =  args[2]; // набор символов в пароле
            byte[] data = new byte[_symbols.Length];

            Process(data, 0);
            Console.ReadLine();
        }

        private static string hash;
        private static byte[] data_trim;
        private static string pass;

        // рекурсивный метод
        static void Process(byte[] data, int index)
        {
            // условие выхода из рекурсии
            if (index == _pass_lenght)
            {
                data_trim = data.TakeWhile((v, idx) => data.Skip(idx).Any(w => w != 0x00)).ToArray(); // удалить в конце нули
                pass = Encoding.ASCII.GetString(data_trim);
                hash = GetHash(pass);

                Console.Write("{0} ", pass);

                if (hash == _findHash)
                {
                    _isFound = true;
                    Console.WriteLine("\n\nPassword was found!\n\t{0} = {1}", hash, pass);
                }
                return;
            }
            // перебор всех вариантов
            foreach (byte c in _symbols)
            {
                if (_isFound)
                    return;

                data[index] = c;
                Process(data, index + 1);
            }
        }

        // возвращает md5 hash из пароля
        static string GetHash(string value)
        {
            MD5 md5 = new MD5CryptoServiceProvider();
            byte[] output = md5.ComputeHash(Encoding.ASCII.GetBytes(value));

            return BitConverter.ToString(output).Replace("-", "").ToLower();	// hex string
        }
    }


Пример с исходником по ссылке.
Запускать: BruteForce.exe [искомый_хеш] [длина_пароля] [символы_пароля]


Сортировка


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

SELECT hash, pass INTO OUTFILE 'd:\\result.csv'
FIELDS TERMINATED BY ',' OPTIONALLY ENCLOSED BY ''
LINES TERMINATED BY '\n'
FROM hashes ORDER BY hash


Ему понадобилось 16 часов времени, а пока это делалось, в папке TEMP создались 2 файла: 16 и 25 гигабайт.
Но даже с индексом (который создавался пару часов) такой вариант всё-равно меня не устроил, хотя бы из-за поглощаемых гигабайтов при сортировке, т.к. при увеличении размера таблиц на моем диске просто не хватило бы места.

Я пробовал сделать таблицу в SQLite, но он не предназначен для больших объемов, поэтому работал очень медленно (в 1 гб поиск по хешу выполнялся около 6 секунд). MySQL быстрее, но в обоих вариантах не устраивал конечный размер, который был почти в 2 или более раз больше исходных данных (вместе с индексом).

Так как я ни разу не занимался сортировкой больших данных (без загрузки всего файла в память), то взял первый попавшийся алгоритм — "сортировка пузырьком" :). Написал небольшой код на C#, чтобы файл сортировался сам в себе, и запустил на ночь пробу на 500 мегабайтах. На следующий день файл всё ещё сортировался. Оно и понятно — ведь если самая меньшая запись находится в конце файла, то с таким алгоритмом она будет двигаться вниз по одной строчке, и для каждого такого сдвига нужно пройти весь файл от начала до конца!

Стал искать другие методы сортировки, подходящими оказались слияние и пирамида. Начал уже реализовывать их гибрид, но случайно нашел информацию об утилите sort, которая по-умолчанию идет с Windows, начиная с XP. Как оказалось, она идеально подходила под мою задачу! Не знаю, как она работает, но в описании написано, что сортирует файл за один проход (5 гб отсортировались за полчаса). В процессе сортировки утилита требует столько же дополнительного свободного места, сколько весит исходный файл (для временного файла).

Но и тут все было не все гладко. Когда сортировался файл 190 гб, ей понадобилось в 3 раза больше места, и я начал что-то искать и удалять, чтобы освободить место на диске. Помимо этого, в конечном файле появились непонятные «артефакты»:


Они оказались, примерно, в 10-ти в случайных частях файла. Я запускал сортировку несколько раз, ожидая каждый раз по 24 часа, но артефакты всё-равно появлялись. Я не понял, почему так произошло, у меня 12 гб ОЗУ, Win7 x64, на тот момент комп проработал неделю без выключения. Могу предположить, что память за это время «засорилась», т.к. после перезагрузки системы та же самая сортировка с первого раза прошла успешно.

Поиск


Теперь это кажется глупо, но раньше мне всегда казалось, что поиск по файлам можно осуществлять только загрузив весь файл в память, либо читая весь файл построчно. Попробовав бинарный поиск в большом файле на практике, и увидев, насколько быстро это работает, да ещё и на PHP, — для меня это оказалось маленьким открытием. Такой поиск может работать столь же быстро с мега большими объемами данных, причем, не нагружая процессор и не съедая память.


Бинарный (он же двоичный) поиск работает по следующему принципу:
  1. Массив делится на 2 половины и позиция чтения перемещается в середину.
  2. Текущее значение, которое найдено посередине, сравнивается с искомым
  3. Если искомое > текущего, то берется вторая половина массива, если искомое < текущего — первая половина.
  4. Проделываем 1 по 3 шаг с данной половиной массива.

И, конечно же, главное условие бинарного поиска — массив должен быть отсортирован по поисковому ключу.

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

На этом можно было бы и остановиться, если бы не одно НО…

Деление


Поиск оказался невозможным по файлам, превышающих значение PHP_INT_MAX (2147483647 байт). Причем, иногда функция fseek возвращает -1, а иногда у нее все нормально, но смещение устанавливается непонятно куда. В итоге читается совсем не то, что нужно. Баг был неочевиден, но в процессе поиска проблемы нашел инфу в багтрекере. Ещё на сайте документации PHP к функции fseek есть комментарий как искать по файлам больше 2 гб (функция fseek64). Она сводится к чтению не с начала файла, а с текущего смещения, до необходимого места, итерацией. Но я проверил, это тоже не работает.

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

Может кому и понадобиться, качать с исходниками отсюда.
Запускать: Split.exe [файл] [размер_в_байтах]

Сжатие


Для начала, отсортированные данные я разделил в два отдельных файла: .hash, .pass, в которых хранятся хеши и пароли к ним, соответственно. Затем, все данные я просто «запаковал» в хекс. Числа легко пакуются таким образом до 2х раз, а так как длина каждого значения фиксированая, то в недостающий промежуток добавляется 0xF.

Каким образом сделано сжатие, и то, как происходит поиск, наглядно видно на следующем примере (ищем пароль для хеша 0dd5eac5b02376a456907c705c6f6fb0b5ff67cf):


0D D5 EA — первые 6 символов хеша. Таким образом будут повторяющиеся хеши, но их получается не так много. А поскольку пароли все сохранены, то даже из тысячи паролей можно очень быстро восстановить исходный хеш.

70 FF — здесь запаковано число 70, это количество паролей, которое содержится в файле digits.pass для хешей, начинающихся на 0dd5ea

59 99 95 68 FF FF — здесь запаковано число 59999568, это позиция начала чтения паролей в файле digits.pass

11a19a90 — позиция, с которой начинается чтение 70-ти паролей в файле digits.pass; она вычисляется так: 59999568 * 5 (длина любого пароля, уже сжатого, в байтах) = 299997840 (переводим в hex)

84 04 05 38 8F — здесь запаковано число 840405388, это и есть пароль, соответствующий искомому хешу

Затем я разбил файл .pass по частям таким образом, чтобы пароли не обрезались в конце файла, и не выходили за границу PHP_INT_MAX: 2147483647 — (2147483647 % размерпароля) байт.
Максимальный размер файла .hash получился 185 мб, и его разбивать не пришлось.


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

Все необработанные файлы весили 260 гб, а после сжатия получилось 70 гб. Этот размер включает в себя пароли от 1 до 6 символов из цифр с буквами, и от 7 до 10 символов — только цифры, всего около 13,5 млрд. паролей. Позже я добавил ещё 100 млн. словарных слов. В итоге, около 90% паролей с реального PvPGN сервера должны находиться (с моего бывшего сервера PvPGN нашлось 93,5%).

Маленькая оптимизация


Один хороший человек портировал хеш функцию PvPGN'а с PHP на JavaScript (он же предоставил мне виртуальный сервер с 250 гб места под таблицы).

Я сделал замеры производительности разных реализаций хеша:


Реализации на разных языках доступны для загрузки harpywar.pvpgn.pl/?do=hash
Очевидно, что на Си быстрее всего. Во всех браузерах скорость примерно одинаковая, хотя Firefox подвисает на время выполнения скрипта.

Оказалось, мой поиск притормаживал из-за PHP. Поэтому, сразу после тестирования, я решил отправлять клиенту в браузер эту ресурсоемкую задачу. Тем более, для клиента это будет совсем незаметно — в среднем сгенерировать требуется не более 1000 хешей за 1 поисковый запрос. Переделывать то, что уже было пришлось самую малость: найденные пароли нужно передавать клиенту в JSON массиве, а в браузере сделать итерацию паролей и генерацию из них хешей. Если сгенерированный хеш подходит под искомый, то пароль считается найденным.
Грубый, но наглядный пример того, как это работает, на скриншоте (на нем ещё несжатый файл):


Итог


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

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

Update

— Выложил PHP исходники для интересующихся, но не имея файлов таблиц их изучение может быть неинтересным: index.php, hashcrack.class.php.

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

— С тоталкомандером я ошибся — с помощью него всё-таки можно точно по байтам разделить файл на части (подсказал Joshua5).

— Я не сильно знаком с особенностями различных БД, из-за чего поиск был долгим.
Alexey Pechnikov подсказывает, что на SQLite производительность может быть очень высокой, а для таблицы нужно было использовать «fts4». Вероятно, что-то похожее есть и в MySQL.

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

Комментарий от webhamster полностью отражает то, что я хотел показать в этом топике
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 115
  • +5
    Ох*еть, простите.
    • +22
      А тут что ох*енного, простите? То, что автор открыл для себя бинарный поиск? Даже школьники знают, что его сложность O(log n).
      • 0
        Я действительно не знал. Мне должно быть стыдно? Уже пол дня изучаю этот метод.
        • +15
          Да, если Вы не знали про двоичный поиск, то Вам должно быть стыдно.
          • +4
            Если бы меня кто то учил… Он мне просто не было нужен. По крайней мере я так думал.
            • +6
              Вас не учили логарифмам? Ну тогда вот вам еще одно откровение: поиск по массиву, размер которого равен количеству атомов во вселенной, потребует не более 266 операций сравнения. Даже на PHP.
              • 0
                По произвольному массиву? Что-то не верится.
                • +2
                  По отсортированному массиву.
                  По неотсортированному — 2^266 операций на обычном компьютере, или 2^133 на квантовом.
                  • 0
                    Время сортировки еще учтите и тогда будет все нормально ;)
                    • –1
                      Время сортировки такого объема — около пары часов, не больше.
                      Есть даже специальные соревнования по такой дисциплине, как сортировка больших объёмов данных.
                      • +1
                        Ого!
                        Найдите компьютер, способный хотя бы хранить 2^266 бит информации — и весь мир у Ваших ног.
                        • +7
                          Да что вы накинулись? У меня специальность кинотехник, TimTowdy, давайте не будем, а? Если я не знал про бинарный поиск, не значит, что я не знаю ничего. Просто не сталкивался с этим.
                          • 0
                            А кто вообще говорил о 2^266 битах?
                            В статье — 70 гигабайт данных.
                • +2
                  Метод половинного деления?
              • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              То, что сам бинарный поиск существует, действительно знает любой прошаренный школьник.
              Для себя я открыл бинарный поиск в больших файлах, без необходимости загрузки содержимого в память.
            • 0
              Называемый вами «бинарный поиск» имеет другое название, более точно его определяющее — дихотомический поиск.
              Алгоритм такого поиска я писал на C# в консоли будучи студентом.
            • +3
              Интересно на сколько будут отличаться результаты, если все это дело переписать на Си
              • 0
                скорость Сишных программ в 5 раз быстрее ПХПешных
                но если переделывать, то надо использовать не только другой язык, но и немного другие методы:

                про сортировку для подготовки данных я написал ниже.

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

                для связи с WEB сервером используем протоколscgi
                поиск будет занимать доли секунд. сам делал похожие штучки.
                • 0
                  Согласно приведенной автором табличке, C обгоняет PHP чуть больше чем в 2000 раз.
                  • +3
                    это во многом зависит как от используемого алгоритма, так и от используемого железа.
                    во первых в РНР очень много хорошо оптимизированных Сишных функций
                    во вторых, исходя из текста статьи компетенция автора — сомнительна как в алгоритмах,
                    так и в выборе инструментария.

                    программы с частыми операциями i/o на С не на много обгоняют РНР;
                    если на Си использовать технику паралельных вычислений, то можно добиться и большей производительности.
                  • +1
                    5 раз — это откуда цифра? Всё зависит от того, что вы хотите делать. У меня в одной программе, которая обращалась к большой двумерной табличке в цикле (а в PHP все массивы работают как хэш-таблицы) после грамотной оптимизации получился 200-кратный прирост скорости работы.
                    • +2
                      Позволю себе упомянуть свою статью: пишем PHP extension. Там просто есть некоторые цифры.
                      • 0
                        как-то решил реализовать на РНР некоторый алгоритм со сдвигами и хорами
                        строчек на 10
                        вышел раз в 50 тыс медленне
                        не замерял — но на глаз он точно тормозил.
                        так что на вычислительных задачах — РНР еще тот тормоз ;)
                        • 0
                          а статья у тебя неплохая…
                          жаль что не могу ее «поднять»
                          • 0
                            Спрашивайте, чего не понятно. Народ толковый найдется подскажет.
                        • 0
                          делал замеры для определенного круга задач
                          в среднем от 5 до 20 раз
                          я взял наихудший вариант
                          • 0
                            несомненно в вычислительных задачах — РНР проигрывает
                            ежу понятно.
                      • +4
                        По ходу прочтения у меня возник вопрос, а зачем вы все в 1 отсортированный файл пихаете?
                        Получается чтобы добавить 1 хеш придется все перестроить / пересортировать.
                        Раз вы получили фиксированную длину хеша, то можно разграничит диапазоны для каждого файла, сделав его на этапе создания по 2 ГБ. После сортировать можно в параллель. При бинарном поиске вы так же будете знать в каком файле (файлах) искать.
                        Но в тоже время Mysql неплохо справляется секционированием больших таблиц.

                        • –1
                          Да, добавление одного хеша в моем случае требует полной перегенерации. Это большой минус, хотя для статичных данных это может быть в тему.
                          В первую очередь, мне было интересно узнать, как будет происходить поиск в большом файле. Наверное, из-за этого и получилась так, как получилось :)
                          • –1
                            Можно было использовать 0 байт (лишь показуха) под все записи, расположив хеши в именах файлов в папке и используя поиск Windows Explorer)))
                        • +5
                          Переходите на x64

                          >> php -r 'echo PHP_INT_MAX;'
                          9223372036854775807
                          • 0
                            Да, я в курсе, но предоставленный мне хостинг был с 32битным php.
                            • –4
                              Радужные таблицы требуют нагрузки на процессор, соответственно не быстрый поиск.
                              • +4
                                А вы пробовали их применять?

                                Имхо, посчитать цепочку из 100 хешей будет быстрее, чем сходить за одним хэшом в память, а уж тем более на диск (у вас же не 75гб памяти?)
                                • 0
                                  p.s.: к тому же, входную цепочку можно заставить считать браузер. Да и выходную восстанавливать тоже.
                                  • –3
                                    Я к ним присматривался, но, если честно, не до конца понял, как они работают :)
                                    Читая про них, я мне пришла идея убрать избыточные данные, сохраняя только часть хеша, а все пароли в отдельном файле.
                                    • +1
                                      Попробуйте перечитать и вынести хотя-бы обратное восстановление на клиента. Это очень сильно снизит объём вашей БД. А по скорости будет примерно так же.

                                      Если ещё вынести генерацию и входной цепочки, то мне кажется, что будет даже быстрее.
                                      • +3
                                        Перескажу вам вкратце оригинальную статью Охслина.
                                        0) H — наша хеш-функция. Например, мд5.
                                        1) Множество паролей, для которых строится таблица, можно пронумеровать. функция R берёт хеш (как одно число) по модулю количество_паролей и использует результат как индекс в этом множестве паролей. (Радужность таблицы, на самом деле, подразумевает, что для таблицы с номером k к хешу мы ещё добавим k)
                                        2) Возьмем произвольный хеш. Построим чейн: применим к хешу по очереди функции R и H, к результату применим их ещё раз, и так всего N раз. Получим какой-то хеш в самом конце. N называется длиной чейна. Первый и последний хеши сохраним в таблицу. Сделаем так M раз.
                                        3) Отсортируем таблицу по второй колонке (где последние хеши), чтобы было удобнее дальше работать.
                                        4) Время взломать хеш. Строим вышеописанным способом чейн, начиная с данного хеша. Для каждого из промежуточных хешей делаем следующее. Мы ищем его во второй колонке. Если найден, восстанавливаем чейн по хешу из первой колонки. Если нам повезло, то исходный текст для исходного хеша попадётся в ходе вычисления чейна. Если не вполне понятно, рекомендую нарисовать себе картинку: чейн для исходного хеша и чейн из таблицы, сдвинутые друг относительно друга (некий элемент первого совпадает с последним второго).
                                    • 0
                                      Поиск там ровно такой же, просто радужная таблица меньше, чем полная таблица перебора всех паролей. Генерить её дольше, но искать в итоге по меньшему объёму данных.
                                      • 0
                                        Да, поиск не ровно такой же, каюсь
                                  • +2
                                    «prepair» резануло глаз.
                                  • +1
                                    C помощью javascript?! Забавно будет подсовывать всем клиентам небольшой кусок данных и javascript. Эдакое клиент-серверное распределение :D
                                    • 0
                                      Почитайте про методы Монте-Карло — будет интересно)
                                      • –2
                                        статья похожа на сгенерированную сеошниками для поисковых машин, читать и понять что к чему сложновато.
                                        А если вам надо быстро что-то найти в 75Gb посмотрите с сторону Map/Reduce, Hadoop, ваша задача туда хорошо ложиться
                                        • +4
                                          Кладётся :-P
                                          • +1
                                            если вам надо быстро что-то найти в 75Гб, посмотрите в сторону
                                          • 0
                                            Мисье знает толк в толковых извращениях.
                                            Теперь осталось попробовать сотворить тоже самое на своём сервере, или сервере друга :D.
                                            Автору зачёт, ещё по твоим мануалам учился настраивать pvpgn :)
                                            • +4
                                              А причем тут PHP? В статье C# встречается чаще чем PHP…
                                              И вообще какой вывод должны сделать читатели прочитавшие статью? Что у вас все получилось?
                                              Как то бесполезно…
                                              • 0
                                                и исходников с алгоритмом нету )
                                              • 0
                                                На C# сделана вся подготовка бинарных файлов. А PHP потому, что поиск реализован на нем. Могу выложить и исходник на PHP, но ведь подробнее об этом написано в разделе «поиск».
                                                Я думаю, что отсюда могут пригодиться некоторые идеи. То, как сделан сам поиск, или перенос нагрузки на клиента.
                                              • +5
                                                немного не понял.
                                                это статья о том как крут бинарный поиск?
                                                ну да, он крут, и...?
                                                • +5
                                                  > это статья о том как крут бинарный поиск?

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

                                                  Автор так же выяснил, что для реализации бинарного поиска на больших объемах данных достаточно стандартных дервних файловых функций fopen(), fseek(), fread().

                                                  Так же он выяснил, что при применении правильного алгоритма для решения задачи, неважно на каком языке реализован алгоритм — хоть на PHP, хоть на C, разница в скорости небольшая — C оказался быстрее всего в два раза.

                                                  Это бесценный опыт на самом деле, и он поможет автору в дальнейшем правильно смотреть на новые технологии незамыленным взглядом.
                                                  • 0
                                                    C оказался быстрее в двадцать раз. С его использованием посчитали миллион хэшей, а не 100 000.
                                                    • +1
                                                      C оказался быстрее в 2000 раз. На PHP посчитали 1000 хешей, а не 100 000.
                                                      • 0
                                                        Ну да. Но я сравнивал с JS.
                                                • +2
                                                  Код на php написан не оптимизированно, поэтому и тормоза (хотя js все-равно быстрее будет). Например, из for не вынесены length и count. bolknote.ru/2011/06/23/~3290#74 — вот тут было одного алгоритма на разных языках — вынос count из for дал 66% ускорения!
                                                  • +4
                                                    сортирует файл за один проход

                                                    Т.е. сортировка O(n)? ))… Прорыв в теории алгоритмов ?? ))
                                                    • +1
                                                      Вы слышали про radix sort?
                                                      • 0
                                                        Файл со строками можно вполне сортировать за O(длина файла в битах) с помощью бора. Впрочем не знаю каким методом пользуется стандартная утилита sort.
                                                      • +3
                                                        у меня было тестовое задание — отсортировать 109 строк по 8 цифр( 87Гб)
                                                        решалось банально просто: файл бился на 1024 кусков (где-то по 1 млн строк),
                                                        каждый из них сортировался, далее происходило слияние парами.

                                                        Эти части вполне реально распаралелить.
                                                        Сортировка заняла около 7-15х мин.

                                                        практически можно подобрать соотношение: кол-во кусков/размер.
                                                        В зависимости от процессора и памяти может 8192 или 16384 куска обработать быстрее, чем 1024
                                                        программа использовала метод qsort и была реализована на С++

                                                        может научимся БД использовать как хранилище данных, а не забивать микроскопом гвозди
                                                        Объемы раз в 10 превышающие ваши хеши.
                                                        • +2
                                                          По 8 цифр? То есть возможных различных входных строк не более 10^8? Тогда сортировка подсчетом же!
                                                          • 0
                                                            ну по условиям задачи надо было сделать для float
                                                            генерировал данные для 8 цифр, так как при выводе я округлял до 8 цифр

                                                            но если использовать строго для 8-9 цифр, то сортировка подсчетом несомненно будет быстрее.
                                                        • 0
                                                          Реализации на разных языках доступны для загрузки harpywar.pvpgn.pl/?do=hash
                                                          Очевидно, что на Си быстрее всего.
                                                          ежу понятно,
                                                          так как в других языках используют либо бинд этой функции, либо ее реализуют своими средствами
                                                          • –1
                                                            Хм. BST же (двоичное дерево поиска).
                                                            • +1
                                                              Его ещё создать надо, что займет памяти больше чем исходный размер файла!
                                                              • 0
                                                                дерево в миллиарды вершин в память не влезет — его надо бить на части
                                                              • +14
                                                                Вы не пробовали арифметический поиск? Поскольку хеши довольно случайны, то он должен дать значительное уменьшение операций чтения с диска.
                                                                Табличка у Вас, конечно, хорошая.

                                                                График у Вас совершенно замечательный:) Только должен он выгляеть так.
                                                                • 0
                                                                  Имхо, уже некуда уменьшать количество операций чтения с диска. Подскажите, где почитать про арифметический поиск? Поиск в гугле дает только ссылку на Ваш комментарий)
                                                                  • 0
                                                                    Хм, не думал, что это столь редкое название:)
                                                                    • +1
                                                                      Упс, коммент рано отправился.
                                                                      Правильное его название — интерполяционный поиск
                                                                      • +1
                                                                        Ага, особенно хорошо он работает на данных вроде списка степеней двойки.

                                                                        Спойлер: O(N) в этом (худшем) случае.
                                                                        • 0
                                                                          Если у Вас хеши паролей — это степени двойки, то Вы пользуетесь либо очень странными паролями, либо очень странной хеш-функцией.
                                                                          Для «хорошей» криптографической хеш0функции на «нормальных» входных данных результат распределен более-менее равномерно. Что дает нам O(log log N) запросов.
                                                                          Как Вы думаете, стоит ли попробовать сделать топик, в котором будут сравниваться разные способы решения этой задачи?
                                                                • +5
                                                                  Как только увидел название и еще не видел содержания поста сразу понял:

                                                                  1) что данные отсортированы
                                                                  2) что непонятно зачем упоминать php :)
                                                                  • 0
                                                                    Убрал «PHP» из заголовка. Конечно же, такой поиск можно сделать на любом языке, просто здесь он осуществляется именно через PHP скрипт, не используя ничего дополнительного.
                                                                  • 0
                                                                    С CDB не сравнивали ваше решение?
                                                                    • –1
                                                                      У меня есть предположение, что CDB уже устаревшая технология, которая мало где используется, тем более для больших объемов данных.
                                                                      Напишите, если это не так.
                                                                      • 0
                                                                        Это не так. Чтобы технология устарела, ей что-то на замену прийти должно. Вы знаете что-то более быстрое?
                                                                        • –1
                                                                          Увы, не доводилось использовать CDB, поэтому не могу сравнивать и говорить про скорость.
                                                                          Есть у Вас есть ссылки на сравнительные тесты с другими БД, и информация о том, где её лучше использовать — это будет интересно посмотреть.
                                                                          • 0
                                                                            Да она простая очень, вот почитайте: cr.yp.to/cdb.html
                                                                            Там же есть стоимость операций, посмотрите, станет всё понятно.
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                      • 0
                                                                        А вы уверены что SQLite такой быстрый?)
                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                          • +4
                                                                            Alexey Pechnikov. подсказывает, что SQLite поиск по хэшу выполняется со скоростью порядка десятков тысяч операций в секунду на БД размером в 100 Гб на десктопе уровня коре квадро.
                                                                            Цитирую письмо:

                                                                            Надо было так:

                                                                            CREATE VIRTUAL TABLE t USING fts4(hash TEXT, password TEXT);

                                                                            Искать как:

                                                                            select * from t where hash math '...';

                                                                            Смысл в том, что fts4 использует индексное мультидерево и нет деградации скорости вставки на больших таблицах, при сохранении высокой скорости поиска. Впрочем, даже при обычном индексе на поле хэша вы должны были получить быстрый поиск и медленную вставку, но никак не медленный поиск. Попробуйте взять мою сборку эскулайт
                                                                            sqlite.mobigroup.ru/home

                                                                            Тест поиска (на нетбуке) можете посмотреть здесь
                                                                            geomapx.blogspot.com/2010/01/sqlite-fts3.html
                                                                            Вот здесь есть тест с генерацией БД, для изучения скорости вставки
                                                                            book.mobigroup.ru/dir?ci=c9fc797c01deb246&name=web_project_DBMS/distributed_schema
                                                                            См. файлы perftest_log_* с результатами теста на разных носителях.
                                                                            • 0
                                                                              ≈4½ года спустя я наткнулся на этот комментарий и оставляю к нему исправление: в письме Печникова весьма вероятна опечатка, так как в пособии по употреблению FTS3 и FTS4 кодовым словом служит не «math», а «match».
                                                                        • +1
                                                                          Интересно, а много нашлось таких, кто решили проверить свои пароли, а для получения хэшей воспользовались этим же сайтом, который вполне мог добавить в словарь (базу) их пароли?
                                                                          • 0
                                                                            Моя реализация не позволяет быстро добавить в существующую базу новые пароли (http://habrahabr.ru/blogs/php/127569/#comment_4212877), поэтому они нигде не сохраняются.
                                                                          • 0
                                                                            закончил читать после сообщения о том, что в тотал коммандере нельзя разбить файл с точностью до байта.
                                                                            • 0
                                                                              Действительно, ошибся. Не помню, как так пробовал, но сейчас получилось :)
                                                                              • +1
                                                                                Экий вы перфекционист. Человек либо прав во всём, либо во всём ошибается?
                                                                              • –1
                                                                                Хa! Уже в который раз на Хабре сталкиваюсь с упертыми людьми (в комментариях), которые в подобных случаях предлагают бинарный поиск. Видимо, в вузах дальше него ничего не изучают. Бинарный поиск отнюдь не хорош, так как требует постоянных вызовов fseek() и дерганий головкой HDD. А при реализации в памяти — требует громоздкую уродливую структуру с кучей указателей (кто любит указатели?). По моему, это какая-то устаревшая структура данных из 60-х.

                                                                                В данным случае (поиск по огромному количеству хешей) надо использвоать хеш-таблицу. Эта замечательная технология, например, применяется в не менее замечательном PHP. Она позволяет рещить задачу, используя только 2 вызова fseek64() и чтение порядка 8 Кб данных. Естественно, с этим примитивным бинарным поиском такого никогда не достичь.

                                                                                Реализуется она примерно так:

                                                                                1) определяем нужный нам объем индексного файла. У нас был 190 Гб файл с паролями+хешами, значит там примерно 5 млрд. паролей. Пусть на 1 entry в индексе приходится в среднем 300 паролей (они займут как раз что-то оклоло 4-8 Кб — пара секторов на диске) — значит нам нужен индекс на 16 млн значений (16M * 300 = 5 млрд).

                                                                                2) придумываем хеш-функцию hash(), которая из 32-символьного хеша делает 24-битное значение. В данном случае эта функция простая: просто берем первые 24 бита хеша (первые 6 символов):

                                                                                hash(«1234006f7865...») -> 0x123400

                                                                                3) В индексный файл (index) пишем подряд 6-байтные оффсеты в файле с паролями для каждого хеша:

                                                                                offset_000000 (смещение, по которому хранится блок, а в нем все пароли, с хешами начинающимися на 000000)
                                                                                offset_000001 (то же для хешей с 000001)

                                                                                offset_ffffff

                                                                                Размер индексного файла получается 16 Mb * 6 = 96 Mbytes

                                                                                4) Разбиваем пароли на блоки, в каждом блоке пароли, хеши которых начинаются с одних и тех же 6 символов.

                                                                                5) Ну и в файл с паролями (data) пишем эти блоки (длина блока + magic number + содержимое): либо разделенные символом \0 пароли, либо структуры(длина пароля + пароль), либо пароли с хешами (чтобы не вычислять эти 300 хешей).

                                                                                Для поиска достаточно сделать следущее:

                                                                                Берем первые 6 символов хеша, преобразуем их в unsigned long:

                                                                                hashOfHash = getFirst24bit(hash)

                                                                                Делаем fseek() в индексном файле на hashOfHash * 6 (размер поля offset_*). Читаем оттуда 6 байт — это смещение блока в основном файле (data), где хранятся пароли, хеши которых начинаются с этих цифр. Читаем блок (он должен быть порядка 4-8 Кб, так что можно сразу читать 8 Кб, и если блок длиннее, читать вторым запросом остальное).

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

                                                                                Автор, не хотите попробовать реализовать?

                                                                                И да, кстати насчет сортировок и разбиений файлов: если бы вы использвоали linux, то обнаружили бы что там есть и средства для сортировки больших файлов, и для разбиения. Все это давно написано и оттестировано, и всяко лучше самодельного велосипеда.
                                                                                • +1
                                                                                  [sarcasm]Ха! Уже в который раз на Хабре сталкиваюсь с людьми, уверенными, что хеши — панацея от всего и вся[/sarcasm]
                                                                                  Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.
                                                                                  Уродливым он выглядит только будучи написанным криво. Посмотрите, например, реализацию в вики — она проста и прекрасна.

                                                                                  Нет, хеши сильны. Очень сильны. На практике, если против нас не работает Мерлин, они во многих случаев действительно лучше чем что бы то ни было другого.

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

                                                                                  Кроме того, не забываем про специально придуманные для работы с внешней памятью B-деревья.

                                                                                  Если будет время и будет не лень — попробую аккуратно написать все варианты:)

                                                                                  PS. А SSD не решают проблему дерганья головки?
                                                                                  • 0
                                                                                    > Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.

                                                                                    Ага, только это будет 24 операции seek и 24 чтения из разбросанных по всему диску местам, против 1 seek и 1 чтения из индекса в моем случае. SSD уменьшает время поиска, но алгоритм все равно остается неэффективным из-за ненужных лишних чтений. Хеш-таблица в данном случае — оптимальное решение.

                                                                                    В данном случае хеш-таблица требует в разы (в 24 раза?) меньше операций поиска и чтения. Хеш-табица, правда, отличие от дерева, не позволяет делать сравнения по диапазону (>/
                                                                                    • 0
                                                                                      И еще хеш-таблица (в предложенном Вами варианте) обладает очень медленным временем добавления. Если мы хотим уметь добавлять данные — то дерево — единственный выход.
                                                                                      • 0
                                                                                        Ну насчет добавления данных (в определенных пределах) — можно извратиться, например при добавлении пароля в блок, дописывать этот обновленный блок в конец data-файла, менять 1 оффсет этого блока в индексе, а старый кусок блока помечать где-нибудь как свободную память. Индексный файл расти не должен, расти будет только data-файл. Ведь и с деревьями не все так просто, их надо балансировать, а каждая операция перестановки вершин требует обновления в 2 участках файла, которые, скорее всего будут в разных секторах диска, а таких операций надо иногда делать отнюдь не одну.

                                                                                        Но все же хеш таблицы в той же MySQL не используют (для диска) — видимо, есть какая-то причина. Или просто реализовать было лень?
                                                                                  • +1
                                                                                    Думаю лет через 5-10 твердотельные накопители будут преобладать над дисковыми.
                                                                                    И бинарный поиск не будет таким уж накладным на уровне обращения к дисковой памяти.
                                                                                  • +3
                                                                                    > Я написал на C# простенькую утилиту, читающую исходный файл по байтам и складывающую их последовательно в отдельные файлы заданного размера.

                                                                                    На что только не идут люди, чтобы не пользоваться юниксовыми утилитами… MSYS принесет столько чудных открытий!
                                                                                    • –1
                                                                                      На PHP есть проецирование файлов в память?
                                                                                      • +1
                                                                                        Проецирование файлов в память это ведь не средство языка, а механизм операционной системы. У PHP другие задачи, по сравнению с другими языками.
                                                                                        • 0
                                                                                          Ну да, неверно выразился. Я имел ввиду возможна ли эта операция средствами стандартной библиотеки? Проецирование файлов в память никогда лишним не будет. Даже в .NET наконец-то сделали))
                                                                                          • 0
                                                                                            Неужели ранее нельзя было вызывать CreateFileMapping и сопутствующие из WinAPI? Ничего не путаете?
                                                                                            • –1
                                                                                              Можно было из WinAPI, но сейчас это стало удобнее.

                                                                                              Все операции с файлами тоже можно осуществлять через WinAPI, но в разы удобнее использовать потоки .NET.
                                                                                              • 0
                                                                                                Понял, само собой согласен. Просто «даже в .Net наконец-то сделали» предыдущего автора звучит несколько удивительно, будто раньше этим пользоваться было невозможно.
                                                                                      • +1
                                                                                        В арсенале Windows, как ни странно, такой утилиты нету. В тоталкомандере нельзя разбить по байтам, а мне нужна была точность.
                                                                                        Я написал на C# простенькую утилиту, читающую исходный файл по байтам и складывающую их последовательно в отдельные файлы заданного размера.

                                                                                        OMG, только не велосипед!

                                                                                        качаем Win32 порт coreutils в котором есть
                                                                                        split: split a file into pieces

                                                                                        впрочем, там полно и других не менее полезных консольных утилит, заимствованных из GNU
                                                                                        • 0
                                                                                          Проще написать утилиту на C, которая будет заниматься темже самым, прописать ей нужные права и запускать с параметрами из php.
                                                                                          • 0
                                                                                            Вам проще на С. Я бы мог написать под ASP.NET или Mono. Не суть.
                                                                                            Этот комментарий полностью отражает то, что я хотел показать в топике.
                                                                                          • 0
                                                                                            не пробовали реализовать на Google Go?
                                                                                            • 0
                                                                                              А чтобы перебор не помог нало использовать bcrypt и солить его SHA-512 в несколько итераций, чтобы генерирование нужного хеша занимало, ну, например полсекунды.
                                                                                              Пароли надо ШИФРОВАТЬ а не хешировать, хэширование рассчитано на быстрое вычисление хэша, а нам как раз этого и не надо.

                                                                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.