Thiago Silva

Posted on Sep 15

SetrixDB: motor de conjuntos em Go — interseção exata sobre IDs (e onde ele perde)

#database #go #performance #showdev

“Dado um ID, ele está nesta lista?” e “quais IDs aparecem nas duas listas ao mesmo tempo?” Parecem
exercícios de livro-texto. Mas quando essas listas têm milhões ou bilhões de elementos e precisam
responder em microssegundos — num filtro facetado, numa checagem de permissão, num pré-filtro de
candidatos para um LLM — a resposta deixa de ser trivial.

Este artigo é sobre uma primitiva específica: um motor de conjuntos exato sobre IDs uint64, com
números medidos e reproduzíveis — e uma seção dedicada a onde ele perde para uma biblioteca
consagrada. Não é sobre substituir bancos de dados; é sobre uma operação que costuma ficar em aberto.

O problema: álgebra de conjuntos sobre IDs

Boa parte do software moderno passa o tempo cruzando listas de identificadores:

E-commerce / busca: “produtos desta cor E deste tamanho E desta marca E em estoque” — interseção de quatro conjuntos.
Permissões / RAG: “quais documentos este usuário pode ver E casam com a busca?” — interseção de uma lista de permissão com uma lista de candidatos.
Antifraude / acesso: “este ID está em alguma lista de bloqueio?” — pertencimento puro.
Texto: cada termo ou frase vira uma chave; consultas combinadas são interseções.

Em todos esses casos o que importa é presença e interseção exatas sobre IDs — não payloads.
Estruturas genéricas (map, joins, varredura ordenada) resolvem isso — só não de forma otimizada:
carregam ponteiros, indireções e comparações desnecessárias quando o dado é o número.

A escolha central: trabalhar sempre com IDs uint64. Um conjunto é um monte de uint64; a
interseção é um AND. Tudo é aritmética.

O erro que valeu o projeto: 78% de colisão

Antes de existir conjunto, preciso de identificadores densos e sem colisão. O primeiro keygen foi um
hash posicional — uma fórmula aritmética simples. Ele colidia feio: numa base de 200 mil tokens
alfanuméricos curtos, 78% colidiam, e "Oa" e "0b" caíam no mesmo ID.

A correção foi implementar um Minimal Perfect Hash Function (CHD v2, do zero):

0 colisões numa base de 50 milhões de chaves;
4,03 bits/chave (≈ 24 MiB para 50M de chaves) — 3,4× menos memória que a v1 (13,68 bits/chave);
lookup em ~118 ns, e o pertencimento continua exato.

Se este artigo tiver uma única lição, é esta: medir a taxa de colisão no corpus real é o passo
que quase todo mundo pula — e é o que muda a arquitetura inteira.

Como funciona (do termo ao resultado)

Keygen (MPHF): termo → ID uint64 determinístico e sem colisão.
Representação: o ID i vira o bit i de um bitset; há também conjunto esparso (lista ordenada) e um híbrido (faixas quentes em bitset + cauda fria esparsa).
Kernel: o AND dos bitsets roda em AVX-512 (vpandq + vpopcntq) via cgo, com dispatch em runtime (__builtin_cpu_supports) e fallback escalar — o mesmo binário funciona em qualquer máquina.
Escala: o universo é fatiado em shards (paraleliza o compute); no cluster, cada nó serve um shard, o coordenador faz broadcast e soma, e um consistent hash ring decide a posse (entrar/sair um nó remapeia só ~1/(N+1) dos IDs).

Os números reais

Ambiente (todas as medições): servidor de referência — 2 vCPU AMD EPYC (Zen4, AVX-512), 3,8 GB
RAM, Go 1.22 (+ gcc para o cgo). Data: 09/2026.

Pertencimento (n = 1M)

Estrutura	memória	velocidade	exato?
`map[uint64]` (Go)	22,3 B/chave	133,3M ops/s	sim
SetrixDB (MPHF CHD v2)	0,5 B/chave (estrutura)	~118 ns/lookup	sim
Bloom filter (1% falso-positivo)	1,2 B/chave	23,6M ops/s	não

Paridade de velocidade com o map, com 2,2× menos memória — e resultado exato, ao contrário
de um filtro probabilístico.

Interseção (A = B = 1M)

Estratégia	IDs densos (`denso32`)	IDs aleatórios 64-bit (`aleat64`)
Merge ordenado (SetrixDB)	9,2 ms	11,3 ms
Roaring (bitmap comprimido)	148 µs	523 ms
Hash join (`map`)	91,6 ms	94,9 ms
Bitset `AND` (Go puro)	29 µs	—
Bitset `AND` (AVX-512)	6 µs	—

Onde ele perde (e por que isso importa)

Vou ser explícito, porque comparação sem contexto engana:

Universo esparso e enorme: quando o universo não cabe na RAM, o bitset denso deixa de ser opção (ele ocupa universo/8, sempre). Aí o Roaring ganha — é para isso que ele existe. Medido: universo 2²⁶, o Roaring64 usou ~2 MB contra 8,2 MB do meu bitset (mais lento em tempo, mais econômico em memória).
IDs aleatórios de 64 bits: no caso aleat64, o Roaring levou 523 ms — mas porque ele foi projetado para outro regime. O ponto não é “eu ganho sempre”; é em qual regime cada um brilha.
Range queries, similaridade, joins: o SetrixDB não faz. É igualdade pura.
Atualizações frequentes: um MPHF é construído para um conjunto; inserir/remover chaves novas exige reconstrução. Para cargas mutáveis, ele não é a ferramenta.

Então onde ele ganha? No regime oposto: universo denso que cabe em RAM, conjuntos grandes,
interseção exata no caminho quente. Foi exatamente o que um teste com dados reais mostrou ↓

Dados reais (nada de só sintético)

Rodei três datasets públicos e conferi cada resultado por fora do SetrixDB (sort + comm).

Varejo — Online Retail II (UCI)

1.067.371 linhas reais de venda (UK, 2009–2011). Consulta “Reino Unido E 4º tri/2011 E
preço ≥ 5” → 22.701 linhas em 823 µs. Verificação independente: 22.701. Idêntico.

Texto — títulos da Wikipédia (19,3 milhões de termos)

enwiki-latest-all-titles-in-ns0: 19.264.252 títulos. “multi-palavra E começa com s” →
1.408.399 em 9,5 ms; “multi-palavra E United” → 38.602 em 8,0 ms. Verificado: idêntico.

Escala — MovieLens 25M (25 milhões de interações)

25.000.095 avaliações reais; facetas derivadas (gênero, década, nota). Conjuntos com 10,9M e
12,4M de membros. Três consultas, todas verificadas por fora:

Consulta	Resultado
Drama E anos 2000 E nota ≥ 4	1.634.027
Drama E nota ≥ 4	6.096.563
Comédia E nota ≥ 4 E anos 2000	965.677

O resultado mais revelador deste teste é sobre escolher a representação certa. No mesmo
universo de 25M de IDs, com conjuntos de dezenas de milhões:

Caminho	memória/conjunto	latência (A∩B)
Merge de listas ordenadas	87,7 MB	80,4 ms
Bitset denso (AVX-512)	2 MB	227 µs

Mesmo resultado exato, ~350× mais rápido e ~43× menor. Quando o universo é denso e cabe na
memória, o bitset não é só o mais rápido: é o mais econômico também.

O que o SetrixDB É — e o que NÃO É

É um motor de conjuntos embarcável, em Go, que responde presença e interseção exatas
sobre IDs uint64, com kernel SIMD, sharding e modo de cluster. Ele coexiste com o seu banco
atual: o dado continua onde está; o SetrixDB entra ao lado como índice/pré-filtro.

Não é banco relacional, colunar, NoSQL ou vetorial. Não faz SQL, joins nem similaridade. E —
importante — guarda conjuntos de IDs, não payloads.

Limitações honestas

Alpha (v0.1.0). Testado em loopback e entre duas máquinas; o cluster de 3 nós rodou em nuvem, mas ainda não em produção multi-datacenter.
Memória do bitset é linear no universo (universo/8); o híbrido mitiga (2³⁶ IDs: 8,59 GB densos → 1,73 MB híbridos), mas é uma escolha com custo.
Backend de NPU e protocolo UDP compacto: roadmap, não implementados.
Benchmarks de energia (J/busca): planejados, ainda não medidos.
Se algum número não se reproduzir na sua máquina, isso é um bug — e eu quero saber.

Perguntas difíceis (e respostas)

“Por que não usar CRoaring/Roaring direto?”
Porque o Roaring é excelente — e é a resposta certa quando o universo não cabe em RAM ou é muito
esparso. O SetrixDB mira outro ponto: Go nativo, embarcável, universo denso que cabe em RAM, com
MPHF no keygen e sharding/cluster integrados. Se o seu caso é o do Roaring, use o Roaring.

“Por que não um map/Bloom filter?”
map guarda ponteiros e é ~44× mais gordo por chave (22,3 vs 0,5 B/chave aqui). Bloom é menorzinho,
mas erra (1% de falso-positivo) — em permissão, errar para o lado “pode ver” é inaceitável.

“MPHF aguenta inserção/remoção?”
Não. Ele é construído para um conjunto. Cargas mutáveis exigem reconstrução (ou o modo esparso). É
uma troca consciente por lookup O(1) e ~4 bits/chave.

“E o GC do Go no caminho quente?”
Os bitsets são []uint64 contíguos, alocados uma vez; o laço quente não aloca. Para DMA (NPU) há
UnsafePtr + pinning — com o aviso de manter o buffer vivo.

“Isso não é só ‘bitset com AVX-512’?”
Em parte, sim — e é bom que seja: bitset + SIMD é uma base sólida e conhecida. O que o projeto
adiciona é o pacote: keygen sem colisão, representação adaptativa (denso/esparso/híbrido),
sharding/cluster e o modo “conjuntos armazenados” (só o nome trafega na rede).

O convite

O SetrixDB é open source (Apache-2.0). Se a próxima onda não é sobre guardar mais, mas sobre
decidir mais rápido — e se operações de conjunto merecem um motor dedicado, exato e vetorizado,
ao lado do que você já usa — venha testar.

Código, benchmarks reproduzíveis e quickstart: https://github.com/setrixdb/setrixdb

Rode os benchmarks, abra uma issue e me diga onde os números não fecham.

SetrixDB — the arithmetic set engine.
Conjuntos. Em microssegundos. Em qualquer chip. Ao lado do seu banco.

DEV Community