Eu sabia da universidade sobre o filtro Bloom , uma estrutura probabilística de dados com o nome de Burton Bloom. Mas não tive a oportunidade de usá-lo. No mês passado, essa oportunidade apareceu - e essa estrutura literalmente me fascinou. No entanto, logo encontrei algumas falhas nela. Este artigo é uma história sobre meu breve caso de amor com o filtro Bloom.

No processo de pesquisa de falsificação de IP, foi necessário verificar os endereços IP nos pacotes recebidos, comparando-os com a localização geográfica de nossos data centers. Por exemplo, pacotes da Itália não devem ir ao data center brasileiro. Esse problema pode parecer simples, mas no cenário em constante mudança da Internet está longe de ser simples. Basta dizer que, no final, acumulei muitos arquivos de texto grandes com aproximadamente o seguinte conteúdo:

Isso significa que uma solicitação do endereço IP resolvido 192.0.2.1 foi registrada no datacenter número 107 do Cloudflare. Esses dados vieram de várias fontes, incluindo nossas amostras ativas e passivas, os logs de alguns domínios que possuímos (por exemplo,cloudflare.com), fontes abertas (por exemplo, tabelas BGP) etc. A mesma linha geralmente é repetida em vários arquivos.

No final, recebi um conjunto de dados gigantesco desse tipo. Em algum momento, em todas as fontes coletadas, contei 1 bilhão de linhas. Normalmente, escrevo scripts bash para pré-processar dados de entrada, mas nessa escala essa abordagem não funcionou. Por exemplo, a remoção de duplicatas a partir deste minúsculo arquivo de 600 MiB e 40 milhões de linhas leva ... a eternidade:

basta dizer que as linhas de duplicação com comandos comuns do tipo sortem várias configurações (ver --parallel, --buffer-sizee --unique) não era o melhor para tal um grande conjunto de dados.

Filtros Bloom

Ilustração de David Epstein em domínio público

Então me dei conta: não ordene as linhas! Você precisa remover duplicatas, para que algum tipo de estrutura de dados 'definida' funcione muito mais rápido. Além disso, eu sei aproximadamente o tamanho do arquivo de entrada (o número de linhas únicas) e a perda de alguns dados não é crítica, ou seja, a estrutura probabilística dos dados é bastante adequada.

Isso é perfeito para filtros Bloom!

Enquanto você lê aWikipedia sobre filtros Bloom, é assim que eu olho para essa estrutura de dados.

Como você implementariaa pluralidade? Dada uma função de hash ideal e memória infinita, podemos simplesmente criar um bitmap infinito e definir um número de bit para cada elementohash(item). Isso fornece a estrutura de dados ideal para a "multidão". Direita? Trivialmente. Infelizmente, as funções de hash colidem, e a memória infinita não existe; portanto, em nossa realidade, precisamos comprometer. Mas podemos calcular a probabilidade de colisões e gerenciar esse valor. Por exemplo, temos uma boa função de hash e 128 GB de memória. Podemos calcular que a probabilidade de colisão para cada novo elemento é de 1 a 1099511627776. Quando você adiciona mais elementos, a probabilidade aumenta à medida que o bitmap é preenchido.

Além disso, podemos aplicar mais de uma função de hash e obter um bitmap mais denso. É aqui que o filtro Bloom funciona bem, que é um conjunto de dados matemáticos com quatro variáveis:

n - número de elementos inseridos (número cardinal)
m - memória usada pelo bitmap
k - o número de funções hash calculadas para cada entrada
p - probabilidade de coincidência falso positiva

Dado o número cardinal ne a probabilidade desejada de um falso positivo p, o filtro Bloom retorna a memória necessária me o número necessário de funções de hash k.

Confira esta excelente visualização de Thomas Hurst de como os parâmetros se afetam.

mmuniq-bloom

Guiado pela intuição, adicionei a ferramenta probabilística mmuniq-bloom ao meu arsenal, que recebe a entrada STDIN e retorna apenas linhas exclusivas no STDOUT. Deve ser muito mais rápido que uma combinação de sort+ uniq!

Ali está ele:

mmuniq-bloom.c

Para simplificar e agilizar, defini inicialmente alguns parâmetros. Primeiro, a menos que seja indicado de outra forma, o mmuniq-bloom usa oito funções de hash k = 8. Parece estar perto do número ideal para o tamanho dos nossos dados, e a função hash pode produzir rapidamente oito hashes decentes. Em seguida, alinhamos a memória mno bitmap à potência de dois para evitar uma operação cara %modulo, que no assembler diminui a velocidade div. Se o array for igual à potência de dois, podemos simplesmente usar AND bit a bit (por diversão, leia como os compiladores otimizam algumas operações de divisão multiplicando por uma constante mágica ).

Agora podemos executá-lo no mesmo arquivo de dados que usamos anteriormente:

Oh, isso é muito melhor! 12 segundos em vez de dois minutos. O programa usa uma estrutura de dados otimizada, uma quantidade relativamente limitada de memória, análise de linha otimizada e bom buffer de saída ... e com tudo isso, 12 segundos parecem uma eternidade em comparação com a ferramenta wc -l:

O que está acontecendo? Entendo que contar seqüências de caracteres é wcmais fácil do que calcular seqüências únicas, mas a diferença de 26 horas é realmente justificada? O que a CPU absorve mmuniq-bloom?

Deve ser para hashes de computação. O utilitário wcnão gasta o processador, fazendo toda essa matemática estranha para cada uma das 40 milhões de linhas. Eu uso uma função hash não trivial siphash24, com certeza queima o processador, certo? Vamos verificar executando apenas a função hash, mas nãonão executando operações com o filtro Bloom:

Isso é estranho. O cálculo da função hash leva apenas cerca de dois segundos, embora todo o programa na execução anterior tenha sido executado por 12 segundos. Um filtro Bloom funciona por 10 segundos? Como isso é possível? Essa é uma estrutura de dados tão simples ...

Arma Secreta - Profiler

É hora de aplicar a ferramenta certa para esta tarefa - vamos executar o criador de perfil e ver no que o processador está trabalhando. Primeiro, vamos correr stracepara verificar se não há chamadas inesperadas do sistema:

tudo parece bom. Dez chamadas para mmap4 ms cada (3971 μs) são intrigantes, mas tudo bem. Nós preenchemos a memória com MAP_POPULATE, para evitar erros posteriormente devido à falta de uma página.

Qual é o próximo passo? Claro que sim perf!

Então vamos ver o resultado:

Então, nós realmente queimamos 87,2% dos ciclos no código principal. Vamos ver exatamente onde. A equipe perf annotate process_line --sourceimediatamente mostra algo inesperado.

Vimos que 26,90% do processador queimaram emmov, Mas isso não é tudo! O compilador insere corretamente a função e expande o loop. Acontece que a maioria dos ciclos vai para isso movou para a linha uint64_t v = *p!

Obviamente, perf está errado, como uma string tão simples pode ocupar tantos recursos? Mas repetir o teste com qualquer outro gerador de perfil mostra o mesmo problema. Por exemplo, eu gosto de usar o google-perftools com o kcachegrind devido aos diagramas coloridos:

O resultado da visualização é o seguinte:

Deixe-me resumir o que descobrimos até agora.

O utilitário padrão wcprocessa um arquivo 600 MiB por 0,45 s. Nossa ferramenta otimizada mmuniq-bloomdura 12 segundos. O processador é gravado em uma instrução mov, desreferenciando a memória ...

Imagem de Jose Nicdao , CC BY / 2.0

Oh! Como eu poderia esquecer. O acesso aleatório à memória émuitolento! Muito, muito, muito devagar!

De acordo com osnúmeros que todo programador deve saber, um único acesso à RAM leva cerca de 100 ns. Vamos contar: 40 milhões de linhas, 8 hashes cada. Como nosso filtro Bloom tem um tamanho de 128 MiB, emnosso hardware antigoele não se encaixa no cache L3! Os hashes são distribuídos uniformemente por uma ampla faixa de memória - cada um deles gera uma falha de cache. Coloque tudo junto, e acontece ...

Acontece que 32 segundos queimam apenas em acessos à memória. O programa real cabe em apenas 12 segundos, já que o filtro Bloom ainda se beneficia do cache. É fácil ver com isso perf stat -d:

Sim, deveríamos ter tido pelo menos 320 milhões de erros de cache (LLC-load-misses), mas apenas 280 milhões ocorreram: isso ainda não explica por que o programa funcionou em apenas 12 segundos. Mas não importa. É importante que o número de falhas de cache seja um problema real, e só podemos resolvê-lo reduzindo o número de acessos à memória. Vamos tentar configurar o filtro Bloom para usar apenas uma função de hash:

Ay! Isso realmente dói! Para obter uma probabilidade de colisão de 1 por 10.000 linhas, o filtro Bloom exigia 64 gigabytes de memória. É horrível!

Além disso, não parece que a velocidade tenha aumentado significativamente. O sistema operacional levou 22 segundos para preparar a memória para nós, mas ainda gastamos 11 segundos no espaço do usuário. Acredito que agora todas as vantagens de um acesso mais raro à memória são compensadas por uma menor probabilidade de entrar no cache devido a um tamanho de memória bastante aumentado. Antes, 128 MiB eram suficientes para o filtro Bloom!

Recusando filtros Bloom

Isso está ficando ridículo. Para reduzir a probabilidade de falsos positivos, você deve usar muitos hashes no filtro Bloom (por exemplo, oito) com muitos acessos de memória ou deixar uma função de hash, mas use grandes quantidades de memória.

Na verdade, não temos um limite de memória, queremos minimizar o número de chamadas para ele. Precisamos de uma estrutura de dados que custe no máximo uma falta de cache por elemento e use menos de 64 gigabytes de RAM ...

É claro que você pode implementar estruturas de dados complexas, como um filtro de cuco , mas certamente existe uma opção mais fácil. E a boa e antiga tabela de hash de sondagem linear?

Ilustração de Vadims Podans

