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

¿Filtro Bloom o hash de cuco? - algoritmo, hash, filtro

cuál prefieres y por qué?

Ambos pueden usarse para realizar tareas similares, pero tengo curiosidad por ver qué personas han usado en las aplicaciones reales y su razonamiento para hacerlo.

Respuestas

9 para la respuesta № 1

Los filtros Bloom y los filtros Cuckoo se usan en situaciones similares, pero hay muchas diferencias debajo que generalmente determinan cuál es una mejor opción.

Los filtros Bloom se usan internamente en la base de datosmotores, notablemente Apache Cassandra. Las razones son, como dicen otros carteles, para reducir el costo de las operaciones lentas. Básicamente, cualquier operación de "si esto no existe o definitivamente no existe" con un alto costo puede usar un filtro Bloom para reducir la cantidad de comprobaciones realizadas.

Otro ejemplo común con el modelo de SaaS de hoySería un servicio REST remoto con un costo por llamada. Cualquier llamada API con una respuesta binaria como "es esta dirección NO VÁLIDA" puede usar un filtro de floración para eliminar más del 90% de las consultas duplicadas. Tenga en cuenta que dado que los filtros Bloom y Cuckoo tienen falsos positivos, NO son útiles para la operación inversa "es esta dirección VÁLIDA"

Importante recordar es que Bloom y Cuckoolos filtros NO tienen falsos negativos. Esto hace que estos filtros sean útiles para comprobaciones como "definitivamente esto no es así o tal vez es correo no deseado", pero no es útil para operaciones en las que los falsos positivos son inaceptables, como verificar los permisos de los usuarios. En este aspecto, pueden conceptualmente considerarse lo opuesto a un caché. Tanto el filtro Bloom como el cuco se usan principalmente para reducir el costo de operaciones costosas con una respuesta booleana, excepto que las memorias caché no tienen falsos positivos y Bloom / Cuckoo no tiene falsos negativos.

Las diferencias notables entre Cuckoo / Bloom incluyen:

  • Combinación. Los filtros Bloom se pueden fusionar eficientemente siempre que se creen con los mismos parámetros. Rápido y con poco ancho de banda. Esta es la razón por la que los ve con frecuencia en sistemas distribuidos masivamente, intercambiar filtros Bloom es rápido. Los filtros de cuco no son fácilmente compostables, lo que los hace menos útiles en estas circunstancias.

  • Tasa de falsos positivos. Los filtros Cuckoo son más eficientes en cuanto a espacio. Muchos casos de uso para ambas estructuras se centran en redes de bajo nivel. En hardware débil, la eficacia ~ 40% mayor de los filtros Cuckoo para la misma tasa de falsos positivos puede ser importante. La implementación de referencia, en c ++, clasifica los elementos dentro de cada segmento para ahorrar espacio adicional, aprovechando la posición de un elemento dentro de un cubo para almacenar huellas dactilares más pequeñas. Las bibliotecas adicionales que mencionaré más adelante (incluida la mía) no parecen haz esto. Si alguien alguna vez usa mi biblioteca, podría agregarla :).

  • Tasa constante de falsos positivos. Los filtros Bloom tienen tasas asintóticamente peores de falsos positivos a medida que superan el tamaño diseñado. Puede seguir insertando elementos para siempre, pero finalmente su tasa de falsos positivos será casi del 100%. Los filtros de cuco, basados ​​en hashing de Cuckoo, tienen una capacidad establecida en la que las inserciones realmente fallarán. La repetición de la inserción de hashes de elementos no aleatorios puede hacer que los filtros Cuckoo fallen su inserción, posiblemente mucho antes de su nivel de llenado diseñado.

  • Velocidad. Esto es subjetivo y depende mucho del hardware, pero los filtros Cuckoo generalmente son más rápidos en el caso promedio (según mi experiencia). La mayoría de los diseños de filtro de Bloom ejecutan una función hash dos veces. Al usar funciones hash seguras especialmente, esto puede ser una gran desventaja en comparación con los filtros Cuckoo que solo insertan elementos hash una vez. El código que he visto utiliza varias funciones de hash para los filtros Bloom y Cuckoo. Google Bloom de Guava usa Murmur3, muchas otras implementaciones usan SHA1 u otra cosa. Si las colisiones hash se pueden explotar para su caso de uso, asegúrese de que la biblioteca utilice un hash seguro. Es importante saber que los filtros Bloom tardan aproximadamente un tiempo constante en insertarse, mientras que los filtros Cuckoo tienen un caso PROMEDIO de tiempo constante. A medida que los filtros Cuckoo alcanzan un porcentaje de capacidad, las velocidades de inserción disminuyen considerablemente. Incluso entonces, solo se ralentiza la velocidad de inserción, todas las demás operaciones son tiempo promedio constante.

  • Flexibilidad. Los filtros Bloom solo admiten inserción y contienen. Los filtros Cuckoo también son compatibles con la eliminación y el conteo limitado. En el diseño de referencia, los filtros Cuckoo pueden determinar cuántas veces se insertó un artículo, hasta 7 veces. Los filtros Bloom solo pueden determinar si-no. Los filtros Cuckoo también son compatibles con la eliminación de elementos insertados, un gran positivo en muchos casos de uso en comparación con Bloom. Cuando se utilizan filtros Bloom, es bastante normal recrear el filtro desde cero cuando está "lleno" (la tasa estimada de falsos positivos supera el umbral) ya que no se pueden eliminar elementos antiguos. Tenga en cuenta que la reconstrucción del filtro aún ocurre con los filtros Cuckoo cuando se inserta comience a fallar, por lo que dependiendo del caso de uso, esto podría ser discutible. En ciertas situaciones, los filtros Cuckoo son más útiles ya que puede eliminar elementos para mantenerse dentro de los límites del filtro en lugar de reconstruir.

  • Apoyo. Los filtros de cuco son bibliotecas nuevas y estables para muchos idiomas simplemente no existen.

