Про MongoDb было рассказано не так много, но относительно полно, например здесь. Хочу поделиться еще с одним практическим использованием этой БД — это построение цепочек друзей. Построение цепочек и концепцию кругов было использовано в Мойм Круге. Вот пример: Я — Иван Петров — Петр-Иванов — Киририлл Лавров — Вася Пупкин.

MongoDb было выбрано как высокопроизводительное хранилище данных, позволяющее быстро извлекать массивы структур данных. Традиционные key/value DB для этого не подходят, почему — поймете по ходу изложения статьи.

В данной статье рассмотрен опыт использования noSQL DB при построение «цепочек друзей» в небольшой соц-сети 300 тыс пользователей.


Особенность MongoDb — это хранение объектов в формате BSON — бинарный JSON. Все данные хранятся в ввиде объектов. В нашем случае — все объекты будут иметь одинаковую структуру:
{ user_id : 12, friends : [1,2,3,4,5], ffriends : [11,21,22,33...], fffriends : [121,221,222,233...]}

• user_id — id анкеты
• friends — массив id друзей
• ffriends — массив id друзей-друзей (II-круг)
• fffriends — массив id друзей III-круга

Данные массивов ffriends & fffriends подготавливаются заранее в бэдграундовском процессе (например по ночам, если мы изменяли список своих друзей). Считаем, что эти данные уже подготовленны.

Шаг 1

Делаем запрос на профиль А и В (А — это профиль нашей анкеты — его данные уже могут как-то использоваться, B — это профиль просматриваемого пользователя). Нужно построить цепочку друзей.
проверяем, нет ли данных id в массивах friends.

Шаг 2

Ищем общие id в массивах ffriends. Поиск осуществляем слиянием — этот алгоритм имеет линейную сложость. если нет, то сл шаг иначе шаг 5:

Шаг 3

Ищем общие id в массивах fffriends (III-круг). Как правило — этого бывает достаточно, так как получается цепочка из 5-промежуточных звеньев. если нет — сл. шаг иначе шаг 5:

Шаг 4

строим 4-й круг: выбираем все профили третьего круга и все данные массива friends сливаем в хештаблицу. Выбор из таблицы — постоянное время, добавление — линейное время. можно построить сразу и 5-й круг — но это пока не делается. 75% входит в 4й полукруг ( 7 промежуточных звеньев )

Шаг 5

Нашли общее id пользователя (пересечение 2-4 круга), теперь необходимо построить цепочку Друзей. Строится она от обратного для каждого профиля: выбираются все профили для id на шаге круг-1 ( т.е для 4-го круга выбираем все профили 3-го круга, для 3-го круга — все профили 2-го круга)

Шаг 6

Ищем в массиве friends наш общий-id,
нашли: имя пользователя кладем с стек, переходим к поиску в предыдущем круге.

Шаг 7

Ищем пока не спустимся до первого круга. В результате мы имеем две полу цепочки: от профиля А до профиля Х и от профиля Х до профиля В.

Шаг 8

вытаскиваем из стеков А и В имена друзей-друзей и передаем на их клиент в ввиде JSON. На клиенте строим красивую цепочку друзей.

алгоритм реализован на С++, скорость построения цепочки для 300 тыс пользователей 0.3 -0.5 сек.
После доведения до ума код будет выложен в оперсоурс.

Если Вас заинтересовала тема «Использование NoSQL» то прошу поддержать мой доклад на PHPDevConf