Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Redis

Comprender la magia de los filtros Bloom con Node.js y Redis

by
Length:LongLanguages:

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

En el caso de uso correcto, los filtros Bloom parecen mágicos. Esa es una afirmación audaz, pero en este tutorial exploraremos la curiosa estructura de datos, la mejor manera de usarla y algunos ejemplos prácticos usando Redis y Node.js.

Los filtros Bloom son una estructura de datos probabilística y unidireccional. La palabra 'filtro' puede ser confusa en este contexto; filter implica que es una cosa activa, un verbo, pero podría ser más fácil pensar en él como almacenamiento, un sustantivo. Con un simple filtro Bloom puedes hacer dos cosas:

  1. Agrega un artículo.
  2. Verifique si un artículo no ha sido agregado previamente.

Estas son limitaciones importantes que debe comprender: no puede eliminar un artículo ni puede enumerarlos en un filtro Bloom. Además, no puede decir con certeza si un elemento se ha agregado al filtro en el pasado. Aquí es donde entra la naturaleza probabilística de un filtro Bloom: son posibles falsos positivos, pero los falsos negativos no lo son. Si el filtro está configurado correctamente, los falsos positivos pueden ser extremadamente raros.

Existen variantes de filtros Bloom y agregan otras habilidades, como eliminación o escala, pero también agregan complejidad y limitaciones. Es importante comprender primero los filtros Bloom simples antes de pasar a las variantes. Este artículo solo cubrirá los filtros Bloom simples.

Con estas limitaciones, tiene una serie de beneficios: tamaño fijo, encriptación basada en hash y búsquedas rápidas.

Cuando configura un filtro Bloom, le da un tamaño. Este tamaño es fijo, por lo que si tiene un elemento o mil millones de elementos en el filtro, nunca crecerá más allá del tamaño especificado. A medida que agrega más elementos a su filtro, la posibilidad de un falso positivo aumenta. Si ha especificado un filtro más pequeño, esta tasa de falsos positivos aumentará más rápidamente que si tiene un tamaño más grande.

Los filtros Bloom se basan en el concepto de hash unidireccional. Al igual que el almacenamiento correcto de contraseñas, los filtros Bloom usan un algoritmo hash para determinar un identificador único para los elementos que se pasan a él. Los hash, por naturaleza, no se pueden revertir y están representados por una cadena de caracteres aparentemente aleatoria. Por lo tanto, si alguien obtiene acceso a un filtro Bloom, no revelará directamente ninguno de los contenidos.

Finalmente, los filtros Bloom son rápidos. La operación implica muchas menos comparaciones que otros métodos, y se puede almacenar fácilmente en la memoria, evitando hits de bases de datos que roban el rendimiento.

Ahora que conoce los límites y las ventajas de los filtros Bloom, echemos un vistazo a algunas situaciones donde puede usarlos.

Preparacion

Utilizaremos Redis y Node.js para ilustrar los filtros Bloom. Redis es un medio de almacenamiento para su filtro Bloom; es rápido, en memoria y tiene algunos comandos específicos (GETBIT, SETBIT) que hacen que la implementación sea eficiente. Asumiré que tienes Node.js, npm y Redis instalados en tu sistema. Su servidor Redis debería ejecutarse en localhost en el puerto predeterminado para que nuestros ejemplos funcionen.

En este tutorial, no implementaremos un filtro desde cero; en su lugar, nos centraremos en usos prácticos con un módulo preconstruido en npm: bloom-redis. bloom-redis tiene un conjunto de métodos muy concisos: addcontains  y clear.

Como se mencionó anteriormente, los filtros Bloom necesitan un algoritmo hash para los identificadores únicos generados para un artículo. bloom-redis usa el conocido algoritmo MD5, que, aunque quizás no sea el ajuste perfecto para un filtro Bloom (un poco lento, excesivo en bits), funcionará bien.

Nombres de usuario únicos