La mayor ventaja de los filtros Bloom es quetienen un soporte de biblioteca más maduro en la mayoría de los idiomas. La matemática detrás de los filtros Bloom también es mejor entendida por los científicos. La mayoría de las características de los filtros Cuckoo han sido determinadas empíricamente, mientras que los filtros Bloom tienen una base numérica sólida. Esto excluye los filtros Cuckoo para sistemas críticos y en tiempo real que deben tener verificación de su rendimiento, aunque la evidencia experimental muestra que los filtros Cuckoo funcionan mejor en la mayoría de las circunstancias.

Shameless Plug: soy el desarrollador de una biblioteca de filtros Cuckoo para Java. CuckooFilter4J . Le falta el semi-tipo de cubo utilizado en elpapel, por lo que la eficiencia del espacio es algo menor que la implementación de referencia. En el archivo Léame del proyecto, tengo enlaces a otras implementaciones de las que tengo conocimiento. La estructura que es mejor depende de su caso de uso, pero principalmente de si existe una implementación sólida de filtro Cuckoo para su idioma.

Definitivamente deberías echarle un vistazo a la fuenteantes de usar un filtro Cuckoo / Bloom en producción. Leí varias librerías antes de escribir las mías ... muchas de ellas tenían límites de tamaño silenciosos debido a arreglos subyacentes de 32 bits o problemas obvios de rendimiento. La mayoría tenía cero pruebas. La implementación de Google Guava Bloom tuvo la mejor calidad de código y pruebas (y admite límites de matriz de 64 bits). Las únicas deficiencias con Bloom de Guava es que no tiene una opción para usar una función de hash segura y no es " t multihilo.

En un sistema de producción, es posible que deseemulti-threading para la velocidad. La respuesta para Bloom de Guava es hacer un filtro diferente para cada hilo y combinarlos de vez en cuando. Como los filtros Cuckoo no se pueden combinar, agregué el uso simultáneo a mi biblioteca de filtros Cuckoo. El otro soy consciente de que no son seguros o no son concurrentes.


8 para la respuesta № 2

¿Qué prefieres, vino o queso?

UN filtro de floración es para cuando tienes espacio limitado, alto costo de consultay consultas en su mayoría negativas.
En ese caso, un filtro de floración con 8 bits por tecla y 4 funciones hash te dio 2.5% tasa de falsos positivos; usted procesa consultas casi 40 veces más rápido que antes, a costa de 1 byte por clave.

Por otro lado, si alguno de los las condiciones previas no son válidas, un tabla hash que actúa como un caché tiene sentido, aunque obviamente tomará una mucho más de un byte por entrada :-)

Incluso puede omitir los casos de borde duro de hash cuco si es un caché. Eso también hace que los problemas de aumento de tamaño de tablas de hash cuco (o cualquier cosa que no sea hash lineal) discutible.


5 para la respuesta № 3

Filtro de cuco.

"Filtro de cuco: Prácticamente mejor que Bloom". Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994

De uno de los autores " Blog:

Déjame describir un filtro de cuco y algunos delo que está en el papel para usted. Si desea evitar una discusión técnica, todo lo que necesita saber es que para conjuntos de tamaño razonablemente grande, para la misma tasa de falsos positivos que un filtro Bloom correspondiente, los filtros de cuco usan menos espacio que Bloom filtros, son más rápidos en las búsquedas (pero más lentos en las inserciones / construcciones) y, sorprendentemente, también permiten eliminar las claves (lo que los filtros Bloom no pueden hacer). Si desea ver el código, incluso hay una repositorio github para ti con código para filtros de cuco.


2 para la respuesta № 4

Prefiero el hash del cuco. Desconfío de los falsos positivos que pueden aparecer con los filtros de floración en factores de relleno más altos.
Hemos utilizado hashing de cuco en una aplicación donde teníamos tablas hash muy grandes y estábamos teniendo problemas de presión de memoria. Por favor mira mi biblioteca de eCollections en http://codeplex.com/ecollections para la implementación de una variante de hash de cuco.

Saludos cordiales,


0 para la respuesta № 5

Si puedo tolerar los falsos positivos y el espacio es crítico, uso un filtro Bloom porque ocupa menos espacio. De lo contrario, uso un hash.