Qué es el Bloom Filter?

Hablamos de una estructura de datos no tan común pero que tiene casos de uso interesantes, ademas es una buena opción cuando queremos reducir el uso de memoria. Como es un filtro, la respuesta esperada es si por lo que estoy preguntando, se encuentra o no guardado en nuestros sistemas.

Con esto en mente, tenemos que saber que es una estructura probabilística, con dos resultados posibles, estos son:

• Seguro que no ❌​
• Probablemente si 🤞​

Si nos dice que no, es que no está y eso es seguro, pero no puede garantizar que sí, entonces si la respuesta es probablemente si vamos a tener que asegurarnos yendo a verificar por segunda vez, pero a otro lugar, no al filtro. Esto se puede dar por colisiones en funciones hash y también en que, al reducir el espacio en memoria, las colisiones van a estar presentes.

Ahora vemos como funciona

Hablamos de probabilidades, hashes, colisiones y demás, vamos a explicar con un caso concreto.

Supongamos que dev.to no quiere recomendarte un post que ya leíste en el ultimo tiempo, entonces, vamos a ir cargando los posts vistos en el filtro de una manera particular, que ahora detallamos.

Para nuestro filtro vamos a usar un arreglo (slice si sos gopher) con un numero que sepamos, en este caso 100, así no crece indiscriminadamente porque la idea principal es mantener nuestro uso de memoria, bajo. Usamos bool para representar 0 y 1.
Cada función de hash (podemos usar varias, recomiendo fuertemente más de una) va a devolver un numero entero como resultado y cada entrada va a ser representada por n números siendo n la cantidad de funciones de hash que usemos. Después todos los resultados van a traducirse en que ese mismo indice, va a quedar en true. Por ejemplo si tenemos un slice de 10 de bool y las tres funciones nos devuelven 2, 3 y 6 nos queda algo así:
[f][f][✅​][✅​][f][f][✅​][f][f][f]

Entonces...

var filter [100] bool //100 para tener una buena distribución

Ahora las funciones hash

var h1 = func(i interface{}) int{...}
var h2 = func(i interface{}) int{...}
var h3 = func(i interface{}) int{...}

Si bien son placeholders, la idea es que tome cualquier valor y devuelva un entero que esté dentro del rango, por eso vamos a aplicar el operador modulo a la respuesta. Cualquier implementación que usemos, tenemos que saber que el resultado tiene que ser siempre el mismo ante la misma entrada, como una función pura y determinística.

index1 := h1("dev.to/post-x") % 100
index2 := h2("dev.to/post-x") % 100
index3 := h3("dev.to/post-x") % 100

filter[index1] = true
filter[index2] = true
filter[index3] = true

De esta manera ya queda resuelto como podemos escribir un bloom filter, para la lectura, básicamente es lo mismo, pero debemos preguntar si los indices son true y ahi tenemos cómo podemos estudiar las respuestas que vimos previamente.

Si algún indice nos da falso, sabemos que la URL que enviamos no esta en nuestro filtro.

Si todos los indices dan verdadero, decimos que probablemente si, ya que, al tener un array "chico" y que las funciones hash tienen colisiones, puede que otra URL haya generado los mismos números o algo mas fácil, puede ser este ejemplo:
La url 1 nos da el resultado 1, 3 y 6
La url 2 nos da el resultado 2, 5 y 7
la url 3 nos da el resultado 2, 3 y 7 -> nos da que sí son todos true, pero la url 3 en sí, no estaba guardada, por eso en el segundo check (puede ser una base de datos) nos da que no estaba.

Conclusión

El bloom filter es una buena opción para cuando queremos ahorrar tiempo y espacio. Puede usarse como alternativa de un hashmap o un cache, para hacer operaciones en memoria y evitarnos salidas de red. Espero que lo prueben en sus proyectos!

Hasta la próxima!

PS: sponsoreame aca si te gusto el contenido