Социальный граф Одноклассников в Target Mail.Ru

Задача выглядит обманчиво простой — рядом с баннером игры из Одноклассников показывать текстовый тизер «в эту игру играет Кот Матроскин и ещё 5 твоих друзей» (имя и количество берутся из друзей пользователя на Одноклассниках). Как обрабатывать граф друзей проекта Одноклассники для этой задачи?

На этот простой вопрос дают разные ответы:

взять графовую базу данных;
использовать матрицу инцидентности;
использовать список смежных вершин.

Если уточнить, что сырые данные занимают полтора терабайта, в графе 200 миллионов вершин и 13 миллиардов связей, то ручные решения сразу отметаются.
«Графовая база данных!». Стоит озвучить нагрузку в десятки тысяч запросов секунду и требования отвечать за миллисекунды (тысячные доли секунды!), как графовые базы сразу оказываются за бортом: типичное время ответа на простые запросы — единицы секунд.

Экс-разработчик MySQL и SciDB, ныне ведущий разработчик Mail.Ru Target Олег Царёв расскажет, как решалась эта непростая задача в рамках проекта Mail.Ru Target.

Презентация доклада:

Запись выступления:

Все на CodeFest X →

Социальный граф Одноклассников в Target Mail.Ru

Партнёры