Share
En el caso de uso correcto, los filtros Bloom parecen mágicos. Esa es una declaración audaz, pero en este tutorial exploraremos la estructura de datos curiosos, la mejor manera de usarla y algunos ejemplos prácticos utilizando 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; filtro implica que es una cosa activa, un verbo, pero podría ser más fácil pensar que es un almacenamiento, un sustantivo. Con un simple filtro Bloom puedes hacer dos cosas:
Estas son limitaciones importantes para comprender: no puede eliminar un elemento ni puede enumerar los elementos en un filtro Bloom. Además, no puede saber, con certeza, si un elemento se ha agregado al filtro en el pasado. Aquí es donde la naturaleza probabilística de un filtro Bloom es posible. Los falsos positivos son posibles, 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 simples filtros Bloom..
Con estas limitaciones, tiene una serie de beneficios: tamaño fijo, cifrado basado en hash y búsquedas rápidas.
Cuando configuras un filtro Bloom, le das 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, aumenta la posibilidad de un falso positivo. Si especificó 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 le pasan. Los hash, por naturaleza, no se pueden revertir y están representados por una cadena de caracteres aparentemente aleatoria. Entonces, si alguien obtiene acceso a un filtro Bloom, no revelará directamente ninguno de los contenidos..
Por último, los filtros Bloom son rápidos. La operación implica muchas menos comparaciones que otros métodos, y puede almacenarse fácilmente en la memoria, lo que evita los aciertos en la base 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 en las que puede usarlos..
Usaremos 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 la implementación eficiente. Asumiré que tiene Node.js, npm y Redis instalados en su sistema. Tu servidor Redis debería estar ejecutándose 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 los usos prácticos con un módulo preconstruido en npm: bloom-redis. bloom-redis tiene un conjunto muy conciso de métodos: añadir, contiene y claro.
Como se mencionó anteriormente, los filtros Bloom necesitan un algoritmo de hashing para generar identificadores únicos para un artículo. bloom-redis utiliza el conocido algoritmo MD5, que, aunque tal vez no sea el ajuste perfecto para un filtro Bloom (un poco lento, exagerado en bits), funcionará bien.
Los nombres de usuario, especialmente aquellos que identifican a un usuario en una URL, deben ser únicos. Si crea una aplicación que permite a los usuarios cambiar el nombre de usuario, entonces probablemente querrá un nombre de usuario que tenga Nunca Ha sido usado para evitar confusiones y el uso de nombres de usuario..
Sin un filtro Bloom, necesitaría hacer referencia a una tabla que tiene todos los nombres de usuario utilizados alguna vez, y a escala esto puede ser muy costoso. Los filtros Bloom le permiten agregar un elemento cada vez que un usuario adopta un nombre nuevo. 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 usado un nombre de usuario cuando no lo ha hecho, pero esto es erróneo y no puede causar ningún daño real (aparte de un usuario, tal vez no pueda reclamar 'k3w1d00d47').
Para ilustrar esto, construyamos un servidor REST rápido con Express. Primero, crea tu paquete.json Archivo y luego ejecute los siguientes comandos de terminal.
npm instalar 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 falla en el lado de la precaución, pero es bastante grande. La configuración del tamaño del filtro Bloom es crítica: demasiado grande y desperdicia memoria, demasiado pequeño y su tasa de falsos positivos será demasiado alta. Las matemáticas involucradas para determinar el tamaño son bastante complicadas y están fuera del alcance de este tutorial, pero afortunadamente hay una calculadora de tamaño de filtro Bloom para hacer el trabajo sin romper un libro de texto.
Ahora, crea tu app.js como sigue:
"javascript var Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
aplicación, cliente, filtro;
// configura nuestra aplicación de servidor Express = express ();
// crear la conexión con el cliente Redis = redis.createClient ();
filter = new Bloom.BloomFilter (cliente: cliente, // asegúrese de que el módulo Bloom use nuestra conexión recién creada con la clave Redis: 'username-bloom-filter', // la clave Redis
// Tamaño calculado del filtro Bloom. // Aquí es donde se realizan las compensaciones de tamaño / probabilidad //http://hur.st/bloomfilter?n=100000&p=1.0E-6 tamaño: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', función (req, res, next) // verifique que la cadena de consulta tenga 'username' si (typeof req.query.username === 'undefined') // skip esta ruta, vaya a la siguiente: dará como resultado un 404 / no encontrado a continuación ('ruta'); ) if (err) next (err); // si se encuentra un error, envíelo al cliente else res.send (username: req.query.username, // si el resultado es falso, entonces sabemos que el artículo tiene no utilizado // si el resultado es verdadero, podemos asumir que el elemento se ha utilizado estado: ¿resultado? 'usado': 'libre'); ); );
app.get ('/ save', function (req, res, next) if (typeof req.query.username === 'undefined') next ('route'); else // primero, necesitamos para asegurarse de que aún no esté en el filtro filter.contains (req.query.username, function (err, result) if (err) next (err); else if (result) // verdadero resultado significa ya existe, así que dile al usuario res.send (username: req.query.username, status: 'not-created'); else // agregaremos el nombre de usuario pasado en la cadena de consulta al filtro filter.add (req.query.username, function (err) // Los argumentos de devolución de llamada a añadir no proporciona información útil, así que solo verificaremos que no se haya pasado ningún error si (err) next (err); else res.send (username: req.query.username, status: 'created'); ); ); );
app.listen (8010); "
Para ejecutar este servidor: nodo app.js. Vaya a su navegador y apúntelo a: https: // localhost: 8010 / check? username = kyle. La respuesta debe ser: "username": "kyle", "status": "free".
Ahora, guardemos ese nombre de usuario apuntando su navegador a http: // localhost: 8010 / save? username = kyle. La respuesta será: "nombre de usuario": "kyle", "estado": "creado". Si vuelves a la dirección. http: // localhost: 8010 / check? username = kyle, la respuesta será "username": "kyle", "status": "used". Del mismo modo, volviendo a http: // localhost: 8010 / save? username = kyle resultará en "username": "kyle", "status": "no creado".
Desde la terminal, puede ver el tamaño del filtro: redis-cli strlen nombre de usuario-bloom-filtro.
En este momento, con un elemento, debe mostrar 338622.
Ahora, adelante, intente agregar más nombres de usuario con el /salvar ruta. Intenta tantos como quieras.
Si luego verifica el tamaño nuevamente, puede notar que su tamaño ha aumentado ligeramente, pero no para cada adición. Curioso, ¿verdad? Internamente, un filtro Bloom establece bits individuales (1's / 0's) en diferentes posiciones en la cadena guardada en el nombre de usuario-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 estará entre 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 especificó.
El contenido fresco en un sitio web hace que el usuario regrese, así que, ¿cómo le muestra a un usuario algo nuevo cada vez? Usando un enfoque de base de datos tradicional, puede agregar una nueva fila a una tabla con el identificador de usuario y el identificador de la historia, y luego consultar esa tabla cuando decida mostrar una parte del contenido. Como puede imaginar, su base de datos crecerá extremadamente rápido, especialmente con el crecimiento tanto de los usuarios como del contenido..
En este caso, un falso negativo (por ejemplo, que no muestra un contenido invisible) tiene muy pocas consecuencias, lo que hace que los filtros Bloom sean una opción viable. A primera vista, puede pensar que necesitaría 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 manera podemos utilizar un único filtro para todos los usuarios..
En este ejemplo, vamos a construir otro servidor Express básico que muestre contenido. Cada vez que visitas la ruta. / show-content / any-username (con cualquier nombre de usuario siendo cualquier valor seguro para la URL), se mostrará una nueva pieza de contenido hasta que el sitio esté fuera de contenido. En el ejemplo, el contenido es la primera línea de los diez mejores libros sobre el Proyecto Gutenberg..
Necesitaremos instalar un módulo npm más. Desde la terminal, ejecute: npm instalar async --save
Su nuevo archivo app.js:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
aplicación, cliente, filtro,
// Del Proyecto Gutenberg: líneas de apertura de los 10 principales ebooks de dominio público // https://www.gutenberg.org/browse/scores/top openingLines = 'pride-and-prejudice': 'Es una verdad reconocida universalmente , que un hombre soltero en posesión de una buena fortuna, debe estar en la necesidad de una esposa ',' alices-adventures-in-wonderland ':' Alice estaba empezando a cansarse de sentarse junto a su hermana en el banco, y de no tener nada que hacer: una o dos veces se asomó al libro que su hermana estaba leyendo, pero no tenía imágenes ni conversaciones en él, "¿y cuál es el uso de un libro, 'pensó Alice' sin imágenes o conversaciones?" , 'a-christmas-carol': 'Marley estaba muerta: para empezar.', 'metamorfosis': 'Una mañana, cuando Gregor Samsa se despertó de sueños problemáticos, se encontró transformado en su cama en un horrible parásito', 'frankenstein': 'Te alegrarás al saber que ningún desastre ha acompañado el comienzo de una empresa que has considerado con malos presentimientos', 'adventur es-of-huckleberry-finn ':' USTED no sabe de mí sin haber leído un libro con el nombre de Las aventuras de Tom Sawyer; pero eso no importa, "aventuras de Sherlock Holmes": "Para Sherlock Holmes ella es siempre la mujer", "narrativa de la vida de Frederick-Douglass": "Yo Nació en Tuckahoe, cerca de Hillsborough, y a unas doce millas de Easton, en el condado de Talbot, Maryland. o principados ',' adventures-of-tom-sawyer ':' TOM! ' ;
app = express (); cliente = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, key: '3content-bloom-filter', // el tamaño de la clave Redis: 2875518, // ~ 350kb // tamaño: 1024, numHashes: 20);
app.get ('/ show-content /: user', function (req, res, next) // vamos a recorrer los ContentIds, verificando si están en el filtro. // Desde este Pasa tiempo en cada contentId. No sería recomendable hacerlo con un alto número de contentIds // Pero, en este caso, el número de contentIds es pequeño / fijo y nuestra función filter.contains es rápida, está bien. var // crea una matriz de las claves definidas en openingLines contentIds = Object.keys (openingLines), // obteniendo parte de la ruta del usuario URI = req.params.user, checkingContentId, found = false, done = false;
// ya que filter.contains es asíncrono, estamos usando la biblioteca async para hacer nuestro ciclo async.whilst (// función de verificación, donde nuestro ciclo asíncrono terminará la función () return (! found &&! done);, function (cb) // obtiene el primer elemento de la matriz de contentIds checkContentId = contentIds.shift ();
Accentsconagua
// falso significa que estamos seguros de que no está en el filtro si (! checkContentId) done = true; // esto será capturado por la función de verificación sobre cb (); else // concatenar al usuario (desde la URL) con el id del contenido filter.contains (usuario + comprobaciónContentId, función (err, resultados) if (err) cb (err); else found =! resultados; cb ();); , function (err) if (err) next (err); else if (openingLines [checkContentId]) // antes de que enviemos el contentId nuevo, lo agregamos al filtro para evitar que vuelva a mostrar filter.add (usuario + checkContentId, function (err) if (err) next (err); else // envía la nueva cita res.send (openingLines [CheckContentId]);); else res.send ('no hay nuevo contenido!'); ); ); app.listen (8011); "
Si presta atención al tiempo de ida y vuelta en Dev Tools, notará que cuanto más solicite una ruta única con un nombre de usuario, más tiempo llevará. Si bien la verificación del filtro lleva un tiempo fijo, en este ejemplo, estamos comprobando la presencia de más elementos. Los filtros de Bloom están limitados en lo que pueden decirle, 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.
En este ejemplo, construiremos un pequeño servidor Express que hará dos cosas: aceptar nuevos datos a través de POST y mostrar los datos actuales (con una solicitud GET). Cuando los nuevos datos se envían 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 lo obtendrá de Redis y lo enviará al cliente.
Esto es diferente de las dos situaciones anteriores, ya que los falsos positivos no estarían bien. Usaremos 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 que ingresen los datos. Haré una verificación frente a la fuente de datos real.
Entonces, ¿qué ganamos? Ganamos la velocidad de no tener que verificar la fuente real cada vez. En situaciones donde la fuente de datos es lenta (API externas, bases de datos pokey, la mitad 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 el consola.tiempo / 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 restringido de bits: solo 1024. Se llenará rápidamente. A medida que se llene, mostrará más y más falsos positivos: verá cómo aumenta el tiempo de respuesta a medida que la tasa de falsos positivos se llena..
Este servidor usa los mismos módulos que antes, así que configure el app.js archivo a
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), bodyParser = require ('body-parser'), express = require ('express'), redis = require ('redis' ),
aplicación, cliente, filtro,
currentDataKey = 'current-data', usedDataKey = 'used-data';
app = express (); cliente = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, key: 'stale-bloom-filter', // para fines ilustrativos, este es un filtro súper pequeño. Debe llenarse con alrededor de 500 artículos, así que para una carga de producción, necesitarías algo mucho más grande! tamaño: 1024, numashes: 20);
app.post ('/', bodyParser.text (), function (req, res, next) var used;
console.log ('POST -', req.body); // registrar los datos actuales que se publican console.time ('post'); // comience a medir el tiempo que lleva completar nuestro filtro y el proceso de verificación condicional //async.series se utiliza para administrar varias llamadas de función asíncronas. async.series ([function (cb) filter.contains (req.body, function (err, filterStatus) if (err) cb (err); else used = filterStatus; cb (err);) ;, función (cb) si (usado === falso) // Los filtros Bloom no tienen falsos negativos, por lo que no necesitamos más verificación cb (null); else // it * puede * estar en el filtro, por lo que necesitamos hacer una verificación de seguimiento // a los fines del tutorial, agregaremos un retraso de 150 ms aquí, ya que Redis puede ser lo suficientemente rápido como para que sea difícil de medir y el retraso simulará una base de datos lenta o API call setTimeout (function () console.log ('posible falso positivo'); client.sismember (usedDataKey, req.body, function (err, membresía) if (err) cb (err); else / / sismember devuelve 0 si un miembro no es parte del conjunto y 1 si lo es. // Esto transforma esos resultados en booleanos para una comparación lógica consistente utilizada = membership === 0? false: true; cb (err); );, 150);, function (cb) if (used === false) console.log ('Adding to filter'); filter.a dd (req.body, cb); else console.log ('Adición de filtro omitido, [falso] positivo'); cb (nulo); , function (cb) if (used === false) client.multi () .set (currentDataKey, req.body) // los datos no utilizados se configuran para acceder fácilmente a la clave de 'datos actuales' .sadd (usedDataKey, req.body) // y se agregó a un conjunto para una fácil verificación posterior .exec (cb); else cb (null); ], función (err, cb) if (err) next (err); else console.timeEnd ('post'); // registra la cantidad de tiempo desde la llamada de console.time por encima de res.send (guardado:! usado); // devuelve si se guardó el elemento, verdadero para datos nuevos, falso para datos obsoletos. ); ); app.get ('/', function (req, res, next) // simplemente devuelve los datos nuevos client.get (currentDataKey, function (err, data) if (err) next (err); else res.send (datos);););
app.listen (8012); "
Dado que la POSTing a un servidor puede ser complicado con un navegador, usemos curl para probar.
curl --data "sus datos van aquí" --header "Content-Type: text / plain" http: // localhost: 8012 /
Se puede usar un script de bash rápido para mostrar cómo se ve el llenado del filtro completo:
bash #! / bin / bash para i en 'seq 1 500'; do curl --data “data $ i" --header "Content-Type: text / plain" http: // localhost: 8012 / done
Mirar un relleno o filtro completo es interesante. Ya que este es pequeño, puedes verlo fácilmente con redis-cli. Mediante la ejecución redis-cli get stale-filter Desde el terminal entre la adición de elementos, verá que aumentan los bytes individuales. Un filtro completo será \ xff para cada byte. En este punto, el filtro siempre devolverá positivo..
Los filtros Bloom no son una solución de panacea, pero en la situación correcta, un filtro Bloom puede proporcionar un complemento rápido y eficiente a otras estructuras de datos.
