Como deixei meu algoritmo de pesquisa 5x mais rápido apenas fugindo do óbvio (Search Engine v2)
Introdução
Já faz tempo que vejo no Tabnews muitos pithes sem sal e notícias sensacionalistas, raramente vejo alguém começar um debate técnico realmente interessante, que dê vontade de comentar ou se quer ler até o final...
Então aqui fazer minha contribuição para tentar trazer este lado da comunidade de volta
Por isso vou começar uma série de posts relatando meus desafios na construção da minha rede social, e as soluções que encontrei para cada um deles.
Eu já tinha feito um post aqui sobre algoritmos de pesquisa há algum tempo, hoje com mais experiência volto para trazer melhorias, e mostrar como criar algo "simples" como pesquisa de usuários pode ser mais desafiador do que parece.
Primeira Versão: Post sobre Search Engine V1
Porque essa dor existe
Estou criando uma rede social, e na tela de pesquisa de usuários, eu precisava de um método de pesquisa mais eficiente que Users.findAll(), afinal para uma aplicação com dezenas de usuários até seria possível, mas um pouco mais que isso, se tornaria inviável simplesmente varrer todos os usuários.
Na minha aplicação cada letra adicionada ao input de pesquisa, é necessária uma nova consulta no banco, o que torna extremamente custoso pesquisar por milhares de usuários.
Outro problema é que, um usuário quer pesquisar por alguém que ele já conheça, alguém que esteja na mesma região ou alguém que tenha muitos seguidores por exemplo.
Então você quer ver estes usuários em primeiro na lista, e não completos desconhecidos, assim como acontece no instagram por exemplo
Pode parecer bobo, mas se sua aplicação tiver talvez 1000 usuários, sem um algoritmo desses você simplesmente não encontraria ninguém que você procura ao pesquisar (ou demoraria demais), o que acaba totalmente com o objetivo de existir um campo de pesquisa.
O que já foi resolvido e os problemas da primeira versão
Na primeira versão já resolvi o problema maior dos problemas, que era como criar um ranqueamento realmente relevante para o usuário, que levasse em conta semelhanças (como localização) e interações (seguir, bloquear etc).
O tempo de resposta foi um pouco mais chato, na época estava começando a estudar SQL e como otimizar queries, não citei no post, mais depois criei um índice dos nomes de usuário na tabela, e boa parte do meu problema foi embora.
Mas ainda tinha um grande problema, ainda era custoso demais pesquisar por todos os usuários da tabela e suas interações com o usuário para ponturar score
Então tinha que limitar a query de candidatos iniciais um número pequeno e isso causava alguns problemas... Já explico mais sobre, mas tinhamos uma saída parecida com isso:
[
{
id: 1,
username: 'apple',
profilePicture: "https://example.image",
followYou: false,
youFollow: true,
score: 7 // este score é apenas um exemplo
},
{
id: 2,
username: 'microsoft',
profilePicture: "https://example.image",
followYou: true,
youFollow: false,
score: 4 // este score é apenas um exemplo
}
... +18 items
]
// retorna followYou e youFollow porque eu os utilizo no front.
Para muitos parece bom o suficiente, mas não para mim, o problema não eram os dados de saída e sim a qualidade deles...
O monstro que ainda me assombrava
Como comecei a falar, o principla problema é que, a ordenação com base no score é feita em cima de um número super limitado de candiadtos (ex: 100) para manter a performance estável mesmo com múitos usuários no banco, ou seja, ele entrega os usuários mais relevantes para você, mas somente os mais relevantes daqueles 100 iniciais...
Então alguém que teria uma pontuação alta no algoritmo e que você gostaria de ver, provavelmente ficará de fora dos resultados somente por não estar nos 100 candidatos iniciais.
Você pode estar pensando.. Bom é só aumentar o número de candidatos iniciais como 1000 ou 10.000, e você está certo, mas isso não é sustentável.
É equivalente a tentar secar uma piscina usando balde, funciona? sim, mas ao invés de conseguir mais baldes para ser mais rápido, podemos pensar em uma solução que vai nos exigir menos esforço.
Em fim, passei um tempo pesquisando como resolver, e depois de quebrar a cabeça percebi que, por sorte minha isso já havia sido resolvido há pelo menos algumas décadas.
Me inspirando nos gigantes
Para qualquer um que já estudou o básico sobre estrutura de dados ao ouvir a palavra "rede social" já pensam em grafos automaticamente, e não é atoa, redes sociais quase sempre são o exemplo perfeito de porque grafos são úteis e eficientes para se utilizar em sistemas.
Lendo sobre o funcionamento do twitter (que são relativamente abertos em relação a sua arquitetura) podemos ver que eles um banco de dados de grafo, para armazenar as interações
Assim usando algoritmos que navegam por nós e arestas, tornam os algoritmos de pesquisas e recomendação muito mais rápidos, do que usar SQL ou um KEY-VALUE normal.
Mas é óbvio que não sou o twitter estou longe de precisar de toda essa performance e complexidade apenas para um pesquisa simples, mas observe que ao utilizar grafos podemos garantir que todos os usuários que devem estar na lista estejam lá.
já que quanto mais arestas os nós tem em comum, mais tende a refletir a proximidade geral como, interesses, seguir as mesmas pessoas, morar perto etc.
Logo se começarmos a pesquisa ordenando pelo numero de arestas em comum achamos eles gastando muito menos processamento.
A gambiarra do bem
Pensei bastante em como eu poderia abstrair essas soluções para algo que seja útil para a minha rede social, e veja bem...
Grafos são só a maneira como interpretamos os dados, qualquer relação pode ser interpretada como grafo, então ao invés de gastar tempo e dinheiro com um banco de grafos, posso simplesmente criar uma tabela que faz o papel de mapear relações entre os usuários.
E não, nem de longe o mais performático, mas é o que resolve meu problema por agora, então vamos lá...
Mapeando Relações
Tabela user_relations:
| valor | tipo |
|---|---|
| user_id | bigint |
| related_user_id | bigint |
| weight | number |
primeiro criei uma tabela que simboliza um grafo bidirecional
Bidirecional porque eu posso ter uma "afinidade" grande com um usuário ao ver muitos conteúdos dele por exemplo, e ele uma baixa "afinidade" comigo caso ele mal sabe quem eu sou
isso acontece no caso de influencers por exemplo
Para o nosso objetivo não precisamos de multiplas arrestas conectando usuários, utilizaremos só uma, e colocaremos pesos para saber intensidade da relação entre usuários.
Cada interação de um usuário com outro adiciona ou subtrai dessa intensidade de relação entre eles, como like em post: +5, bloquear: -20 etc. (isso depende das suas regras de negócio)
Assim quando receber o termo de pesquisa primeiro vejo quem aquele usuário mais se relaciona (tem o weight maior) e assim filtro pelo termo de pesquisa
Assim garanto que as pessoas que o usuário interage mais vão aparecer no resultado independente da página (caso se encaixe no termo da pesquisa obviamente)
Mudanças Principais
Agora podemos fazer algumas modificações na estrutura, veja que agora temos 2 tipos de candidatos muito bem definidos, os que o usuário conhece, e os que ele não conhece.
Então separarmos o algoritmo em 2 com relatedCandidates e unknownCandidates, assim vamos conseguir trabalhar melhor as particularidades de cada um.
Related Candidates
Aqui ao invés de buscarmos na tabela Users como fazíamos antes, agora vamos buscar ta tabela de Relations
Temos que colocar um weight minimo, para evitar gastar tempo e procesamento com pessoas que você já interagiu mas foi uma interação boba, como dar like em um único post por exemplo.
Então, chega de enrolar e vamos ao código:
// Removi alguns trechos como tratativa de erros e tipagem para melhor visualização
export class relatedCandidates extends searchEngine {
constructor(...) {...}
private async find(): Promise<FindedCandidatesProps[]> {
const relations = await Relation.findAll({
attributes: ["related_user_id", "weight"],
order: [["weight", "DESC"]],
where: {
user_id: this.user.id,
weight: {[Op.gte]: this.rules.min_relation_weight},
related_user_id: {[Op.not]: this.user.id}
}
})
return Promise.all(
relations.map(async (relation) => {
const user = await User.findOne({
attributes: ["id", "username"],
where: { id: relation.related_user_id },
}).then((user) => {
if (!user)
throw new InternalServerError({ message: "Can´t possible find related user." })
return { username: user.username, user_id: user.id }
})
if (user.username.includes(this.searchTerm)) {
return { user, weight: relation.weight }
}
return null
})
).then((candidates) => candidates.filter((candidate) => candidate !== null))
} catch (error) {
console.error("Error in find_search_candidates:", error)
throw error
}
}
//outras funções da classe
private filter() { ... }
async process() { ... }
}
Obs: Para melhor performance também coloquei indices na coluna weight da tabela de relations
Assim temos uma busca rápida e direto ao ponto, de forma aceitavelmente performática, a ideia é garantir que o usuário sempre encontrará quem ele já interagiu
Ainda faremos o ranqueamento dos candidatos com base nos pesos config.weights.related :
export const config = {
rules: {...},
weights: {
unknown: {
distance: 5,
verifyed: 1,
total_followers_num: 2,
follow_you: 3,
you_follow: 7,
block_you: -30,
muted: -50
}
related: {
block_you: -30,
muted: -50
}
}
}
Se observar a quantidade de parametros levados em consideração para o score é bem pequena, se comparado com os pesos de unknown porque já temos o weight vindo das Relations
Para economizar requisições ao banco, e tempo de resposta vamos manter com poucos parametros mesmo, e utilizar o wight das próprias Relations para nos ajudar no cálculo do score.
Vamos escrever a função de Rank:
public rank(candidates: any[], type: "related" | "unknown"): any[] {
// Calcula o score de cada candidato e retorna ordenando do maior para o menor
const weights = this.weights[type]
return candidates
.map((candidate) => {
let totalScore = candidate.weight
for (const criterion in weights) {
if (candidate[criterion] !== undefined && weights[criterion].weight !== undefined
) {totalScore += candidate[criterion] ? weights[criterion].weight : 0}
}
return {
id: candidate.id,
username: candidate.username,
name: candidate.name,
verifyed: candidate.verifyed,
blocked: candidate.blocked,
you_follow: candidate.you_follow,
profile_picture: candidate.profile_picture,
statistic: { total_followers_num: candidate?.statistic?.total_followers_num },
score: totalScore,
}
})
.sort((a, b) => b.score - a.score)
}
Então o score começa já com o weight das Relations, assim podemos usar essa função de ranqueamento também na classe de unknownCandidates, ai basta zerar weigh para unknown e tudo funciona perfeitamente no cálculo.
Agora temos que pesquisar candidatos desconhecidos, afinal o usuário pode estar pesquisando por alguém que ele nunca interagiu antes
Unknown Candidates
Aqui faremos um pouco diferente, prequisaremos em Users
e buscaremos outros dados importantes para o ranqueamento dos candidatos já que não teremos weight de Relation para nos ajudar agora:
export class unknownCandidates extends searchEngine {
constructor(...) {...}
private async find(): Promise<FindedCandidatesProps[]> {
const users = await User.findAll({
attributes: ["id", "username", "verifyed", "muted", "name", "blocked"],
where: {
...this.filterSearchParams(),
id: {[Op.not]: this.user.id},
},
include: [
{
model: Coordinate,
as: "coordinates",
attributes: ["latitude", "longitude"],
},
{
model: Statistic,
as: "statistics",
attributes: ["total_followers_num"],
},
{
model: ProfilePicture,
as: "profile_pictures",
attributes: ["tiny_resolution"],
},
],
limit: this.rules.candidates.maxUnknown,
}),
return users.map((user) => ({
user: {
username: user.username,
user_id: user.id,
},
weight: 0, // zeramos weight para o calculo do score
}))
}
}
Aqui a função de rank também é aplicada com base nesses pesos mas dessa vez utilizando config.weights.unknown:
export const config = {
rules: {...},
weights: {
unknown: {
distance: 5,
verifyed: 1,
total_followers_num: 2,
follow_you: 3,
you_follow: 7,
block_you: -30,
muted: -50
}
related: {
block_you: -30,
muted: -50
}
}
}
Recaptulando
graph TD
SearchTerm --> ParallelFind
ParallelFind --> RelatedCandidates
RelatedCandidates --> FindWithCache/Filter/Hidratation/Rank
UnknownCandidates --> Find/Filter/Hidratation/Rank
ParallelFind --> UnknownCandidates
Agora temos 2 listas, uma com candidatos relacionados e outra com candidatos desconhecidos, precisamos de uma terceira classe responsável por juntar as 2 listas
Você deve estar se perguntando o por quê se eu poderia simplesmente fazer:
relatedCandidates.concat(unknownCandidates)
Mas observe o seguinte, qualquer rede social que você procura algo, no topo estão as pessoas que você "conhece", mas também aparecem alguns desconhecidos
Isso aumenta o fator de descobrimento que é muito importante para uma rede se manter ativa e saudável. Então vamos implementar o Mixer Service.
Mixer Service
Aqui não tem nenhum segredo, apenas vamos filtrar primeiro caso haja algum usuário duplicado (que apareceu nas 2 listas por acaso) com removeDuplicates()
Depois misturamos os elementos da lista com mix() usando um monte de funções matemáticas que não vem ao caso agora, mas a classe fica com essa estrutura:
export class mixerService extends searchEngine {
constructor(...) {...}
private removeDuplicates(related, unknown) {...}
public mix(related, unknown) {...}
}
graph TD
SearchTerm --> ParallelFind
ParallelFind --> RelatedCandidates
RelatedCandidates --> FindRelated/Filter/Hidratation/Rank
UnknownCandidates --> FindUnknown/Filter/Hidratation/Rank
ParallelFind --> UnknownCandidates
FindRelated/Filter/Hidratation/Rank --> MixService
FindUnknown/Filter/Hidratation/Rank --> MixService
MixService --> SecurityFilter
SecurityFilter --> ResponseList
Otimizações
Agora que já temos toda a estrutura base pronta, observe que as duas funções de RelatedCandidates e UnknownCandidates são independentes uma da outra, porque não paralelizar as duas?
Então é isso que faremos, mas não vou falar muito sobre como paralelizei as 2 funções mporque não é tão complicado assim, nada que um tutorial bobo de 5 minutos no youtube não te ensinaria
Apliquei também algorítmos para filtrar input de pesquisa previnindo ataques de SQL e outros já que lidamos com operações usando o termo de pesquisa direto no banco de dados.
Também coloquei algoritmos de segurança internos para filter usuários bloqueados pelo sistema chamado Security Filter assim como já tinhamos antes mas agora processando em batch para aumentar a velocidade.
E por último fiz um sistema de cache para RelatedCandidates já que todo caractére digitado pelo usuário na pesquisa os usuários procurados serão os mesmos
Infelizmente isso não adiciona performance, visto que mesmo que seja mais rápido ele é limitado pela velocidade dos UnknownCandidates porque depois precisamos dos 2 resultados para o MixerService e SecurityFilter, mas economizamos requisições desnecessárias para o banco.
O fluxo fica desse jeito:
graph TD
SearchTerm --> ParallelFind
ParallelFind --> RelatedCandidates
RelatedCandidates --> CandidatesCache
CandidatesCache --> FindRelated/Filter/Hidratation/Rank
UnknownCandidates --> FindUnknown/Filter/Hidratation/Rank
ParallelFind --> UnknownCandidates
FindRelated/Filter/Hidratation/Rank --> MixService
FindUnknown/Filter/Hidratation/Rank --> MixService
MixService --> SecurityFilter
SecurityFilter --> ResponseList
Resultados Finais
Vamos falar sobre como evoluímos da primeira versão até agora no tempo de resposta geral:
- Teste feito com uma média de 20 requisições de cada versão
- Como saída esperamos uma lista com 30 usuários totais
- O número de candidatos iniciais será de 100 (totais na V1 e de Unknowns para a V2)
Resultados:
Search Engine V1 (já com índices)
- Média de 130 ms no tempo de resposta (melhor tempo de 96 ms)
- Algoritmo "burro" (traz poucas pessoas relevantes para o usuário, deixando muitos potenciais bons candidatos de fora do ranqueamento)
- Não otimizado, faz muitas requisições desnecessárias no banco de dados
Search Engine V2
- Média de 34 ms no tempo de resposta (melhor tempo de 19 ms)
- Algoritmo inteligente (traz pessoas realmente relevantes para o usuário, sem deixar alguém potencialmente relevante de fora)
- Bem otimizado, faz muito menos requisições no banco de dados
Considerações finais
✅ Aplicando todas as mudanças no algoritmo conseguimos reduzir em média 100 ms do tempo de resposta.
✅ Melhoramos a qualidade da lista final de usuários, agora levamos em conta cada micro interação para o ranqueamento.
✅ Também fazemos menos requisições no banco, diminuindo o número de conecções mínimas necessárias para rodar a aplicação bem.
Meu objetivo aqui era mostrar que, somente com mudanças e otimizações "bobas" porém criativas conseguimos mudar de forma expressiva não só no tempo de resposta mas também na qualidade da resposta, e que as vezes só precisamos sair do óbvio para solucionar nossos problemas.
Sei que ainda existe muito a melhorar nesse algoritmo, e que estou longe de saber tudo sobre otimização, então queria saber se você tem alguma ideia ou consideração sobre o assunto, deixa aqui em baixo para trocarmos um papo.
Comente também sobre qual tema você deseja saber mais sobre redes sociais.