Conceitos
Estruturas probabilísticas (Bloom, HyperLogLog, Count-Min)
Intuição
Imagine que você precisa responder perguntas sobre uma quantidade enorme de itens sem poder guardar a lista inteira: 'já vi este item?', 'quantos itens diferentes vi?', 'quantas vezes apareceu este?'. Em vez da lista, você mantém um quadro pequeno e de tamanho fixo, e cada item, depois de embaralhado por uma fórmula, deixa marcas em algumas posições desse quadro. Como o quadro é bem menor que os dados, ele guarda só um resumo, seja porque itens diferentes acabam marcando as mesmas posições, seja porque as marcas são só um indício estatístico; por isso as respostas são aproximadas e, em troca, quanto maior o quadro, menor o erro, e você escolhe quanto erro aceitar.
Como funciona
Todas essas estruturas usam funções de hash para espalhar os itens de forma que parece aleatória e guardam um resumo de tamanho fixo, em vez do conjunto ou do fluxo. O Bloom filter é um vetor de m bits com k funções de hash: inserir um item liga os k bits correspondentes, e consultar diz 'certamente não está' se algum desses bits for 0, ou 'assume-se que está' se todos forem 1, resposta que pode ser um falso positivo, mas nunca há falso negativo. Depois de inserir n itens, a taxa de falso positivo é aproximadamente (1 − e^(−kn/m))^k, e, dados m e n, o k que a minimiza é ln 2 · m/n, ponto em que metade dos bits fica em 0 e a taxa é cerca de 0,6185^(m/n). O HyperLogLog estima quantos itens distintos existem: os primeiros b bits do hash escolhem um entre m = 2^b registradores, o restante do hash dá o rho (a posição do bit 1 mais à esquerda), e cada registrador guarda o maior rho visto, pois um prefixo com muitos zeros sugere uma cardinalidade grande. A estimativa usa a média harmônica dos valores 2^registrador; no modelo de multiconjunto ideal (valores hasheados uniformes e independentes) e para m ≥ 3, o Teorema 1 do paper dá erro padrão assintótico de β_m/√m mais uma pequena oscilação (menor que 5×10^-4 para m ≥ 16), com β_m limitado e igual a cerca de 1,04 no limite, e uma correção de faixa pequena trata cardinalidades baixas. O Count-Min Sketch estima a frequência de cada item com uma matriz de contadores de d linhas e w colunas, com w = ⌈e/ε⌉ e d = ⌈ln(1/δ)⌉, em que cada linha tem seu próprio hash; uma atualização (i, c) soma c ao contador h_j(i) em cada linha j, e, quando os valores do vetor nunca ficam negativos, a consulta pontual devolve o mínimo entre as linhas, porque aí itens que colidem só acrescentam valor ao contador (se os valores puderem ser negativos, o artigo usa a mediana); no caso não negativo a estimativa nunca fica abaixo do valor real a_i e, com probabilidade de pelo menos 1 − δ, não passa de a_i + ε·||a||₁, em que ||a||₁ é a soma dos valores do vetor, de modo que o erro é sempre para cima. Estes resumos também se combinam: o OU bit a bit de dois Bloom filters de mesmo tamanho e mesmas funções de hash representa a união dos conjuntos, o máximo componente a componente dos registradores do HyperLogLog calculados sobre partes de um arquivo dá os registradores do arquivo inteiro, e dele sai a estimativa total, e a soma linear das atualizações no Count-Min facilita juntar sketches de locais distribuídos.
Na prática
Escolhe-se a estrutura pela pergunta e pelo erro que o sistema tolera: o Bloom filter para pertinência, o HyperLogLog para contar itens distintos e o Count-Min para frequências. No Summary Cache, cada proxy web transmite um Bloom filter do seu cache em vez de uma lista de URLs, e um falso positivo apenas faz o proxy pedir uma página a outro proxy que não a tem, custo que o levantamento de Broder e Mitzenmacher considera menor que o ganho em tráfego; segundo esse levantamento, a técnica é usada no Squid, com o nome de Cache Digests. Em monitoramento de rede, o HyperLogLog conta pares origem-destino distintos, o que ajuda a detectar ataques e a propagação de worms, e, quando as contagens só crescem, o Count-Min permite achar heavy hitters (itens muito frequentes) sem perder nenhum, já que a estimativa nunca fica abaixo do valor real.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.