How to test Theory 6 handshakes in a database with millions of users?

Question

Database

There is a table with a list of people, there is a many-to-many table with "friendship" between one and the second, there are millions of people, each has up to 5k connections

How to check that one user can be a distant friend of the second in 6 connections so that it can be calculated in realtime? Brute-force search obviously will not work: the number of requests already on the second connection is greatly increasing. Caching some separate pieces of the graph for each user is just as expensive as considering it a complete enumeration.

A couple of years ago, VK rolled out such a function and everything worked there instantly (> 40 million users), it became interesting: how did they do it?
Or maybe for friends there is some more interesting database architecture in which this can be solved easier

Answer 1

graph database
neo4j - the most famous
ArangoDB - will suit you

Answer 2

Since this is a task from graph theory, then it needs to be solved in development languages ​​and graph support libraries. 1 million graph nodes is not much for modern memory.
From java libraries there are Guava, Jung, GraphT.

Answer 3

A. Downey - Learning Complex Systems with Python - 2019
Chapter 3 Small World Graphs

Answer 4

1. You need to walk from 2 sides
2. If you don’t fit into your memory, then you should walk in “depth”, and not in width. (search starting from the most "loving") (remembering that you need to "get" not into the second, but into one of his connections, it's easier)
In addition:
Step 0: 1 person
Step 1: 5000 maximum
Step 2: 25,000,000 maximum
Step 3: 40,000,000 maximum -
3 requests came up against it, the plates are theoretically large, practically - all this is ground without problems.

Answer 5

Choose the right tool. In this case, upload the data to the graph database. And in it to shortchange a similar task.

Answer 6

In my opinion, Donald Knuth considered the solution to this problem.