Как проверить Теорию 6 рукопожатий в БД с миллионами юзеров?

Есть таблица со списком людей, есть many-to-many таблица с "дружбой" между одним и вторым, людей миллионы, связей у каждого до 5к

Как проверить, что один юзер может быть дальним другом второго за 6 связей, чтобы это можно было посчитать в реалтайме? Перебором в лоб явно не получится: число запросов уже на второй связи сильно возрастает. Кешировать какие-то отдельные кусочки графа для каждого юзера так же накладно, как и считать полным перебором

Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?
Или может для друзей есть какая-то более интересная архитектура БД, в которой это можно решить проще
  • Вопрос задан
  • 771 просмотр
Пригласить эксперта
Ответы на вопрос 6
dimonchik2013
@dimonchik2013
;)
графовая БД

neo4j - самая известная
ArangoDB - вам подойдет
Ответ написан
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
Поскольку это задача из теории графов - то и решать ее нужно на языках разработки и библиотеках поддержки графов. 1 млн узлов графа - это не много для современной памяти.

Из java библиотек есть Guava, Jung, GraphT.
Ответ написан
Книга Дауни А. - Изучение сложных систем с помощью Python - 2019
Глава 3. Графы «Мир тесен»
Ответ написан
@DDwrt100
Выбрать правильный инструмент. В данном случае выгрузить данные в графовую базу данных. И в ней обсчитывать подобную задачу.
Ответ написан
samodum
@samodum
Какой вопрос - такой и ответ
По-моему, у Дональда Кнута рассматривалось решение этой задачи.
Ответ написан
@Ndochp
1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же:
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись

3 запроса, таблички теоретически большие, практически - все это перемалывается без проблем.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы