Как проверить Теорию 6 рукопожатий в БД с миллионами юзеров?
Есть таблица со списком людей, есть many-to-many таблица с "дружбой" между одним и вторым, людей миллионы, связей у каждого до 5к
Как проверить, что один юзер может быть дальним другом второго за 6 связей, чтобы это можно было посчитать в реалтайме? Перебором в лоб явно не получится: число запросов уже на второй связи сильно возрастает. Кешировать какие-то отдельные кусочки графа для каждого юзера так же накладно, как и считать полным перебором
Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?
Или может для друзей есть какая-то более интересная архитектура БД, в которой это можно решить проще
если задача "чисто математическая" то вариант 1 - перебор. естественно не "в лоб" а путем построения b-tree
если же брать реальный контакт, то там данные довольно сильно кластеризованы. и рост не будет экспоненциальным. особенно после отсева мусора (коллекционеров друзей). и тут можно применять уже какие-то вероятностные методики для ускорения.
Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?
Если я не ошибаюсь, то такого не было (вернее читай последний абзац)
Рекомендуемые друзья явно не далее 6 рукопожатий, скорее сильно меньше, вероятно 1-2.
И если действительно 1-2, то таких друзей можно объединить в какой то один кластер. Круг людей между собой не связанный никак будет следующим кластером. И таких кластеров несколько.
Каждый кластер можно разделить на подгруппы, например один город или учебное заведение...
Я думаю, что система явно не берет тупо всех просчитывать, а ориентируется сначала на первое звено , затем на последующее в цепочке кластеров...
Пару лет назад ВК выкатил такую функцию и там всё работало мгновенно (>40 млн юзеров), стало интересно: как они это сделали?
Такое было относительно недавно, 9-12 месяцев назад в отдельном приложении и там за объекты брались не рандомные люди, а знаменитости и Юзер, а это уже существенно меньше запросов, и вероятно перед выкладкой приложения - все вычисления были сделаны заранее, тем более кто проверит то)
Взяли сотню человек и нашли друзей друзей, это не про всех, а это уже проще считать
Поскольку это задача из теории графов - то и решать ее нужно на языках разработки и библиотеках поддержки графов. 1 млн узлов графа - это не много для современной памяти.
1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же:
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись
3 запроса, таблички теоретически большие, практически - все это перемалывается без проблем.
Простой
