Rinha de Backend 2026: quantizando 298 MB de JSON em 87 MB de i16

Capa do post 4 da série Rinha de Backend 2026: 'Comprime uma vez. Mmapa pra sempre.' à esquerda, e três cards à direita mostrando o caminho dos 3 milhões de vetores — 298 MB JSON na fonte, 87 MB i16 na imagem Docker, e 0 ms de parse/alloc por request.

Começando

No post anterior o Slice 2a fechou a vetorização: cada transação que chega no serviço vira [f32; 14] por uma função pura, com gabarito do regulamento como suite de teste. Bonito. Inútil sem o segundo lado da equação.

O regulamento manda comparar essa transação contra 3 milhões de transações de referência já rotuladas como legítimas ou fraudulentas. Esses 3 milhões moram num arquivo: references.json.gz, 50 MB comprimido, 298 MB de JSON puro descompactado.

O teto de memória da Rinha 2026 é 350 MB pra stack inteira (dois containers de API + nginx). Carregar 298 MB de JSON em runtime, parsear, alocar 3 milhões de objetos Rust com vetor + string de label dentro? Não cabe. Nem perto.

O Slice 2b é a resposta: um binário que roda uma vez no build do Docker, lê o gz, esmaga os 3 milhões de vetores em i16, e cospe três arquivos binários crus que o runtime depois só mapeia em memória — sem parser, sem alocação, sem JSON.

A conta que escolheu o tipo numérico

Antes de escrever uma linha de código, a conta de memória. Cada vetor são 14 números. Multiplicando por 3 milhões e variando o tipo:

Tipo	Bytes por dim	Bytes por vetor	Total (3M)	Cabe em 350 MB?
f32	4	56	168 MB	só com aperto
i16	2	28	84 MB	sim, sobra
u8	1	14	42 MB	sim, com folga

O f32 come metade do orçamento total. Inviável — sobrariam 182 MB pra tudo: dois processos Rust, tokio, nginx, page cache, malloc do serde, buffers de socket. Aperto absurdo.

O u8 é tentador pela folga, mas dá uma dor de cabeça: os vetores podem ter o sentinela -1 nas dimensões 5 e 6 (quando last_transaction: null). Em u8, range [0..255], eu teria que reservar um valor mágico — tipo 255 — pra significar “ausência de dado”. E aí toda a aritmética da distância euclidiana precisa de um branch: “se um dos dois é 255, então ignora essa dimensão”. Branch dentro do hot loop, em SIMD, é exatamente o tipo de coisa que joga o p99 pro espaço.

O i16 resolve isso de graça. Range [-32768, 32767]. Sentinela -1 vira -10000 na quantização e fica natural na conta de distância: se a query também tem null no mesmo índice, dx = 0 (idêntico, contribuição zero). Se uma tem null e a outra tem valor, dx explode e a distância sobe — exatamente o que se quer.

Decidido: i16, escala 10000.

Quantização: o roundtrip que prova que não dói

A função é cinco linhas:

fn quantize(v: f32) -> i16 {
    let scaled = (v * 10_000.0).round();
    if scaled >= i16::MAX as f32 { i16::MAX }
    else if scaled <= i16::MIN as f32 { i16::MIN }
    else { scaled as i16 }
}

round em Rust é round half away from zero — 0.00005 vira 1, -0.00005 vira -1. Estável entre máquinas, idêntico em x86 e arm64. Os clamps na borda existem só por paranóia: os valores do dataset já estão em [-1, 1], mas se algo bagunça (input maluco, bug na vetorização), prefiro saturar a estourar o tipo.

Pra provar que não estou perdendo informação que importa, um teste de roundtrip:

#[test]
fn roundtrip_error_bounded_by_inverse_scale() {
    for x in [0.0, 0.0001, 0.0833, 0.5, 0.9506, 1.0, -1.0] {
        let r = quantize(x) as f32 / 10_000.0;
        assert!((r - x).abs() <= 1.0 / 10_000.0);
    }
}

Erro máximo: 0.0001. As 14 dimensões do regulamento são reportadas com 4 casas decimais — exatamente a precisão que o i16 com escala 10000 entrega. A quantização não muda o valor visível em nenhuma dimensão. A distância euclidiana entre dois vetores quantizados difere da “verdadeira” em ordens de grandeza menores que a separação típica entre legítimo e fraude.

Tradução: a quantização não vai bagunçar a busca. Posso provar com número.

Os três arquivos: sem cabeçalho, sem parser, sem cópia

