Недавно мы с коллегами обсуждали социальную сеть LinkedIn и подняли интересный вопрос. На этом сайте есть функция отображения пути от вашей учетной записи до какой-нибудь другой учетной записи. Максимальное количество шагов равняется трем, т.е. путь выглядит так: Вы->Ваш друг->Друг Вашего друга->Искомый человек. Вопрос состоит в том, как осуществляется поиск этого пути? Он ищется каждый раз когда вы заходите на чью-либо учетную запись? Или все пути для всех пользователей уже просчитаны заранее? Первый вариант приводит к большим временным затратам, второй — к большим затратам на хранение.
Нам с коллегами повезло, как раз в мае этого года на конференции JavaOne 2008 в Сан-Франциско представители LinkedIn провели две презентации об архитектуре их социальной сети. В этом блоге приведен отличный обзор докладов, а здесь — его перевод. Кстати, оба поста содержат ссылки на оригинальные презентации представителей LinkedIn, если кому интересно.
Так вот выяснилось, что весь граф пользователей занимает 12 Гб и постоянно держится в оперативной памяти. Но в начале каждый сессии создается выборка из общего графа персонально для данного пользователя, т.е. как-бы взгляд на социальную сеть с его точки зрения. Этот персональный граф на протяжении всей сессии хранится в кэше и занимает примерно 2 Мб для каждого пользователя. Он обновляется лишь в том случае, если сам пользователь внесет в него какие-либо изменения, например добавит или удалит одного из друзей. В случае если изменения исходят от других пользователей, граф остается неизменным. Очевидно, что поиск пути до какой-нибудь учетной записи происходит именно в этом графе.
Таким образом, в LinkedIn реализован гибридный вариант, т.е. поиск пути происходит на лету, но при этом какая-то часть информации (персональный граф) строится заранее и хранится в памяти. Пытливый читатель может задать вопрос: «Как в случае с полным графом, так и в случае с персональным графом нам придется перебирать все возможные пути от пользователя до искомого человека. В чем же тогда преимущество персонального графа?» Все дело в том, что графы представляются либо массивами, либо линейными списками. И в том и в другом случае чтобы найти какой-нибудь элемент нужно в худшем случае перебрать все имеющиеся элементы. В полном графе таких элементов 22 миллиона (именно столько на LinkedIn зарегистрированных пользователей). Размер персонального графа, очевидно, гораздо меньше. Например если у пользователя, каждого из его друзей и друзей их друзей имеется по 30 контактов, то размер такого графа будет всего 27931. Кроме того, в персональном графе для того чтобы убедиться, что путь существует, не нужно перебирать все возможные пути, достаточно просто проверить присутствует ли в графе искомая учетная запись. Ведь если этот граф строился как «персональный взгляд на сеть» с максимальным количеством шагов равным трем, то наличие в нем какой-либо учетной записи автоматически означает, что путь до пользователя в пределах трех шагов существует и его вообще имеет смысл искать.
И напоследок небольшой оффтопик. С удивлением обнаружил, что граф всей социальной сети имеет 22 миллиона вершин и 120 миллионов ребер. Это означает, что на каждую учетную запись приходится в среднем всего по 5.45 друзей. Видимо это из-за того, что много народу регистрируется, но потом не пользуется своим аккаунтом.
Нам с коллегами повезло, как раз в мае этого года на конференции JavaOne 2008 в Сан-Франциско представители LinkedIn провели две презентации об архитектуре их социальной сети. В этом блоге приведен отличный обзор докладов, а здесь — его перевод. Кстати, оба поста содержат ссылки на оригинальные презентации представителей LinkedIn, если кому интересно.
Так вот выяснилось, что весь граф пользователей занимает 12 Гб и постоянно держится в оперативной памяти. Но в начале каждый сессии создается выборка из общего графа персонально для данного пользователя, т.е. как-бы взгляд на социальную сеть с его точки зрения. Этот персональный граф на протяжении всей сессии хранится в кэше и занимает примерно 2 Мб для каждого пользователя. Он обновляется лишь в том случае, если сам пользователь внесет в него какие-либо изменения, например добавит или удалит одного из друзей. В случае если изменения исходят от других пользователей, граф остается неизменным. Очевидно, что поиск пути до какой-нибудь учетной записи происходит именно в этом графе.
Таким образом, в LinkedIn реализован гибридный вариант, т.е. поиск пути происходит на лету, но при этом какая-то часть информации (персональный граф) строится заранее и хранится в памяти. Пытливый читатель может задать вопрос: «Как в случае с полным графом, так и в случае с персональным графом нам придется перебирать все возможные пути от пользователя до искомого человека. В чем же тогда преимущество персонального графа?» Все дело в том, что графы представляются либо массивами, либо линейными списками. И в том и в другом случае чтобы найти какой-нибудь элемент нужно в худшем случае перебрать все имеющиеся элементы. В полном графе таких элементов 22 миллиона (именно столько на LinkedIn зарегистрированных пользователей). Размер персонального графа, очевидно, гораздо меньше. Например если у пользователя, каждого из его друзей и друзей их друзей имеется по 30 контактов, то размер такого графа будет всего 27931. Кроме того, в персональном графе для того чтобы убедиться, что путь существует, не нужно перебирать все возможные пути, достаточно просто проверить присутствует ли в графе искомая учетная запись. Ведь если этот граф строился как «персональный взгляд на сеть» с максимальным количеством шагов равным трем, то наличие в нем какой-либо учетной записи автоматически означает, что путь до пользователя в пределах трех шагов существует и его вообще имеет смысл искать.
И напоследок небольшой оффтопик. С удивлением обнаружил, что граф всей социальной сети имеет 22 миллиона вершин и 120 миллионов ребер. Это означает, что на каждую учетную запись приходится в среднем всего по 5.45 друзей. Видимо это из-за того, что много народу регистрируется, но потом не пользуется своим аккаунтом.
