Share
Dans le cas d'utilisation approprié, les filtres de Bloom semblent magiques. C'est une déclaration audacieuse, mais dans ce didacticiel, nous allons explorer la structure de données curieuse, la meilleure façon de l'utiliser, ainsi que quelques exemples pratiques utilisant Redis et Node.js..
Les filtres de Bloom sont une structure de données probabiliste à sens unique. Le mot "filtre" peut être déroutant dans ce contexte; Le filtre implique que c'est une chose active, un verbe, mais il serait peut-être plus facile de le considérer comme un stockage, un nom. Avec un simple filtre Bloom, vous pouvez faire deux choses:
Ce sont des limitations importantes à comprendre: vous ne pouvez pas supprimer un élément ni répertorier les éléments dans un filtre Bloom. En outre, vous ne pouvez pas savoir avec certitude si un élément a déjà été ajouté au filtre. C’est là que la nature probabiliste d’un filtre de Bloom intervient: des faux positifs sont possibles, mais pas des faux négatifs. Si le filtre est configuré correctement, les faux positifs peuvent être extrêmement rares.
Il existe des variantes de filtres de Bloom et ils ajoutent d'autres capacités, telles que la suppression ou la mise à l'échelle, mais ils ajoutent également de la complexité et des limites. Il est important de comprendre d'abord les filtres de Bloom simples avant de passer aux variantes. Cet article ne couvre que les filtres Bloom simples.
Avec ces limitations, vous bénéficiez de nombreux avantages: taille fixe, cryptage par hachage et recherches rapides..
Lorsque vous configurez un filtre Bloom, vous lui donnez une taille. Cette taille est fixe. Par conséquent, si vous avez un élément ou un milliard d'éléments dans le filtre, il ne dépassera jamais la taille spécifiée. Au fur et à mesure que vous ajoutez plus d'éléments à votre filtre, les risques de faux positifs augmentent. Si vous avez spécifié un filtre plus petit, ce taux de faux positif augmentera plus rapidement que si vous avez une taille plus grande..
Les filtres Bloom sont construits sur le concept de hachage à sens unique. Tout comme le stockage correct des mots de passe, les filtres de Bloom utilisent un algorithme de hachage pour déterminer un identifiant unique pour les éléments qui y sont transmis. Les hachages, par nature, ne peuvent pas être inversés et sont représentés par une chaîne de caractères apparemment aléatoire. Donc, si quelqu'un a accès à un filtre Bloom, il ne révélera pas directement le contenu..
Enfin, les filtres de Bloom sont rapides. L'opération implique beaucoup moins de comparaisons que les autres méthodes et peut facilement être stockée en mémoire, empêchant ainsi les accès à la base de données de voler des performances.
Maintenant que vous connaissez les limites et les avantages des filtres Bloom, examinons certaines situations dans lesquelles vous pouvez les utiliser..
Nous utiliserons Redis et Node.js pour illustrer les filtres de Bloom. Redis est un support de stockage pour votre filtre Bloom; c'est rapide, en mémoire, et a quelques commandes spécifiques (GETBIT, SETBIT) qui rendent la mise en œuvre efficace. Je présume que Node.js, npm et Redis sont installés sur votre système. Votre serveur Redis devrait fonctionner sur localhost sur le port par défaut pour que nos exemples fonctionnent.
Dans ce tutoriel, nous ne mettrons pas en place un filtre; au lieu de cela, nous allons nous concentrer sur les utilisations pratiques avec un module pré-construit dans npm: bloom-redis. bloom-redis a un ensemble de méthodes très concises: ajouter, contient et clair.
Comme mentionné précédemment, les filtres de Bloom nécessitent un algorithme de hachage pour générer des identifiants uniques pour un élément. bloom-redis utilise l'algorithme bien connu MD5, qui, même s'il n'est peut-être pas la solution idéale pour un filtre de Bloom (un peu lent, est excessif sur les bits), fonctionnera correctement.
Les noms d'utilisateur, en particulier ceux qui identifient un utilisateur dans une URL, doivent être uniques. Si vous créez une application permettant aux utilisateurs de modifier le nom d'utilisateur, vous souhaiterez probablement un nom d'utilisateur comportant jamais été utilisé pour éviter la confusion et le sniping de noms d'utilisateur.
Sans filtre Bloom, vous auriez besoin de référencer une table contenant tous les noms d'utilisateur jamais utilisés. À l'échelle, cela peut coûter très cher. Les filtres Bloom permettent d'ajouter un élément chaque fois qu'un utilisateur adopte un nouveau nom. Lorsqu'un utilisateur vérifie si un nom d'utilisateur est utilisé, il vous suffit de vérifier le filtre Bloom. Il pourra vous dire, avec une certitude absolue, si le nom d'utilisateur demandé a déjà été ajouté. Il est possible que le filtre retourne faussement qu'un nom d'utilisateur ait été utilisé alors que ce n'est pas le cas, mais il s'agit d'une erreur de prudence et ne cause aucun préjudice réel (à part un utilisateur ne pouvant peut-être pas revendiquer 'k3w1d00d47').
Pour illustrer cela, construisons un serveur REST rapide avec Express. Tout d’abord, créez votre package.json fichier et ensuite exécuter les commandes de terminal suivantes.
npm installer bloom-redis --save
npm install express --save
npm install redis --save
Les options par défaut pour bloom-redis ont la taille définie à deux mégaoctets. C'est une erreur de prudence, mais c'est assez important. La définition de la taille du filtre de Bloom est cruciale: trop grande et vous gaspillez de la mémoire, trop petite et votre taux de faux positifs sera trop élevé. Les calculs à effectuer pour déterminer la taille sont assez compliqués et vont au-delà de la portée de ce didacticiel, mais heureusement, il existe un calculateur de taille de filtre Bloom permettant de faire le travail sans craquer un manuel..
Maintenant, créez votre app.js comme suit:
"javascript var Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
application, client, filtre;
// configurer notre serveur Express app = express ();
// crée la connexion à Redis client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, // assurez-vous que le module Bloom utilise notre nouvelle connexion à la clé Redis: 'username-bloom-filter', // la clé Redis
// taille calculée du filtre Bloom. // C'est là que vos compromis taille / probabilité sont faits //http://hur.st/bloomfilter?n=100000&p=1.0E-6 taille: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', fonction (req, res, next) // vérifie que la chaîne de requête contient 'username' if (typeof req.query.username === 'undefined') // ignorer cette route, allez à la suivante - aura comme résultat 404 / not found next ('route'); else filter.contains (req.query.username, // le nom d'utilisateur de la fonction de chaîne de requête (err, result ) if (err) next (err); // si une erreur est rencontrée, envoyez-la au client else res.send (username: req.query.username, // si le résultat est faux, alors nous savons que l'article a ne pas été utilisé // si le résultat est vrai, nous pouvons supposer que l'élément a été utilisé status: résultat? 'utilisé': 'gratuit'); ); );
app.get ('/ save', fonction (req, res, next) if (typeof req.query.username === 'undefined') next ('route'); else // d'abord, nous avons besoin pour vous assurer qu'il ne figure pas encore dans le filtre filter.contains (req.query.username, function (err, résultat) if (err) suivant (err); else if (résultat) // résultat vrai signifie il existe déjà, alors indiquez à l'utilisateur res.send (username: req.query.username, status: 'not-created'); // nous ajouterons le nom d'utilisateur transmis dans la chaîne de requête au filtre filter.add (req.query.username, function (err) // Les arguments de rappel à ajouter ne fournit aucune information utile, nous allons donc vérifier que rien ne s'est passé si (err) next (err); else res.send (username: req.query.username, status: 'created'); ); ); );
app.listen (8010); "
Pour exécuter ce serveur: noeud app.js. Allez sur votre navigateur et dirigez-le vers: https: // localhost: 8010 / check? nom d'utilisateur = kyle. La réponse devrait être: "nom d'utilisateur": "kyle", "status": "gratuit".
Maintenant, sauvegardons ce nom d'utilisateur en pointant votre navigateur sur http: // localhost: 8010 / save? nom d'utilisateur = kyle. La réponse sera: "nom d'utilisateur": "kyle", "status": "créé". Si vous revenez à l'adresse http: // localhost: 8010 / check? nom d'utilisateur = kyle, la réponse sera "nom d'utilisateur": "kyle", "status": "utilisé". De même, revenons à http: // localhost: 8010 / save? nom d'utilisateur = kyle aura pour résultat "nom d'utilisateur": "kyle", "status": "non créé".
Depuis le terminal, vous pouvez voir la taille du filtre: redis-cli strlen filtre-nom-utilisateur-bloom.
En ce moment, avec un élément, il devrait montrer 338622.
Maintenant, essayez d’ajouter plus de noms d’utilisateur avec /enregistrer route. Essayez autant que vous le souhaitez.
Si vous vérifiez à nouveau la taille, vous remarquerez peut-être que votre taille a légèrement augmenté, mais pas pour chaque ajout. Curieux, non? En interne, un filtre Bloom définit des bits individuels (1/0) à différentes positions de la chaîne enregistrée dans nom d'utilisateur-bloom. Cependant, elles ne sont pas contiguës. Par conséquent, si vous définissez un bit à l'index 0, puis un autre à 10 000, tout ce qui est entre 0 sera. Pour des utilisations pratiques, il n'est pas important au départ de comprendre les mécanismes précis de chaque opération. est normal et que votre stockage dans Redis ne dépassera jamais la valeur que vous avez spécifiée.
Un nouveau contenu sur un site Web fait revenir un utilisateur, alors comment lui montrer à chaque fois quelque chose de nouveau? En utilisant une approche de base de données traditionnelle, vous pouvez ajouter une nouvelle ligne à une table avec l'identificateur d'utilisateur et l'identifiant de l'article, puis interroger cette table lorsque vous décidez d'afficher un élément de contenu. Comme vous pouvez l’imaginer, votre base de données augmentera extrêmement rapidement, en particulier avec la croissance du nombre d’utilisateurs et de contenu..
Dans ce cas, un faux négatif (par exemple, ne montrant pas un contenu non vu) a très peu de conséquences, ce qui fait que les filtres de Bloom sont une option viable. De prime abord, vous pensez peut-être qu'il vous faudrait un filtre de Bloom pour chaque utilisateur, mais nous utiliserons une simple concaténation de l'identificateur d'utilisateur et de l'identificateur de contenu, puis insérerons cette chaîne dans notre filtre. De cette façon, nous pouvons utiliser un seul filtre pour tous les utilisateurs.
Dans cet exemple, construisons un autre serveur Express de base affichant le contenu. Chaque fois que vous visitez la route / show-content / any-username (avec n'importe quel nom d'utilisateur quelle que soit la valeur utilisée pour les URL), un nouveau contenu sera affiché jusqu'à ce que le site soit vide. Dans l'exemple, le contenu est la première ligne des dix premiers livres du projet Gutenberg..
Nous aurons besoin d'installer un module npm supplémentaire. Depuis le terminal, lancez: npm install async --save
Votre nouveau fichier app.js:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
application, client, filtre,
// Du projet Gutenberg - Lignes d'ouverture des 10 meilleurs livres numériques du domaine public // https://www.gutenberg.org/browse/scores/top openingLines = 'pride-and-préjugé': 'C'est une vérité universellement reconnue , qu'un homme célibataire en possession d'une bonne fortune doit avoir besoin d'une femme. ',' alices-aventures-au-pays-miracle ':' Alice commençait à en avoir très marre de s'asseoir près de sa sœur à la banque, et de n'avoir rien à faire: une ou deux fois, elle avait jeté un coup d'œil dans le livre que lisait sa soeur, mais elle ne contenait aucune image ni conversation, "et à quoi sert un livre," pensa Alice "sans images ni conversations?" , 'a-christmas-carol': 'Marley était mort: pour commencer.', 'métamorphose': '' Un matin, quand Gregor Samsa s'est réveillé de rêves troublés, il s'est retrouvé transformé dans son lit en une horrible vermine. ', "frankenstein": "Vous vous réjouirez d'entendre qu'aucun désastre n'a accompagné le début d'une entreprise que vous avez envisagée avec de si mauvais pressentiments.", "aventur es-of-huckleberry-finn ':' TU ne sais rien de moi sans avoir lu un livre du nom de The Adventures of Tom Sawyer; mais ce n'est pas grave. ',' aventures-de-sherlock-holmes ':' Pour Sherlock Holmes, elle est toujours la femme. ',' récit-de-la-vie-de-frederick-douglass ':' I est né à Tuckahoe, près de Hillsborough, et à une douzaine de kilomètres d'Easton, dans le comté de Talbot, dans le Maryland " ou principautés. ',' aventures de tom-scieur ':' TOM! ' ;
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, clé: '3content-bloom-filter', // taille de la clé Redis: 2875518, // ~ 350kb // taille: 1024, numHashes: 20);
app.get ('/ show-content /: utilisateur', fonction (req, res, suivant) // nous allons parcourir en boucle les contentIds, en vérifiant s'ils sont dans le filtre. // Depuis cela passe du temps sur chaque contentId ne serait pas conseillé de faire sur un grand nombre de contentIds // Mais dans ce cas, le nombre de contentIds est petit / fixé et notre fonction filter.contains est rapide, c'est correct var // crée un tableau des clés définies dans openingLines contentIds = Object.keys (openingLines), // obtenant une partie du chemin d'accès à partir de l'URI user = req.params.user, checkingContentId, found = false, done = false;
// depuis que filter.contains est asynchrone, nous utilisons la bibliothèque async pour faire notre boucle async.wh While (// check function, où notre boucle asynchrone se terminera function () return (! found &&! done);, function (cb) // récupère le premier élément du tableau de contentIds checkingContentId = contentIds.shift ();
Accentsconagua
// false signifie que nous sommes sûrs qu'il ne figure pas dans le filtre if (! checkingContentId) done = true; // cela sera capturé par la fonction de contrôle ci-dessus cb (); else // concatène l'utilisateur (à partir de l'URL) avec l'id du contenu filter.contains (user + checkingContentId, function (err, résultats) if (err) cb (err); else trouvé =! résultats; cb ();); , function (err) if (err) next (err); else if (openingLines [checkingContentId]) // avant d'envoyer le nouveau contentId, ajoutons-le au filtre pour l'empêcher d'afficher à nouveau filter.add (utilisateur + checkingContentId, function (err) if (err) next (err); else // envoie la nouvelle citation res.send (openingLines [checkingContentId]);); else res.send ('pas de nouveau contenu!'); ); ); app.listen (8011); "
Si vous prêtez une attention particulière au temps d'aller-retour dans Outils de développement, vous remarquerez que plus vous demandez un seul chemin d'accès avec un nom d'utilisateur, plus cela prend de temps. Bien que la vérification du filtre prenne un temps fixe, dans cet exemple, nous vérifions la présence d'autres éléments. Les filtres Bloom sont limités dans ce qu'ils peuvent vous dire, vous testez donc la présence de chaque élément. Bien sûr, dans notre exemple, il est assez simple, mais il serait inefficace de tester des centaines d’articles..
Dans cet exemple, nous construirons un petit serveur Express qui fera deux choses: accepter les nouvelles données via POST et afficher les données actuelles (avec une demande GET). Lorsque les nouvelles données sont envoyées au serveur, l'application vérifie sa présence dans le filtre. S'il n'est pas présent, nous l'ajouterons à un ensemble dans Redis, sinon nous renverrons null. La requête GET le récupérera de Redis et l'enverra au client.
Cela diffère des deux situations précédentes, en ce sens que les faux positifs ne seraient pas acceptables. Nous utiliserons le filtre Bloom comme première ligne de défense. Étant donné les propriétés des filtres de Bloom, nous saurons seulement avec certitude que quelque chose ne figure pas dans le filtre. Dans ce cas, nous pouvons continuer et laisser les données entrer. Si le filtre de Bloom retourne, il est probablement dans le filtre. 'vais faire une vérification par rapport à la source de données réelle.
Alors, que gagnons-nous? Nous gagnons la vitesse de ne pas avoir à vérifier par rapport à la source réelle à chaque fois. Dans les situations où la source de données est lente (API externes, bases de données pokey, au milieu d'un fichier plat), l'augmentation de la vitesse est vraiment nécessaire. Pour démontrer la vitesse, ajoutons un délai réaliste de 150 ms dans notre exemple. Nous allons également utiliser le console.time / console.timeEnd enregistrer les différences entre une vérification de filtre Bloom et une vérification de filtre non Bloom.
Dans cet exemple, nous utiliserons également un nombre de bits extrêmement limité: 1024 seulement. Cela se remplira rapidement. Au fur et à mesure qu'il se remplit, il en ressort de plus en plus de faux positifs. Le temps de réponse augmente à mesure que le taux de faux positifs se remplit..
Ce serveur utilise les mêmes modules qu'auparavant, donc définissez le paramètre app.js déposer dans:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), bodyParser = require ('analyseur de corps'), express = require ('express'), redis = require ('redis' ),
application, client, filtre,
currentDataKey = 'current-data', usedDataKey = 'used-data';
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, clé: 'stale-bloom-filter', // à des fins d'illustration, il s'agit d'un très petit filtre. Il doit être rempli à environ 500 éléments, donc pour une charge de production, vous aurez besoin de quelque chose de beaucoup plus grand! taille: 1024, numHash: 20);
app.post ('/', bodyParser.text (), fonction (req, res, next) var utilisé;
console.log ('POST -', req.body); // enregistre les données actuelles en cours de publication console.time ('post'); // commence à mesurer le temps nécessaire pour terminer notre processus de filtrage et de vérification conditionnelle //async.series est utilisé pour gérer plusieurs appels de fonctions asynchrones. async.series ([function (cb) filter.contains (req.body, fonction (err, filterStatus) (err)) cb (err); else used = filterStatus; cb (err);) ;, function (cb) if (utilisé === false) // Les filtres Bloom n'ont pas de faux négatifs, nous n'avons donc pas besoin de vérification supplémentaire cb (null); else // il * peut * être dans le filtre, nous devons donc faire un suivi //, aux fins du didacticiel, nous ajouterons un délai de 150 ms ici, car Redis peut être assez rapide pour être difficile à mesurer et le délai simule une base de données lente ou Appel API setTimeout (function () console.log ('possible faux positif'); client.sismember (usedDataKey, req.body, fonction (err, appartenance) if (err) cb (err); else / / sismember renvoie 0 si un membre ne fait pas partie de l'ensemble et un nombre égal à 1. // Ceci transforme ces résultats en booléens pour une comparaison logique cohérente utilisée = membership === 0? false: true; cb (err); );, 150);, fonction (cb) if (utilisé === false) console.log ('Ajout au filtre'); filter.a dd (réponse obligatoire, cb); else console.log ('Ajout de filtre ignoré, [false] positif'); cb (null); , function (cb) if (utilisé === false) client.multi () .set (currentDataKey, req.body) // les données inutilisées sont définies pour un accès facile à la clé 'current-data' .sadd (usedDataKey, req.body) // et ajouté à un ensemble pour une vérification facile ultérieure .exec (cb); else cb (null); ], function (err, cb) if (err) next (err); else console.timeEnd ('post'); // enregistre le temps écoulé depuis l'appel console.time au-dessus de res.send (saved:! used); // renvoie si l'élément a été enregistré, true pour les données fraîches, false pour les données obsolètes. ); ); app.get ('/', function (req, res, next) // renvoie simplement les données fraîches client.get (currentDataKey, function (err, données) if (err) next (err); else res.send (data);););
app.listen (8012); "
Le fait de poster sur un serveur peut être délicat avec un navigateur, utilisons curl pour tester.
curl --data "vos données vont ici" --header "Content-Type: text / plain" http: // localhost: 8012 /
Un script bash rapide peut être utilisé pour montrer à quoi ressemble le remplissage de tout le filtre:
bash #! / bin / bash pour i in 'seq 1 500'; do curl --data “data $ i" - entête "Content-Type: text / plain" http: // localhost: 8012 / done
Regarder un filtre de remplissage ou plein est intéressant. Comme celui-ci est petit, vous pouvez facilement le visualiser avec redis-cli. En exécutant redis-cli se filtre vicié à partir du terminal entre l'ajout d'éléments, vous verrez les octets individuels augmenter. Un filtre complet sera \ xff pour chaque octet. À ce stade, le filtre retournera toujours positif.
Les filtres Bloom ne sont pas une solution de panacée, mais dans la bonne situation, un filtre Bloom peut fournir un complément rapide et efficace à d'autres structures de données..