Pipeline do Slice 2b: à esquerda, no build-time, references.json.gz (50 MB gz / 298 MB JSON) entra no binário preprocess (Rust, single thread, 1.83 s) e sai como três arquivos — refs.i16.bin 84 MB, labels.bin 3 MB, metadata.json 200 B, total 87 MB. Esses arquivos são embutidos na imagem Docker e, em runtime, o axum + tokio carrega o Index via memmap2 direto pra &[i16] e itera com chunks_exact(14) — zero parse, zero alloc, page cache compartilhado entre 2 containers. — Build-time roda uma vez (gz → preprocess → 3 binários crus). Runtime só mapeia o arquivo direto pra `&[i16]`, sem parse e sem alocação.

O preprocess escreve três coisas em data/:

Arquivo	Tamanho	Conteúdo
`refs.i16.bin`	84 MB	3M × 14 inteiros i16 little-endian crus, sem cabeçalho
`labels.bin`	3 MB	1 byte por registro: `0` = legit, `1` = fraud
`metadata.json`	200 B	`count`, `dims`, `scale`, encoding dos labels (só pra sanity)

A escolha que paga lá na frente: sem cabeçalho, sem padding, sem versionamento dentro do arquivo binário. O runtime mapeia o arquivo direto pra &[i16] com memmap2::Mmap::map e itera com chunks_exact(14). Zero parse. Zero cópia. Zero alocação no carregamento.

A validação do contrato — “esse arquivo realmente tem 14 dims, escala 10000, etc.” — vive no metadata.json ao lado, lido uma vez no boot. Se algum dia eu precisar mudar o formato (u8, quantização diferente, dims diferentes), bumpa o metadata, recompila o preprocess, faz outra layer Docker. O binário cru continua um array contíguo de inteiros.

preprocess: count=3000000 dims=14 scale=10000 elapsed_ms=1825
  refs:     data/refs.i16.bin (84000000 bytes)
  labels:   data/labels.bin   (3000000 bytes)
  metadata: data/metadata.json

1.83 segundo pra digerir 298 MB de JSON, em release, single-thread. Mais que isso seria preocupante. Menos que isso seria milagre. O bom é que esse passo roda uma vez por build do Docker — pra cada git commit que mexa em algo da imagem. Não na hora da requisição.

Determinismo: o detalhe que parece bobo (e não é)

Rodando o preprocess duas vezes seguidas no mesmo input:

$ shasum -a 256 data/refs.i16.bin
d5beb0640d8a35657d206e2cdd372cf7b74591be23d44253b85ca7dcac337461  data/refs.i16.bin

$ ./target/release/preprocess resources/references.json.gz data
$ shasum -a 256 data/refs.i16.bin
d5beb0640d8a35657d206e2cdd372cf7b74591be23d44253b85ca7dcac337461  data/refs.i16.bin

SHA-256 idêntico. Idem pro labels.bin. Parece detalhe besta. Não é.

O Docker (e o BuildKit) cacheia layers pelo hash do conteúdo do contexto + comando. Se o RUN preprocess produzisse um arquivo diferente a cada build — por exemplo, porque eu usei HashMap em algum lugar e dependi da ordem de iteração, que em Rust é não-determinística por padrão — toda execução do docker build reprocessaria os 3 milhões de registros. Toda execução do CI ficaria 2 segundos mais lenta à toa. Cada push de uma vírgula no Dockerfile invalidaria a layer.

Com saída bit-exact reproduzível, é o oposto: a layer do preprocess fica cacheada pra sempre, até eu mudar o JSON de input ou o código do binário. Build subsequente do Docker pula direto pra parte que mudou.

A garantia vem de coisas pequenas: vetorizar na ordem de leitura do JSON (não em paralelo com ordem indefinida), escrever os bytes em little-endian explícito (i16::to_le_bytes), usar round em vez de as i16 (que trunca de forma diferente entre plataformas pra valores negativos). Cinco minutos pensando nisso, horas de build economizadas depois.

Pausa pra quem não manja de Rust

Vou traduzir o problema todo numa analogia.

A Rinha de Backend pediu pra eu construir um serviço que decide se uma transação de cartão é fraude. O regulamento diz: “compare a transação que chegou com 3 milhões de transações antigas que já sabemos se foram fraude ou não, pegue as 5 mais parecidas, e responda com base nelas”.

Pra fazer isso rápido, eu preciso ter essas 3 milhões na memória do servidor. Mas elas vêm num arquivo JSON gigante — 298 MB. Carregar e parsear isso a cada vez que o serviço sobe seria como abrir uma planilha de Excel com 3 milhões de linhas toda vez que você liga o computador. Lento. E o servidor da Rinha só tem 350 MB de RAM no total — nem cabe.

Solução: pré-cozinhar a comida. Em vez de carregar a planilha em runtime, eu rodo um programa pequeno uma vez, durante a construção da imagem do servidor, que faz três coisas:

Lê o JSON gigante.
Comprime cada número decimal num inteiro pequeno (de 0.0833 pra 833). Como esses inteiros cabem em 2 bytes em vez dos 4 do número original, o arquivo final ocupa metade da memória.
Salva tudo num formato binário cru, sem texto, sem JSON, sem nada — só os bytes dos números encostados.

