Serviço de proximidade (Yelp)

01 · CONTEXTO E REQUISITOS

O que um serviço de proximidade precisa fazer

Um serviço de proximidade responde à pergunta "o que existe perto de mim?": restaurantes, lojas ou serviços ao redor de uma posição. O exemplo clássico é um site de avaliação de negócios locais, e ele serve de pretexto para um assunto maior, a busca por localização. Em entrevista, o primeiro passo é o levantamento de requisitos.

Nos requisitos funcionais do exemplo, a pessoa busca negócios por nome, localização e categoria, vê o negócio com suas avaliações e deixa uma avaliação com nota e texto opcional.

Os requisitos não funcionais mandam no desenho: busca com latência baixa, alta disponibilidade e escala para cem milhões de usuários por dia e dez milhões de negócios, o que empurra a busca para um índice próprio e para cache.

02 · O PROBLEMA

Por que um índice comum não resolve

Achar quem tem idade entre dois valores é rápido porque o B-tree mantém chaves ordenadas lado a lado no disco, e a faixa vira uma leitura quase sequencial.

Com localização o raciocínio quebra: o B-tree ordena por um dos dois números por vez, e achatar o mapa em um eixo pode separar pontos que são vizinhos no chão. Um índice em latitude devolve uma faixa horizontal da Terra inteira, e o banco acaba examinando linhas demais.

1. A pessoa abre o app e o pedido chega ao serviço de busca com a posição, o raio e o filtro.

2. O serviço consulta a tabela de negócios pedindo tudo o que está dentro do raio, com condição em latitude e em longitude.

3. Sem uma estrutura que preserve a proximidade, o banco só consegue usar a ordem de um dos dois números e examina uma faixa enorme de linhas.

O caminho é construir uma estrutura que gera um conjunto pequeno de candidatos perto do ponto. O índice quase nunca entrega a resposta final: a distância exata é calculada só sobre esses candidatos.

03 · FAMÍLIAS DE ÍNDICE

Árvores espaciais e células codificadas

A primeira família constrói uma árvore feita para dados espaciais. Na quadtree, o mapa inteiro é a raiz, dividida em quatro quadrantes, e quadrante com pontos demais é dividido de novo. A árvore se adapta à densidade: o centro de uma metrópole fica profundo e um lago continua sendo uma célula grossa.

O custo aparece em escala: em regiões densas a árvore fica profunda e as regiões mais movimentadas ficam mais lentas. Além disso, a quadtree é uma estrutura de ponteiros, ruim para disco, embora siga comum em memória. Para formas como polígonos, a variante em disco é a R-tree, usada por bancos geoespaciais.

A segunda família transforma cada posição em uma chave que um índice comum já sabe ordenar. No geohash, o mundo é dividido em uma grade de 32 células, cada uma com um caractere, e a divisão se repete célula adentro. Chaves com o mesmo prefixo costumam estar perto, então a busca vira uma varredura por prefixo.

A borda é a armadilha: dois pontos a um metro podem cair em prefixos totalmente diferentes. A correção padrão é consultar a célula do ponto e as oito vizinhas e filtrar por distância exata. Variações como S2 e H3 seguem a mesma ideia, com células mais regulares na esfera ou em hexágonos.

04 · DESENHO

O serviço com índice por célula

O desenho separa dois caminhos. A busca calcula as células do ponto, junta os candidatos e filtra por distância. O cadastro de negócios grava no banco principal, e a replicação mantém o índice por célula atualizado. Como a busca domina, o índice fica em réplicas de leitura e o cache absorve as células mais pedidas.

1. O app envia a posição, o raio e o filtro; o balanceador encaminha ao serviço de busca.

2. O serviço de busca calcula a célula do ponto e as oito vizinhas, para não perder quem está do outro lado de uma borda.

3. Se a mesma região foi consultada há pouco, o cache devolve os candidatos sem passar pelo índice.

4. Se o cache não tem a resposta, o serviço lê os negócios das células na réplica com índice por célula.

5. O serviço calcula a distância exata dos candidatos, descarta os que ficaram fora do raio e ordena o resto.

6. Quando um negócio muda, o serviço de negócios grava no banco principal e a replicação atualiza o índice por célula.

05 · ESCALA E TRADE-OFFS

Particionar sem criar pontos quentes

Quando o índice não cabe em uma máquina, ele é particionado, por exemplo por região, e cada partição ganha réplicas de leitura. A armadilha é a densidade: regiões movimentadas concentram mais pontos e mais consultas, o mesmo problema da quadtree profunda no centro de uma metrópole.

1. O pedido chega ao serviço de busca, que descobre a quais regiões o raio da consulta pertence.

2. A consulta vai apenas às partições dessas regiões, em vez de varrer o índice inteiro.

3. Uma região densa recebe muito mais pontos e consultas que as vizinhas e vira ponto quente.

4. As réplicas de leitura absorvem o excesso de consultas da partição quente.

Em resumo: árvore espacial para formas, células codificadas para pontos em movimento, e sempre filtro final por distância exata. Esse raciocínio vale mais do que decorar o nome de uma biblioteca. Veja também a escolha de banco de dados e o particionamento.