CUCKOO vs BLOOM filter, desde la perspectiva de Gopher

En este artículo, estoy tratando de implementar y probar la eficiencia de un filtro de cuco sobre un filtro de floración. (Lea la publicación anterior en Chord DHT, implementando una tabla hash distribuida en Golang)

Introducción

Las estructuras de datos probabilísticas son muy útiles, especialmente cuando se procesan grandes conjuntos de datos. La mayoría de las veces, mientras se trabaja en el lado de los datos, uno desearía hacer una simple consulta "es el elemento no presente" o "es el elemento ya presente" mientras procesa los datos en tiempo real. Supongamos que desea responder consultas en tiempo real, como el número de ips únicos, los ips más frecuentes, si un anuncio ya se ha entregado a un usuario, el uso de estructuras de datos probabilísticas proporciona una forma eficiente de responder estas consultas. El enfoque típico para tales consultas sería usar un HashMap o un HashTable, o almacenarlo en un caché externo (como redis), pero el problema es con grandes conjuntos de datos, estas estructuras de datos simples no pueden caber en la memoria. Aquí es donde entran en juego las estructuras de datos probabilísticas debido a sus ventajas de espacio y tiempo.

Ejemplos de casos de uso

  • Google Bigtable, Apache HBase y Apache Cassandra, y Postgresql usan filtros Bloom para reducir las búsquedas de disco para filas o columnas inexistentes. Evitar búsquedas costosas de disco aumenta considerablemente el rendimiento de una operación de consulta de base de datos.
  • Medium utiliza filtros Bloom para verificar si un artículo ya ha sido recomendado a un usuario
  • Ethereum usa filtros Bloom para encontrar rápidamente registros en la cadena de bloques Ethereum
  • El navegador web Google Chrome solía usar un filtro Bloom para identificar URL maliciosas. Cualquier URL se verificó primero con un filtro Bloom local, y solo si el filtro Bloom devolvió un resultado positivo se realizó una verificación completa de la URL (y el usuario advirtió, si eso también devolvió un resultado positivo)

¿Qué hay en un "cuco"?

Hemos utilizado filtros de floración en muchos lugares para responder a estas consultas en la plataforma de datos. Recientemente me encontré con este artículo sobre el filtro Cuckoo que me llamó la atención. El título en sí dice: "Filtro de cuco: prácticamente mejor que Bloom", así que decidí echarle un vistazo.

Los filtros de cuco mejoran el diseño del filtro de floración al ofrecer eliminación, recuento limitado y una probabilidad de falsos positivos limitada, al tiempo que mantienen una complejidad espacial similar. Utilizan hash cuckoo para resolver colisiones y son esencialmente una tabla compacta hash cuckoo.

Los filtros Cuckoo y Bloom son útiles para las pruebas de membresía cuando el tamaño de los datos originales es grande. Ambos solo usan 7 bits por entrada. También son útiles cuando se puede evitar una operación costosa antes de la ejecución mediante una prueba de membresía establecida. Por ejemplo, antes de consultar una base de datos, se puede realizar una prueba de pertenencia establecida para ver si el objeto deseado está incluso en la base de datos.

Algoritmo

Parámetros del filtro:
1. Dos funciones de hash: h1 y h2
2. Una matriz B con n cubos. El cubo i-ésimo se llamará B [i]

Entrada: L, una lista de elementos para insertar en el filtro de cuco.

Algoritmo:
Mientras L no está vacío:
    Sea x el primer elemento de la lista L. Elimine x de la lista.
    Si B [h1 (x)] está vacío:
        colocar x en B [h1 (x)]
    De lo contrario, si B [h2 (x) está vacío]:
        colocar x en B [h2 (x)]
    Más:
        Sea y el elemento en B [h2 (x)].
        Anteponer y a L
        colocar x en B [h2 (x)]

Implementación

La implementación parece bastante sencilla, así que decidí intentarlo y comparar cuán eficiente es el espacio / tiempo en comparación con un filtro de floración. El filtro Cuckoo consiste en una tabla hash Cuckoo que almacena las "huellas digitales" de los elementos insertados. La huella digital de un elemento es una cadena de bits derivada del hash de ese elemento. Una tabla hash de cuco consiste en una matriz de cubos donde un elemento a insertar se asigna a dos cubos posibles en función de dos funciones hash. Cada depósito se puede configurar para almacenar un número variable de huellas digitales. Por lo general, un filtro Cuckoo se identifica por su huella digital y el tamaño de la cubeta. Por ejemplo, un filtro Cuckoo (2,4) almacena huellas digitales de 2 bits de longitud y cada cubo en la tabla hash Cuckoo puede almacenar hasta 4 huellas digitales.

Inserción

Algoritmo:

f = huella digital (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
si el cubo [i1] o el cubo [i2] tiene una entrada vacía, entonces
   agregue f a ese cubo;
   volver Listo;
// debe reubicar elementos existentes;
i = elegir aleatoriamente i1 o i2;
para n = 0; n 
// Hashtable se considera completo;
Falla de retorno;

Código:

Buscar

Algoritmo:

f = huella digital (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
si el cubo [i1] o el cubo [i2] tiene f entonces
    volver verdadero;
falso retorno;

Código:

Borrar

Algoritmo:

f = huella digital (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
si el cubo [i1] o el cubo [i2] tiene f entonces
   eliminar una copia de f de este cubo;
   volver verdadero;
falso retorno;

Código:

Prueba de rendimiento

He usado la biblioteca Will Fitzgerald para la prueba del filtro Bloom. La ración FPP (probabilidad falsa positiva) tomada para el filtro de cuco es 0.001

Complejidad espacial

Con respecto a los filtros de cuco y floración, funcionan de manera diferente con diferentes probabilidades de falsos positivos. Cuando la probabilidad de falso positivo del filtro es menor o igual al 3%, el filtro de cuco tiene menos bits por entrada. Cuando es más alto, el filtro de floración tiene menos bits por entrada.

Complejidad de tiempo

En el hash cuckoo, la inserción de un elemento parece mucho peor que O (1) en el peor de los casos porque podría haber muchos casos durante la colisión, donde tenemos que eliminar un valor para dejar espacio para el valor actual. Además, si hay un ciclo, se debe volver a colocar toda la tabla.

Hacer un análisis de tiempo de ambos filtros arroja los siguientes resultados:

A lo largo de este experimento (teniendo en cuenta que mi código puede no estar completamente optimizado), los filtros Bloom parecen funcionar excepcionalmente bien en la complejidad del espacio, ocupando menos cantidad de espacio para una gran cantidad de elementos. El filtro de cuco parece funcionar mejor al insertar una gran cantidad de elementos, pero es un poco más lento en la búsqueda (tiempos de búsqueda) debido a su implementación.

Inferencia

Realmente no tomaría un lado sobre qué filtro recomendar, creo que ambos tienen sus propios casos de uso. Los filtros Bloom no admiten eliminaciones porque el hash es con pérdida e irreversible. Aunque contar los filtros de floración resuelve ese problema, los filtros Cuckoo son útiles en el caso de que necesite eliminaciones. Por supuesto, los filtros Cuckoo dan un error cuando el filtro está lleno, y eso tiene sus propias ventajas, mientras que en un filtro Bloom, no hay control sobre la capacidad, solo se vuelve a colocar sobre la matriz de bits existente.

Código

Referencias

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S Si encuentra algún problema con las pruebas / implementación, no dude en dejar sus sugerencias / comentarios.