o problema
O Bloom filter é de 1970 e está em toda parte: roteador, cache, engine de armazenamento, qualquer lugar onde perguntar “esse item está no conjunto?” precisa ser barato e uma fração pequena de falsos positivos é tolerável. Ele tem duas operações, insert e lookup, e é isso. Não tem delete. Para remover um item você reconstrói o filtro inteiro, ou aceita falsos negativos — que costumam ser inaceitáveis, já que a garantia “se disse não, é não” é justamente o que faz o filtro valer a pena.
As tentativas de consertar isso pagaram caro. O counting Bloom filter troca cada bit por um contador de quatro bits ou mais e usa 3 a 4 vezes o espaço de um Bloom filter otimizado. O d-left counting Bloom filter melhora, mas ainda fica 1,5 a 2 vezes maior. O quotient filter chega perto do Bloom em espaço, só que guarda metadados por entrada e precisa decodificar uma sequência de entradas a cada operação: quando a tabela passa de 75% de ocupação, o desempenho despenca. O consenso implícito era que deleção custa espaço ou custa velocidade. Tem um segundo problema junto: um Bloom filter dimensionado para ε usa k = log2(1/ε) funções de hash, então quanto menor a taxa de erro alvo, mais bits espalhados pelo array cada lookup positivo precisa tocar — e mais cache miss.
a ideia
Em vez de um array de bits, uma tabela hash cuckoo densamente preenchida guardando apenas fingerprints: uma string curta de bits derivada do item. Consultar é procurar o fingerprint nos dois buckets candidatos do item. Como uma tabela cuckoo bem configurada enche até 95% sem colapsar, quase todo bit alocado carrega informação.
O obstáculo é que cuckoo hashing normal precisa realocar itens já inseridos, e para saber o bucket alternativo de um item você precisa da chave dele — que o filtro justamente não guardou. A saída é o partial-key cuckoo hashing: em vez de duas funções independentes, o segundo bucket é definido como h2 = h1 xor hash(fingerprint). O xor é seu próprio inverso, então a partir de qualquer bucket e do fingerprint que está lá dentro dá para calcular o outro candidato. A tabela passa a ser autossuficiente: ela contém tudo que a inserção precisa saber.
como funciona
O insert usa apenas informação local:
f = fingerprint(x)
i1 = hash(x)
i2 = i1 xor hash(f)
se bucket[i1] ou bucket[i2] tem entrada vazia: grava f, fim
i = i1 ou i2 (sorteado)
repita até MaxNumKicks (500 na implementação dos autores):
escolhe uma entrada aleatória de bucket[i]
troca f com o fingerprint dessa entrada
i = i xor hash(f)
se bucket[i] tem entrada vazia: grava f, fim
falha: tabela cheiaO fingerprint é hasheado antes do xor por um motivo prático. Com fingerprints de 8 bits e xor direto, um item expulso do bucket i cairia a no máximo 256 buckets de distância, porque só os bits baixos do índice mudariam. Hashear espalha as vítimas pela tabela inteira.
Lookup lê os dois buckets e compara. Delete remove uma cópia do fingerprint que casar. O caso feio — dois itens diferentes com o mesmo fingerprint no mesmo bucket — se resolve sozinho: se x e y colidem em i1 e no fingerprint, então i2 é o mesmo para os dois, e tanto faz qual cópia foi removida. A taxa de falso positivo depois da deleção continua a mesma.
Os parâmetros se puxam. Bucket maior enche mais (b = 1 chega a 50%, b = 2 a 84%, b = 4 a 95%, b = 8 a 98%), mas exige fingerprint mais longo, porque cada lookup compara 2b entradas: f ≥ log2(2b/ε). O custo por item é f/α. O ponto de equilíbrio para as taxas de erro que aparecem na prática é (2, 4) — dois buckets candidatos, quatro entradas cada. Sobre isso há o semi-sorting: como a ordem dos fingerprints dentro de um bucket não importa, quatro fingerprints de 4 bits ordenados têm só 3.876 combinações possíveis, que cabem num índice de 12 bits em vez de 16. Um bit economizado por item, ao preço de decodificar cada bucket lido.
Na medição dos autores, com filtros de 192 MB: o cuckoo filter guardou 127,78 milhões de itens a 12,60 bits por item com 0,19% de falso positivo; com semi-sorting, 12,58 bits e 0,09%; o Bloom filter, 13,00 bits e 0,19%.
o que isso custou
O ponto teórico incômodo os próprios autores levantam: o fingerprint mínimo cresce com o tamanho do filtro, f = Ω(log n / b), enquanto o Bloom filter gasta um número constante de bits por item independentemente de haver mil ou um bilhão deles. Na prática o b no denominador salva — com b = 4 e uma tabela de 2^30 buckets, seis bits de fingerprint já bastam para chegar perto da ocupação ótima —, mas a assíntota é pior, e a análise completa do partial-key cuckoo hashing fica declarada em aberto.
O resto dos limites é operacional. Existe um teto de ocupação: passado ele, inserir falha e a tabela precisa crescer, enquanto no Bloom filter você continua enfiando itens e só paga em falso positivo. Com deleção habilitada, o mesmo item não pode ser inserido mais que 2b vezes, senão os dois buckets estouram. Deletar item que nunca foi inserido pode apagar um item real que divide o fingerprint. A vazão de inserção cai conforme o filtro enche, porque as cadeias de realocação ficam longas. E o ganho de espaço tem fronteira nítida: abaixo de 3% de falso positivo o cuckoo filter com semi-sorting é menor que o Bloom filter otimizado; acima disso, não é.
onde isso aparece hoje
A comparação de base é o Space/Time Trade-offs in Hash Coding with Allowable Errors, e o inventário de usos que o paper toma como pano de fundo é o Network Applications of Bloom Filters: A Survey. O que o cuckoo filter oferece é uma regra de decisão curta: se seu filtro é dinâmico e o alvo de falso positivo é menor que 3%, ele domina; se o alvo é frouxo ou o filtro é imutável, o Bloom continua imbatível em simplicidade.
Essa segunda metade importa mais do que parece. Em engines LSM, o filtro é construído junto com um arquivo imutável e jogado fora na compactação — deleção nunca é exercida, e a maior vantagem do cuckoo filter não vale nada ali. O caso dele é o outro: conjunto que muda o tempo todo em memória, com orçamento de bits apertado e latência de cauda importando. Os autores publicaram a implementação de referência em C++, cerca de 500 linhas mais outras 500 para o semi-sorting, o que ajuda a explicar por que a estrutura saiu do paper rápido.