Задачка на сообразительность, как решить?

Question

[Александр]

Дано:
Миллион тегов
Миллион пользователей
Каждый пользователь может выбрать несколько любых тегов, тем создав из них уникальную группу и подписаться на эту группу

Задача:
Когда создается контент например с n тегами, надо найти все группы которые можно скомбинировать из этих n тегов в количестве от 2х до n соответсвенно, и отобрать всех пользователей у которых совпали группы

Какие подходы, алгоритмы сортировки и тип базы данных использовать для оптимизации вычислений?

Comments

[Zhainar]

а в чем проблема? таблица многие ко многим и индексы.

[Александр]

В том, что я не знаком с тем как такое решается, спасибо за предложение, буду гуглить

[Александр]

Dr. Bacon, откуда вы взяли ваше "то есть"?
Мне надо оптимизированный фильтр написать для большой выборки, а не перебирать все "в лоб", как вы советуете

[Александр]

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

Answer 1

[Сергей Водаков]

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

update:
Кажется я понял.
Создаете таблицу подписок (subscribers) вида: user, tag
Далее, делаете выборку из этой таблицы, примерно так:

SELECT user, count(tag) as tagcounter
FROM subscribers 
WHERE tag IN (%taglist)
GROUP BY user
HAVING tagcounter>1

где %taglist - список тегов статьи

Comments

[Zhainar]

не сработает на подмножестве тегов

[Александр]

Возможно я не совсем точно сформулировал.
Контент может содержать например 10 тегов, а группа тегов у пользователя например содержит только 3 из этих 10, а не все 10 из 10 одинаковые

[Сергей Водаков]

Александр, тогда рассмотрим граничные случаи:
Что если группа тегов у пользователя состоит из 4х тегов, 3 из которых входят в множество тегов контента?
(перечитал ваш вопрос, если правильно понял, то вам надо делать рассылку всем, у кого минимум 2 тега соответствуют статье)

[Александр]

Сергей Водаков, верно

Answer 2

[Dimonchik]

Миллион тегов
Каждый пользователь может подписаться на любую группу из тегов

в IRL такого не будет

Миллион пользователей

да и такого может не быть, если не боты

Comments

[Александр]

Да более-менее популярный ресурс, соц сеть

[Dimonchik]

ну тегов не наберется, если не по фио тегать

[Александр]

ну это условности, язык тоже не один

Answer 3

[Иван Шумов]

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

Comments

[Александр]

А можно подробнее какие архитектуры искать на ютубе, как уведомления слать то понятно, вопрос как найти кому слать

[Иван Шумов]

Александр, ну, логику продумывать надо) а очереди это такая очень жирная подсказка.

Искать на английском ибо в русскоязычном сегменте в основном не опытные недопередевы с огромным самомнением

[Александр]

Мм, спасибо за подсказку, я попробую поискать в этом ключе, но пока слабо понимаю как очередь может помочь, она в таком случае просто будет копиться и решаться пропускной способностью сервера, а хочется то как раз снизить вычислительную нагрузку, возможно я не понимаю контекста, я переформулировал еще раз немного вопрос, может мы все же немного про разное?

[Иван Шумов]

Александр, проблема в том что в синхронный запрос такой вычислительный объем ты, скорее всего, не засунешь и придется проверять все по списку. А это значит что надо как-то гарантировать выполнение и не рассчитывать на какие-то точные SLA по времени обработки. Вот там и событийная система

[Александр]

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

[Иван Шумов]

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