/ / Bloom filtro ou cuco hash? - algoritmo, hash, filtro

Bloom filtro ou cuco hash? - algoritmo, hash, filtro

Qual você prefere e por quê?

Ambos podem ser usados ​​para realizar tarefas semelhantes, mas estou curioso para ver o que as pessoas usaram em aplicações reais e seu raciocínio para fazê-lo.

Respostas:

9 para resposta № 1

Os filtros Bloom e os filtros Cuckoo são usados ​​em situações similares, mas há muitas diferenças abaixo que geralmente determinam qual é a melhor escolha.

Filtros Bloom são usados ​​internamente no banco de dadosmotores, especialmente o Apache Cassandra. As razões são, como disseram outros pôsteres, para reduzir o custo de operações lentas. Basicamente, qualquer operação "isso talvez ou definitivamente não existe" com um alto custo pode usar um filtro Bloom para reduzir o número de verificações feitas.

Outro exemplo comum com o modelo SaaS de hojeseria um serviço REST remoto com um custo por chamada. Qualquer chamada de API com uma resposta binária, como "este endereço é INVALID", pode usar um filtro de bloom para eliminar mais de 90% das consultas duplicadas! Observe que, como os filtros Bloom e Cuckoo possuem falsos positivos, eles NÃO são úteis para a operação inversa "este endereço é VÁLIDO"

Importante lembrar é que Bloom e Cucofiltros não têm falsos negativos. Isso torna esses filtros úteis para verificações como "isso definitivamente não é ou talvez spam", mas não é útil para operações em que os falsos positivos são inaceitáveis, como a verificação das permissões do usuário. Nesse aspecto, eles podem ser conceitualmente considerados o oposto de um cache. Ambos os filtros e caches Bloom / Cuckoo são usados ​​principalmente para reduzir o custo de operações caras com uma resposta booleana, exceto que os caches não têm falsos positivos e o Bloom / Cuckoo não tem falsos negativos.

Diferenças notáveis ​​entre Cuco / Bloom incluem:

  • Combinação. Os filtros Bloom podem ser mesclados eficientemente desde que sejam criados com os mesmos parâmetros. Ambos rapidamente e com pouca largura de banda. É por isso que você os vê frequentemente em sistemas distribuídos massivamente, trocar rapidamente filtros Bloom é rápido. Os filtros de cuco não são facilmente compostos, tornando-os menos úteis nessas circunstâncias.

  • Taxa positiva falsa. Os filtros de cuco são mais eficientes em termos de espaço. Muitos casos de uso para ambas as estruturas são focados em redes de baixo nível. Em hardware fraco, a eficiência de filtros Cuckoo de ~ 40% a mais para a mesma taxa de falsos positivos pode ser importante. A implementação de referência, em c ++, classifica os itens em cada bucket para economizar espaço adicional, aproveitando a posição de um item em um bucket para armazenar impressões digitais menores. As bibliotecas adicionais que mencionarei posteriormente (incluindo a minha) não parecem Se alguém alguma vez usar minha biblioteca, eu poderia adicioná-la :).

  • Taxa de falsos positivos constante. Os filtros Bloom apresentam taxas de falso positivo assintoticamente piores à medida que ultrapassam o tamanho projetado. Você pode continuar inserindo itens para sempre, mas eventualmente sua taxa de falsos positivos será de quase 100%. Os filtros de cuco, baseados no hashing Cuckoo, têm uma capacidade definida onde as inserções realmente falharão. Repetir a inserção de hashes de itens não aleatórios pode fazer com que os filtros Cuco falhem na inserção, possivelmente muito antes de seu nível de preenchimento projetado.

  • Rapidez. Isso é subjetivo e depende muito do hardware, mas os filtros Cuco geralmente são mais rápidos no caso médio (na minha experiência). A maioria dos designs de filtro Bloom executa uma função hash duas vezes. Ao usar funções hash seguras, especialmente, isso pode ser um grande obstáculo em comparação com os filtros Cuckoo, que só inserem os itens uma vez. O código que vi usa várias funções de hashing para os filtros Bloom e Cuckoo. O Google goava de Murmur3, muitas outras implementações usam SHA1 ou qualquer outra coisa. Se as colisões de hash puderem ser exploradas para você usar o caso, verifique se a biblioteca usa um hash seguro. É importante saber que os filtros Bloom demoram um tempo constante para serem inseridos, enquanto os filtros Cuckoo têm um caso AVERAGE de tempo constante. Como os filtros Cuckoo ficam dentro de alguns por cento da capacidade, as velocidades de inserção diminuem consideravelmente. Mesmo assim, apenas a velocidade de inserção diminui, todas as outras operações são tempo médio constante.

  • Flexibilidade. Os filtros Bloom apenas suportam inserção e contém. Os filtros de cuco também suportam exclusão e contagem limitada. No design de referência, os filtros Cuco podem determinar quantas vezes um item foi inserido, até 7 vezes. Filtros Bloom só podem determinar sim-não. Os filtros cuco também suportam a exclusão de itens inseridos, um grande positivo em muitos casos de uso em comparação com o Bloom. Ao usar filtros Bloom, é bastante comum recriar o filtro do zero quando ele estiver "cheio" (a taxa de positivos falsos estimada excede o limite), pois você não pode excluir itens antigos. Observe que a reconstrução do filtro ainda acontece com filtros Cuckoo quando insere começar a falhar, portanto, dependendo do caso de uso, isso pode ser discutível.Em certas situações, os filtros Cuckoo são mais úteis, pois você pode excluir itens para permanecer dentro dos limites de filtro, em vez de reconstruí-los.

  • Apoio, suporte. Os filtros de cuco são bibliotecas novas e estáveis ​​para muitas línguas simplesmente não existem.

