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

() translation by (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:

Agrega un artículo.
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: add, contains 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:

var
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter;

//setup our Express server
app = express();

//create the connection to Redis
client = redis.createClient();


filter = new Bloom.BloomFilter({ 
  client    : client, //make sure the Bloom module uses our newly created connection to Redis
  key       : 'username-bloom-filter', //the Redis key
  
  //calculated size of the Bloom filter.
  //This is where your size / probability trade-offs are made
  //http://hur.st/bloomfilter?n=100000&p=1.0E-6
  size      : 2875518, // ~350kb
  numHashes : 20
});

app.get('/check', function(req,res,next) {
  //check to make sure the query string has 'username'
  if (typeof req.query.username === 'undefined') {
    //skip this route, go to the next one - will result in a 404 / not found
    next('route');
  } else {
   filter.contains(
     req.query.username, // the username from the query string
     function(err, result) {
       if (err) { 
        next(err); //if an error is encountered, send it to the client
        } else {
          res.send({ 
            username : req.query.username, 
            //if the result is false, then we know the item has *not* been used
            //if the result is true, then we can assume that the item has been used
            status : result ? 'used' : 'free' 
          });
        }
      }
    );
  }
});


app.get('/save',function(req,res,next) {
  if (typeof req.query.username === 'undefined') {
    next('route');
  } else {
    //first, we need to make sure that it's not yet in the filter
    filter.contains(req.query.username, function(err, result) {
      if (err) { next(err); } else {
        if (result) {
          //true result means it already exists, so tell the user
          res.send({ username : req.query.username, status : 'not-created' });
        } else {
          //we'll add the username passed in the query string to the filter
          filter.add(
            req.query.username, 
            function(err) {
              //The callback arguments to `add` provides no useful information, so we'll just check to make sure that no error was passed
              if (err) { next(err); } else {
                res.send({ 
                  username : req.query.username, status : 'created' 
                });
              }
            }
          );
        }
      }
    });
  }
});

app.listen(8010);

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:

var
  async         =   require('async'),
  Bloom         =   require('bloom-redis'),
  express       =   require('express'),
  redis         =   require('redis'),
  
  app,
  client,
  filter,
  
  // From Project Gutenberg - opening lines of the top 10 public domain ebooks
  // https://www.gutenberg.org/browse/scores/top
  openingLines = {
    'pride-and-prejudice' : 
      'It is a truth universally acknowledged, that a single man in possession of a good fortune, must be in want of a wife.',
    'alices-adventures-in-wonderland' : 
      'Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, \'and what is the use of a book,\' thought Alice \'without pictures or conversations?\'',
    'a-christmas-carol' :
      'Marley was dead: to begin with.',
    'metamorphosis' : 
      'One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin.',
    'frankenstein'  : 
      'You will rejoice to hear that no disaster has accompanied the commencement of an enterprise which you have regarded with such evil forebodings.',
    'adventures-of-huckleberry-finn' : 
      'YOU don\'t know about me without you have read a book by the name of The Adventures of Tom Sawyer; but that ain\'t no matter.',
    'adventures-of-sherlock-holmes' :
      'To Sherlock Holmes she is always the woman.',
    'narrative-of-the-life-of-frederick-douglass' :
      'I was born in Tuckahoe, near Hillsborough, and about twelve miles from Easton, in Talbot county, Maryland.',
    'the-prince' :
      'All states, all powers, that have held and hold rule over men have been and are either republics or principalities.',
    'adventures-of-tom-sawyer' :
      'TOM!'
  };


app = express();
client = redis.createClient();

filter = new Bloom.BloomFilter({ 
  client    : client,
  key       : '3content-bloom-filter', //the Redis key
  size      : 2875518, // ~350kb
  //size      : 1024,
  numHashes : 20
});

app.get('/show-content/:user', function(req,res,next) {
  //we're going to be looping through the contentIds, checking to see if they are in the filter.
  //Since this spends time on each contentId wouldn't be advisable to do over a high number of contentIds
  //But, in this case the number of contentIds is small / fixed and our filter.contains function is fast, it is okay.
  var
    //creates an array of the keys defined in openingLines
    contentIds = Object.keys(openingLines),
    //getting part of the path from the URI
    user = req.params.user,
    checkingContentId,
    found = false,
    done = false;
   
  //since filter.contains is asynchronous, we're using the async library to do our looping 
  async.whilst(
    //check function, where our asynchronous loop will end
    function () { return (!found && !done); },
    function(cb) {
      //get the first item from the array of contentIds
      checkingContentId = contentIds.shift();
      
      //false means we're sure that it isn't in the filter
      if (!checkingContentId)  {
         done = true; // this will be caught by the check function above
         cb();
      } else {
        //concatenate the user (from the URL) with the id of the content
        filter.contains(user+checkingContentId, function(err, results) {
          if (err) { cb(err); } else {
            found = !results;
            cb();
          }
        });
      }
    },
    function(err) {
      if (err) { next(err); } else {
        if (openingLines[checkingContentId]) {
          //before we send the fresh contentId, let's add it to the filter to prevent it from showing again
          filter.add(
            user+checkingContentId, 
            function(err) {
              if (err) { next(err); } else {
                //send the fresh quote
                res.send(openingLines[checkingContentId]);
              }
            }
          );
        } else {
          res.send('no new content!');
        }
      }
    }
  );
});

app.listen(8011);

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:

var
  async           =   require('async'),
  Bloom           =   require('bloom-redis'),
  bodyParser      =   require('body-parser'),
  express         =   require('express'),
  redis           =   require('redis'),
  
  app,
  client,
  filter,
  
  currentDataKey  = 'current-data',
  usedDataKey     = 'used-data';
  
app = express();
client = redis.createClient();

filter = new Bloom.BloomFilter({ 
  client    : client,
  key       : 'stale-bloom-filter',
  //for illustration purposes, this is a super small filter. It should fill up at around 500 items, so for a production load, you'd need something much larger!
  size      : 1024,
  numHashes : 20
});

app.post(
  '/',
  bodyParser.text(),
  function(req,res,next) {
    var
      used;
      
    console.log('POST -', req.body); //log the current data being posted
    console.time('post'); //start measuring the time it takes to complete our filter and conditional verification process
    
    //async.series is used to manage multiple asynchronous function calls.
    async.series([
      function(cb) {
        filter.contains(req.body, function(err,filterStatus) {
          if (err) { cb(err); } else {
            used = filterStatus;
            cb(err);
          }
        });
      },
      function(cb) {
        if (used === false) {
          //Bloom filters do not have false negatives, so we need no further verification
          cb(null);
        } else {
          //it *may* be in the filter, so we need to do a follow up check
          //for the purposes of the tutorial, we'll add a 150ms delay in here since Redis can be fast enough to make it difficult to measure and the delay will simulate a slow database or API call
          setTimeout(function() {
            console.log('possible false positive');
            client.sismember(usedDataKey, req.body, function(err, membership) {
              if (err) { cb(err); } else {
                //sismember returns 0 if an member is not part of the set and 1 if it is.
                //This transforms those results into booleans for consistent logic comparison
                used = membership === 0 ? false : true;
                cb(err);
              }
            });
          }, 150);
        }
      },
      function(cb) {
        if (used === false) {
          console.log('Adding to filter');
          filter.add(req.body,cb);
        } else {
          console.log('Skipped filter addition, [false] positive');
          cb(null);
        }
      },
      function(cb) {
        if (used === false) {
          client.multi()
            .set(currentDataKey,req.body) //unused data is set for easy access to the 'current-data' key
            .sadd(usedDataKey,req.body) //and added to a set for easy verification later
            .exec(cb); 
        } else {
          cb(null);
        }
      }
      ],
      function(err, cb) {
        if (err) { next(err); } else {
          console.timeEnd('post'); //logs the amount of time since the console.time call above
          res.send({ saved : !used }); //returns if the item was saved, true for fresh data, false for stale data.
        }
      }
    );
});

app.get('/',function(req,res,next) {
  //just return the fresh data
  client.get(currentDataKey, function(err,data) {
    if (err) { next(err); } else {
      res.send(data);
    }
  });
});

app.listen(8012);

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:

#!/bin/bash
for i in `seq 1 500`;
do
  curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/
done   

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.