Redis
 sql >> Database >  >> NoSQL >> Redis

Introduzione alle strutture dati Redis:bitmap

Bitmap (chiamate anche array di bit, vettori di bit ecc.) è la struttura di dati che viene immediatamente in mente quando è necessario mappare le informazioni booleane per un dominio enorme in un formato compatto rappresentazione. È una struttura dati molto popolare ogni volta che lo spazio di memoria è limitato:kernel del sistema operativo (pagine di memoria, inode ecc.), imaging digitale ecc.

Redis, essendo un server di struttura dati in memoria, fornisce supporto per operazioni di manipolazione dei bit. Tuttavia, non esiste una struttura dati speciale per le bitmap in Redis. Piuttosto, le operazioni a livello di bit sono supportate sulla struttura Redis di base:Strings. Ora, la lunghezza massima per le stringhe Redis è 512 MB. Pertanto, il dominio più grande che Redis può mappare come Bitmap è 2 (512 MB =2 byte =2 bit).

Le operazioni relative ai bit in Redis sono di due tipi:tempo costante (O(1)) ad es. operazioni per ottenere/impostare un particolare bit e operazioni che sono O(N) che fondamentalmente operano su un gruppo di bit. N in questi casi è la lunghezza dei bit su cui l'operazione dovrà lavorare. Diamo un'occhiata ad alcuni esempi.

Comandi

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Oltre agli operatori che lavorano sulla chiave stessa, il BITOP viene utilizzato per operazioni logiche bit per bit tra più chiavi.

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Interni

Dato che le operazioni bitmap non hanno una struttura dati propria, non c'è una struttura dati speciale da descrivere. Le stesse stringhe Redis sono implementate come una stringa binaria sicura. La struttura dei dati della stringa Redis è chiamata internamente Simple Dynamic String (SDS). È essenzialmente un char [] nativo con alcune informazioni aggiuntive sulla tenuta della contabilità. I dettagli sull'implementazione sono disponibili qui.

L'implementazione delle funzioni bitmap è nel file bitps.c .

PS:data l'importanza degli algoritmi di manipolazione dei bit per il sistema operativo critico e le funzionalità grafiche, la maggior parte delle architetture fornisce istruzioni speciali per tali operazioni. Un buon posto per leggere vari interessanti algoritmi aritmetici per computer è il classico senza tempo Hacker's Delight.

Applicazioni

Questo popolare blog di GetSpool è un ottimo esempio di utilizzo di bitmap per l'analisi in tempo reale su un set di dati di grandi dimensioni. È anche un esempio del classico caso d'uso di una bitmap:archiviare informazioni booleane di un dominio estremamente grande in uno spazio (relativamente) piccolo pur mantenendo prestazioni decenti.

La dimensione è solitamente un problema per bitmap molto grandi, poiché la maggior parte delle operazioni utili su di essa sono O(N). Per evitare di lavorare con chiavi enormi, la documentazione Redis consiglia di suddividere chiavi enormi in più chiavi più piccole. Le prestazioni di BITCOUNT rimangono accettabili fino a quando la chiave non diventa grande. A quel punto, il consiglio è di dividere le chiavi o di utilizzare gli argomenti dell'intervallo per eseguire query in modo incrementale. La raccomandazione per gestire le operazioni BITOP lente è di eseguirlo su slave. Quindi, in generale, ha senso gestire chiavi di dimensioni moderate e pianificare la crescita potenziale futura suddividendo le chiavi in ​​più chiavi.

 Set Redis vs Bitmap Redis

La natura della funzionalità fornita da Redis Sets e le operazioni bitmap sono simili. Quindi è spesso confuso quale dei due approcci sia migliore. Bene, dipende davvero dall'esatta natura del caso d'uso. Ovviamente, questa discussione è valida solo per il tipo di operazioni che possono essere eseguite sia dagli insiemi che dalla bitmap.

I set Redis sono in generale efficienti e si adattano bene e dovrebbero essere la struttura dati preferita fino a quando le sue dimensioni non diventano insostenibili. I set Redis sono anche più facili da gestire, il programma e il debug funzionerebbero bene per la maggior parte delle applicazioni. La facilità d'uso di Sets non deve essere sottovalutata:il codice che manipola le bitmap è solitamente difficile da leggere, comprendere, eseguire il debug e mantenere. Anche quando il dominio è molto grande, i set potrebbero essere comunque appropriati. Per es. se un'applicazione ha lo scopo di tenere traccia delle visite giornaliere a un popolare sito di e-commerce, i risultati potrebbero comunque rientrare bene in un insieme poiché di solito solo il 5-10% dell'intera base di utenti visiterà il sito ogni giorno. Questo ovviamente cambia per un sito in cui si prevede che il 60% dell'intera base di utenti acceda quotidianamente. Quindi le bitmap diventano più rilevanti date le dimensioni e le prestazioni delle operazioni logiche a livello di bit su un numero elevato di chiavi. I set Redis hanno anche il netto vantaggio di non dover mappare gli ID sugli offset di bit. Allo stesso modo, se i tuoi valori provengono da un dominio più grande di 2, allora i Redis Set sono più facili da usare che capire i meccanismi per dividere il dominio per bitmap.

Analisi per un MOOC

Ecco un esempio inventato (ma abbastanza reale!) per un luogo in cui si potrebbero applicare operazioni bitmap Redis. Supponiamo che tu stia gestendo un MOOC online molto popolare a cui si sono iscritti centinaia di migliaia di studenti. Il team accademico che facilita il corso desidera una dashboard in cui poter vedere lo stato in tempo reale dei progressi degli studenti e il background generale degli studenti iscritti. Decidi di implementarlo tramite operazioni bitmap Redis. Ecco un approccio passo dopo passo.

  1. Crea un piano per mappare tra l'ID studente e l'offset bitmap. Potrebbe essere semplice come l'ID è l'offset nella bitmap.
  2. Crea e popola varie bitmap relative a dati demografici una volta iniziato il corso. Per es. studenti iscritti ad altri MOOC della stessa università, livello di istruzione, genere ecc.
  3. Ora, man mano che il corso avanza, puoi creare nuove bitmap per registrare i progressi del corso. Per es. studenti che hanno completato la visione di tutte le lezioni della settimana 1, studenti che hanno completato tutti i compiti della settimana 1. ecc.
  4. Ora, creare analisi in tempo reale basate su queste chiavi sarebbe un esercizio molto semplice e può essere eseguito tramite un'interfaccia utente trascina e rilascia. Ad esempio
  • Un professore che vuole vedere quanti studenti hanno seguito le lezioni per la settimana 1 (A) ma non hanno completato il compito per la settimana 1 (B):Operatore:BITOP. Operazione:A AND (NON B).
  • Studente che ha completato tutti i compiti per la settimana 1 (A), la settimana 2 (B), la settimana 3 (C) e la settimana 4 (D):Operatore:BITOP. Operazione A E B E C E D. Diciamo, queste sono le persone che hanno superato il corso.
  • Tutti gli studenti maschi (M) che hanno superato il corso (come calcolato sopra, diciamo, P):Operatore:BITOP. Operazione:M E P.
  • Numero di studenti che hanno superato il corso:BITCOUNT P.

Allo stesso modo, qualsiasi numero di coorti interessanti può essere impostato come bitmap e tali permutazioni vengono eseguite su di esse.

Nota a piè di pagina

Altri post nella nostra serie di strutture dati Redis:

  • Set
  • Hash
  • Set ordinati