Quando o servidor liga, ele só “mapeia” esse arquivo binário em memória — operação do kernel que é praticamente instantânea, não precisa parsear nada. É como abrir um cofre que já está organizado por dentro: o conteúdo está pronto pra uso.

Esse pré-cozinhar acontece uma vez por versão do serviço. Os 3 milhões caem de 298 MB pra 87 MB, e a inicialização passa de “vários segundos parseando JSON” pra “praticamente instantânea”.

Decisões pequenas que vão pagar lá na frente

flate2 como única dependência nova. O preprocess precisa descomprimir gzip. flate2 é a crate canônica em Rust, sem milagre. Recusei serde-with e variantes mais sofisticadas — a entrada é simples (array de objects com vector e label) e o serde_json::from_reader padrão dá conta.

Layout single-threaded. Pensei em paralelizar a quantização com rayon. Não compensa: o gargalo é o parser JSON, e gzip + serde_json já saturam um core. Paralelizar viraria contenção sobre o leitor. 1.83s single-thread já é suficiente — se um dia virar problema (improvável, é build-time), volto.

Sem checksum embutido no refs.i16.bin. Hash do conteúdo de um arquivo binário cru é trivial de calcular com shasum por fora. Embutir um checksum dentro do arquivo iria contra a ideia de “array contíguo sem cabeçalho que mmapa direto pra &[i16]”. O metadata.json carrega o tamanho esperado e o count; se o arquivo for adulterado, o boot percebe pelo tamanho não casar.

Labels em arquivo separado, não interleaved. Poderia ter espremido (vector, label) no mesmo arquivo, alternando 28 bytes de vetor com 1 byte de label. Mas isso quebra o chunks_exact(14) do mmap — eu precisaria fazer stride manual e cuidar do alinhamento. Dois arquivos separados é mais simples e cacheia melhor: durante a busca, o hot loop só toca refs.i16.bin; o labels.bin só é consultado nas (no máximo) 5 inserções no top-K por requisição.

A distribuição que apareceu sem eu pedir

Como bonus do preprocess, contei os labels que saíram do gz:

legit  = 2,000,594  (66.69%)
fraud  =   999,406  (33.31%)

Um terço de fraude. O regulamento não promete essa proporção em lugar nenhum, mas é o que tá no dataset. Isso muda como eu penso sobre o threshold de decisão: fraud_score = num_fraudes_entre_os_5 / 5, approved = score < 0.6. Pra um score acima de 0.6 acontecer, eu preciso de pelo menos 3 fraudes entre os 5 mais próximos.

Numa amostragem aleatória do dataset (não os mais próximos, aleatórios mesmo), a probabilidade de 3 ou mais fraudes em 5 cartas é C(5,3)·0.33³·0.67² + C(5,4)·0.33⁴·0.67 + 0.33⁵ ≈ 21%. Ou seja: chutando 5 vizinhos no escuro, em 21% das vezes eu já marco “fraude” sem ter feito nada inteligente. O algoritmo precisa fazer melhor que isso por uma margem confortável pra valer alguma coisa. A separação dos clusters legítimo/fraude no espaço de 14 dimensões é a aposta — e só vou descobrir se ela existe quando rodar a busca no Slice 3.

O que ficou de fora (de propósito)

u8 com quantização mais agressiva. Discutido na seção do tipo numérico — o sentinela -1 complica demais a aritmética de distância. Talvez volte no Slice 5+ depois de medir.
Cabeçalho versionado no binário. Acrescenta complexidade no carregamento sem ganho real. Se o formato mudar, é outra versão do projeto inteiro.
Quantização paralela. Single-thread já fecha o build-time em < 2s. Otimização sem problema pra resolver.
bytemuck ou crates de cast. Não preciso — i16::to_le_bytes e from_le_bytes da std fazem o trabalho. Menos dependência transitiva, binário menor.
mmap no preprocess. Aqui é write, não read. Manter BufWriter é mais simples e o overhead some no ruído.

Slice 3 é onde toda essa contabilidade paga: o serviço carrega o data/refs.i16.bin mmap’do em 87 MB e responde /fraud-score de verdade — pega o vetor de 14 dims da query, escaneia os 3 milhões de referências, mantém os 5 mais próximos num array de stack, conta as fraudes e responde.

O algoritmo é o pior possível em termos de big-O: linear, 3 milhões de iterações por requisição. Por que? Porque eu ainda não sei se vou precisar de algo melhor. Medir o pior caso primeiro, otimizar com número na mão — é a tese que move o projeto desde o post 2.

Código completo em obrunogonzaga/rinha-backend-2026-rust. PR do Slice 2b: #3.