Dado un nombre de usuario en una página de registro de usuario, ¿cómo sabemos si ya se ha registrado?

Si bien consultar una base de datos indexada ayuda, es lento e incurre en llamadas de red.

Para acelerar las cosas, podemos almacenar en caché la lista de nombres de usuario registrados en un almacén de clave-valor como Redis.

Sin embargo, eso implica almacenar en caché millones de registros y duplicar nuestra huella de memoria.

¿Cómo podemos hacerlo mejor en este problema aparentemente trivial?

El filtro de floración podría ser la respuesta, ¡vamos a comprobarlo!

¿Qué es un filtro Bloom?

Un filtro de floración responde a una pregunta simple,

¿Existe un elemento en un conjunto dado?

Un filtro bloom es una estructura de datos probabilísticos. Dada la pregunta anterior, genera cualquiera de las siguientes respuestas

• Probablemente sí
• 100% No

Y su mayor ventaja es que lo hace en tiempo y espacio CONSTANTES .

¿Como funciona?

Un filtro de floración consta de dos componentes.

• Una matriz de bits de tamaño N
• Varias funciones hash

Primero se inicializa como una matriz de bits de tamaño N con todos sus bits puestos a cero. Supongamos que la longitud de la matriz es 10 por ahora.

Agregar un elemento

Agregar un elemento es trivial

• El elemento que dice "tigre" se codifica usando una función de cifrado
• El hash generado se modifica por la longitud de la matriz para obtener un índice acotado
• El índice de la matriz de bits se establece en 1

Similar a agregar un elemento, hacemos hash del elemento usando una función hash y lo modificamos para obtener un índice acotado.

La salida se evalúa de la siguiente manera,

• Si el valor de índice de la matriz de bits es 0, el elemento NO está en el conjunto.
• De lo contrario, el artículo es PROBABLEMENTE en el conjunto

Almacenamiento de un filtro de floración

En lugar de almacenar el filtro de floración como una matriz, podemos convertir su representación de bits en un número decimal.

Por ejemplo, podemos convertir una matriz que contiene 10011en 19 y almacenarla en un caché.

Si la lista no cambia muy a menudo, el servidor puede enviar el número decimal al cliente, lo que permite que la validación se realice en el lado del cliente.

¿Podemos hacerlo mejor?

Si la función hash genera el índice 1 para "tigre" y "vaca", verificar si "vaca" está en el conjunto produce la respuesta Sí , incluso si no lo es .

Podemos reducir la posibilidad de falsos positivos a través de las siguientes soluciones.

• Aumentar la longitud de la matriz.
• Aumentar el número de funciones hash

En lugar de un índice, podemos obtener múltiples índices usando varios hashes.

Al agregar un elemento, todos los índices obtenidos se establecerán en 1.

Se afirma que un elemento probablemente esté en el conjunto, solo si TODOS los índices se establecen en 1.

Aprovechando estos métodos, podríamos reducir significativamente la probabilidad de falsos positivos.

Aplicaciones

Echemos un vistazo a algunos ejemplos de la vida real.

Comprobar si existe un nombre de usuario en un flujo de registro de usuario

• Cuando se crea un nombre de usuario, el nombre de usuario se agrega a un filtro de floración almacenado en un almacén de clave-valor.
• Cuando un usuario ingresa un nombre de usuario en una página de registro de usuario, el servidor primero consulta el filtro de floración.
• Si el nombre de usuario NO está en el filtro de floración, el servidor devuelve instantáneamente un error al cliente.
• De lo contrario, el servidor consulta y verifica en la base de datos.

• Medium mantiene un filtro de floración para cada usuario.
• Antes de recomendar un artículo, Medium verifica si el ID del artículo existe en el filtro de floración del usuario.
• Se recomiendan al usuario los artículos que ciertamente NO están en el filtro de floración.

• Al acceder a una URL, Chrome primero valida si la URL es parte de una lista maliciosa.
• En lugar de consultar el servidor de Google cada vez, Google crea un filtro de floración utilizando una lista maliciosa predeterminada y lo envía al navegador.
• El navegador codifica la URL y realiza una verificación cruzada con el filtro de floración antes de acceder al sitio web.

Si bien puede haber falsos positivos , un filtro de floración es útil cuando queremos saber si un elemento definitivamente no está en una lista.

Se puede utilizar como primera capa de filtrado debido a su eficiencia tanto en el tiempo como en el espacio.

¡Espero que te sea útil, y te veré en la próxima!