Chain Friends by MongoDB

About MongoDb, not much has been said, but relatively comprehensively, for example here . I want to share with another practical use of this database - this is the construction of chains of friends. Chaining and the concept of circles were used in the Moym Circle. Here is an example: I - Ivan Petrov - Petr-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 DBs are not suitable for this, why - you will understand during the course of the article.

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


A feature of MongoDb is the storage of objects in BSON format - binary JSON. All data is stored as 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 - id of the profile
• friends - array of friends id
• ffriends - an array of id friends-friends (II-circle)
• fffriends - array of friends id of the III-circle

The data from the ffriends & fffriends arrays is prepared in advance in the badground process (for example, at night, if we changed the list of our friends). We believe that this data has 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 if id data is in friends arrays.

Step 2

We are looking for common id in ffriends arrays. Search is carried out by merging - this algorithm has linear complexity. if not, then step otherwise; 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 - next step otherwise 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 a hash table. The choice from the table is constant time, the addition is linear time. you can immediately build the 5th circle - but this has not yet been done. 75% is in the 4th semicircle (7 intermediate links)

Step 5

Found a common user id (intersection of 2-4 circles), now you need to build a chain of Friends. It is built from the inverse for each profile: all profiles for id are selected at the circle-1 step (i.e. for the 4th circle we 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, we
have found: put the username on the stack, go to the search in the previous circle.

Step 7

We are looking 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 the names of friends-friends from stacks A and B and pass them to their client in the form of JSON. We build a beautiful chain of friends on the client.

the algorithm is implemented in C ++, the chain-building speed for 300 thousand users is 0.3 -0.5 seconds.
After bringing to mind the code will be posted in the opersource.

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