Rinha de Backend 2026: Construindo uma API de Detecção de Fraude em 350MB

3 milhões de vetores, 14 dimensões, 1 CPU e um p99 que foi de 13.200ms para 2,47ms.

O que é a Rinha de Backend?

Rinha de Backend é uma competição brasileira de backend onde participantes submetem uma API que é testada sob carga e pontuada. A edição de 2026 foi sobre detecção de fraude em transações financeiras usando busca vetorial exata k-NN.

Você envia um Docker Compose. Os organizadores executam k6 contra ele. Sua pontuação é uma combinação de latência (p99) e qualidade de detecção (FP/FN). Há limites: 1 CPU no total, 350MB de memória no total, distribuídos entre quantos containers você quiser, com pelo menos um load balancer e duas instâncias da API.

Submeti uma API em Go atrás de nginx, fazendo busca exata k-NN sobre 3 milhões de vetores de referência rotulados. Esta é a história de como o p99 foi de 13,2 segundos para 2,47 milissegundos.

O Desafio

Os organizadores fornecem um arquivo com 3 milhões de vetores rotulados (references.json.gz, ~284MB descompactado). Cada vetor tem 14 dimensões, representando características como valor da transação, parcelas, distância de casa, risco MCC e muito mais. Cada vetor é rotulado como "fraud" ou "legit".

Quando uma requisição chega, você vetoriza o payload no mesmo espaço de 14 dimensões, encontra os 5 vizinhos mais próximos usando distância euclidiana (exata, sem sqrt), e classifica: se 3+ dos 5 são fraude, negue.

A fórmula de pontuação é a soma de dois componentes independentes:

final_score = score_p99 + score_det
  • Pontuação de latência: 1000 × log₁₀(1000ms / p99). Teto em +3000 (p99 ≤ 1ms), piso em −3000 (p99 > 2000ms).
  • Pontuação de detecção: Função logarítmica de erros ponderados. FP peso 1, FN peso 3, erros HTTP peso 5. Se taxa de falha > 15%, fixo em −3000.

Pontuação máxima possível: +6000. Mínima: −6000.

Ponto de Partida: Força Bruta

Minha primeira implementação foi força bruta ingênua. Cada requisição computava distância euclidiana ao quadrado contra todos os 3 milhões de vetores. Na minha máquina:

Benchmark de busca: 15.8 ms/op (força bruta, 3M vetores)

Sob teste de carga com 100 VUs, o p99 atingiu 13,2 segundos. A pontuação ficou em torno de −1300. Timeouts em toda parte.

Executar força bruta em 3 milhões de vetores de 14 dimensões por requisição dentro de um orçamento de 350MB nunca funcionaria. O dataset é claro na documentação: "usar força bruta provavelmente terá desempenho muito ruim (O(N × 14)) para este desafio."

Eu precisava de um índice.

Clustering IVF: O Primeiro Salto

Implementei IVF (Inverted File Index) com clustering k-means. Em vez de escanear todos os 3M vetores, escolha o centróide do cluster mais próximo e escaneie apenas seus membros.

Com K=1024 clusters, o tamanho médio do cluster era ~2.930 vetores. Pontuação: +3.919, p99 muito melhor.

Então mudei um número:

K := 1024  // → 4096

Uma linha. A reconstrução do artefato levou 32 minutos. K=4096 reduziu o tamanho médio do cluster para ~732 vetores. A pontuação saltou para +4.517, um ganho de +598 pontos com uma única mudança de parâmetro. A busca local foi de ~269μs/op para ~295μs/op (10% mais lenta por consulta devido à sobrecarga do centróide), mas o efeito líquido no p99 sob carga foi fortemente positivo porque clusters menores significavam menos cache misses.

A Arquitetura Evolui

Nas iterações seguintes, empilhei otimizações:

Layout de memória SoA. Reorganizei os 3M vetores de Array-of-Structs (14 floats por vetor, dispersos) para Structure-of-Arrays (14 arrays contíguos de int8). Isso transformou acesso aleatório à memória em varreduras sequenciais. O artefato caiu de ~284MB JSON para ~45MB binário via quantização int8.

