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

Question

[Алексей Сундуков]

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

Два основных условия:
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?) и кто что использует.

Comments

[sim3x]

Какое железо?

[Алексей Сундуков]

sim3x: Как я понимаю CPU этот ark.intel.com/ru/products/82765/Intel-Xeon-Process... + 64ГБ ОЗУ, диск ark.intel.com/ru/products/75684/Intel-SSD-DC-S3500...

А у вас какое ПО?

[sim3x]

Алексей Сундуков: помещается ли БД целиком в память?

[Алексей Сундуков]

sim3x: Со всем мусором база занимает что-то около 4Гб. Т.е. да, вся в память заходит. Но это не принципиально как мне кажется, т.к. для текущей задачи есть тупо множество ID представляющих собой unsigned 32-ый int. Если загонять их в Redis (по схеме: ключ "tagId.ID_тега" (например "tagId.100"), значение SET в котором ID документов связанных с этим тегом, т.е. ID документа дублируется много раз), то получается что-то около 2,5Гб.

[sim3x]

Алексей Сундуков:
Тогда стоит покрутить настройки своей субд
Посмотри таблицы-индексы-медленные запросы, как работают твои запросы

Не будем пока про редис думать - тут есть много накладных расходов и деталей
Пока субд целиком помещается в память -- нужно оптимизировать ее

[Алексей Сундуков]

sim3x: РУСБД как позывает практика тут не очень ложится... Возможно просто выбрал не правильный метод реализации... Структура на самом деле примитивная, только 2 поля: tagId и docId (это Mysql и тип unsignet int) . Просто таблица связей. 3 индекса, по каждому полю и один составной tagId+docId. Записей сейчас 3.6М. SQL запрос который бы вытащил ID по описанному фильтру я вижу примерно таким:

SELECT DISTINCT t1.docId FROM c_tag_doc t1
INNER JOIN
 c_tag_doc t2
ON
 t2.tagId IN(12357,18326,10273,10274,10275,10276,10277,10278,10279,10280,10281,10282,10283,10284,10285,10286,10287,12576,12577,12578,12579,12580,12581,12582,12583,12584,12585,12586,12587,12588,12589,12590) 
AND t1.docId = t2.docId

INNER JOIN
 c_tag_doc t3
ON
 t3.tagId IN(12357,18326,10273,10274,10275,10276,10277,10278,10279,10280,10281,10282,10283,10284,10285,10286,10287,12576,12577,12578,12579,12580,12581,12582,12583,12584,12585,12586,12587,12588,12589,12590) 
AND t2.docId = t3.docId

INNER JOIN
 c_tag_doc t4
ON
 t4.tagId IN(2001,2002) 
AND t3.docId = t4.docId

INNER JOIN
 c_tag_doc t5
ON
 t5.tagId IN(863,8000,8001,11131,11132,11222,11224,11225,11226,11307,14032,14697,18441,18442,18443,18571,18572,18573,18574,18576,18577,18578,18587,19185,19186,19226,19767,19799,19800,19801,19802,19803,19804,19805,19806,9010,9004,9005,9006,9009,9007,9008,9011,9013,14705,19172,19173,19174,19175,19176,19177) 
AND t4.docId = t5.docId

LIMIT 100

Он отрабатывает ~150 мс. А тут только 4 И. А есть фильтры где их до 10! Есть какой-то другой вариант организации такого фильтра?

[Алексей Сундуков]

sim3x: Нет, не так. IN по сути и есть OR. Кроме того изначальная задача совсем другая. Нужно "найти ID всех документов у которых есть (тег-1 или тег-500 или тег-N...) И (тег-20 или тег-30) И ...". Других вариантов кроме как join я не вижу. В общем в рамках РСУБД это плохо работает.

[Алексей Сундуков]

