Как Facebook может заказать друзей по общему количеству друзей?

Question

Facebook имеет возможность заказывать пользователей (например, в поиске) по общему количеству друзей.Другой пример - поиск друзей.Порядок более или менее одинаков.

Мой вопрос: как они могут отслеживать общее количество друзей, поскольку у вас есть друзья друзей?Как они могут заказать друзей за такое короткое время?

Если мы просто предположим, что у каждого пользователя есть 100 друзей, просто это в худшем случае означало бы, что для каждого человека должно быть n ^ 2 = 10'000записей на пользователя в таком индексе.

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

Answer 1

Скорее всего, они предварительно рассчитывают результаты и сохраняют их в распределенной базе данных KV. Вот объяснение того, как digg делает нечто подобное : http://nosqleast.com/2009/slides/sarkissian-cassandra.pdf

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

Answer 2

Facebook хранит пользователей и отношения в графической базе данных (см. https://developers.facebook.com/docs/opengraph/). Я не знаю, являются ли они основными решениями для внутреннего хранения данных (насколько я знаю, они используют Apache Cassandra , который NoSQL, но столбцы ориентированы аналогично Google BigTable), но, по крайней мере, у них есть доступ к графу всех пользователей на Facebook. Графики допускают интересные методы обхода , которые гораздо более мощные и производительные для таких данных, чем обычные SQL-запросы.

Используя, например, алгоритм кратчайшего пути, очень легко найти всех друзей друзей: см. Как рассчитать общих друзей с neo4j?

Вот также интересный пост Эмиля Эйфрема (одного из создателей Neo4j), посвященный открытому графику Facebook: http://blogs.neotechnology.com/emil/2010/04/on-the-facebook-open-graph-and-graph-databases.html

Answer 3

я не вижу индекса n ^ 2, я боюсь ... скажем, у таблицы дружбы есть 100 записей на пользователя с 100 друзьями - вот так:

user_id friend_id
1       2
1       3
2       1
2       ...

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

with my_friends_view (friend_id) as (
  select friend_id
  from friendship
  where user_id = @my_user_id
)
select user_id "my_friend_id", count(*) "mutual_friends_count"
from friendship
where user_id in my_friends_view
and friend_id in my_friends_view

Answer 4

Они могут сделать это, потому что они владеют этими данными и имеют прямой доступ к их получению, в то время как мы, разработчики, направляемся через их API, который имеет ограничения (а в большинстве случаев так и должно быть). У них есть группы людей, которым поручено обеспечить индексацию, хранение, разбивку на страницы и кэширование данных в нужных местах, чтобы пользователь чувствовал себя таким, какой он есть.