Chain Friends by MongoDB

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

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 62

      +5
      Получается MongoDB это идеальная база данных для MMO?
      { user_id: 12,spells: [1,2,3,4,5], items_in_backpack: [11,21,22,33...], items_on_body: [121,221,222,233...]}
        0
        все зависит, каким способом решаешь задачу, можно авторизацию на memcachedb замудрить так, что она будет медленнее мускульной.

        если на мускуле эта задача будет решаться быстрее- то я буду только рад.
          +1
          А вообще я благодарен идеи — на досуге надо проверить на memcachedb.
          но достоинство MongoDb в возможности репликации.
            0
            memcachedb не подойдет для моего круга из-за архитектурных недостатков
              0
              Скажите, могли бы Вы подробнее рассказать об архитектурных недостатках mongoDb? Как и где вообще можно применять эту технологию?
                0
                я про memcachedb. mongodb знаю то что код нестабилен и нет асинхронной работы с сокетами, а текущая при большом количестве подключений глючит — т.е. надо работать по persisten соединениям.
                  0
                  спасибо, ждем допила и ебилдов mongodb :)
            +1
            «цепочки для 300к пользователей» = цепочки, в которой от А до B — 300к человек?
              0
              Юмор оценен, держи 5
                +1
                Я к тому, что 0,3 — 0,5 секунд на построение цепочки это очень много, ведь такие цепочки нужно строить в реальном времени. Вы совсем не описали, как производили измерения. Если A и B в первом-втором круге друг у друга — цепочка должна получаться мгновенно.
                  0
                  это время затраченное на поиск за 5-м-6-м кругом,
                  конечно смешно искать в цепочке во втором круге.
                  Несомненно, если A и B в первом-втором круге друг у друга — цепочка получается мгновенно.

                  весь поик осуществляется онлайн, есть место для оптимизации кода. На тестовом сервере цепочка получается почти мгновенно.
              0
              Как хорошо, что начали писать статьи про объектные БД!) побольше б таких статей.*ушел писать доклад*
                +1
                А можно вписать тот момент, где мы увидим все таки, что key-value сливают монго? Вы про какие именно key-value? Memcache, Redis, Cassandra, Riak? И главное — в чем слив? Попрошу memcache в качестве примера не приводить, это не БД, это кеш все таки.
                Еще бы хотелось увидеть не рыбу поста, а такой пост, чтобы его можно было понять. Я вот ваш алгоритм не понял, по нему выходит, что мы сравниваем первые круги, потом вторые круги, потом третьи :) А если id у одного в третьем, а другого во втором?

                Вот еще, их текста:
                  0
                  Попробую объяснить. Если ни A ни B не «состоят между собой в дружбе,» то мы сравниваем вначале первые «круги» друзей пользователей A и B. Если в их первых кругах есть хотя бы один общий id (то есть id, который встречается и в первом круге пользователя A и в первом круге пользователя B) — это означает, они соеденены через одного пользователя. (Возможно таких пользователей несколько, но это, думаю, не так важно.)
                  Если ни одного общего id в их первых кругах нет, то нужно сравнить «вторые круги». Что такое второй круг друзей пользователя A? Это все друзья пользователя A, и все друзья его друзей. То есть, если у A есть друг Q, у которого есть друг W, то во втором кругу пользоватля A (массив ffriends в статье) будут id как пользователя Q так и пользователя W.
                  Сравнивая последовательно круги их друзей можно найти объеденяющий набор пользователей, через которых они между собой «знакомы» (пользователь A знает пользователя Q, который знает пользоватля W, который знает пользователя B)

                  Общая идея понятна? Если нет, то могу попробовать объяснить по другому. Но тогда желательны конкретные вопросы — что именно не понятно.
                    0
                    Проблема не в том, что я не понимаю алгоритма, проблема в том, что вы так торопились его опубликовать, что не сделали вычитку. Из вашего текста алгоритм выходит очень кривым, но если конечно догадываться, то можно ваш и не читать.

                    И главный вопрос — при чем тут MongoDB? Вы считаете, что в key-value базах нельзя хранить списки? Да даже множества можно, Redis вот например. Для друзей операции со множествами это самое очевидное решение, так что на Redis это вообще все решается элементарно.
                      0
                      А по-моему, проблема в том, что вы так торопились обличить автора, что даже не глянули что он это не я :)

                      Насчёт _моего_ мнения по поводу применения mongodb к этой проблеме: думаю практически любое key-value хранилище справилось не хуже бы. Думаю прийдёт автор и объяснит почему было выбрано mongo, и почему он считает что другое хранилище было бы хуже.
                        0
                        Вы хорошо мимикрировали, и явно не поняли моего комментария, иначе не стали бы мне рассказывать этот алгоритм. Ведь там была явная просьба привести топик в нормальный вид.
                          0
                          Прокрутить страницу вверх довольно просто. Проще, чем понять, что [Я вот ваш алгоритм не понял, по нему выходит, что мы сравниваем первые круги, потом вторые круги, потом третьи :) А если id у одного в третьем, а другого во втором?] это фраза в комментарии просто так, и само по себе содержание вас не интересует.

                          Мне жаль, что я потратил на объяснение время, и это оказалось не нужно.
                            –1
                            А надо полностью читать: ) И не будет разочарований.
                              0
                              Да я вот полностью прочитал. И думаю что вы так же могли бы делать. С топиками, например.
                                –2
                                Хм, а я вот как раз прочитал, меня стошнило, и я об этом написал. А о чем пишете вы, милейший?
                                  +2
                                  Консмтруктивного диалога у нас не получилось. Предлагаю заканчивать дискуссию.
                          0
                          tasman спасибо за поддержку
                          согл: практически любое key-value хранилище справилось не хуже бы

                          выбор за MongoDB:
                          — масштабируемость
                          — возможность репликации
                          — планируем использовать для других данных
                          –1
                          В редисе вполне можно хранить списки, но эта задача явно не для редиса. Можно использовать для этой задачи вполне можно использовать и key/value,
                          хранить всю информацию в том же JSON,
                          ключ user_id_12
                          lданные { friends: [1,2,3,4,5], ffriends: [11,21,22,33...], fffriends: [121,221,222,233...]}
                          если использовать списки редися — то дубет очень накладно.

                          будет время, попробую это на memcachedb, это я озвучил в своем втором посте этой темы.
                            –1
                            То есть не для редиски, я для мемкеша вполне? О мой бог!
                              –1
                              ну я про А ты про Бэ…
                              можно и в редиске, но в том же формате, что и в memcachedb
                              по этому выигрыша абсолютно ни какого.
                              списки редиса здесь никаким боком не засунешь, а если и засунешь, то только огребешь лишнюю головную боль и тормоза.

                              замечу что мемкеш и memcachedb — это все же разные системы хранения данных.
                                –1
                                Хм, а множества Redis тоже никаким боком? И пост как был трешем, так и остался.

                                И на брудершафт я с вами не употреблял, задолбали.
                                  0
                                  разговор будет предметным
                                  если Вы представите мне структура данных на редисе.

                                  а самым предметным — если сделать тесты
                                    0
                                    Да мне уже надоело вести разговор, если честно. На хабре уже много треша, и мне на это повлиять не удается, в виду непрошибаемости авторов.
                                    А потому я лучше полезными делами займусь, чем делать за вас тесты: )
                      0
                      Вот еще, из текста:
                      [проверяем, нет ли данных id в массивах friends.]

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

                        Вполне логично предположить, что проверяемые id принадлежат пользователям A и B.
                          0
                          Вполне. Но из текста это должно следовать, а вы ведь даже не удосужились перечитать, и поправить, и это печалит меня.
                            0
                            Ответил вам выше. Я не автор, я просто пытался внести ясность, думая, что вам интересен алгоритм. А вам оказалось интересно погнобить автора за сумбурный топик.
                              0
                              Да мне не интересно его погнобить, мне интересно, почему ни разу, сколько бы я не гнобил авторов, никто из них не поправил свое творение.
                              А гнобил я их жестоко, но, по всей видимости, авторы действуют как дети по Гиппенрейтер, включают отрицание.
                                –1
                                спасибо за критику
                                  0
                                  Не за что, правда пост не изменился ;-)
                                    0
                                    а что конкретно в нем должно измениться?
                                    если я где-то не прав, то поправлю
                        +2
                        Итог — мне надоело открывать пост в надежде прочесть пост профессионала, со светлой головой, в которой сидят упорядоченные мысли, да на интересную тему. А там блин как всегда.
                          0
                          { user_id: 12, friends: [1,2,3,4,5], ffriends: [11,21,22,33...], fffriends: [121,221,222,233...]}
                          Что-то не понял, разве эти данные нельзя хранить в таблице обычной реляционной БД (на пример MySQL) в строковых полях? В чём прикол объектной БД тут?
                            +2
                            зачем же в строковых, у postgresql есть массивы например www.postgresql.org/docs/8.4/interactive/arrays.html на которые, кстати, можно класть индексы, и производить с ними всякие операции, в том числе overlap www.postgresql.org/docs/8.4/interactive/functions-array.html
                            ну, это я так. но мне тоже показалось, что преимущества mongodb в статье совсем не освещены. да и при чем тут вообще бд, когда описывается достаточно абстрактный алгоритм?
                              0
                              преимущество в скорости извлечения
                                0
                                А вы меряли?
                                В posgresql массивы можно пересечь на базе, не гоняя данные по сети. Тем более — третьи круги. Для пользователя, у которого всего лишь 50 контактов третий насчитывает уже тысячи (и чем выше связность сети — тем больше)
                                  0
                                  с постргесом нет, с мускулем мерил
                                    0
                                    сколько займет время пересечения?
                                    один такой умник (архитектор tradebox), чтоб не гонять данные по сети, решил большую часть логики впихнуть в БД в ввиде хранимых процедур. В результате когда вышли на реальную нагрузку база просела, мощный сервер просто не стал справляться.
                                    так что надо соизмерять что можно делать при нагрузках, а что нельзя.
                                      0
                                      «база просела» и «использовать хранимые процедуры» — вещи никак не связанные. с таким же успехом можно написать запросы, которые не попадут в индекс и база так же просядет, так что это не аргумент.

                                      вот эти патчи dklab.ru/lib/dklab_postgresql_patch/ делают пересечение очень быстро.
                                        0
                                        конечно, я не спорю — ты хороший специалист по постгесу
                                        но, очевидно, с высоконагруженными системами ты не работал.
                                          +1
                                          lol. вообще, я разрабатываю тот самый мой круг, который ты упомянул в суе в своем посте.
                                            0
                                            супер!
                                            есть у кого проконсультироваться!

                                            так вы там на постгресе делаете пересечения?

                                            а как дела обстят с шардингом? или всю «дружбу» сливают в одну центральную БД.
                                            у меня почему такая архитектура: потому что все профили пользователей разбиты по мускульным шардам, а всю дружбу решили загнать в монго.

                                              0
                                              пересекаем в базе, да.

                                              а по-поводу дружбы — почему не держать друзей в тех же шардах? ведь списки друзей всё равно дублируются для каждого пользователя — список друзей можно строить по тому же шарду, где и храниться профиль.

                                              да, при этом не получится строить список за 5-м звеном. но, честно говоря, 5й круг не несет уже вообще никакого business value — там уже совсем незнакомые люди.
                                                0
                                                у нас дружба шла отдельной таблицой, которая шардится по user_id. таким образом — был построен только первый круг. Построение второго круга оказалась довольно-таки трудоемкая процедура, по этому решили вынести всех «друзей» в центральное хранилище.

                                                но, с другой стороны, всякому будет интересно, через каких друзей он связан с Дмитрием Котеровым.
                                    0
                                    на чем основано это мнение?
                                    вот тут например недавно был пост, показывающий, что скорость селекта монгодб по большому счету примерно равен mysql.
                                      0
                                      конечно все зависит от селекта :)
                                      есть задачи в которых мускуль выигрывает — это бесспорно. В данной — мускул проигрывает.
                                  0
                                  можно, прикол в скорости извлечения.

                                  сколько приблизительно запросов надо сделать на создание цепочки?
                                  +3
                                  Автор, хоть шаги и расписаны подробно, но все равно в них трудно ориентироваться, не хватает иллюстраций и примеров что ли. Может быть лучше кодом? :) Это конечно ИМХО, но код легче понять когда излагаются подобные мысли.
                                    0
                                    согл, кодом лучше,
                                    но кода слишком много, а вырывать код из контекста — будет еще непонятнее.
                                    уже есть такой опыт.

                                    Будут интересны исходники, можешь в них покопаться, тестовую версию скоро выложу.
                                      0
                                      С удовольствием покопаюсь
                                    +4
                                    Пост рассказывает о том, как сделать нечто на MongoDB, но, к сожалению, не дает никакого сравнения с альтернативами и преимуществах MongoDB хотя бы на примере данной задачи. Увы, складывается впечатление, что сравнение разных технологий проведено и не было. Жаль, это ведь как раз то, что всем хотелось бы узнать, тем более что сама тема очень интересная.
                                      0
                                      согл, чтоб сделать сравнение, надо тоже самое реализовать на другой технологии. Я сейчас это отлажываю. По крайней мере преимущество с RMBD — в скорости извлечения.
                                      Как я замечал выше, возможно использовть на memcachedb (или редис но первое надежнее и быстрее)
                                      но мы еще планируем Mongodb под др задачи.
                                      0
                                      Вопрос может быть немного отвлеченный, но скажите вы пользовались map-reduce в mongodb? Если да расскажите ваши впечатления. Спасибо.
                                        0
                                        нет пока не пользоватлся,
                                        много других текущих задач.
                                        Обязательно попробую, поделюсь как только так срзу
                                        0
                                        по вопросу выбора языка:
                                        выбран C++, так как скриптовые языки требуют много памяти под выделяемые хешмассивы.
                                        2-круг есть пользователи более 400 друзей, третий от 1200 друзей. Хотелось бы все вычисления делать быстро в онлайн.

                                        приложение реализовано как fcgi модуль, проксируется через nginx
                                          0
                                          Приходите на DEVCONF 2010 — пофлудим… мы планируем собрать все noSQL БД!

                                          Мы продлили прием заявок на доклады… до 12 апреля…
                                          Уже 215 участников успели зарегистрироваться…
                                          devconf.ru/offers/

                                          Only users with full accounts can post comments. Log in, please.