sim3x: Нет, так не работает. Первый же AND после IN приведет к тому, что результат будет нулевым. Ну банально потому, что после декартово объединения из FROM в получившийся таблице не будет строк у которых тег_ид содержит все IN. Т.е. вот даже ( ДокументТег.тег_ид IN (1) AND ДокументТег.тег_ид IN (2.) ) вернет пустой результат даже если будет документ (пусть ID=5) у которого тег 1 и 2 заданы, т.к. в результирующей таблице нет строки в которой док_ид=5 И тег_ид=1 И тег_ид=2. Это ключевой момент из-за которого приходится использовать JOIN в количестве штук равный количеству условий И. И чем их больше, тем сильнее деградируем по производительности.

[Алексей Сундуков]

sim3x: Комментарий "Важные уточнения к вашему вопросу вставляйте в само описание вопроса, а не в комментарии к нему." не понял. В вопросе, в описании все>/b> сформулировано. И про про И и про ИЛИ.

[sim3x]

Алексей Сундуков:
Попробуй
https://www.techonthenet.com/mysql/intersect.php

Дальше уже нужно курить explain по обоим запросам и смотреть, кому каких кешей не хватает

Есть варианты с временными таблицами, процедурами и просто функциями на сях
Но уже на базе постгреса

[Алексей Сундуков]

sim3x: В postgres ситуация такая же. На сях тоже делал на базе стандартной библиотеки (тупо дернув готовый код из описания), но все равно медлее, чем сфинкс. Другой минус, этот код еще нужно инфраструктурой обвязать. В общем отложил пока.

[sim3x]

Алексей Сундуков: я про написание кода для запроса внутри постгреса
https://www.postgresql.org/docs/8.2/static/xfunc-c.html

[sim3x]

Алексей Сундуков: ну и
"РУСБД как позывает практика тут не очень ложится."
рсубд - единственный инструмент у которого есть теоретическая и практическая база для такого рода вещей

[sim3x]

Алексей Сундуков: и хммм
похоже мускул не имеет интерсекта
dev.mysql.com/doc/refman/5.7/en/select.html

Я б подумал о переезде :)

[Алексей Сундуков]

sim3x: Не имеет, я в курсе. Про сишное расширение под постгри я конечно думал, но если чисто сишный код не может сделать пересечение N множеств (представляющих собой int) быстрее, чем сфинкс, то значит курить в сторону сишного расширения под постри рано. Я конечно понимаю, что наверное код не очень оптимальный и есть над чем подумать, но я не сишник поэтому своими силами не допилю. А поскольку задача в принципе не уникальная, я как-то надеюсь, что кто-то уже нечто подобное создал в виде готовой библиотеки. Вот и ищю.

[sim3x]

Алексей Сундуков: в постгресе есть нативный intersection
Сишное расширение понадобится уже когда исчерпаются возможности кеширования для клиентов

[igruschkafox]

Повеселили :))))
использую SQL 2014
две таблицы с разными документами по 300 миллионов каждая
по две таблицы для Архивных документов 200 миллионов строк каждая
используются промежуточные таблицы отношений документа к тегам

По заданным параметрам выбирается любой документ меньше чем за секунду
группа документов в пределах двух недель (неважно сколько документов) выбирается не более 10 секунд
максимальное время выборки всех документов по всем тегам 20 минут

сервер почти дно - 1 проц 8 ядер, 58 Гб оперативки, при этом на это сервере еще 32 базы активно используются (только диски хорошие)

Учите мат часть
- Секционирование
- Индексы
- Файловые группы
- Инмемори

База 4 гига :))))) у меня эта база 700 ГБ и таблицы более 100 Гб ничего так нормальненько, очень даже быстро выбирается :)

Уверен на других платформах тоже можно оптимизировать

Блин!
База 4 Гига - Карл ! ты слышишь 4 Гига Карл !!!!
(при вашей задаче одни индексы должны были весть хз сколько, у меня индексы весят больше чем данные в 1,5 раза)

[Алексей Сундуков]

igruschkafox для меня секунда это ОЧЕНЬ долго. (А еще у меня MySQL). Фильтр должен отрабатывать максимум за 50 мс. В примитивной таблице в 2 поля (которые int-ы) tagId, docId накосячить довольно сложно. И записей там всего лишь на 4М. Вроде все просто. И работает. Только в нужно мне контексте слишком медленно. Сколько времени у вас в базе уходит на ответ на вопрос "найти id документов в которых есть (тег-1 или тег-2 или тег-10) и (тег-100 или тег-200 или тег-300 ...) и ...", т.е. по сути банальный IN() and IN() and IN()... при этом в такой выборке минимум пару тегов связаны более чем с 100к документов. Пусть в IN будет до 10 тегов, и таких условий максимум тоже 10. Как выглядит запрос и сколько он выполняется?