Migração fasthttp. Troquei net/http + chi por valyala/fasthttp. A pontuação saltou para +5.183 (p99=3,84ms). O tratamento de requisições com zero alocações fez diferença a 900+ req/s.

Kernel AVX2 fusionado com duplo acumulador. O hot path era ScanClusterSoA: para cada um dos ~183 blocos (8 vetores cada), chamava uma função Go por dimensão, 14 chamadas de assembly por bloco, com acumulação escalar entre elas. Isso era ~2.562 chamadas de função por consulta.

Substituí por uma única função assembly:

# Y0 = acumulador de dimensões pares (0, 2, 4, 6, 8, 10, 12)
# Y4 = acumulador de dimensões ímpares (1, 3, 5, 7, 9, 11, 13)
VFMADD231PS Y2, Y2, Y0      # fused multiply-add

O duplo acumulador divide a cadeia de dependência pela metade (7 hops × 5 ciclos = 35 ciclos por cadeia em vez de 70 seriais). Um checkpoint na dim 8 permite sair mais cedo de blocos inteiros quando todas as somas parciais já excedem a pior distância conhecida. O hardware prefetch traz o próximo bloco para L1d enquanto os FMAs estão em execução.

O detalhe crítico: os sobreviventes do fast path float32 passam por um re-ranqueamento exato int64 antes da inserção no TopK. A acumulação float32 tem ~0,5% de erro relativo; o re-ranqueamento preserva a exatidão (FP=1/FN=0).

Pontuação: +5.509 (p99=2,52ms).

O Muro de Debugging: Uma Linha, 4 Submissões Perdidas

Esta é a parte que dói contar.

Fiz 5 mudanças simultâneas (violação da regra de isolamento de variável única): modo TCP do HAProxy, GC=200, GOAMD64=v3, PGO, warmup. A pontuação caiu de +5.504 para +4.673. O p99 foi de 2,55ms para 17,25ms.

Reverti para nginx, mas esqueci de restaurar a CPU do nginx de 0,10 para 0,20. As outras 4 variáveis continuaram mudando. Cada submissão culpou um culpado diferente:

| Tag | p99 | Hipótese | |-----|:---:|----------| | v11 | 17,25ms | "O modo TCP do HAProxy é o culpado" | | v12 | 88,48ms | "GC=200 é o culpado" | | v13 | 88,23ms | "GOAMD64=v3 é o culpado" | | v14 | 90,79ms | "PGO cross-arch é o culpado" | | v15 | 91,23ms | Todas as hipóteses de build esgotadas |

A diferença real? CPU do nginx em 0,10 (metade do original). 35x mais lento por falta de 0,10 de CPU. O conserto foi uma linha no docker-compose.yml:

cpus: "0.10"  # → "0.20"

Uma linha, 4 submissões perdidas, 3 horas perseguindo hipóteses erradas. A lição: nunca mude mais de uma variável entre testes. Anote cada mudança.

Engenharia Reversa do Número 1

Neste ponto eu tinha +5.183. O líder tinha +5.964 com p99=1,09ms e zero erros de detecção. Precisava entender o que estava perdendo.

Analisei as 2 melhores soluções:

| Competidor | Pontuação | p99 | FP/FN | |------------|:---------:|:---:|:-----:| | muanlartins | +5.964 | 1,09ms | 0/0 | | Joyce | +5.853 | 1,40ms | 0/0 | | Eu (ivf-v8) | +5.183 | 3,84ms | 2/1 |

O avanço foi o IVF exato de dois níveis do muanlartins:

Tier rápido (95,84% das consultas):
  RankCentroids(q, K=4096) → pegar top-2 centróides
  ScanCluster × 2 (~1.464 vetores no total)
  Se resultado for confiante → CONCLUÍDO

Escalação (4,16% das consultas):
  Pegar próximos 32 centróides restantes
  ScanCluster × 32 com AABB-LB + poda por desigualdade triangular
  → KNN-5 exato

Isso é KNN-5 exato com velocidade de busca aproximada. Ele pré-calculou limites de calibração offline contra os dados de teste. 95,84% das consultas completam após escanear apenas 1.464 vetores. Só quando o resultado é ambíguo ele escala para escanear mais centróides.

