Papers
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics, Vol. 1, No. 4, pp. 485-509 (2004), 2004
O problema e o princípio do Bloom filter
O artigo é um levantamento: reúne, de forma unificada, como os Bloom filters foram usados e modificados em problemas de rede. Um Bloom filter é uma estrutura de dados randomizada, econômica em espaço, que representa um conjunto para responder consultas de pertinência. O preço é aceitar falsos positivos, mas os autores observam que a economia de espaço muitas vezes compensa isso quando a probabilidade de erro é controlada. A estrutura é um vetor de m bits, inicialmente todos em 0, mais k funções de hash independentes que mapeiam cada item para posições do vetor. Para inserir um elemento, calculam-se as k posições e ligam-se esses bits em 1. Para consultar, calculam-se as k posições do item: se algum bit for 0, o item certamente não está no conjunto; se todos forem 1, assume-se que está, embora possa ser um falso positivo. Portanto não há falsos negativos. O tema que une as aplicações é que o filtro oferece uma forma sucinta de representar uma lista ou conjunto que, completo, ocuparia espaço demais na rede. Os autores resumem isso no chamado princípio do Bloom filter: onde quer que se use uma lista ou conjunto e o espaço seja precioso, considere um Bloom filter se o efeito dos falsos positivos puder ser mitigado. O artigo agrupa as aplicações em quatro categorias, que os próprios autores admitem ser soltas e não exaustivas: colaboração em redes de sobreposição e peer-to-peer, roteamento de recursos, roteamento de pacotes e medição.
A matemática: taxa de falso positivo, k ótimo e limite inferior
Após inserir os n elementos, a probabilidade de um bit específico continuar em 0 é aproximadamente e elevado a menos kn/m. A taxa de falso positivo é então aproximadamente (1 menos essa quantidade) elevada a k. Há duas forças opostas: mais funções de hash dão mais chances de encontrar um bit 0 para um item de fora do conjunto, mas deixam menos bits em 0 no vetor. Dados m e n, o número de funções que minimiza a taxa é k igual a ln 2 vezes m/n; nesse ponto, metade dos bits fica em 0 e a taxa fica em (1/2) elevado a k, cerca de (0,6185) elevado a m/n. Na prática k precisa ser inteiro, e um k um pouco menor pode ser preferido porque exige calcular menos hashes. O artigo cita como exemplo que, com m igual a 8n, a taxa de falso positivo é pouco acima de 0,02. Os autores também derivam um limite inferior: qualquer representação que permita falsos positivos para uma fração no máximo ε do universo, sem falsos negativos, precisa de essencialmente n log2(1/ε) bits, quando n é pequeno em relação ao tamanho do universo (o caso prático). Comparando, o Bloom filter ótimo precisa de um fator log2 e, cerca de 1,44, a mais que esse limite assintótico. Esquemas com menos bits existem, como os baseados em hash perfeito, mas o artigo os descreve como mais complicados e menos flexíveis; com hash perfeito, qualquer mudança no conjunto exigiria recomputar a função.
Variações: união, contadores e filtros comprimidos
A estrutura simples permite truques baratos. Se dois filtros representam conjuntos diferentes, têm o mesmo número de bits e usam as mesmas funções de hash, o OU bit a bit dos vetores representa a união. Se o tamanho é potência de 2, o filtro pode ser reduzido à metade fazendo o OU da primeira metade com a segunda e mascarando o bit mais significativo nas consultas. Outro problema é a remoção: zerar os bits de um item removido pode apagar bits compartilhados com outros itens. A solução, atribuída no artigo a Fan e colaboradores, é o counting Bloom filter, que troca cada bit por um pequeno contador, incrementado na inserção e decrementado na remoção. A análise citada no artigo indica que 4 bits por contador bastam para a maioria das aplicações, e que, com k no máximo (ln 2)m/n, a probabilidade de algum contador chegar a 16 fica abaixo de 1,37 × 10^-15 vezes m. Se um contador estoura, uma abordagem é deixá-lo no valor máximo. Há ainda o filtro comprimido, proposto por Mitzenmacher: quando o filtro será transmitido, pode valer a pena usar um vetor maior e mais esparso, com menos funções de hash, e comprimi-lo. No exemplo da tabela do artigo, com no máximo 16 bits transmitidos por elemento, passar de 16 bits por elemento e 11 hashes (taxa de 0,000459) para um vetor de 48 bits por elemento e 3 hashes, que comprimido fica abaixo de 16 bits por elemento com alta probabilidade, reduz a taxa cerca de pela metade.
Aplicações colaborativas e de roteamento de recursos
O exemplo detalhado do artigo é o Summary Cache, de Fan e colaboradores, para compartilhamento entre caches web. Em vez de trocar listas de URLs, cada proxy transmite periodicamente um Bloom filter do conteúdo do seu cache. Em um falso positivo, o proxy pede uma página a outro proxy que não a tem, gerando atraso extra; ainda assim, o texto afirma que o ganho em tráfego supera esse custo. Como o cache muda com frequência, sugere-se manter localmente um counting Bloom filter e difundir a versão comum de 0 e 1; a alternativa seria reconstruir o filtro do zero a cada atualização enviada, e o counting Bloom filter reduz e amortiza esse custo. O artigo diz que a técnica é usada no proxy Squid, onde os filtros se chamam Cache Digests. Em redes peer-to-peer de tamanho moderado (centenas de nós), guardar um filtro para cada um dos outros nós pode ser viável quando guardar a lista de objetos de cada nó não é, como no protótipo PlanetP. Para reconciliar conjuntos, um par envia seu filtro ao outro, que então envia só o que parece faltar; devido aos falsos positivos, nem tudo é enviado, mas a maior parte sim. No roteamento de recursos, um framework em árvore mantém listas unificadas por nó, e a união por OU facilita construí-las. Um falso positivo pode levar o pedido a um caminho errado, exigindo retrocesso ou um mecanismo mais lento e seguro. Rhea e Kubiatowicz usam o attenuated Bloom filter, um vetor de filtros por aresta, um por distância de saltos.
Roteamento de pacotes, medição e limites
No roteamento de pacotes, o artigo descreve três usos. Em Icarus, cada pacote leva no cabeçalho um pequeno Bloom filter dos nós visitados; se o OU da máscara de um nó não altera o filtro, pode haver um laço. No Stochastic Fair Blue, um counting Bloom filter detecta fluxos agressivos ou que não respondem à marcação de congestionamento. Cada contador tem uma probabilidade de marcação que sobe quando há muitos pacotes enfileirados naquele contador e desce quando não há nenhum, e o pacote é marcado com a menor das k probabilidades; um fluxo bem-comportado que cai nos mesmos contadores sofre um falso positivo, e uma mitigação sugerida é trocar periodicamente as funções de hash. Para multicast, Grönvall propõe guardar, por interface, um filtro de endereços, evitando armazenar os endereços no roteador. Em medição, Estan e Varghese hasheiam cada pacote k vezes em contadores de bytes e marcam um fluxo como pesado se o menor contador passa de um limiar; a atualização conservadora, que só eleva os contadores ao máximo que o fluxo pode ter acumulado, reduz bastante os falsos positivos em dados reais, pois vários fluxos leves que caem no mesmo contador têm menos chance de empurrá-lo acima do limiar. No SPIE, roteadores guardam filtros dos pacotes vistos para rastrear a origem de pacotes maliciosos; um falso positivo cria ramificações extras no caminho reconstruído. O artigo fecha lembrando o custo: os falsos positivos precisam ser avaliados em cada aplicação, e cita extensões posteriores como count-min sketch, spectral e Bloomier filters.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.