Chain Friends by MongoDB

About MongoDb it was told not so much, but relatively complete, for example here . I want to share with another practical use of this database - is building chains of friends. Chaining and the concept of circles was used in Moim Krug. Here is an example: I am Ivan Petrov - Peter-Ivanov - Kirill Lavrov - Vasya Pupkin.

MongoDb was chosen as a high-performance data warehouse that allows you to quickly retrieve arrays of data structures. Traditional key / value DB for this is not suitable, why - you will understand in the course of the presentation of the article.

This article describes the experience of using noSQL DB when building “chains of friends” in a small social network of 300 thousand users.

')
The MongoDb feature is storing objects in BSON format - binary JSON. All data is stored in the form of objects. In our case - all objects will have the same structure:
{ user_id : 12, friends : [1,2,3,4,5], ffriends : [11,21,22,33...], fffriends : [121,221,222,233...]}

• user_id - profile id
• friends - array id of friends
• ffriends - array id friends of friends (II-circle)
• fffriends - id array of friends of the III circle

The data of the ffriends & fffriends arrays are prepared in advance in the Badraundian process (for example, at night if we change the list of our friends). We believe that these data have already been prepared.

Step 1

We make a request for profile A and B (A is the profile of our profile - its data can already be used somehow, B is the profile of the user being viewed). Need to build a chain of friends.
check for id data in friends arrays.

Step 2

We are looking for common id in ffriends arrays. The search is carried out by merging - this algorithm has a linear complexity. if not, then step or step 5:

Step 3

We are looking for common id in fffriends arrays (III-circle). As a rule - this is enough, as it turns out a chain of 5 intermediate links. if not, then. step or step 5:

Step 4

build the 4th circle: select all the profiles of the third circle and merge all the data from the friends array into the hash table. The choice from the table is constant time, the addition is linear time. You can also build the 5th circle right away - but this is not done yet. 75% included in the 4th semicircle (7 intermediate links)

Step 5

Found a common user id (the intersection of 2-4 laps), now you need to build a chain of Friends. It is built from the inverse for each profile: all profiles for id are selected on lap-1 step (ie, for the 4th circle, select all profiles of the 3rd circle, for the 3rd circle - all profiles of the 2nd circle)

Step 6

We are looking for our common-id in the friends array,
found: put the username from the stack, go to the search in the previous round.

Step 7

We are looking for until we go down to the first round. As a result, we have two semi chains: from profile A to profile X and from profile X to profile B.

Step 8

we pull out from the stacks A and B the names of friends and friends and transfer to their client in the form of JSON. On the client we build a beautiful chain of friends.

the algorithm is implemented in C ++, the chain building speed for 300 thousand users is 0.3-0.5 sec.
After bringing to mind the code will be laid out in the opsource.

If you are interested in the topic "Using NoSQL", then please support my report on PHPDevConf