Outra descoberta crucial: QuantScale=10000 (não 32767). O dataset tem 4 casas decimais; k/10000 mapeia exatamente para int16(k) com perda de quantização zero. Isso eliminou o último falso negativo que eu carregava.

A Descoberta do mmap: Simples é Melhor

Minha otimização final quase não aconteceu. Tentei trocar o artefato de //go:embed para unix.Mmap para reduzir pressão de memória. Todas as 4 submissões de teste saíram imediatamente com OOM.

{
  "p99": "2.47ms",
  "scoring": {
    "breakdown": {"FP": 1, "FN": 0, "TP": 24037, "TN": 30020, "http_errors": 0},
    "failure_rate": "0%",
    "final_score": 5516.20
  }
}

Mas v22-v22d falharam todas com exit code 1. A causa raiz:

Segmento de dados binário (//go:embed artifact.bin): 86.6 MB  ← cobrado ao cgroup
Mmap (/artifact.bin, PROT_READ MAP_PRIVATE):         86.6 MB  ← file-backed
Total: ~174 MB
Limite de memória do cgroup: 130 MB
Resultado: OOM → exit 1

Eu tinha tanto //go:embed QUANTO mmap, duas cópias dos mesmos 86,6MB. O conserto foi remover o embed:

Depois (apenas mmap):
Tamanho binário: 5.8 MB (87MB → 5,8MB, 15x menor)
RSS total: ~45 MB
Espaço livre: 85 MB ✓

A submissão v22e marcou +5.516 (p99=2,47ms). A melhoria do GC por si só raspou 0,03ms da cauda porque o heap vivo caiu de ~96MB (embed) para ~10MB (mmap-only).

Resultados Finais

| Métrica | Valor | |---------|:-----:| | Pontuação final | +5.516 | | p99 | 2,47ms | | Falsos positivos | 1 (de 54.057 requisições) | | Falsos negativos | 0 | | Erros HTTP | 0 | | Recursos usados | 276MB de 350MB, 1,00 CPU | | Classificação geral | 46° de 230 |

Após uma revisão pós-submissão em 23 de maio, o reteste mostrou +5.251,25 (p99=2,66ms, 0,02% de falhas), mantendo a posição 46/230.

O que Aprendi

  1. Algoritmo vence micro-otimização. O clustering IVF deu +598 pontos com uma linha. O kernel AVX2 deu +3. O conserto do nginx deu +823 restaurando um único número.

  2. Mude uma variável por vez. Perdi 4 submissões e 3 horas porque fiz 5 mudanças de uma vez e não acompanhei o limite de CPU do nginx.

  3. Faça engenharia reversa dos melhores. Analisar o código-fonte do muanlartins revelou IVF exato de dois níveis, QuantScale=10000 e limites de calibração, nada disso eu teria inventado sozinho.

  4. Conheça seus limites de recursos. A contagem dupla embed+mmap era óbvia em retrospecto. Eu deveria ter medido o uso de memória virtual no container antes de enviar.

  5. A melhor otimização às vezes é deletar código. Remover //go:embed artifact.bin (1 import, 1 declaração de variável) reduziu o binário em 15x e consertou o OOM. Zero código novo.

Uma Nota Sobre as Ferramentas

Usei Opencode com DeepSeek V4 para 99% do código. Um commit foi feito com Cursor + GPT 5.5 (consertando um repositório git aninhado). O modelo V4 lidou com tudo, desde clustering IVF e assembly AVX2 até otimização de Docker e mmap. Modelos premium não são sempre necessários, contexto e estrutura importam mais que capacidade bruta.

Este foi também meu primeiro projeto em Go. Vindo de Python e C (42 School), o binário único do Go, a concorrência embutida e a biblioteca padrão rica o tornaram ideal para este problema. O hot path terminou com zero alocações por requisição, usando unsafe.Pointer para controle de memória nível C onde necessário, enquanto o GC cuidava de todo o resto.

Parei porque o projeto está completo e eu tinha outros projetos para trabalhar, todas as 5 fases, todos os 44 requisitos, rank 46/230. O retorno marginal da otimização estava diminuindo, e o tempo para outros trabalhos chamava. Foi genuinamente divertido, e eu recomendo que qualquer engenheiro de backend experimente uma competição como esta.