Krav: Nylig så jeg en video av Redis Bloom-algoritmen på Bilibili for å løse problemet med cache-penetrasjon, enkelt sagt, legge til et lag med logisk vurdering før tilgang til databasen for å avgjøre om dataene eksisterer, og i så fall, få tilgang til databasen. For eksempel, hvis et nettsted er et nyhetssystem, genereres URL-ene til artikler av selvøkende primærnøkkel-IDer (URL-format example:/news-1.html), nettstedet kan bare ha titusenvis av artikler og cacher.
Opprinnelig:
Be om nyhetsressurs -> Bestem om cachen eksisterer -> Tilstedeværelse -> Cachen returnerer data.
Be om nyhetsressurser -> Avgjør om cachen eksisterer -> ikke eksisterer -> Søk fra databasen -> Presenter -> Cache og returner data.
Be om en nyhetsressurs -> Bestem om cachen eksisterer -> ikke eksisterer -> Søk fra databasen -> Finnes ikke -> Returnerer en 404-feil.
Akkurat nå:
Be om nyhetsressurs -> Blooms algoritme -> Existence -> Følg den opprinnelige logikken.
Be om nyhetsressurs -> Blooms algoritme -> ikke eksisterer -> returnerer en 404-feil direkte.
BloomFilter
BloomFilter-algoritmen er en stor dataplanleggingsalgoritme. I en mengde med store mengder data kan det nøyaktig fastslås at et objekt ikke er i mengden; Det er mulig å vurdere et objekt i en mengde og ta opp lite plass. detDen er ikke egnet for situasjoner som krever høy nøyaktighet og null feil。 Effektiv plassbruk oppnås ved å ofre delvis nøyaktighet.
Blooms algoritme er en metode basert påOfre en viss nøyaktighet i bytte mot en filtreringsalgoritme med lavt minneforbruk, som kan realisere filtrering, deduplisering og andre operasjoner av store mengder data.
Bloom-algoritmen er bare et abstrakt konsept og kan implementeres på mange måter, og bruken av BitMap i Redis i artikkelen er bare en enkel implementering.
Referanse:Innloggingen med hyperkoblingen er synlig.
Introduksjon til BitMap
BitMap er et bitmap, som egentlig er et byte-array, representert binært.Det finnes bare to tall, 0 og 1, bitmap er å bruke hver binær bit til å lagre eller markere verdien som tilsvarer et element. Den brukes vanligvis for å avgjøre om en viss data eksisterer eller ikke, fordi den lagres i biter, så Bitmap i seg selv vil spare lagringsplass betydelig.
Som vist i figuren nedenfor, lagres strengen i binær form i datamaskinen.
BitMap-datatyper i Redis
Datatypen som Redis gir er BitMap, og hver bit tilsvarer to tilstander: 0 og 1. Selv om den interne lagringen fortsatt er i String-typen, gir Redis noen instruksjoner for direkte håndtering av BitMap, som kan betraktes som et bitarray, og indeksen til arrayet er offset.
Fordelene er:Lav minneoverhead og høy effektivitetOg operasjonen er enkel.
Plasssparing: En bit brukes til å representere verdien eller tilstanden til et element, der nøkkelen er verdien til det tilsvarende elementet. Faktisk kan 8 biter utgjøre en byte, så det sparer plass.
Høy effektivitet: Tidskompleksiteten til setbit og getbit er O(1), og effektiviteten til andre biter er også høy.
Her er et eksempel på bruk av set-samlingen og BitMap-lagring:
| datatype | Hver userid tar opp plass | Antallet brukere som må lagres | Alt opptar minnet | | sett | 32 biter er 4 byte (forutsatt at userid bruker heltall, mange nettsteder bruker faktisk lange heltall) | 50,000,000 | 32 biter * 50 000 000 = 200 MB | | Punktgrafikk | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 MB |
Tiden strekker seg litt
| | En dag | En måned | Ett år | | sett | 200M | 6G | 72G | | Punktgrafikk | 12,5M | 375M | 4,5G |
Etter beregning ble det funnet at etter hvert som tiden gikk, økte mengden data som skulle registreres, kontrasten ble mer tydelig, og BitMap tok mindre plass enn det som var satt opp.
Redis gir følgende instruksjoner for å bruke BitMap:
Kommandodokumentasjon:Innloggingen med hyperkoblingen er synlig.
Nå som du har en kort forståelse av algoritmen og Bitmap-funksjonene og syntaksen til Redis, la oss bruke redis til å gjøre en enkel operasjon.
SETBIT-syntaks:SETBIT-nøkkelforskyvningsverdi
Sett artikkelen id:9, 10, 156 til 1, og kommandoen er som følger:
GETBIT-syntaks: GETBIT-nøkkelforskyvning
For å avgjøre om id: 10 eller 11 eksisterer, er kommandoen som følger:
.NET/C# manipulerer Redis sin BitMap-type
Vi lærte om flere BitMap-kommandoer i redis og hvordan man bruker dem programmessig. Lag et nytt .NET 3.1-konsollprosjekt, referer til StackExchange.Redis-pakken, og bruk følgende kommando:
Kildekoden er som følger:
Det finnes mange andre bitmap-applikasjonsscenarier for Redis, som følger:
- Den kan brukes som et enkelt Bloom-filter for å avgjøre om en bruker har utført visse handlinger.
- Statistikk over brukerens daglige aktivitet, månedlig aktivitet og opprettholdelsesrate
- Forstå statistikken for antall brukeroppstarter
- Brukernes tilstedeværelse på nett og statistikk over personer
(Slutt)
|
Publisert på 02.01.2023 17:37:01
|
|
|
|
Vert|
Publisert på 02.01.2023 17:41:56
|
Publisert på 02.01.2023 20:42:47
|
