Комментарии 20
А я все ждал, когда же вы изобретёте btree индекс ;). В таком случае, почему сразу просто не залить таблицу в любую базу данных, которая умеет btree индексы и искать в ней? Если взять докер образ какого-нибудь постгреса весь проект уместится в 5 строчек на баше.
Как мне кажется, запускать докер с базой — оверкилл.
Кстати, а сколько будет вставляться весь набор данных никто не замерял?
Аналогично с поиском.
Было бы интересно увидеть порядок цифр.
Вставка такого объема одной транзакцией может не пройти без подстройки конфигурации, а несколькими транзакциями будет накладно для диска.
Но вот если взять libmdbx, то точно будет проще и быстрее.
Вполне возможно что в 10-100 раз быстрее постгреса и без докера.
SQLite3 очень шустро импортирует csv файл в пустую базу (в классическом режиме. С WAL тормозит). Тем более, если посортировать предварительно.
11ГБ в ту же монго это несколько МИНУТ работы, потом от силы час на создание индекса.
Искать будет в районе милисекунды.
Лучше расскажите сколько автор креатива реального времени убил на этот мусорный проект.
SQLite3
Сортированный файл, обьявленный как csv через встроенный импорт csv влетит пулей.
Менеджер паролей, который тянет за собой 12гб-ный файл (в будущем размер будет расти) или отправляет sha1-хеш (даже sha2 без соли отправлять — плохое решение) — сомнительные применения. Единственный практичный вариант — при регистрации на сайте этот сайт (на него пароль и так отправится) проверяет стойкость пароля. Но в этом случае правильнее использовать бд.
Когда-то работал с проектом, в котором пароли лежали без соли, сделали проверку стойкости паролей тупо по частоте появления хеша, правда очень быстро функцию пришлось отключить — у заказчиков фантазии для придумывания редких паролей (среди бд на пару млн. пользователей) не хватало.
У меня есть смутное подозрение, что можно сделать намного проще даже при недостатке памяти:
- Создать memory mapped file и доверить задачу загрузки/выгрузки в память и на диск операционной системе.
- Записать в него бинарные данные (11 гб — это немного).
- Отсортировать обычным алгоритмом типа quicksort — у него практически последовательный доступ к памяти (он идёт сначала и с конца массива), так что работать должно быстро.
- Отдельные хеши искать бинарным поиском.
- Если очень хочется скорости — пробежать по файлу и сделать табличку с адресами, чтобы по первой паре байт знать, между какими адресами искать нужный хеш.
- Альтернативный вариант для скорости — посмотреть, блоками какого размера грузятся файлы (допустим, 4кб) и для каждого блока сохранить хеш из его начала. Тогда можно будет за одно обращение к диску сказать, есть ли хеш.
Можно было пойти простым и эффективным путём — просто записать строки в LMDB, открыв базу данных с флагом MDB_NOSYNC. На Python это делается почти элементарно:
import lmdb
env = lmdb.open('dbenv', map_size=1024*1024*1024*32, sync=False)
for line in map(str.strip, open('file.txt').readlines()):
if line:
k, v = line.split(':')
with env.begin(write=True) as txn:
txn.put(k.encode(), v.encode())
env.sync()
Да, но на всякий — libmdbx быстрее LMDB на 10-20%
Нет биндинга для Python. Я уже несколько раз натыкаюсь на MDBX (и поставил звезду за труды), в связи с чем у меня два вопроса:
- За счёт чего получили ускорение на 20%?
- С какой версией LMDB проводили последний бенчмарк?
Нет биндинга для Python.
Какие-то биндинги для питона есть, но вне opensource. Сделать их по мотивам LMDB-шных достаточно просто. Но сам я питоном не пользуюсь, а на LMDB-шные были какие-то нарекания. Поэтому не стал делать лишнего (кому надо — тот сделает, а я добавлю ссылку).
За счёт чего получили ускорение на 20%?
Корректнее сказать "до 20%" быстрее, так как во многих тестах до 99.9% времени занимает обмен с диском. Тем не менее, примерно такие результаты фиксируется бенчмарками оценивающими скорость работы самого движка (например, при размещении БД в tmpfs). Аналогичные результаты буду при больших/толстых транзакциях (с множеством апдейтов), т.е. libmdbx тратит меньше тактов CPU внутри себя.
Получено ускорение за счет переработки реализаций внутренних компонентов (например, списка грязных страниц и т.п.) и микро-оптимизаций. Но никакого простого ответа дать нельзя, отличий очень много. В частности, в MDBX всегда работает автокомпактификация и используетcя madvise() — поэтому "в долгую" libmdbx всегда выигрывает (нередко в разы).
С какой версией LMDB проводили последний бенчмарк?
Для бенчмарков используется ioarena, субмодуль LMDB там установлен на версию 0.9.24. Однако, в LMDB очень давно не было каких-либо изменений влияющих на производительность (только исправление багов и течей памяти), т.е. разнизы не будет с любыми версиями за последние 2-3 года.
Если будут еще вопросы, то лучше задавать в телеграм-группе (создана на днях).
По сути это на один шаг больше, чем 256 файлов описанный в статье.
Это было бы 256 папок и 256*256 файлов.
Если grep занимал две минуты, то после такой реструктуризации по логике он будет занимать какие-то доли секунды. Содержимое файлов при этом сортировать не обязательно, они такие-же текстовые и грепаются.
bloom filter? Мне кажется, идеально подходит для первичного ответа "есть или нет".
Так как файл изначально сортированный, я вот думаю есть-ли какая-нибудь стандартная прога в Linux которая ищет в уже сортированном текстовом файле, с помощью двоичного поиска? Я помню писал что-то такое лет 20 назад, но вдруг есть готовое решение? Что предлагают на сайте? Думаю zfs этот файл хорошо сожмёт за счёт некоторой потери в скорости поиска. Update: Для поиска можно использовать look.
Ускорение поиска в Have I Been Pwned до 49 микросекунд (С++)