Exigences : Récemment, j’ai vu une vidéo de l’algorithme Redis Bloom sur Bilibili pour résoudre le problème de la pénétration du cache, en termes simples, ajouter une couche de jugement logique avant d’accéder à la base de données pour déterminer si les données existent, et si oui, accéder à la base de données. Par exemple, si un site web est un système d’actualités, les URL des articles sont générées par des identifiants de clé primaires auto-incrémentifs (format URL example:/news-1.html), le site peut ne compter que des dizaines de milliers d’articles et de caches.
Originairement:
Demander une ressource d’actualités -> Déterminer si le cache existe -> Présence -> Le cache renvoie les données.
Demander des ressources d’actualités -> Déterminer si le cache existe -> n’existe pas -> Interroger depuis la base de données -> Présent -> Cache et retourner les données.
Demander une ressource d’actualités -> Déterminer si le cache existe -> n’existe pas -> Requête depuis la base de données -> N’existe pas -> Retourne une erreur 404.
Tout de suite:
Demander une ressource d’actualités -> Algorithme de Bloom -> Existence -> Suivez la logique originale.
Ressource de demande d’actualités -> l’algorithme de Bloom -> n’existe pas -> renvoie directement une erreur 404.
BloomFilter
L’algorithme BloomFilter est un algorithme de planification de big data. Dans un ensemble contenant une grande quantité de données, il est possible de déterminer avec précision qu’un objet ne fait pas partie de l’ensemble ; Il est possible de juger un objet dans un ensemble et de prendre peu d’espace. ilIl n’est pas adapté aux situations nécessitant une grande précision et zéro erreur。 L’utilisation efficace de l’espace est obtenue en sacrifiant une précision partielle.
L’algorithme de Bloom est une méthode basée surSacrifier une certaine précision en échange d’un algorithme de filtrage à faible consommation de mémoire, qui peut effectuer le filtrage, la déduplication et d’autres opérations d’une grande quantité de données.
L’algorithme de Bloom n’est qu’un concept abstrait et peut être implémenté de plusieurs façons, et l’utilisation du BitMap dans Redis dans l’article est simplement une implémentation simple.
Référence:La connexion hyperlientérée est visible.
Introduction des cartes de bits
BitMap est un bitmap, qui est en réalité un tableau d’octets, représenté en binaire.Il n’y a que deux chiffres, 0 et 1, la bitmap consiste à utiliser chaque bit binaire pour stocker ou marquer la valeur correspondant à un élément. Il est généralement utilisé pour déterminer si certaines données existent ou non, car elles sont stockées en bits, donc le bitmap lui-même permet d’économiser beaucoup d’espace de stockage.
Comme montré dans la figure ci-dessous, la chaîne est stockée sous forme binaire dans l’ordinateur.
Types de données BitMap dans Redis
Le type de données fourni par Redis est BitMap, et chaque bit correspond à deux états : 0 et 1. Bien que le stockage interne soit toujours de type String, Redis fournit certaines instructions pour manipuler directement BitMap, ce qui peut être considéré comme un tableau de bits, et le sous-indice du tableau est le décalage.
Ses avantages sont :Faible surcharge mémoire et haute efficacitéEt l’opération est simple.
Économie d’espace : Un bit est utilisé pour représenter la valeur ou l’état d’un élément, où la clé est la valeur de l’élément correspondant. En fait, 8 bits peuvent constituer un octet, donc c’est un peu plus loin.
Haute efficacité : La complexité temporelle du setbit et du getbit est O(1), et l’efficacité des autres bits est également élevée.
Voici un exemple d’utilisation de la collection d’ensembles et du stockage BitMap :
| type de données | Chaque userid prend de l’espace | Le nombre d’utilisateurs à stocker | Tous occupent la mémoire | | poser | 32 bits correspondent à 4 octets (en supposant que l’userid utilise des entiers, beaucoup de sites web utilisent en fait des entiers longs) | 50,000,000 | 32 bits * 50 000 000 = 200 Mo | | Image matricielle | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 Mo |
Le temps s’étire un peu
| | Un jour | Un mois | Année | | poser | 200M | 6G | 72G | | Image matricielle | 12,5M | 375M | 4,5G |
Après calcul, il a été constaté qu’avec le temps, la quantité de données à enregistrer augmentait, le contraste devenait plus évident, et BitMap prenait moins d’espace que le set.
Redis fournit les instructions suivantes pour faire fonctionner BitMap :
Documentation du commandement :La connexion hyperlientérée est visible.
Maintenant que vous avez une compréhension rapide de l’algorithme, des fonctionnalités et de la syntaxe Bitmap de Redis, utilisons Redis pour effectuer une opération simple.
Syntaxe SETBIT :Valeur de décalage de clé SETBIT
Mettez les articles id :9, 10, 156 à 1, et la commande est la suivante :
Syntaxe GETBIT : décalage de tonalité GETBIT
Pour déterminer si id : 10 ou 11 existe, la commande est la suivante :
.NET/C# manipule le type BitMap de Redis
Nous avons découvert plusieurs commandes BitMap dans Redis et comment les utiliser de manière programmatique. Créez un nouveau projet console .NET 3.1, référez le paquet StackExchange.Redis et utilisez la commande suivante :
Le code source est le suivant :
Il existe de nombreux autres scénarios d’application bitmap pour Redis, comme suit :
- Il peut être utilisé comme un simple filtre de Bloom pour déterminer si un utilisateur a effectué certaines actions.
- Statistiques sur l’activité quotidienne des utilisateurs, l’activité mensuelle et le taux de rétention
- Comprenez les statistiques du nombre de lancements utilisateurs
- Présence en ligne des utilisateurs et statistiques sur les personnes
(Fin)
|
Publié sur 02/01/2023 17:37:01
|
|
|
|
Propriétaire|
Publié sur 02/01/2023 17:41:56
|
Publié sur 02/01/2023 20:42:47
|
