alekciy
@alekciy
Вёбных дел мастер

Какие реализации могут быстро искать пересечение множеств (система тегов)?

Хотелось бы спросить, кто как решает задачу с поиском по тегам. Каким ПО.

Два основных условия:
1) Задача - система должна быстро (~1-50 мс) ответить на вопрос в духе "найти все документы в которых есть (Тег-1 или Тег-30 или Тег-100500 или ... ) и (Тег-50 или Тег-1000 или...) и ...". В ИЛИ может быть до двух десятков тегов, И условий может быть под десяток.
2) Поскольку данные могут часто обновляться, то нужно достичь минимального времени актуализации внесенных изменений.

Пробовал делать на Redis используя типы SET и BITMAP (примерно как тут "Быстрый фильтр каталога для интернет-магазинов на ..."). SET не подошел (в set-а хранились ID документов), т.к. в случае пересечения даже двух множеств по 100к думает дольше, чем требуется. BITMAP не подошел из-за сильной разряженности по ID документов, как следствие лишний расход памяти на "дырки". В общем если множества большие, то Redis из коробки подходит плохо.

Сейчас работает вариант на Sphinx. ID тегов пишутся в sql_attr_multi. Это обеспечивает заданное требование по скорости поиска документов. Требование обновлений решается построением главного и delta индекса. Основной индекс (по которому ведем поиск) объявлен как distributed. Это в принципе неплохо работает, но порой бывает много новых изменений и дельта индекс начинает тормозить. Перестроение главного индекса занимает несколько минут (сейчас что-то около 3.5М id документов в нем). Вроде не долго, но планируется увеличение количества документов в десятки раз. Время актуализации данных тоже начнет увеличиваться.

Хотел бы узнать, есть ли какие-то другие варианты решения (С? Tarantool? Elasticsearch?) и кто что использует.
  • Вопрос задан
  • 832 просмотра
Пригласить эксперта
Ответы на вопрос 2
alekciy
@alekciy Автор вопроса
Вёбных дел мастер
Оставлю как ремарку для истории. На данный момент схема в sphinx получается самой быстрой. Вопрос с дельта индексом решился просто более частым его пересчетом. Теперь приложение следит за его размеров и как только в нем больше 20к документов, запускается ротирование. Получается требуемая быстрота выборки даже на сложных запросах.
Ответ написан
@yspb
В 4 версии редиски появилась возможность подключать внешние модули.
Например можно добавить поддержку JSON и roaring bitmaps:
https://github.com/RedisLabsModules/rejson
https://github.com/aviggiano/redis-roaring

Последний уменьшает использование памяти разряженными bitmap.
Быстрее операций and, or и xor битовых масок ничего не может быть.
Я думаю такой же механизм сжатия используется и в Sphinx.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Альфа Банк Екатеринбург
от 80 000 руб.
SaveTime Москва
от 110 000 руб.
Университет ИТМО Санкт-Петербург
от 40 000 руб.
27 мая 2019, в 08:28
11111 руб./за проект
27 мая 2019, в 07:43
15000 руб./за проект
27 мая 2019, в 06:01
1000 руб./за проект