Étant donné un nom d'utilisateur sur une page d'inscription d'utilisateur, comment savoir s'il a déjà été enregistré ?

Bien que l'interrogation d'une base de données indexée soit utile, elle est lente et entraîne des appels réseau.

Pour accélérer les choses, nous pouvons mettre en cache la liste des noms d'utilisateur enregistrés dans un magasin clé-valeur comme Redis.

Cependant, cela implique de mettre en cache des millions d'enregistrements et de doubler notre empreinte mémoire.

Comment pouvons-nous faire mieux dans ce problème apparemment trivial ?

Le filtre de floraison pourrait être la réponse, vérifions-le !

Qu'est-ce qu'un filtre Bloom ?

Un filtre bloom répond à une question simple,

Un élément existe-t-il dans un ensemble donné ?

Un filtre bloom est une structure de données probabiliste. Compte tenu de la question ci-dessus, il génère l'une des réponses suivantes

• Probablement Oui
• 100% Non

Et son plus grand avantage est qu'il le fait dans un temps et un espace CONSTANTS .

Comment ça marche?

Un filtre bloom se compose de deux composants

• Un tableau de bits de taille N
• Plusieurs fonctions de hachage

Il est d'abord initialisé en tant que tableau de bits de taille N avec tous ses bits mis à zéro. Supposons que la longueur du tableau soit de 10 pour l'instant.

Ajout d'un élément

L'ajout d'un élément est trivial

• L'élément dit "tigre" est haché à l'aide d'une fonction de hachage
• Le hachage généré est modifié par la longueur du tableau pour obtenir un index borné
• L'indice du tableau de bits est alors mis à 1

Semblable à l'ajout d'un élément, nous hachons l'élément à l'aide d'une fonction de hachage et le modifions pour obtenir un index borné.

La sortie est évaluée comme suit,

• Si la valeur d'index du tableau de bits est 0, l'élément n'est PAS dans l'ensemble.
• Sinon, l'article est PROBABLEMENT dans l'ensemble

Stockage d'un filtre bloom

Au lieu de stocker le filtre bloom sous forme de tableau, nous pouvons convertir sa représentation binaire en un nombre décimal.

Par exemple, nous pouvons convertir un tableau contenant 10011en 19 et le stocker dans un cache.

Si la liste ne change pas très souvent, le serveur peut envoyer le nombre décimal au client, permettant de faire la validation côté client.

Peut-on faire mieux ?

Si la fonction de hachage génère l'index 1 pour "tigre" et "vache", vérifier si "vache" est dans l'ensemble donne la réponse Oui même si ce n'est pas le cas .

Nous pouvons réduire le risque de faux positifs via les solutions suivantes.

• Augmenter la longueur du tableau
• Augmenter le nombre de fonctions de hachage

Au lieu d'un index, nous pouvons obtenir plusieurs index en utilisant plusieurs hachages.

Lors de l'ajout d'un élément, tous les index obtenus seront mis à 1.

Un élément est déclaré être probablement dans l'ensemble, uniquement si TOUS les index sont définis sur 1.

En tirant parti de ces méthodes, nous pourrions réduire considérablement la probabilité de faux positifs.

Applications

Jetons un coup d'œil à quelques exemples concrets.

Vérifier si un nom d'utilisateur existe dans un flux d'inscription d'utilisateur

• Lorsqu'un nom d'utilisateur est créé, le nom d'utilisateur est ajouté à un filtre bloom stocké dans un magasin clé-valeur.
• Lorsqu'un utilisateur saisit un nom d'utilisateur sur une page d'inscription d'utilisateur, le serveur interroge d'abord le filtre Bloom.
• Si le nom d'utilisateur n'est PAS dans le filtre bloom, le serveur renvoie instantanément une erreur au client.
• Sinon, le serveur interroge et recoupe la base de données.

• Medium maintient un filtre bloom pour chaque utilisateur.
• Avant de recommander un article, Medium vérifie si l'ID de l'article existe dans le filtre bloom de l'utilisateur.
• Les articles qui ne sont certainement PAS dans le filtre bloom sont recommandés à l'utilisateur.

• Lors de l'accès à une URL, Chrome vérifie d'abord si l'URL fait partie d'une liste malveillante.
• Au lieu d'interroger le serveur Google à chaque fois, Google construit un filtre bloom à l'aide d'une liste malveillante prédéterminée et l'envoie au navigateur.
• Le navigateur hache l'URL et vérifie avec le filtre Bloom avant d'accéder au site Web.

Bien qu'il puisse y avoir des faux positifs , un filtre bloom est pratique lorsque nous voulons savoir si un élément n'est définitivement pas dans une liste.

Il peut être utilisé comme première couche de filtrage en raison de son efficacité à la fois dans le temps et dans l'espace.

J'espère que vous trouverez cela utile, et je vous verrai au prochain !