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

Question

[FlameArt]

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

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

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

Comments

[Antonio Solo]

если задача "чисто математическая" то вариант 1 - перебор. естественно не "в лоб" а путем построения b-tree

если же брать реальный контакт, то там данные довольно сильно кластеризованы. и рост не будет экспоненциальным. особенно после отсева мусора (коллекционеров друзей). и тут можно применять уже какие-то вероятностные методики для ускорения.

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

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

[Антон]

Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?

Если я не ошибаюсь, то такого не было (вернее читай последний абзац)
Рекомендуемые друзья явно не далее 6 рукопожатий, скорее сильно меньше, вероятно 1-2.
И если действительно 1-2, то таких друзей можно объединить в какой то один кластер. Круг людей между собой не связанный никак будет следующим кластером. И таких кластеров несколько.
Каждый кластер можно разделить на подгруппы, например один город или учебное заведение...
Я думаю, что система явно не берет тупо всех просчитывать, а ориентируется сначала на первое звено , затем на последующее в цепочке кластеров...

Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?

Такое было относительно недавно, 9-12 месяцев назад в отдельном приложении и там за объекты брались не рандомные люди, а знаменитости и Юзер, а это уже существенно меньше запросов, и вероятно перед выкладкой приложения - все вычисления были сделаны заранее, тем более кто проверит то)
Взяли сотню человек и нашли друзей друзей, это не про всех, а это уже проще считать

Answer 1

[Dimonchik]

графовая БД

neo4j - самая известная
ArangoDB - вам подойдет

Answer 2

[mayton2019]

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

Из java библиотек есть Guava, Jung, GraphT.

Answer 3

[Александр Ворона]

Книга Дауни А. - Изучение сложных систем с помощью Python - 2019
Глава 3. Графы «Мир тесен»

Answer 4

[Ndochp]

1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же:
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись

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

Answer 5

[DDwrt100]

Выбрать правильный инструмент. В данном случае выгрузить данные в графовую базу данных. И в ней обсчитывать подобную задачу.

Answer 6

[Developer]

По-моему, у Дональда Кнута рассматривалось решение этой задачи.