Grafo social: graus de separação

01 · CONTEXTO E REQUISITOS

O que a busca precisa fazer

Neste exercício, o usuário busca alguém numa rede social e o sistema mostra o caminho mais curto até essa pessoa. O serviço também precisa ter alta disponibilidade. Fixar isso é o levantamento de requisitos do problema.

As premissas qualitativas já limitam as soluções: o tráfego não é uniforme, algumas buscas são muito mais populares que outras e outras acontecem uma única vez, o grafo não cabe em uma máquina e as arestas não têm peso.

02 · O PROBLEMA

BFS cabe numa máquina, o grafo não

Sem a restrição de milhões de vértices e bilhões de arestas, uma busca em largura (BFS) geral resolveria o caminho mais curto, já que as arestas não têm peso.

Mas a fonte afirma que não será possível colocar todos os usuários na mesma máquina. A saída é o sharding dos usuários entre Person Servers, acessados por meio de um Lookup Service que diz onde cada pessoa está. Na fonte, cada pessoa tem identificador, nome e a lista de ids dos amigos, o modelo de dados do exercício.

03 · DESENHO INICIAL

Do clique ao caminho mais curto

O fluxo atravessa várias camadas antes de chegar à busca. Acompanhe o caminho de uma requisição.

1. O cliente envia a requisição ao Web Server, que atua como proxy reverso.

2. A requisição é encaminhada do Web Server à Search API e desta ao User Graph Service.

3. O User Graph Service consulta o Lookup Service para achar o Person Server onde ficam os dados do usuário.

4. O serviço lê a lista de amigos do usuário no Person Server apropriado.

5. O serviço executa a BFS a partir do usuário atual.

6. Para cada vizinho a ser lido, o serviço precisa localizar de novo o Person Server correto, algo que a fonte marca como potencial de otimização.

04 · ESCALANDO

Cache, pré-cálculo e menos saltos

A fonte avisa para não pular direto ao desenho final. Entre os acréscimos, ela propõe servir dados de pessoas a partir de um cache em memória, como Redis ou Memcached, para reduzir o tempo de resposta e o tráfego aos serviços a jusante. Isso seria útil para quem faz várias buscas em sequência e para pessoas muito conectadas.

A fonte cita esta comparação de latência: ler 1 MB sequencialmente da memória leva cerca de 250 microssegundos, enquanto o SSD leva 4 vezes mais e o disco 80 vezes mais.

1. Dados de pessoas podem ser servidos pelo cache em memória, reduzindo o tempo de resposta e o tráfego aos serviços a jusante.

2. O cache também pode guardar travessias BFS completas ou parciais para acelerar buscas seguintes.

3. Um cálculo em lote offline produz travessias completas ou parciais e as guarda em um banco NoSQL para acelerar buscas seguintes.

4. Agrupar as consultas de amigos hospedados no mesmo Person Server reduz os saltos entre máquinas.

5. Particionar os Person Servers por localização melhora isso, pois amigos costumam morar perto uns dos outros.

05 · OTIMIZAÇÕES DA BUSCA

Menos trabalho por busca

Além da infraestrutura, há otimizações na própria busca, resumidas abaixo.