Krav: For nylig så jeg en video af Redis Bloom-algoritmen på Bilibili for at løse problemet med cache-penetration, ganske enkelt tilføje et lag af logisk dømmekraft, før man tilgår databasen for at afgøre, om dataene eksisterer, og i så fald adgang til databasen. For eksempel, hvis et website er et nyhedssystem, genereres artiklernes URL'er ved selv-inkrementerende primærnøgle-ID'er (URL-format example:/news-1.html), kan websitet kun have titusindvis af artikler og caches.
Oprindelig:
Anmod om nyhedsressource -> Bestem om cachen eksisterer -> Tilstedeværelse -> Cachen returnerer data.
Anmod om nyhedsressourcer -> Bestem om cachen eksisterer -> ikke eksisterer -> Forespørg fra databasen -> Præsenter -> Cache og returner data.
Anmod om en nyhedsressource -> Bestem om cachen eksisterer -> ikke eksisterer -> Forespørgsel fra databasen -> Findes ikke -> Returnerer en 404-fejl.
Lige nu:
Anmod om nyhedsressource -> Blooms algoritme -> Existence -> Følg den oprindelige logik.
Anmod om nyhedsressource -> Blooms algoritme -> ikke eksisterer -> returnerer direkte en 404-fejl.
BloomFilter
BloomFilter-algoritmen er en big data-planlægningsalgoritme. I en mængde med store mængder data kan det nøjagtigt bestemmes, at et objekt ikke er i mængden; Det er muligt at bedømme et objekt i en mængde og optage lidt plads. detDen er ikke egnet til situationer, der kræver høj nøjagtighed og nul fejl。 Effektiv udnyttelse af pladsen opnås ved at ofre delvis nøjagtighed.
Blooms algoritme er en metode baseret påOfre en vis nøjagtighed til fordel for en filtreringsalgoritme med lavt hukommelsesforbrug, som kan realisere filtrering, deduplikering og andre operationer af store mængder data.
Bloom-algoritmen er blot et abstrakt koncept og kan implementeres på mange måder, og brugen af BitMap i Redis i artiklen er blot en simpel implementering.
Henvisning:Hyperlink-login er synlig.
BitMap-introduktion
BitMap er et bitmap, som faktisk er et byte-array, repræsenteret binært.Der er kun to tal, 0 og 1, bitmap er at bruge hver binær bit til at gemme eller markere værdien, der svarer til et element. Det bruges normalt til at afgøre, om en bestemt data eksisterer eller ej, fordi den er gemt i bits, så Bitmap i sig selv sparer meget lagerplads.
Som vist i figuren nedenfor gemmes strengen i binær form i computeren.
BitMap-datatyper i Redis
Datatypen, som Redis leverer, er BitMap, og hver bit svarer til to tilstande: 0 og 1. Selvom den interne lagring stadig er i String-typen, giver Redis nogle instruktioner til direkte manipulation af BitMap, som kan betragtes som et bitarray, og arrayets subskript er offset.
Dens fordele er:Lav hukommelsesbelastning og høj effektivitetOg operationen er enkel.
Pladsbesparelse: En bit bruges til at repræsentere værdien eller tilstanden af et element, hvor nøglen er værdien af det tilsvarende element. Faktisk kan 8 bit udgøre en byte, så det sparer plads.
Høj effektivitet: Tidskompleksiteten for setbit og getbit er O(1), og effektiviteten af andre bits er også høj.
Her er et eksempel på brug af set collection og BitMap-lagring:
| Datatype | Hver brugerid fylder | Antallet af brugere, der skal lagres | Alt optager hukommelsen | | sæt | 32 bit er 4 bytes (forudsat at brugerid bruger heltal, bruger mange hjemmesider faktisk lange heltal) | 50,000,000 | 32 bit * 50.000.000 = 200 MB | | Bitmap | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Tiden strækker sig lidt
| | En dag | En måned | Et år | | sæt | 200M | 6G | 72G | | Bitmap | 12,5 m | 375M | 4,5G |
Efter beregning fandt man, at jo længere tiden gik, desto større blev mængden af data, der skulle registreres, og kontrasten blev mere tydelig, og BitMap fyldte mindre end det indstillede.
Redis giver følgende instruktioner til at betjene BitMap:
Kommandodokumentation:Hyperlink-login er synlig.
Nu hvor du har en kort forståelse af algoritmen og Bitmap-funktionerne og syntaksen i Redis, lad os bruge redis til at udføre en simpel operation.
SETBIT-syntaks:SETBIT nøgleforskydningsværdi
Sæt artiklen id:9, 10, 156 til 1, og kommandoen er som følger:
GETBIT-syntaks: GETBIT-nøgleforskydning
For at afgøre, om id: 10 eller 11 eksisterer, er kommandoen som følger:
.NET/C# manipulerer Redis' BitMap-type
Vi lærte om flere BitMap-kommandoer i redis og hvordan man bruger dem programmatisk. Opret et nyt .NET 3.1 konsolprojekt, referer til StackExchange.Redis-pakken, og brug følgende kommando:
Kildekoden er som følger:
Der findes mange andre bitmap-applikationsscenarier for Redis, som følger:
- Det kan bruges som et simpelt Bloom-filter til at afgøre, om en bruger har udført bestemte handlinger.
- Statistik over brugerens daglige aktivitet, månedlige aktiviteter og fastholdelsesrate
- Forstå statistikkerne for antallet af brugerlanceringer
- Brugernes online tilstedeværelse og statistik over personer
(Slut)
|
Opslået på 02/01/2023 17.37.01
|
|
|
|
Udlejer|
Opslået på 02/01/2023 17.41.56
|
Opslået på 02/01/2023 20.42.47
|
