Zahteve: Nedavno sem videl video algoritma Redis Bloom na Bilibili, ki rešuje problem penetracije predpomnilnika, preprosto povedano, doda plast logičnega presoja, preden dostopa do baze podatkov, da ugotovi, ali podatki obstajajo, in če da, dostop do baze. Na primer, če je spletna stran novičarski sistem, se URL-ji člankov generirajo z samopovečevanjem primarnih ključnih ID-jev (format URL-ja example:/news-1.html), spletna stran pa lahko vsebuje le na deset tisoče člankov in predpomnilnikov.
Prvotno:
Zahteva vir novic -> Ugotovi, ali predpomnilnik obstaja -> Prisotnost -> Predpomnilnik vrne podatke.
Zahtevajte vire novic -> Ugotovite, ali predpomnilnik obstaja -> ne obstaja -> Poizvedite iz baze podatkov -> Prisotni -> Predpomnilnik in vrni podatke.
Zahteva vir novic -> Ugotovi, ali predpomnilnik obstaja -> ne obstaja -> Poizvedba iz baze -> Ne obstaja -> Vrne napako 404.
Takoj:
Zahtevajte novičarski vir -> Bloomov algoritem -> Obstoj -> Sledite izvirni logiki.
Request news resource -> Bloomov algoritem -> ne obstaja -> neposredno vrne napako 404.
BloomFilter
Algoritem BloomFilter je algoritem za razporejanje velikih podatkov. V množici z veliko količino podatkov je mogoče natančno določiti, da objekt ni v množici; Možno je oceniti predmet v množici in zasedati malo prostora. onoNi primeren za situacije, ki zahtevajo visoko natančnost in ničelne napake。 Učinkovita uporaba prostora se doseže z žrtvovanjem delne natančnosti.
Bloomov algoritem je metoda, ki temelji naŽrtvovati določeno natančnost v zameno za algoritem filtriranja z nizko porabo pomnilnika, ki lahko izvede filtriranje, deduplikacijo in druge operacije velike količine podatkov.
Algoritem Bloom je le abstrakten koncept in ga je mogoče implementirati na več načinov, uporaba BitMapa v Redisu v članku pa je le preprosta implementacija.
Referenčni:Prijava do hiperpovezave je vidna.
Uvod v BitMap
BitMap je bitna mapa, ki je pravzaprav bajtno polje, predstavljeno v binarni obliki.Obstajata le dve številki, 0 in 1, bitna mapa pomeni uporabo vsakega binarnega bita za shranjevanje ali označevanje vrednosti, ki ustreza elementu. Običajno se uporablja za ugotavljanje, ali določeni podatki obstajajo ali ne, saj so shranjeni v bitih, zato bitmapa sama močno prihrani prostor za shranjevanje.
Kot je prikazano na spodnji sliki, je niz shranjen v binarni obliki v računalniku.
BitMap podatkovni tipi v Redisu
Podatkovni tip, ki ga zagotavlja Redis, je BitMap, vsak bit pa ustreza dvema stanjema: 0 in 1. Čeprav je notranji pomnilnik še vedno v tipu String, Redis ponuja nekaj navodil za neposredno upravljanje BitMapa, ki ga lahko razumemo kot bitno polje, indeks polja pa je odmik.
Njegove prednosti so:Nizka obremenitev pomnilnika in visoka učinkovitostIn operacija je preprosta.
Prihranek prostora: Bit se uporablja za predstavitev vrednosti ali stanja elementa, kjer je ključ vrednost ustreznega elementa. Pravzaprav lahko 8 bitov tvori en bajt, zato varčuje prostor.
Visoka učinkovitost: Časovna zahtevnost setbita in getbita je O(1), učinkovitost drugih bitov pa je prav tako visoka.
Tukaj je primer uporabe zbirke setov in BitMap shranjevanja:
| Tip podatkov | Vsak userid zavzame prostor | Število uporabnikov, ki jih je treba shraniti | Vse zaseda pomnilnik | | nastaviti | 32 bitov je 4 bajte (ob predpostavki, da userid uporablja cela števila, veliko spletnih strani dejansko uporablja dolga cela števila) | 50,000,000 | 32 bitov * 50.000.000 = 200 MB | | Bitne slike | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Čas se malo razteza
| | Nekega dne | En mesec | Eno leto | | nastaviti | 200M | 6G | 72G | | Bitne slike | 12,5M | 375M | 4,5G |
Po izračunu so ugotovili, da se s časom povečuje količina podatkov, ki jih je treba zabeležiti, kontrast pa je postal bolj očiten, BitMap pa je zavzel manj prostora, kot je bil nastavljen.
Redis ponuja naslednja navodila za upravljanje BitMapa:
Dokumentacija ukazov:Prijava do hiperpovezave je vidna.
Zdaj, ko na kratko razumete algoritem ter bitne značilnosti in sintakso Redisa, uporabimo redis za preprosto operacijo.
SETBIT sintaksa:Vrednost zamika ključa SETBIT
Nastavite ID članka:9, 10, 156 na 1, ukaz pa je naslednji:
GETBIT sintaksa: GETBIT zamik ključa
Za ugotavljanje, ali obstaja id: 10 ali 11, je ukaz naslednji:
.NET/C# upravlja Redisov tip BitMap
Naučili smo se več BitMap ukazov v redisu in kako jih programatično upravljati. Ustvarite nov .NET 3.1 konzolni projekt, poglejte paket StackExchange.Redis in uporabite naslednji ukaz:
Izvorna koda je naslednja:
Obstaja še veliko drugih scenarijev uporabe bitnih map za Redis, in sicer:
- Uporablja se lahko kot preprost Bloom filter za ugotavljanje, ali je uporabnik izvedel določena dejanja.
- Statistika dnevne aktivnosti uporabnikov, mesečne aktivnosti in stopnje zadrževanja uporabnikov
- Upoštevajte statistiko števila zagonov uporabnikov
- Spletna prisotnost uporabnikov in statistika o ljudeh
(Konec)
|
Objavljeno na 2. 01. 2023 17:37:01
|
|
|
|
Najemodajalec|
Objavljeno na 2. 01. 2023 17:41:56
|
Objavljeno na 2. 01. 2023 20:42:47
|
