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

Question

[Алексей Солодкий]

i.imgur.com/fTwGNcc.png
есть список сайтов (10млн)
и список ключей (40млн)
у каждого сайта есть ключи. У сайта на скрине их 500к
таблица конкурентов конкретного сайта это все сайты которые пересекаются ключами с данным. Отсортированные примерно по количеству этих самых пересечений/общее количество ключей сайта.

Необходимо иметь возможность быстро получать такие таблицы. (постранично)

Основная проблема объём данных.
Таблица большая (736к) имеет пагинацию и сортировку по любому параметру.

Интересует скорее подход чем конкретное решение. Я думаю что mysql на этой задаче сляжет. Что может подойти?
Как можно делать такие выборки за приемлемое время (10 сек)?
Возможно графовые бд? Или может хватит обычной реляционной базы?

Answer 1

[Дмитрий Энтелис]

imho правильно смотреть и думать в сторону hadoop & mapreduce

Comments

[lega]

Как вы на мап-редьюс предлагаете решать данную задачу? Он не для этого.

Answer 2

[lega]

Можно попробовать sphinxsearch (или эластик), он ищет с сортировкой по релевантности, т.е. сверху будут наибольшие пересечения ключей, но он может сильно задуматься если там много пересечений.
Либо попробовать сделать обратный индекс с сортировпнными сайтами, за один проход вычислять пересечение по сайту, все сайты раскидать по нодам, результат скидывать в БД для сортировки.

Сколько в среднем ключей у сайта?

Comments

[Алексей Солодкий]

Максимально до 500к (хотелось бы чтобы максимальный вариант хорошо отрабатывал а не средний.)
Пересечений там много. И сайтов самих тоже много.
>Либо попробовать сделать обратный индекс с сортировпнными сайтами, за один проход вычислять пересечение по сайту, все сайты раскидать по нодам, результат скидывать в БД для сортировки.
Поясните этот вариант.

Я думал о том чтобы вычислить один раз процент конкурентности для каждой пары сайтов. Но это таблица 60м х 60м записей

[lega]

> Максимально до 500к (хотелось бы чтобы максимальный вариант хорошо отрабатывал а не средний.)

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

> Поясните этот вариант.

Возможно без обратного индекса будет лучше, если пересечений очень много, я бы попробовал так: сделать базу где все имена перевести в числа (keyvalue хранилище), далее сделать либу на C/C++ в которой реализовать загрузку и поиск, храним массив data[site_id] = [key3, key5] где ключи отсортированы, таким образом вес сайта можно вычислить за один проход, собираем результат сортируя. Возвращаем результат.

Если медленно - 2 улучшения:
1) Разбить все сайты на 10 (или более) кусков и раскидать на 10 ядер (машин), в теории ускориться в ~10 раз, делать запрос параллельно, собирать результаты и мержить.

2) Если пересечения не сильно большие, то можно использовать обратный индекс, это позволит не перебирать все сайты, а только те в которых есть ключи.

> Таблица большая (736к)
Я правильно понял что это результат по одному сайту?

[Алексей Солодкий]

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

Получается струткра размером ~ 10 млн на 250к. А это слишком много даже для одного прохода.
+Ловим проблему с тем что после получения результатов (700к сайтов) с ними нужно строить таблицы.
В прочем я думаю это можно решить записав результат во временную mysql таблицу-кеш. И делать сортировки уже по ней. Потом её удалять.
Но это проход по 2.5 миллиардов элементов + выгрузка 700к в базу. Мне кажется что даже деля на 10 серверов мы не успеем это обработать за минуту.
(когдя я писал олимпиады на паскале цикл из 1-5млн элементов обрабатывался за секунду. Не думаю что с тех пор производительность систем изменилась на несколько порядков)

[Алексей Солодкий]

>> Таблица большая (736к)
>Я правильно понял что это результат по одному сайту?
Да конечно

[lega]

> Получается струткра размером ~ 10 млн на 250к. А это слишком много даже для одного прохода.
10млн х 250к х 4b = 2300Gb, да и памяти не хило занимает.

На счет прохода, сейчас попробовал перебор, у меня ноутбук на одном ядре перебирает более 2000млн/сек, т.е. 8 ядерный сервер можно прикинуть ~32Gi/sec, 2500/32 = 78 сек полный перебор на одном сервере, хотя реальный код может быть сложнее.

Тут ещё вопрос, где вы столько рам возмете? это не дешево, а на диске хранить не вариант.

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

[Алексей Солодкий]

Вы с графовыми бд не работали? Мне почему-то кажется что эта задача на них должна лечь.

[lega]

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

Answer 3

[Алексей Лихачев]

несовсем понимаю сути проблемы, но если у вас запросы корректные, то есть все нужные вам данные сразу выдает БД, без дополнительной логики кода и вы используете пагинацию (скажем запрашиваете для 1 страницы 100 строк) то все и так будет выполняться за приемлимое время, если нет, то проверьте используете ли вы индексы при запросах