Los nombres de usuario, especialmente aquellos que identifican a un usuario en una URL, deben ser únicos. Si construye una aplicación que permite a los usuarios cambiar el nombre de usuario, entonces probablemente querrá un nombre de usuario que nunca se haya utilizado para evitar confusiones y ataques de nombres de usuario.

Sin un filtro Bloom, necesitaría hacer referencia a una tabla que tenga todos los nombres de usuario utilizados, y a gran escala esto puede ser muy costoso. Los filtros Bloom le permiten agregar un artículo cada vez que un usuario adopta un nuevo nombre. Cuando un usuario verifica si se toma un nombre de usuario, todo lo que necesita hacer es verificar el filtro Bloom. Podrá decirle, con absoluta certeza, si el nombre de usuario solicitado ha sido agregado previamente. Es posible que el filtro devuelva falsamente que se ha utilizado un nombre de usuario cuando no lo ha hecho, pero esto es obvio por precaución y no puede causar ningún daño real (aparte de que un usuario no pueda reclamar 'k3w1d00d47') .

Para ilustrar esto, construyamos un servidor REST rápido con Express. Primero, cree su archivo package.json y luego ejecute los siguientes comandos de terminal.

npm install bloom-redis --save

npm install express --save

npm install redis --save

Las opciones predeterminadas para bloom-redis tienen el tamaño establecido en dos megabytes. Esto se equivoca por precaución, pero es bastante grande. Configurar el tamaño del filtro Bloom es fundamental: demasiado grande y desperdiciará memoria, demasiado pequeño y su tasa de falsos positivos será demasiado alta. La matemática involucrada en determinar el tamaño es bastante complicada y está más allá del alcance de este tutorial, pero afortunadamente hay una calculadora de tamaño de filtro Bloom para hacer el trabajo sin descifrar un libro de texto.

Ahora, crea tu app.js de la siguiente manera:

Para ejecutar este servidor: node app.js. Vaya a su navegador y apúntelo a: https://localhost:8010/check?username=kyle. La respuesta debería ser: {"username":"kyle","status":"free"}.

Ahora, guardemos ese nombre de usuario apuntando su navegador a http://localhost:8010/save?username=kyle. La respuesta será: {"username":"kyle","status":"created"}. Si vuelve a la dirección http://localhost:8010/check?username=kyle, la respuesta será {"username":"kyle","status":"used"}. Del mismo modo, volver a http://localhost:8010/save?username=kyle resultará en {"username":"kyle","status":"not-created"}.

Desde la terminal, puede ver el tamaño del filtro: redis-cli strlen username-bloom-filter.

En este momento, con un elemento, debe mostrar 338622.

Ahora, continúe e intente agregar más nombres de usuario con la ruta /save. Prueba todos los que quieras.

