Задача выглядит обманчиво простой - рядом с баннером игры из Одноклассников показывать текстовый тизер "в эту игру играет Кот Матроскин и ещё 5 твоих друзей" (имя и количество берутся из друзей пользователя на Одноклассниках).
Как обрабатывать граф друзей проекта Одноклассники для этой задачи?
На этот простой ответ дают разные ответы:
- взять графовую базу данных;
- использовать матрицу инцидентности;
- использовать список смежных вершин.
Если уточнить, что сырые данные занимают полтора терабайта, в графе 200 миллионов вершин и 13 миллиардов связей, то ручные решения сразу отметаются.
"Графовая база данных!". Стоит озвучить нагрузку в десятки тысяч запросов секунду и требования отвечать за миллисекунды (тысячные доли секунды!) как графовые базы сразу оказываются за бортом - типичное время ответа на простые запросы - единицы секунд.
Экс-разработчик MySQL и SciDB, ныне ведущий разработчик Mail.Ru Target Олег Царёв расскажет, как решалась эта непростая задача в рамках проекта Mail.Ru Target.