Про секционирование я в курсе. Вот хочу сделать на Postgresql через наследование таблиц.

Answer 1

[Алексей Сундуков]

Оставлю как ремарку для истории. На данный момент схема в sphinx получается самой быстрой. Вопрос с дельта индексом решился просто более частым его пересчетом. Теперь приложение следит за его размеров и как только в нем больше 20к документов, запускается ротирование. Получается требуемая быстрота выборки даже на сложных запросах.

Comments

[Сергей Еремин]

А обязательно получать ВСЕ? Всё же все равно сразу пользователь не прочтет. Можно получать каждый тег отдельно, а после AJAX-ом подтягивать и , если надо, сортировать на клиенте...

[Алексей Сундуков]

Сергей Еремин: Конечно все не нужны. Всегда нужна Х страница. И на клиенте ни чего сделать не получиться. В категории может быть 10к товаров их нельзя на клиенте отработать. Слишком долго. Я конечно понимаю, что разработчики сидят на хороших компах с большими мониторами. И у них 10к переварить со скрипом, но можно. В общем что говорить про клиент, эта задача чисто серверная и только там она и может быть решена. А аякс может лишь подтянуть результаты. Вот этот датасет для него и нужно получить.

Answer 2

[yspb]

В 4 версии редиски появилась возможность подключать внешние модули.
Например можно добавить поддержку JSON и roaring bitmaps:
https://github.com/RedisLabsModules/rejson
https://github.com/aviggiano/redis-roaring

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

Comments

[Алексей Сундуков]

Спасибо! Не видел еще этого. А самому щупать приходилось?

Сам недавно мельком опробовал схему с Postgresql и JSONB (таблица с товарами, одно из полей это JSONB в котором в массиве лежит список тегов) на 100к товаров у которых 10 характеристик (тегов). Сработало оччень даже неплохо, но нужно щюпать на сложной выборке и каталоге на 1М. Плюс по сравнению со Sphinx это согласованность данных (в индексе которого одно, а в базе уже немного другое).

[yspb]

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

127.0.0.1:6379> SETBIT aaa 4000000000 1
(integer) 0
127.0.0.1:6379> info memory
# Memory
used_memory:537721360
used_memory_human:512.81M

И я тоже отказался от битовых масок, хотя понимал что это самый быстрый способ.
С сжатием всё стало намного лучше + пишут что быстрее битовые операции в разы чем у обычных строк.
JSONB точно будет отставать

127.0.0.1:6379> R.SETBIT bbb 4000000000 1
(integer) 0
127.0.0.1:6379> info memory
# Memory
used_memory:850144
used_memory_human:830.22K

[Алексей Сундуков]

yspb как я понимаю пришлось из исходников собрать и сам redis сервер из unstable ветки?

[yspb]

Алексей Сундуков, redis server 4.0 уже stable, а модули из исходников. Модуль подключается в redis.conf через директиву loadmodule с указанием пути до полученного so файла.

[Алексей Сундуков]

yspb, дошли руки потестит. Впечатляет. Махнул сразу 15к тегов, 1,5М товаров, 20 тегов/товар (30М связей). Фильтр отрабатывает за ~2 мс, жрет 20Мб ОЗУ. Прямо какой-то космос. Буду перепроверять еще. Ну и параллельную нагрузку еще не тестил. Но в целом да, JSONB тут конечно даже близко не пройдет.

У себя в прод запиливали?

[yspb]

Алексей Сундуков, отличный результат! Редиска однопоточная, все параллельные запросы будут выполнятся последовательно, но очень быстро.
У меня пока объёмы меньше чем у вас, поэтому такой подход как из bfg по воробьям. Но если думать о highload, то запас просто огромный. И это single instance без всяких кластеров и балансировщиков.