Cerințe: Recent, am văzut un videoclip cu algoritmul Redis Bloom pe Bilibili pentru a rezolva problema penetrării cache-ului, pe scurt, să adaugi un strat de judecată logică înainte de a accesa baza de date pentru a determina dacă datele există și, dacă da, să accesezi baza de date. De exemplu, dacă un site web este un sistem de știri, URL-urile articolelor sunt generate de ID-uri cheie primare auto-incrementante (format URL example:/news-1.html), site-ul poate avea doar zeci de mii de articole și cache-uri.
Inițial:
Solicită resursă de știri -> Determină dacă cache-ul există -> Prezență -> Cache-ul returnează date.
Solicită resurse de știri -> Determină dacă cache-ul există -> nu există -> Interogează din baza de date -> Prezintă -> Cache și returnează date.
Solicită o resursă de știri -> Determină dacă cache-ul există -> nu există -> Interogare din baza de date -> Nu există -> Returnează o eroare 404.
Chiar acum:
Solicită resursă de știri -> Algoritmul lui Bloom -> Existență -> Urmează logica originală.
Solicită resursa de știri -> algoritmul lui Bloom -> nu există -> returnează direct o eroare 404.
BloomFilter
Algoritmul BloomFilter este un algoritm de planificare a datelor mari. Într-un set cu o cantitate mare de date, se poate determina cu precizie că un obiect nu face parte din set; Este posibil să judeci un obiect dintr-un set și să ocupi puțin spațiu. elNu este potrivit pentru situații care necesită o acuratețe ridicată și zero erori。 Utilizarea eficientă a spațiului se realizează prin sacrificarea acurateței parțiale.
Algoritmul lui Bloom este o metodă bazată peSacrifică o anumită acuratețe în schimbul unui algoritm de filtrare cu un consum scăzut de memorie, care poate realiza filtrarea, deduplicarea și alte operații ale unei cantități mari de date.
Algoritmul Bloom este doar un concept abstract și poate fi implementat în multe moduri, iar utilizarea BitMap în Redis din articol este doar o implementare simplă.
Referință:Autentificarea cu hyperlink este vizibilă.
Introducere în BitMap
BitMap este un bitmap, care este de fapt un tablou de octeți, reprezentat în binar.Există doar două numere, 0 și 1, bitmap-ul este să folosești fiecare bit binar pentru a stoca sau marca valoarea corespunzătoare unui element. De obicei este folosită pentru a determina dacă anumite date există sau nu, deoarece sunt stocate în biți, astfel încât Bitmap-ul însuși va economisi mult spațiu de stocare.
După cum se vede în figura de mai jos, șirul este stocat în formă binară în calculator.
Tipuri de date BitMap în Redis
Tipul de date oferit de Redis este BitMap, iar fiecare bit corespunde a două stări: 0 și 1. Deși stocarea internă este încă de tip String, Redis oferă unele instrucțiuni pentru manipularea directă a BitMap-ului, care poate fi considerată un tablou de biți, iar subscriptul array-ului este offset-ul.
Avantajele sale sunt:Sarcină redusă a memoriei și eficiență ridicatăȘi operațiunea este simplă.
Economisirea spațiului: Un bit este folosit pentru a reprezenta valoarea sau starea unui element, unde cheia este valoarea elementului corespunzător. De fapt, 8 biți pot constitui un octet, deci economisește spațiu.
Eficiență ridicată: Complexitatea temporală a setbitului și a bitului getbit este O(1), iar eficiența altor biți este, de asemenea, ridicată.
Iată un exemplu de utilizare a colecției de seturi și a stocării BitMap:
| tip de date | Fiecare userid ocupă spațiu | Numărul de utilizatori care trebuie stocați | Toate ocupă memoria | | apus | 32 de biți înseamnă 4 octeți (presupunând că userid-ul folosește numere întregi, multe site-uri chiar folosesc numere întregi lungi) | 50,000,000 | 32 biți * 50.000.000 = 200 MB | | Bitmap | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Timpul se întinde puțin
| | O zi | O lună | Un an | | apus | 200M | 6G | 72G | | Bitmap | 12,5M | 375M | 4,5G |
După calcul, s-a constatat că, pe măsură ce timpul avansa, cantitatea de date ce trebuia înregistrată creștea, iar contrastul devenea mai evident, iar BitMap ocupa mai puțin spațiu decât set.
Redis oferă următoarele instrucțiuni pentru operarea BitMap:
Documentația comenzilor:Autentificarea cu hyperlink este vizibilă.
Acum că ai o scurtă înțelegere a algoritmului, a caracteristicilor Bitmap și a sintaxei Redis, să folosim redis pentru o operație simplă.
Sintaxa SETBIT:Valoarea decalării cheii SETBIT
Setează articolul id:9, 10, 156 la 1, iar comanda este următoarea:
Sintaxa GETBIT: Offset de cheie GETBIT
Pentru a determina dacă id: 10 sau 11 există, comanda este următoarea:
.NET/C# manipulează tipul BitMap al lui Redis
Am învățat despre mai multe comenzi BitMap în redis și cum să le operăm programatic. Creează un nou proiect de consolă .NET 3.1, consultă pachetul StackExchange.Redis și folosește următoarea comandă:
Codul sursă este următorul:
Există multe alte scenarii de aplicație bitmap pentru Redis, după cum urmează:
- Poate fi folosit ca un filtru Bloom simplu pentru a determina dacă un utilizator a efectuat anumite acțiuni.
- Statistici privind activitatea zilnică a utilizatorilor, activitatea lunară și rata de retenție
- Cunoaște statisticile privind numărul de lansări de utilizatori
- Prezența online a utilizatorilor și statisticile privind populația
(Sfârșit)
|
Postat pe 02.01.2023 17:37:01
|
|
|
|
Proprietarul|
Postat pe 02.01.2023 17:41:56
|
Postat pe 02.01.2023 20:42:47
|
