Pull to refresh

Comments 115

А тут что ох*енного, простите? То, что автор открыл для себя бинарный поиск? Даже школьники знают, что его сложность O(log n).
Я действительно не знал. Мне должно быть стыдно? Уже пол дня изучаю этот метод.
Да, если Вы не знали про двоичный поиск, то Вам должно быть стыдно.
Если бы меня кто то учил… Он мне просто не было нужен. По крайней мере я так думал.
Вас не учили логарифмам? Ну тогда вот вам еще одно откровение: поиск по массиву, размер которого равен количеству атомов во вселенной, потребует не более 266 операций сравнения. Даже на PHP.
По произвольному массиву? Что-то не верится.
По отсортированному массиву.
По неотсортированному — 2^266 операций на обычном компьютере, или 2^133 на квантовом.
Время сортировки еще учтите и тогда будет все нормально ;)
Время сортировки такого объема — около пары часов, не больше.
Есть даже специальные соревнования по такой дисциплине, как сортировка больших объёмов данных.
Ого!
Найдите компьютер, способный хотя бы хранить 2^266 бит информации — и весь мир у Ваших ног.
Да что вы накинулись? У меня специальность кинотехник, TimTowdy, давайте не будем, а? Если я не знал про бинарный поиск, не значит, что я не знаю ничего. Просто не сталкивался с этим.
А кто вообще говорил о 2^266 битах?
В статье — 70 гигабайт данных.
Метод половинного деления?
UFO landed and left these words here
То, что сам бинарный поиск существует, действительно знает любой прошаренный школьник.
Для себя я открыл бинарный поиск в больших файлах, без необходимости загрузки содержимого в память.
Называемый вами «бинарный поиск» имеет другое название, более точно его определяющее — дихотомический поиск.
Алгоритм такого поиска я писал на C# в консоли будучи студентом.
Интересно на сколько будут отличаться результаты, если все это дело переписать на Си
скорость Сишных программ в 5 раз быстрее ПХПешных
но если переделывать, то надо использовать не только другой язык, но и немного другие методы:

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

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

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

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

Да, добавление одного хеша в моем случае требует полной перегенерации. Это большой минус, хотя для статичных данных это может быть в тему.
В первую очередь, мне было интересно узнать, как будет происходить поиск в большом файле. Наверное, из-за этого и получилась так, как получилось :)
Можно было использовать 0 байт (лишь показуха) под все записи, расположив хеши в именах файлов в папке и используя поиск Windows Explorer)))
UFO landed and left these words here
Переходите на x64

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

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

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

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

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

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

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

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

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

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

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

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

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

Спойлер: O(N) в этом (худшем) случае.
Если у Вас хеши паролей — это степени двойки, то Вы пользуетесь либо очень странными паролями, либо очень странной хеш-функцией.
Для «хорошей» криптографической хеш0функции на «нормальных» входных данных результат распределен более-менее равномерно. Что дает нам O(log log N) запросов.
Как Вы думаете, стоит ли попробовать сделать топик, в котором будут сравниваться разные способы решения этой задачи?
UFO landed and left these words here
Убрал «PHP» из заголовка. Конечно же, такой поиск можно сделать на любом языке, просто здесь он осуществляется именно через PHP скрипт, не используя ничего дополнительного.
С CDB не сравнивали ваше решение?
У меня есть предположение, что CDB уже устаревшая технология, которая мало где используется, тем более для больших объемов данных.
Напишите, если это не так.
Это не так. Чтобы технология устарела, ей что-то на замену прийти должно. Вы знаете что-то более быстрое?
Увы, не доводилось использовать CDB, поэтому не могу сравнивать и говорить про скорость.
Есть у Вас есть ссылки на сравнительные тесты с другими БД, и информация о том, где её лучше использовать — это будет интересно посмотреть.
Да она простая очень, вот почитайте: cr.yp.to/cdb.html
Там же есть стоимость операций, посмотрите, станет всё понятно.
UFO landed and left these words here
А вы уверены что SQLite такой быстрый?)
UFO landed and left these words here
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_* с результатами теста на разных носителях.
≈4½ года спустя я наткнулся на этот комментарий и оставляю к нему исправление: в письме Печникова весьма вероятна опечатка, так как в пособии по употреблению FTS3 и FTS4 кодовым словом служит не «math», а «match».
Интересно, а много нашлось таких, кто решили проверить свои пароли, а для получения хэшей воспользовались этим же сайтом, который вполне мог добавить в словарь (базу) их пароли?
Моя реализация не позволяет быстро добавить в существующую базу новые пароли (http://habrahabr.ru/blogs/php/127569/#comment_4212877), поэтому они нигде не сохраняются.
закончил читать после сообщения о том, что в тотал коммандере нельзя разбить файл с точностью до байта.
Действительно, ошибся. Не помню, как так пробовал, но сейчас получилось :)
Экий вы перфекционист. Человек либо прав во всём, либо во всём ошибается?
Х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, то обнаружили бы что там есть и средства для сортировки больших файлов, и для разбиения. Все это давно написано и оттестировано, и всяко лучше самодельного велосипеда.
[sarcasm]Ха! Уже в который раз на Хабре сталкиваюсь с людьми, уверенными, что хеши — панацея от всего и вся[/sarcasm]
Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.
Уродливым он выглядит только будучи написанным криво. Посмотрите, например, реализацию в вики — она проста и прекрасна.

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

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

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

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

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

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

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

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

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

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

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

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

впрочем, там полно и других не менее полезных консольных утилит, заимствованных из GNU
Проще написать утилиту на C, которая будет заниматься темже самым, прописать ей нужные права и запускать с параметрами из php.
Вам проще на С. Я бы мог написать под ASP.NET или Mono. Не суть.
Этот комментарий полностью отражает то, что я хотел показать в топике.
не пробовали реализовать на Google Go?
А чтобы перебор не помог нало использовать bcrypt и солить его SHA-512 в несколько итераций, чтобы генерирование нужного хеша занимало, ну, например полсекунды.
Пароли надо ШИФРОВАТЬ а не хешировать, хэширование рассчитано на быстрое вычисление хэша, а нам как раз этого и не надо.
Only those users with full accounts are able to leave comments. Log in, please.