A maior vantagem dos filtros Bloom é queeles têm suporte de biblioteca mais maduro na maioria dos idiomas. A matemática por trás dos filtros Bloom também é melhor compreendida pelos cientistas. A maioria das características dos filtros Cuckoo foi determinada empiricamente, enquanto os filtros Bloom têm uma base numérica sólida. Isso exclui os filtros Cuco para sistemas críticos e em tempo real que devem ter verificação de seu desempenho, mesmo que evidências experimentais mostrem que os filtros Cuco têm um desempenho melhor na maioria das circunstâncias.

Shameless Plug: Eu sou o desenvolvedor de uma biblioteca de filtros Cuckoo para Java. CucoFiltro4J . Está faltando o semi-tipo de balde usado nopapel para que a eficiência do espaço é um pouco menor do que a implementação de referência. No readme do projeto, tenho links para outras implementações que conheço. Qual estrutura é melhor depende do seu caso de uso, mas principalmente se existe uma implementação sólida de filtro Cuckoo para o seu idioma.

Você deve definitivamente dar uma olhada na fonteantes de usar um filtro Cuco / Bloom em produção. Eu li várias libs antes de escrever o meu próprio ... muitos deles tinham limites de tamanho silencioso devido a matrizes subjacentes de 32 bits ou problemas óbvios de desempenho. A maioria teve zero testes. A implementação do Guava Bloom do Google teve de longe a melhor qualidade de código e testes (e suporta limites de matriz de 64 bits). As únicas deficiências com o Bloom da Guava é que ele não tem uma opção para usar uma função hash segura e isn " t multi-threaded.

Em um sistema de produção, você pode querermulti-threading para velocidade. A resposta para o Bloom do Guava é fazer um filtro diferente para cada thread e combiná-los ocasionalmente. Como os filtros do Cuckoo não podem ser combinados, adicionei threading simultâneo à minha biblioteca de filtros Cuckoo. Os outros que eu estou ciente não são seguros ou não são concorrentes.


8 para resposta № 2

Qual você prefere, vinho ou queijo?

UMA filtro de flores é para quando você tem espaço limitado, alto custo de consultae principalmente consultas negativas.
Nesse caso, um filtro de flores com 8 bits por tecla e 4 funções hash da-te Taxa de falsos positivos de 2,5%; você processa consultas quase 40 vezes mais rápido do que antes, ao custo de 1 byte por tecla.

Por outro lado, se algum dos condições anteriores não seguram, uma tabela de hash agindo como um cache faz sentido, embora, obviamente, vai demorar um muito mais do que um byte por entrada :-)

Você pode até mesmo ignorar os casos difíceis de cuco se é um cache. Isso também faz com que os problemas de aumento de tamanho tabelas de hash de cuco (ou qualquer coisa diferente de hash linear) discutível.


5 para resposta № 3

Filtro de cuco.

"Filtro de cuco: praticamente melhor que Bloom." Fan de Bin, David Andersen, Michael Kaminsky e Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994

De um dos autores " blog:

Deixe-me descrever um filtro de cuco e algunsO que está no jornal para você? Se você quer evitar uma discussão técnica, tudo que você precisa saber é que, para conjuntos de tamanhos razoavelmente grandes, para a mesma taxa de falso positivo de um filtro Bloom correspondente, os filtros de cuco usam menos espaço do que Bloom filtros, são mais rápidos em pesquisas (mas mais lento em inserções / para construir), e surpreendentemente também permitem exclusões de chaves (o que filtros Bloom não pode fazer). Se você quiser olhar para o código, há mesmo um repositório github para você com código para filtros de cuco.


2 para resposta № 4

Eu prefiro hash cuco. Desconfio dos falsos positivos que podem aparecer com filtros de bloom em fatores de preenchimento mais altos.
Usamos o hashing cuco em um aplicativo em que tínhamos tabelas hash muito grandes e estávamos enfrentando problemas de pressão na memória. Por favor, veja minha biblioteca eCollections em http://codeplex.com/ecollections para a implementação de uma variante do hashing cuco.

Atenciosamente,


0 para a resposta № 5

Se eu posso tolerar os falsos positivos e o espaço é crítico, eu uso um filtro Bloom porque ele ocupa menos espaço. Caso contrário, eu uso um hash.