Requisiti: Recentemente ho visto un video dell'algoritmo Redis Bloom su Bilibili per risolvere il problema della penetrazione della cache; in parole semplici, aggiungere uno strato di giudizio logico prima di accedere al database per determinare se i dati esistono e, in tal caso, accedere al database. Ad esempio, se un sito web è un sistema di notizie, gli URL degli articoli sono generati da ID chiave primarie auto-incrementanti (formato URL example:/news-1.html), il sito web potrebbe avere solo decine di migliaia di articoli e cache.
Originariamente:
Richiedi risorsa di notizie -> Determina se la cache esiste -> Presenza -> La cache restituisce dati.
Richiedi risorse di notizie -> Determina se la cache esiste -> non esiste -> Interroga dal database -> Presente -> Cache e restituisci dati.
Richiedi una risorsa di notizie -> Determina se la cache esiste -> non esiste -> Consulta dal database -> Non esiste -> Restituisce un errore 404.
Subito:
Richiedi risorsa di notizie -> algoritmo di Bloom -> Esistenza -> Segui la logica originale.
Richiedi notizie -> l'algoritmo di Bloom -> non esiste -> restituisce direttamente un errore 404.
BloomFilter
L'algoritmo BloomFilter è un algoritmo di pianificazione dei big data. In un insieme con una grande quantità di dati, si può determinare con precisione che un oggetto non fa parte dell'insieme; È possibile giudicare un oggetto in un insieme occupando poco spazio. essoNon è adatto a situazioni che richiedono alta precisione e zero errori。 L'uso efficiente dello spazio si ottiene sacrificando una precisione parziale.
L'algoritmo di Bloom è un metodo basato suSacrificare una certa accuratezza in cambio di un algoritmo di filtraggio con basso consumo di memoria, che può eseguire il filtraggio, la deduplicazione e altre operazioni di una grande quantità di dati.
L'algoritmo di Bloom è solo un concetto astratto e può essere implementato in molti modi, e l'uso di BitMap in Redis nell'articolo è solo un'implementazione semplice.
Riferimento:Il login del link ipertestuale è visibile.
Introduzione al BitMap
BitMap è una bitmap, che in realtà è un array di byte, rappresentato in binario.Ci sono solo due numeri, 0 e 1, la bitmap consiste nell'utilizzare ogni bit binario per memorizzare o segnare il valore corrispondente a un elemento. Di solito viene usato per determinare se un certo dato esiste o meno, poiché sono memorizzati in bit, quindi la Bitmap stessa farà risparmiare notevolmente spazio di archiviazione.
Come mostrato nella figura sottostante, la stringa è memorizzata in forma binaria nel computer.
Tipi di dati BitMap in Redis
Il tipo di dato fornito da Redis è BitMap, e ogni bit corrisponde a due stati: 0 e 1. Sebbene la memoria interna sia ancora nel tipo Stringa, Redis fornisce alcune istruzioni per manipolare direttamente BitMap, che può essere considerata come un bit array, e il sottopedice dell'array è lo offset.
I suoi vantaggi sono:Basso sovraccarico di memoria e alta efficienzaE l'operazione è semplice.
Risparmio di spazio: Un bit viene usato per rappresentare il valore o lo stato di un elemento, dove la chiave è il valore dell'elemento corrispondente. In effetti, 8 bit possono costituire un byte, quindi risparmia spazio.
Alta efficienza: La complessità temporale di setbit e getbit è O(1), e anche l'efficienza degli altri bit è elevata.
Ecco un esempio di utilizzo della raccolta set e dello storage BitMap:
| Tipo di dati | Ogni userid occupa spazio | Il numero di utenti da memorizzare | Tutti occupano la memoria | | mettere | 32 bit corrispondono a 4 byte (assumendo che userid usi interi, molti siti web usano effettivamente interi lunghi) | 50,000,000 | 32 bit * 50.000.000 = 200 MB | | Bitmap | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Il tempo si sta allungando un po'
| | Un giorno | Un mese | Un anno | | mettere | 200M | 6G | 72G | | Bitmap | 12,5M | 375M | 4.5G |
Dopo il calcolo, si scoprì che con l'aumentare del tempo, la quantità di dati da registrare aumentava, il contrasto diventava più evidente e BitMap occupava meno spazio rispetto al set.
Redis fornisce le seguenti istruzioni per l'uso di BitMap:
Documentazione del comando:Il login del link ipertestuale è visibile.
Ora che hai una breve comprensione dell'algoritmo, delle caratteristiche e della sintassi Bitmap di Redis, usiamo Redis per eseguire un'operazione semplice.
Sintassi SETBIT:Valore di offset chiave SETBIT
Imposta l'articolo id:9, 10, 156 a 1, e il comando è il seguente:
Sintassi GETBIT: Offset chiave GETBIT
Per determinare se esiste id: 10 o 11, il comando è il seguente:
.NET/C# manipola il tipo BitMap di Redis
Abbiamo imparato diversi comandi BitMap in redis e come usarli in modo programmativo. Crea un nuovo progetto console .NET 3.1, fai riferimento al pacchetto StackExchange.Redis e usa il seguente comando:
Il codice sorgente è il seguente:
Esistono molti altri scenari di applicazione bitmap per Redis, come segue:
- Può essere usato come semplice filtro di Bloom per determinare se un utente ha eseguito determinate azioni.
- Statistiche sull'attività giornaliera degli utenti, l'attività mensile e il tasso di fidelizzazione
- Comprendi le statistiche del numero di lanci utente
- Presenza online degli utenti e statistiche sulle persone
(Fine)
|
Pubblicato su 02/01/2023 17:37:01
|
|
|
|
Padrone di casa|
Pubblicato su 02/01/2023 17:41:56
|
Pubblicato su 02/01/2023 20:42:47
|