Si luego verifica el tamaño de nuevo, puede notar que su tamaño ha aumentado levemente, pero no para cada adición. Curioso, ¿verdad? Internamente, un filtro Bloom establece bits individuales (1's / 0) en diferentes posiciones en la cadena guardada en username-bloom. Sin embargo, estos no son contiguos, por lo que si establece un bit en el índice 0 y luego uno en el índice 10.000, todo lo que haya entre ellos será 0. Para usos prácticos, inicialmente no es importante comprender la mecánica precisa de cada operación, solo sepa que esto es normal y que su almacenamiento en Redis nunca excederá el valor que usted especificó.

Contenido fresco

El contenido fresco en un sitio web hace que un usuario regrese, entonces ¿cómo se le muestra a un usuario algo nuevo cada vez? Utilizando un enfoque de base de datos tradicional, podría agregar una nueva fila a una tabla con el identificador de usuario y el identificador de la historia, y luego consultaría esa tabla cuando decidiera mostrar una parte del contenido. Como se puede imaginar, su base de datos crecerá extremadamente rápido, especialmente con el crecimiento tanto de usuarios como de contenido.

En este caso, un falso negativo (por ejemplo, que no muestre una porción de contenido invisible) tiene muy pocas consecuencias, haciendo que los filtros Bloom sean una opción viable. A primera vista, puede pensar que necesita un filtro Bloom para cada usuario, pero usaremos una concatenación simple del identificador de usuario y el identificador de contenido, y luego insertaremos esa cadena en nuestro filtro. De esta forma, podemos usar un solo filtro para todos los usuarios.

En este ejemplo, construyamos otro servidor Express básico que muestre contenido. Cada vez que visita la ruta /show-content/any-username (con cualquier nombre de usuario como valor seguro de URL), se mostrará una nueva pieza de contenido hasta que el sitio se quede sin contenido. En el ejemplo, el contenido es la primera línea de los diez mejores libros del Proyecto Gutenberg.

Tendremos que instalar un módulo npm más. Desde la terminal, ejecuta: npm install async --save

Su nuevo archivo app.js:

Si prestas atención cuidadosamente al tiempo de ida y vuelta en Dev Tools, notarás que cuanto más solicites una ruta única con un nombre de usuario, más tiempo tomará. Si bien el control del filtro lleva un tiempo fijo, en este ejemplo, estamos verificando la presencia de más elementos. Los filtros Bloom están limitados en cuanto a lo que le pueden decir, por lo que está probando la presencia de cada elemento. Por supuesto, en nuestro ejemplo es bastante simple, pero probar cientos de elementos sería ineficiente.

Datos obsoletos

En este ejemplo, construiremos un pequeño servidor Express que hará dos cosas: aceptar datos nuevos a través de POST y visualizar los datos actuales (con una solicitud GET). Cuando los datos nuevos se envían por POST al servidor, la aplicación verificará su presencia en el filtro. Si no está presente, lo agregaremos a un conjunto en Redis, de lo contrario, devolveremos nulo. La solicitud GET la obtendrá de Redis y la enviará al cliente.

Esto es diferente a las dos situaciones anteriores, en que los falsos positivos no estarían bien. Utilizaremos el filtro Bloom como primera línea de defensa. Dadas las propiedades de los filtros Bloom, solo sabremos con certeza que algo no está en el filtro, por lo que en este caso podemos continuar y dejar entrar los datos. Si el filtro Bloom regresa probablemente en el filtro, Haremos un control en comparación con la fuente de datos real.

Entonces, ¿qué ganamos? Ganamos la velocidad de no tener que verificar contra la fuente real cada vez. En situaciones en las que la fuente de datos es lenta (API externas, bases de datos pokey, el centro de un archivo plano), el aumento de velocidad es realmente necesario. Para demostrar la velocidad, agreguemos un retraso realista de 150 ms en nuestro ejemplo. También usaremos console.time / console.timeEnd para registrar las diferencias entre una comprobación de filtro Bloom y una comprobación de filtro no Bloom.

En este ejemplo, también usaremos un número extremadamente limitado de bits: solo 1024. Se llenará rápidamente. A medida que se llena, mostrará más y más falsos positivos: verá que el tiempo de respuesta aumenta a medida que se llena la tasa de falsos positivos.

Este servidor utiliza los mismos módulos que antes, por lo que debe establecer el archivo app.js en:

Dado que POSTing a un servidor puede ser complicado con un navegador, usemos curl para probar.

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

Se puede usar un script bash rápido para mostrar cómo se ve el llenado de todo el filtro:

Ver un relleno o un filtro completo es interesante. Como este es pequeño, puedes verlo fácilmente con redis-cli. Al ejecutar redis-cli get stale-filter desde el terminal entre la adición de elementos, verá que los bytes individuales aumentan. Un filtro completo será \xff para cada byte. En este punto, el filtro siempre regresará positivo.

Conclusión

Los filtros Bloom no son una solución panacea, pero en la situación correcta, un filtro Bloom puede proporcionar un complemento rápido y eficiente a otras estructuras de datos.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.