Comments 36
sphinxsearch ?
К счастью, в большинстве языков програмирования есть замечательная функция seek()
Есть ещё mmap() с которой бегать по файлу несколько проще.
HDD диски не очень любят читать "назад"
Оно, конечно, ещё встречается (скажем, на моём домашнем ноуте), но на реальной рабочей машине...
Одни и те же позиции считываются многократно. А это плохо.
Дисковый кеш операционки не помогает?
странное сравнение, у вас подготовленные файлы, где есть сортировка по uuid и БД в которой индекс = номер, но поиск запускается по uuid.
Если попробовать, так (нужна БД которая имеет нормальную поддержку работы с uuid - Postgres)
CREATE TABLE hashes(
id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
val int
);и вот тут делать поиск по uuid.
Есть ещё mmap() с которой бегать по файлу несколько проще.
Лимитировано размером адресного пространства процесса. Хотя на 64-бит стало существенно проще. :)
1) Да, mmap() может быть быстрее, но с ней достаточно просто напортачить, так как она может менять не только данные в файле, но и любые данные за его пределами. К тому же возникнут сложности при многопоточности (у меня она реализована). Но вариант тоже неплохой.
2) Я уточнял, что это актуально для больших строк. Замедление происходит при переходе из одного блока (8КБ кажется) в предыдущий.
3) Кэш операционки сохраняет очень большие фрагменты - по 64КБ или 256КБ обычно. Учитывая, что он занимает по умолчанию до 10% оперативки, максимально удасться кэшировать 250000 - 60000 позиций при 16GB оперативной памяти. Но фактически меньше, так как он постоянно очищается.
А если писать функцию кэширования самому, размер кэша одной позиции будет 0.1 Кб, а значит можно будет хранить десятки миллионов позиций и искать по ним быстрее.
Я это сравнивал. Но ты прав, на небольших файлах и кэш операционки неплохо справляется.
так как она может менять не только данные в файле, но и любые данные за его пределами
Это как? Начнём с того, что файл вы вроде только читаете.
К тому же возникнут сложности при многопоточности
Опять же, какие проблемы с одновременным чтением?
Учитывая, что он занимает по умолчанию до 10% оперативки
Да может и почти всю. Вот у знакомого на домашнем сервере 64Gb на 32битной Windows (c PAE, естественно) с минимумом живых процессов, память в основном кеширует дисковые запросы.
Согласен, что мелкая гранулярность в самописном кеше позволяет более эффективно использовать память.
На самом деле, проще открыть в бинарном режиме 'rb' и читать не строки, а байты
Ну и конечно поиск сломается, если мы захотим найти первую строку
Вместо бин поиска тут больше подойдет алгоритм с золотыми сечениями, он как раз оптимизирует операции чтения
Тест несправедлив к базе данных. find_hashes_csv - это по сути один запрос, а база каждую итерацию вынуждена выполнять много оверхеда, типа парсинга SQL-запроса, обмен данными между процессами. И и со всем этим она умудряется работать лишь немного медленнее чем ваш алгоритм.
Предлагаю, справедливости ради, переписать тест для базы чтобы запросы отправлялись батчами.
Ты прав, у базы данных есть большое преимущество - накопление запросов. Если выполнять одновременно тысячи запросов, а не один, они выполнятся значительно быстрее.
Но для справедливости тогда нужно реализовать эту же фичу и в бинарном поиске, что тоже возможно - достаточно при поиске делить запросы на две части - левую и правую и выполнять рекурсивный поиск с каждой из этих частей.
Потом я, возможно, вроеду и такое сравнение.
Ещё можно попробовать что-то такое использовать.
Цитирую прорекламированный бот:
? Всё что вам нужно - отправить файл с электронными почтами и паролями боту.
? Файл может быть в одном из следующих форматов:
├ email:password
├ email;password
├ email password
└ email
Если интересно, то эта функция даёт только общий отчёт - сколько запросов найдено, а сколько нет. Я использовал её для класификации баз - какие уже добавлены, а какие нет, а так же собираюсь использовать это для бизнесовой части проекта - проверка всех аккаунтов какого-нибудь сайта на утечку.
И что бы было безопасно, бот будет получать только логины в виде хэшей, искать по ним, хэшировать полученные пароли с той же солью, что и на сервере и в таком виде пересылать обратно.
Одни и те же позиции считываются многократно. А это плохо. Если мы используем SSD, такой подход может изностить его со временем
Что? Где вы нашли ssd, который изнашивает чтение?
Хорошая попытка, но матчасть слабовата.
Во-первых, вам не нужен кэш - ОС и так кэширует данные с диска, причем сразу страницами по 4 КиБ.
Во-вторых, никак не обыгран readahead — когда программа читает с какого-то места в файле, ОС, разумно полагая, что чтение продолжится и дальше, читает не только то что запросили, а достаточно много сверх того (128 КиБ по дефолту в линуксе, емнип). То есть можно сикать по файлу так, чтобы в память поднималось по 64К сзади и 64К спереди, для пущей эффективности.
Там сверху упоминали mmap - может быть, работать так точно удобнее, но по факту скорее всего не быстрее, чем обычный файловый IO, а может быть и медленнее - надо бенчмаркать.
И да, ничего удивительного в том, что вы обыграли MySQL, ведь у вас hash_value - не VARCHAR, а TEXT (это очень неэффективный способ хранить строки), и индекс по нему - полнотекстовый, а не b-tree или какой там по дефолту :)
mysql 8.0+ (возможно даже так будет лучше)
CREATE TABLE hashes (
uuid BINARY(16) PRIMARY KEY,
value INT
);Кэш нужен, так как операционка кэширует большими блоками - по 64 или 256 килобайтов. А значит в кэш, который занимает не более 10% оперативки, влезет всего несколько десятков тысяч позиций. Если кэшировать только одну строку, это будет быстрее и влезут десятки миллионов позиций. Но для небольших файлов и кэша операционки хватит.
Про readahead - это скорее проблема, поищу потом способ это отключить. Но ты прав, можно и использовать в свою пользу. И кстати это ещё один аргумент за кэширование средствами программы.
А индекс по файлу у меня был не полнотекстовый, а именно бинарное дерево. Тест даже был не в пользу бинарного поиска, так как при поиске по файлу я использовал более сложный алгоритм, который искал не одно вхождение строки, а все, при этом без учёта регистра и с поддержкой лимита по количеству строк.
По поводу хранения в виде текста - в моём случае строки могут быть любой длины и varchar не подходит.
Я не знаю как в винде, боженька миловал, но в линуксе кэш занимает всю память :) и он там, несколько упрощая, тоже LRU. И если уж вы решили поработать со своим кэшированием, то возможно стоит поиграться вокруг O_DIRECT, потому что иначе все чтения все равно будут в пейджкэш подниматься
Про индекс вы правы, по TEXT может быть и обычный, я правда что-то не вижу длины индексируемого префикса в DDL, он там вроде обязательный. В любом случае spatial типы в мускуле - такое себе.
Поставил вам в карму плюс за стремление к изобретению велосипедов) Это очень полезное стремление, пользой от которого является, в основном, повышение скилов.
А вот за статью - минус. В основном, вот за это:
Бинарный поиск эффективно использовать тогда, когда данных много и в оперативнуюю память их вместить нельзя.
Прочтите это книгу, что бы не писать подобные, очень неверные (мягко говоря) вещи. Двоичный поиск эффективен как раз именно тогда, когда данные помещаются в памяти. Потому что ветвление тут всего 2. Для миллиона записей тут нужно будет 20 ветвлений, и до 20-ти чтений с диска, причем читается весь кластер на каждом чтении.
Для блочных устройств гораздо более эффективны сильноветвящиеся B-деревья. Они тоже описаны в этой книге. У них коэффициент ветвления может быть, например, 100. И чтений тут будет уже всего максимум 3. И базы данных делаются именно на них.
А есть еще и хэш-таблицы и другие структуры...
Почему ваши тесты говорят обратное?
Ну, например, на sql вы сделали две таблицы вместо одной. Одну - где кластерный индекс по id, а в листьях - hash_value. Вторую (индекс) - это таблица, где кластерный индекс по hash_value, а в данных - id. В итоге поиск идет в начале по одной таблице, а потом - по другой. Создайте таблицу в БД правильно, одну, с кластерным индексом по hash_value, это возможно в my_sql. Скорее всего, одного этого будет достаточно, что бы sql опередил ваш поиск.
Еще, скорее всего, вы читаете из дискового кэша и преимущество B-деревьев уменьшается. Попробуйте сбросить кэши перед тестом. Ну или увеличите количество записей, например, до миллиарда, что бы они не помещались в кэш.
Спасибо за конструктивную критику. Моей целью было не только сделать быстрый поиск, но и упростить добавление новых данных. В случае с деревьями, это конечно, тоже удобно, но если где-то напортачить, то файл с данными потом фиг разберёшь. В этом плане текстовый файл гораздо надёжнее. Да и добавлять данные в базу можно просто закидывая отсортированные текстовики в папку, никакая индексация не нужна. Изучу позже тему деревьев, я мало пользовался ими на практике.
По добавлению новых данных B-деревья так же далеко обходят двоичный поиск. Добавляется просто запись в блок (страницу), записывается один блок. Иногда происходит деление блока, записываются 3 блока (старый, новый, и уровнем выше). Иногда происходит расщепление и на более высоких уровнях, но это уже так редко, что можно пренебречь.
Почитайте этот том 3 Кнута, там все это есть. И двоичный поиск есть, и сравнение эффективности всех этих алгоритмов.
И предлагаю провести тест с такой таблицей:
CREATE TABLE hashes (
uuid BINARY(16) PRIMARY KEY,
value INT) WITHOUT ROWID;Здесь конструкция WITHOUT ROWID говорит sql lite, что не надо создавать свой ключ и отдельный индекс. Будет одна таблица с кластерным индексом по uuid. Объем данных должен сократится в два раза и ускорится поиск. Подозреваю, что тесты очень сильно изменятся. Причем с ростом количества записей SQL будет их извлекать почти с той же скоростью, а двоичный поиск тормозить все сильнее и сильнее.
Автор явно работает с какой-то очень простой структурой, и неясно - а зачем здесь вообще строки? Бинарная структура фиксированного размера уменьшит размер данных в несколько раз (что особо актуально при терабайтных размерах данных) и позволит сделать нормальный бинарный поиск.
Можно сделать свой индекс по файлу так, чтобы он помещался в памяти. 2.5 ТБ - это 2.5 миллиона мегабайтных блоков. Сначала вести бинарный поиск блока, а потом прочитать 1Мб блок в память и искать в нем.
В общем, результат в 20 rpc не особо впечатляет.
PS. Кэширование открытия файла??? Почему не открыть файл один раз и не передать его в функцию поиска?
PPS. Нелюбовь к SQL не разделяю. Надо еще разобраться - почему так медленно получилось? Если индекс в памяти - должно намного быстрее работать.
20 поисков в секунду на HDD это практически потолок, если не использовать зашкаливающие по сложности алгоритмы. 90% времени и так уходит на перемещение головки. При этом база у меня не одна, а разделена на 5 частей, в каждой из которых поиск происходит независимо, если слить будет 100 в секунду, но это сортировка 40 миллиардов строк, что долго.
Про кэширование файла - у меня файл не один, а примерно 10000 во всех базах. Тоже в алфавитном порядке. Примерно то что ты и предложил с блоками. Все файлы одновременно ты не откроешь да и толку от этого ноль.
20 поисков в секунду на HDD это практически потолок, если не использовать зашкаливающие по сложности алгоритмы. 90% времени и так уходит на перемещение головки.
Точно!
Количество чтений - это логарифм от количества записей. Основание логарифма - это коэффициент ветвления дерева. Для двоичного поиска он равен двум. А для B-дерева намного больше, обычно десятки. Именно по этому двоичный поиск целесообразно использовать там, где стоимость чтения невелика - в памяти. Для диска это плохой вариант.
20 поисков в секунду на HDD это практически потолок
Не потолок. Типичный HDD дает около 100-200 iops. Судя по скорости, сейчас у вас на один поиск расходуется, примерно 5-10 дисковых операций (реальных, а не вызовов чтения из программы).
Индекс на 40 млрд записей блоками по 64кБ (~1000 записей, оптимальный размер блока надо подобрать экспериментально) - это всего 40 млн блоков, информация о которых элементарно умещается в памяти. Т.е. на каждую операцию поиска будет тратиться ровно одна операция ввода-вывода, весь остальной поиск - в памяти. Это увеличит rps в 5-10 раз при условии, что все упирается в скорость диска. И реализуется такой велосипед совершенно несложно. Даже деревья не нужны, просто плоский сортированный список блоков в памяти, по которому проходим бинарным поиском...
При этом база у меня не одна, а разделена на 5 частей, в каждой из которых поиск происходит независимо, если слить будет 100 в секунду
А вы измерьте. Если узким местом являются операции ввода-вывода, то сильного прироста не получится. Немного можно выиграть разве что за счет более более глубокой очереди запросов к диску. Но это не достоинство алгоритма поиска.
В теории это всё хорошо. А на практике - ты когда-нибудь пробовал отсортировать 2,5TB данных? Я пробовал и предпочитаю тот алгоритм, в котором сложнее всего напортачить, что бы не пришлось всё переделывать. И я измерял скорости. Узкое место - ввод вывод, так как на SSD скорость выше на порядки. И большая часть времени уходит именно на челночный бег головки по диску.
Может это просто опечатка, но в тексте вы указываете что используете для теста MySQL, однако в коде у вас используется sqlite3. Чем вы это объясните?
<занудство>
Я один в первом абзаце увидел "расскажу как ускорить бинарный поиск в сотни раз", а в конце сравнение резульиатов менее чем в 2 раза? Понимаю, что не все рассказали, но хотелось бы получать то, что заявлено или тогда уже переформулировать, что "в конце цикла статей вы узнаете как ускорить бинарный поиск в сотни раз".
</занудство>
Так-с. Внесу немного свою лепту:
Предложение 1: Экономим место в СУБД
В СУБД ты можешь делать не create table mytable(hash text, password text); create index on mytable(hash);
Гораздо круче сделать так: create table mytable(password text); create index on mytable(md5(password));
Получается, что ты хэш будешь хранить только в индексе. Для поиска: `select from mytable where md5(password) = ?`
Предложение 2:
Если ты пользуешься всё-же поиском только одного единственного значения ( в том смысле, что не делаешь поиск нескольких хэшей одновременно), то рекомендую посмотреть в сторону хэш-индексов ( `create index on mytable using hash(md5(password))` )
То же самое можешь сделать и на уровне csv.
Поиск по хэшу идёт быстрее, но есть некоторые недостатки ( см ниже)
Предложение 3:
А вот если ты вдруг захочешь искать несколько строк ( представим на миг, что ты делаешь сервис по дэхэшированию):
Ты приятно удивишься, что поиск N значений разом идёт на много быстрее, чем N поисков по одному ( даже если убрать овертайм на запросы и т.д.)
Но при хэш-индексе ( и п.2) такая фигня не прокатит :)
В случае, если подобное захочешь делать с файлами - берёшь входной массив хэшей, сортируешь по возрастанию и делаешь поиск ( когда нашёл первый хэш, то второй 100% будет идти после него, соответственно `lef{i+1}> = mid{i}+1`
UPD: Интересно узнать, а конфиг СУБД был стандартный или ей разрешалось тоже забирать память из системы ?)
Велосипеды там, где они вообще не нужны.
Если вы пришли к тому, что пишете свою БД - то либо вы огромная корпорация, готовая отдать на это сотни тысяч крайне квалифицированных человеко-часов, либо делаете что-то не то.
Как ускорить бинарный поиск