Про 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