Conheça mmuniq-hash

Aqui está a nova versão do mmuniq-bloom usando uma tabela de hash:

mmuniq-hash.c

Em vez dos bits do filtro Bloom, agora armazenamos hashes de 64 bits da função 'siphash24' . Isso fornece uma proteção muito melhor contra colisões de hash: muito melhor que uma por 10.000 linhas.

Vamos contar. Adicionar um novo item a uma tabela de hash, digamos, com 40 milhões de entradas, dá a chance de colisões de hash 40 000 000/2^64. Isso é cerca de 1 em 461 bilhões - uma probabilidade bastante baixa. Mas não adicionamos um elemento ao conjunto pré-preenchido! Em vez disso, adicionamos 40 milhões de linhas ao conjunto inicialmente vazio. De acordo com o paradoxo do aniversário , isso aumenta muito a probabilidade de colisões. Uma aproximação razoável seria uma estimativa '~n^2/2m, no nosso caso, é~(40M^2)/(2*(2^64)). Acontece uma chance em 23.000. Em outras palavras, com uma boa função de hash, esperamos uma colisão em um dos 23.000 conjuntos aleatórios de 40 milhões de elementos. Essa é uma probabilidade diferente de zero, mas ainda melhor do que no filtro Bloom, e é completamente tolerável para o nosso caso de uso.

O código com uma tabela de hash funciona mais rápido, possui melhores padrões de acesso à memória e menor probabilidade de falsos positivos do que no filtro Bloom.

Não se assuste com a linha de “conflitos de hash”, ela mostra o quão cheia a tabela de hash está. Usamos o sensor linear, portanto, quando entramos no conjunto completo, pegamos o próximo vazio. No nosso caso, temos que pular uma média de 0,7 conjuntos para encontrar um ponto vazio na tabela. Isto é normal. Como iteramos os conjuntos em uma ordem linear, a memória deve estar qualitativamente cheia.

No exemplo anterior, sabemos que nossa função hash leva cerca de dois segundos. Concluímos que 40 milhões de acessos à memória levam cerca de quatro segundos.

Lições aprendidas

Os processadores modernos são realmente bons no acesso seqüencial à memória quando é possível prever padrões de amostragem (consulte pré-busca em cache ). O acesso aleatório à memória, por outro lado, é muito caro.

Estruturas de dados avançadas são muito interessantes, mas tenha cuidado. Computadores modernos exigem o uso de algoritmos otimizados para cache. Ao trabalhar com grandes conjuntos de dados que não cabem no L3, é preferível a otimização sobre o número de ocorrências, em vez da otimização sobre a quantidade de memória usada.

É justo dizer que os filtros Bloom têm um ótimo desempenho quando colocados no cache L3. Mas se não, então eles são terríveis. Isso não é novidade: os filtros Bloom são otimizados para a quantidade de memória, não o número de chamadas. Por exemplo, vejaartigo científico sobre filtros de cuco .

Outra coisa são discussões intermináveis sobre funções de hash. Honestamente, na maioria dos casos isso não importa. O custo de contar até funções complexas de hash parece ser siphash24pequeno comparado ao custo do acesso aleatório à memória. No nosso caso, simplificar a função hash trará apenas um pequeno benefício. O tempo de CPU é desperdiçado em outro lugar - aguardando memória!

Um colega costuma dizer: “Pode-se supor que os processadores modernos sejam infinitamente rápidos. Eles trabalham em velocidade infinita, até descansarem contra a parede da memória ".

Por fim, não repita meu erro. Você sempre precisa primeiro criar perfis comperf stat -de veja o contador do IPC (instruções por ciclo). Se for menor que um, isso geralmente significa que o programa está parado aguardando memória. Os valores ótimos estão acima de dois. Isso significa que a carga de trabalho está principalmente na CPU. Infelizmente, em minhas tarefas, o IPC ainda é baixo ...

Mmuniq superior

Com a ajuda de colegas, escrevi uma versão aprimorada da ferramenta mmuniq com base em uma tabela de hash. Aqui está o código:

mmuniq.c

Ele pode alterar dinamicamente o tamanho da tabela de hash, suporta entrada com um número cardinal arbitrário. Em seguida, processa os dados em pacotes, efetivamente usando a dica prefetchna CPU, que acelera o programa em 35-40%. Tenha cuidado, o uso abundante prefetchno código raramente produz efeito. Para usar essa função, reordenei especialmente os algoritmos. Com todas as melhorias, o tempo de execução foi reduzido para 2,1 segundos:

o fim

A criação de uma ferramenta básica que tenta superar a combinação 'sort / uniq' revelou alguns recursos ocultos da computação moderna. Depois de suar um pouco, aceleramos o programa de mais de dois minutos para dois segundos. Durante o desenvolvimento, aprendemos sobre o atraso no acesso aleatório à memória, bem como sobre o poder das estruturas de dados amigáveis ao cache. Estruturas de dados bizarras atraem a atenção, mas na prática geralmente é mais eficiente reduzir o número de acessos aleatórios à memória.

Quando o filtro bloom não se encaixa